ファンクションセグを取得するには？

Question

リスト内のすべての連続セグメントのリストを返す関数segsを作成するにはどうすればよいですか？いや、これは本からの問題ではありません（

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

私はHTDPで説明した設計原理に従って、この問題を解決する方法には特に興味がある：例えば 、(segs '(l i s t))は、次のような答えを生成する必要がありますので、それを議論するために自由に感じてください！）それを解決する方法？プログラムの導出にはどの原則を使用するのですか？

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)を2回呼びます：(non-empty-prefixes tail)を呼び出す(segs tail)を呼び出し、を再帰的に呼び出す(non-empty-prefixes (cons head tail))を呼び出すためです。これは、単純な関数が不必要に悪い複雑さを持つことを意味します。

問題は、(segs tail)は(non-empty-prefixes tail)を計算してから忘れてしまいますので、(segs (cons head tail))は作業をやり直す必要があります。それからちょうど第二部分を廃棄アダプタ関数としてsegsを定義

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

：ソリューションは、両方の答えを計算する単一の関数にsegsとnon-empty-prefixesを融合させることにより、余分な情報を保持することです。これは、複雑さの問題を解決します。

（編集中）segs+ne-prefixesについて：ここにはnon-empty-prefixesを定義する方法が1つあります。 （注：空のリストには空の接頭辞はありません。エラーを発生させる必要はありません。）

;; 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+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)))])) 

私が持っていた場合、この機能はまだ設計のレシピを、次の（またはそれが希望：

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

あなたはこのようにそれらを融合することができます私のテストを示しています）：特に、リスト上の構造的再帰のためにテンプレートを使用します。 HtDPはvaluesとlet-valuesについては言及していませんが、情報をグループ化する補助的な構造でも同じことができます。

HtDPは少し複雑ですが、このような計算の再編成は、通常、アルゴリズムコースの「動的プログラミングとメモ帳」で詳しく説明されています。 2つの機能を融合させる代わりに、non-empty-prefixesをメモすることができました。複雑さも修正されました。

最後のもの：appendの末尾にある引数は、逆にすると(append ne-prefixes segs-of-rest)になるはずです。 （もちろん、それは新しい順序を使う​​ためにすべてのテストを書き直すことを意味するか、または順序を区別しないリスト比較関数を書く/見つけることを意味する）大きなリスト（約300〜400要素）で関数の2つのバージョンをベンチマークする。あなたが違いを知ることができ、あなたがそれを説明できるかどうかを見てください。 （より多くのアルゴリズムの材料であり、デザインではありません）

Answer 2

2回の再帰が行われます。左から1番目のチョップアトム、2番目のチョップアトムが右から外れています。ここでは（私はSchemeで流暢じゃないので）私は無地の用語で、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. 

は、すべての結果を蓄積し、あなたは黄金です。