如何导出函数段？

Question

如何构造函数 segs 返回列表中所有连续段的列表？ 例如，(segs '(list))应该产生以下答案：

(() (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)))

通过查看示例，您可以进行观察（我使用格式来突出显示）：每个示例的答案都包含答案中的所有元素对于前面的例子。事实上，非空列表的连续子序列只是其尾部的连续子序列加上列表本身的非空前缀。

因此，将 main 函数搁置起来，编写 non-empty-prefixes

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

有了该辅助函数，就可以轻松编写 main 函数。

（可选）生成的朴素函数的复杂性很差，因为它重复调用非空前缀。考虑(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)) code> 必须重做工作。解决方案是通过将 segs 和 non-empty-prefixes 融合到计算两个答案的单个函数中来保留这些额外信息：

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

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

（编辑添加）关于segs+ne-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 稍微讨论了复杂性，但这种计算重组通常在算法课程的“动态编程和记忆”下更多地讨论。请注意，融合这两个函数的另一种方法是记忆非空前缀；这也可以解决复杂性问题。

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

Answer 2

正在进行两次递归：第一次从左侧砍掉原子，第二次从右侧砍掉原子。下面是我如何用两个函数递归地解决这个问题，用简单的术语来说（因为我不太熟悉Scheme）：

Start with the FullList variable in function A, 
accumulate right-chop results on FullList from recursive function B, 
then chop off the left character of FullList and call function A with it. 
Stop when an empty list is received. 

累积所有结果，你就很优秀了。