スキームで再帰関数を指定すると、その関数を末尾再帰に変更するにはどうすればよいですか?次に、ストリームを使用してそれを実装するにはどうすればよいですか? このように機能を変更する際に従うパターンやルールはありますか?
この関数を 2-m から数値のリストを作成する例として取り上げます (これは末尾再帰ではありませんか?)
コード：
(define listupto
(lambda (m)
(if (= m 2)
'(2)
(append (listupto (- m 1)) (list m)))))
私はあなたの例を説明することから始めます。それは間違いなく末尾再帰ではありません。この関数がどのように実行されるかを考えてください。追加するたびに、最初に戻って、基本ケースに到達するまで再帰呼び出しを行う必要があります。その後、元のケースに戻ります。
関数のトレースは次のようになります。
(listupto 4)
| (append (listupto(3)) '4)
|| (append (append (listupto(2)) '(3)) '(4))
||| (append (append '(2) '(3)) '(4))
|| (append '(2 3) '(4))
| '(2 3 4)
'(2 3 4)
再帰呼び出しをプルインしてからプルアウトする V パターンに注目してください。末尾再帰の目標は、すべての呼び出しをまとめて構築し、1 回だけ実行することです。あなたがする必要があるのは、関数とともにアキュムレータを渡すことです。このようにして、関数がベースケースに達したときに1回だけ追加できます。
関数の末尾再帰バージョンは次のとおりです。
(define listupto-tail
(lambda (m)
(listupto m '())))
# Now with the new accumulator parameter!
(define listupto
(lambda (m accu)
(if (= m 2)
(append '(2) accu)
(listupto (- m 1) (append (list m) accu)))))
このトレースが表示されると、次のようになります。
(listupto 4)
| (listupto (3) '(4)) # m appended with the accu, which is the empty list currently
|| (listupto (2) '(3 4)) # m appended with accu, which is now a list with 4
||| (append '(2) '(3 4))
'(2 3 4)
パターンがどのように異なるかに注意してください。再帰呼び出しをトラバースする必要はありません。これにより、無意味な実行を回避できます。末尾再帰は理解するのが難しい概念になる可能性があります。ここを参照することをお勧めします。第 5 章には、役立つセクションがいくつかあります。
通常、末尾再帰形式に切り替えるには、コードを変換して、結果を構築し、最終的な戻り値として使用されるアキュムレータ パラメーターを受け取るようにします。これは通常、メイン関数も委任するヘルパー関数です。
フォームの何か：
(define listupto
(lambda (m)
(listupto-helper m '())))
(define listupto-helper
(lambda (m l)
(if (= m 2)
(append '(2) l)
(listupto-helper (- m 1) (append (list m) l)))))
コメントが指摘しているように、ヘルパー関数は名前付き let に置き換えることができます。これは明らかに (Scheme をあまり/十分に行っていません!) より慣用的です (コメントが示唆consするように、リストを作成して追加するよりもはるかに優れています)。
(define listupto
(lambda (n)
(let loop ((m n) (l '()))
(if (= m 2)
(append '(2) l)
(loop (- m 1) (cons m l))))))
ストリームについても尋ねます。たとえば、ストリーム ビルダーが定義されているここまたはここで使用される SICP スタイルのストリームを見つけることができます。from-By
;;;; Stream Implementation
(define (head s) (car s))
(define (tail s) ((cdr s)))
(define-syntax s-cons
(syntax-rules ()
((s-cons h t) (cons h (lambda () t)))))
;;;; Stream Utility Functions
(define (from-By x s)
(s-cons x (from-By (+ x s) s)))
このようなストリームの作成はマクロに依存しており、特別な方法でアクセスする必要があります。
(define (take n s)
(cond ; avoid needless tail forcing for n == 1 !
((= n 1) (list (head s))) ; head is already forced
((> n 1) (cons (head s) (take (- n 1) (tail s))))
(else '())))
(define (drop n s)
(cond
((> n 0) (drop (- n 1) (tail s)))
(else s)))
ただし、それらは永続的ではありません。つまりtake、dropアクセスごとに再計算されます。ストリームを永続化する 1 つの方法は、アクセス時に最後のコンス セルを外科的に変更するテーリング クロージャを作成することです。
(1 . <closure>)
(1 . (2 . <closure>))
....
このような：
(define (make-stream next this state)
(let ((tcell (list (this state)))) ; tail sentinel cons cell
(letrec ((g (lambda ()
(set! state (next state))
(set-cdr! tcell (cons (this state) g))
(set! tcell (cdr tcell))
tcell)))
(set-cdr! tcell g)
tcell)))
(define (head s) (car s))
(define (tail s)
(if (or (pair? (cdr s))
(null? (cdr s)))
(cdr s)
((cdr s))))
こんな風に使えるようになりました
(define a (make-stream (lambda (i) (+ i 1)) (lambda (i) i) 1))
;Value: a
a
;Value 13: (1 . #[compound-procedure 14])
(take 3 a)
;Value 15: (1 2 3)
a
;Value 13: (1 2 3 . #[compound-procedure 14])
(define b (drop 4 a))
;Value: b
b
;Value 16: (5 . #[compound-procedure 14])
a
;Value 13: (1 2 3 4 5 . #[compound-procedure 14])
(take 4 a)
;Value 17: (1 2 3 4)
a
;Value 13: (1 2 3 4 5 . #[compound-procedure 14])
では、 は何(make-stream (lambda (i) (list (cadr i) (+ (car i) (cadr i)))) car (list 0 1))を定義しているのでしょうか。
更新: Daniel Friedmanの1994 年のスライド「The Joys of Scheme, Cont'd」では、これらの「メモ化されたストリーム」(そこで呼び出されているため) のより単純な実装が見つかり、tail関数自体が強制ストリームをテール センチネルに格納します。なので
(define (tail s)
(if (or (pair? (cdr s))
(null? (cdr s)))
(cdr s)
(let ((n ((cdr s))))
(set-cdr! s n)
(cdr s))))
;; can be used as e.g. (https://ideone.com/v6pzDt)
(define fibs
(let next-fib ((a 0) (b 1))
(s-cons a (next-fib b (+ a b)))))