ラケットに組み込みプロシージャ "build-list"を構築する

Question

ラケットに組み込みプロシージャbuild-listをビルドしようとしています。

組み込み関数は次のように動作します：私は私の実装を呼び出すと

(define (my-build-list-recur list-len proc) 
    (if (= list-len 0) 
     '() 
     (cons (proc (sub1 list-len)) (my-build-list-recur (sub1 list-len) proc)))) 

は、私が持っている：

(build-list 10 (lambda (x) (* x x))) 

>> '(0 1 4 9 16 25 36 49 64 81) 

私の実装では、再帰的な手続きのために再帰的な定義であります

(my-build-list-recur 10 (lambda (x) (* x x))) 
>> '(81 64 49 36 25 16 9 4 1 0) 

ご覧のとおり、同じ結果が得られますが、逆の順序です。

ネイティブ関数と同じ順序で結果を返すにはどうすればよいですか？

P .:私は完全に動作する反復プロシージャの再帰的定義を使用して実装を行っています。私は今、完全に再帰的な手順で同じ結果を生成するために苦労しています。私はすでに長い尾の再帰でこの疑問を解決する方法を知っています。あなたは状態変数と末尾呼び出しを使用していない答えを探しているよう

(define (my-build-list list-len proc) 
    (define (iter list-len accu n) 
    (if (= (length accu) list-len) 
     (reverse accu) 
     (iter list-len (cons (proc n) accu) (add1 n)))) 
    ;(trace iter) 
    (iter list-len '() 0)) 

Answer 1

OK：

これはロングテール再帰と私の実装です。再帰的な手順もまた、再帰的プロセスを展開します。わからないなぜあなたは定義がどのように異なっているかを見る以外にこれが欲しい。 末尾再帰モジュロコンロー（hereおよびon wikipedia）も読んでください。この質問に関連しています。

;; recursive procedure, recursive process 
(define (build-list n f) 
    (define (aux m) 
    (if (equal? m n) 
     empty 
     (cons (f m) (aux (add1 m))))) 
    (aux 0)) 

(build-list 5 (λ (x) (* x x))) 
;; => '(0 1 4 9 16) 

aux呼び出しが末尾位置にもはやどのように注意してください - それは、その引数にauxコールを評価されるまで、すなわち、consが評価を完了することはできません。このプロセスは、スタックに進化し、次のようになります。

(cons (f 0) ...) 
(cons (f 0) (cons (f 1) ...)) 
(cons (f 0) (cons (f 1) (cons (f 2) ...))) 
(cons (f 0) (cons (f 1) (cons (f 2) (cons (f 3) ...)))) 
(cons (f 0) (cons (f 1) (cons (f 2) (cons (f 3) (cons (f 4) ...))))) 
(cons (f 0) (cons (f 1) (cons (f 2) (cons (f 3) (cons (f 4) empty))))) 
(cons (f 0) (cons (f 1) (cons (f 2) (cons (f 3) (cons (f 4)'()))))) 
(cons (f 0) (cons (f 1) (cons (f 2) (cons (f 3)'(16))))) 
(cons (f 0) (cons (f 1) (cons (f 2)'(9 16)))) 
(cons (f 0) (cons (f 1)'(4 9 16))) 
(cons (f 0)'(1 4 9 16)) 
'(0 1 4 9 16) 

あなたはconsコールが記入されており、最後の...がするまでemptyで満たされていない...まで開いてぶら下がって残っていることがわかります。 mはnに等しい。

---

あなたは、内側aux手続きが気に入らない場合は、デフォルトのパラメータを使用することができますが、これは、パブリックAPIにプライベートAPIの一部を漏らすん。たぶんそれはあなたにとって有用であるかもしれませんし、多分あなたは本当に気にしないかもしれません。

;; recursive procedure, recursive process 
(define (build-list n f (m 0)) 
    (if (equal? m n) 
     '() 
     (cons (f m) (build-list n f (add1 m))))) 

;; still only apply build-list with 2 arguments 
(build-list 5 (lambda (x) (* x x))) 
;; => '(0 1 4 9 16) 

;; if a user wanted, they could start `m` at a different initial value 
;; this is what i mean by "leaked" private API 
(build-list 5 (lambda (x) (* x x) 3) 
;; => '(9 16)

---

スタックセーフな実装

あなたは、特に、特に、それは書くことがいかに簡単かを考えると、芋、再帰的プロセス（スタックを成長1）が奇妙であるたいと思う理由stack-safe build-listスタックを拡張しないプロシージャ。ここでは、線形反復プロセスを使用した再帰的プロシージャをいくつか示します。

最初は非常に単純ですが、accパラメータを使用してプライベートAPIを少し漏らしています。最初の解決策と同じように、aux手順を使用して簡単に修正できます。

;; recursive procedure, iterative process 
(define (build-list n f (acc empty)) 
    (if (equal? 0 n) 
     acc 
     (build-list (sub1 n) f (cons (f (sub1 n)) acc)))) 

(build-list 5 (λ (x) (* x x))) 
;; => '(0 1 4 9 16) 

リスト全体が構築されるまで、それは常に1つのスタックフレームを再利用することができますので、これはめちゃくちゃ良いです

(cons (f 4) empty) 
(cons (f 3) '(16)) 
(cons (f 2) '(9 16)) 
(cons (f 1) '(4 9 16)) 
(cons (f 0) '(1 4 9 16)) 
;; => '(0 1 4 9 16) 

進化のプロセスをチェックしてください。追加の利点として、0からnまでのカウンタを保持する必要はありません。代わりに、リストを後方に構築し、n-1から0まで数えます。

---

最後に、線形反復プロセスを進化させる別の再帰的な手順を示します。これは、指定されたletと継続の通過スタイルを使用します。このループは、今度はAPIの漏れを防ぐのに役立ちます。

;; recursive procedure, iterative process 
(define (build-list n f) 
    (let loop ((m 0) (k identity)) 
    (if (equal? n m) 
     (k empty) 
     (loop (add1 m) (λ (rest) (k (cons (f m) rest))))))) 

(build-list 5 (λ (x) (* x x))) 
;; => '(0 1 4 9 16) 

あなたはcomposeとcurryを使用する場合、それは少しカントーをクリーンアップ：

;; recursive procedure, iterative process 
(define (build-list n f) 
    (let loop ((m 0) (k identity)) 
    (if (equal? n m) 
     (k empty) 
     (loop (add1 m) (compose k (curry cons (f m))))))) 

(build-list 5 (λ (x) (* x x))) 
;; => '(0 1 4 9 16) 

この手順から進化プロセスは多少異なりますが、あなたは、それはまた成長しないことに気づくでしょう代わりに、ヒープ上にネストされたラムダのシーケンスを作成します。だから、これはnの十分に大きな値のために十分であろう：

(loop 0 identity)      ; k0 
(loop 1 (λ (x) (k0 (cons (f 0) x)))  ; k1 
(loop 2 (λ (x) (k1 (cons (f 1) x)))  ; k2 
(loop 3 (λ (x) (k2 (cons (f 2) x)))  ; k3 
(loop 4 (λ (x) (k3 (cons (f 3) x)))  ; k4 
(loop 5 (λ (x) (k4 (cons (f 4) x)))  ; k5 
(k5 empty) 
(k4 (cons 16 empty)) 
(k3 (cons 9 '(16))) 
(k2 (cons 4 '(9 16))) 
(k1 (cons 1 '(4 9 16))) 
(k0 (cons 0 '(1 4 9 16))) 
(identity '(0 1 4 9 16)) 
'(0 1 4 9 16)