3

如何构造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 中描述的设计原则解决这个问题特别感兴趣（不，这不是书中的问题，所以请随意讨论！）如何解决？在程序推导中使用哪些原则？

4

2 回答 2

6

首先建立一组相关的例子，首先是最简单的：

(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 函数就很容易了。

（可选）生成的朴素函数的复杂性很差，因为它重复调用non-empty-prefixes. 考虑(segs (cons head tail))。它调用(non-empty-prefixes tail)了两次：一次是因为它调用(segs tail)了 which 调用(non-empty-prefixes tail)，另一次是因为它调用了(non-empty-prefixes (cons head tail))which 调用(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 不谈论valuesand let-values，但你可以用一个辅助结构来做同样的事情来对信息进行分组。

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

最后一件事：append接近结尾的论点应该颠倒过来，到(append ne-prefixes segs-of-rest). （当然，这意味着重写所有测试以使用新顺序，或者编写/查找不区分顺序的列表比较函数。）尝试在一个大列表（大约 300-400 个元素）上对该函数的两个版本进行基准测试，看看你能不能分辨出来，看看你能不能解释一下。（这是更多的算法材料，而不是设计。）

于 2012-01-10T07:57:42.447 回答
0

进行了 2 次递归：第一次将原子从左侧切掉，第二个将原子从右侧切掉。简单来说，这是我在 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.

累积所有结果，你就是金子。

于 2012-01-09T23:19:30.650 回答