recursion - 如何导出函数段？

Question

如何构造函数 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中描述的设计原则来解决这个问题(不，这不是书上的问题，所以请随意讨论!)如何解决？在程序推导中使用哪些原则？

Answer 1

首先建立一组相关的例子，首先是最微不足道的例子:

(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 稍微谈到了复杂性，但这种计算重组通常在算法类(class)中的“动态规划和记忆化”下有更多讨论。请注意，融合这两个函数的替代方法是内存 non-empty-prefixes；这也可以解决复杂性。

最后一件事:接近末尾的 append 的参数应该反转为 (append ne-prefixes segs-of-rest)。 (当然，这意味着重写所有测试以使用新顺序，或者编写/查找顺序不敏感的列表比较函数。)尝试在大列表(大约 300-400 个元素)上对函数的两个版本进行基准测试，看看你能不能说出区别，看看你能不能解释一下。 (这是更多的算法 Material ，而不是设计。)