recursion - リストを使用したスキームの累積再帰

Question

リストをパラメーターとして関数に再帰的に要素を追加する関数に渡し、再帰が発生したときにリストを変更しないようにするにはどうすればよいですか？

再帰の各レベルでリストを使用し、より深い再帰レベルで値が追加されたリストを使用したいと思います。

具体的には、グラフでDFS検索を実行し、アクセスしたノードをリストに格納します。

Answer 1

古いリストに値を適用して新しいリストを作成すると、その古いリストは変更されません。

(define old '(1 2 3))
(define new (cons 55 old))

new
>(55 1 2 3)
old
>(1 2 3)

「new」の最初のコンスの「テール」はリスト「old」です。でも古さは変わらない。

(cdr new)
> (1 2 3)

Answer 2

これを行う 1 つの方法は、リストを返すだけで、より高いレベルの再帰でアクセスできるようにすることです。

別の方法は、リストを再帰の外の変数に格納することです。つまり、スタックに格納されません。これにグローバル変数を使用するのは良い考えではないため、ローカル再帰が必要です。

次のコードは、リストを逆にする愚かな方法ですが、私が話している手法を示しています。

(define (letrecreverse lst)
  (letrec ((retlist '())
           (reverse (lambda (lst)
                      (if (null? lst)
                          '()
                          (begin
                            (set! retlist (cons (car lst) retlist))
                            (reverse (cdr lst)))))))
    (reverse lst)
    retlist))

(letrecreverse '(1 2 3 4))
;outputs '(4 3 2 1)

この手法を目的に採用できますか?

Answer 3

あなたの質問を正しく理解していれば、これが1つの解決策になる可能性があります。

;; Just a helper to print the current list.
(define (show list)
  (display "list = ")
  (display list) 
  (newline) 
  (flush-output))

;; Maximum depth of recursion
(define max-recur 5)
;; Original list is backed-up here.
(define orig-list null)

(define (recur list depth)
  (if (null? orig-list) 
      (set! orig-list list))
  (cond ((< depth max-recur)
         (show list)
         (recur (cons (random max-recur) list) (add1 depth)))
        (else orig-list)))

サンプルラン:

> (recur '(1) 0)
list = (1)
list = (1 1)
list = (2 1 1)
list = (3 2 1 1)
list = (4 3 2 1 1)
(1) ;; In the end you get the original list back.