recursion - 如何得出功能段？

我该如何构造函数segs来返回列表中所有连续段的列表？
例如，(segs '(l i s t))应该产生以下答案:

(() (t) (s) (s t) (i) (i s) (i s t) (l) (l i) (l i s) (l i s t))

我对如何按照HtDP中描述的设计原则解决此问题特别感兴趣(不，这不是本书中的问题，因此请随时讨论!)如何解决？在程序推导中使用哪些原则？

最佳答案

首先建立一组相关的示例，首先是最简单的:

(equal? (segs '())
        (list '()))
(equal? (segs '(z))
        (list '()
              '(z)))
(equal? (segs '(y z))
        (list '() '(z)
              '(y) '(y z)))
(equal? (segs '(x y z))
        (list '() '(z) '(y) '(y z)
              '(x) '(x y) '(x y z)))

通过查看示例，您可以观察到一个结果(我已经使用格式突出显示了该示例):每个示例的答案都包括上一个示例答案中的所有元素。实际上，非空列表的连续子序列只是其尾部的连续子序列以及列表本身的非空前缀。

因此保留主函数并编写non-empty-prefixes

non-empty-prefixes : list -> (listof non-empty-list)

使用该辅助函数，可以轻松编写主要函数。

(可选)由于朴素的函数重复了non-empty-prefixes的调用，因此它的复杂性很差。考虑(segs (cons head tail))。它两次调用(non-empty-prefixes tail):一次是因为它调用了(segs tail)，它调用了(non-empty-prefixes tail)，又一次是因为它调用了(non-empty-prefixes (cons head tail))，它递归地调用了(non-empty-prefixes tail)。这意味着天真函数具有不必要的不​​良复杂性。

问题在于(segs tail)先计算(non-empty-prefixes tail)，然后将其忘记，因此(segs (cons head tail))必须重做工作。解决方案是通过将segs和non-empty-prefixes融合到一个计算两个答案的函数中来保留这些额外的信息:

segs+ne-prefixes : list -> (values (listof list) (listof non-empty-list))

然后将segs定义为仅删除第二部分的适配器函数。这解决了复杂性的主要问题。

(编辑添加)关于segs+ne-prefixes:这是定义non-empty-prefixes的一种方法。 (注意:空列表没有非空前缀。无需引发错误。)

;; non-empty-prefixes : list -> (listof non-empty-list)
(define (non-empty-prefixes lst)
  (cond [(empty? lst)
         empty]
        [(cons? lst)
         (map (lambda (p) (cons (first lst) p))
              (cons '() (non-empty-prefixes (rest lst))))]))

segs看起来像这样:

;; segs : list -> (listof list)
(define (segs lst)
  (cond [(empty? lst) (list '())]
        [(cons? lst)
         (append (segs (rest lst))
                 (non-empty-prefixes lst))]))

您可以像这样融合它们:

;; segs+ne-prefixes : list -> (values (listof list) (listof non-empty-list))
;; Return both the contiguous subsequences and the non-empty prefixes of lst
(define (segs+ne-prefixes lst)
   (cond [(empty? lst)
          ;; Just give the base cases of each function, together
          (values (list '())
                  empty)]
         [(cons? lst)
          (let-values ([(segs-of-rest ne-prefixes-of-rest)
                        ;; Do the recursion on combined function once!
                        (segs+ne-prefixes (rest lst))])
            (let ([ne-prefixes
                   ;; Here's the body of the non-empty-prefixes function
                   ;; (the cons? case)
                   (map (lambda (p) (cons (first lst) p))
                        (cons '() ne-prefixes-of-rest))])
              (values (append segs-of-rest ne-prefixes)
                      ne-prefixes)))]))

该函数仍然遵循设计秘诀(或者，如果我已经展示了我的测试，它也会这样做):特别是，它使用模板在列表上进行结构递归。 HtDP没有讨论values和let-values，但是您可以使用辅助结构对信息进行分组来完成相同的操作。

HtDP稍微讨论了复杂性，但是这种计算的重组通常在“动态编程和记忆”下的算法课程中讨论得更多。注意，融合这两个功能的替代方法是记住non-empty-prefixes；这也将解决复杂性。

最后一件事:结尾处的append的参数应该反转为(append ne-prefixes segs-of-rest)。 (当然，这意味着重写所有测试以使用新的顺序，或编写/查找对顺序不敏感的列表比较功能。)请尝试在一个较大的列表(约300-400个元素)上对函数的两个版本进行基准测试，看看是否可以分辨出差异，并可以解释。 (这是更多算法的材料，而不是设计。)

关于recursion - 如何得出功能段？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8796244/