如何推導函數分段？

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有點複雜地討論複雜性，但是這種計算的重組通常在算法課程中在「動態編程和記憶」下討論。請注意，融合這兩種功能的另一種方法是記憶non-empty-prefixes;這也可以解決複雜問題。

最後一件事：append接近尾聲的參數應該顛倒，(append ne-prefixes segs-of-rest)。 （當然，這意味着要重寫所有測試以使用新訂單，或者編寫/查找對訂單不敏感的列表比較函數。）嘗試在大型列表（大約300-400個元素）上對函數的兩個版本進行基準測試，看看你能否分辨出來，看看你能否解釋它。 （這是更多的算法材料，而不是設計。）

Answer 2

有2個遞歸正在進行：第一排原子離開左邊，第二排原子離開右邊。以下是我想遞歸解決它在2個功能，在普通條件（因爲我不流利的計劃）：

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. 

厚積薄發的所有結果，你是金色的。