再帰とスキームのリストの返却

Question

再帰を使用してリストを作成し、そのリストをベースケースのために返すという方法で私の頭を折り返すのに問題があります。具体的には、2つの32ビットの数値（x1とx2）をALUに入力し、ビットごとに（ALU1を介して）評価し、結果の数値のリストを作成します。この再帰アルゴリズムのベースケースは（null？x1）ですが、この時点で結果リストにはどのようにしてアクセスできますか？私はスキーム内のリストが不変であることを知っているので、空のリストを作成して結果のリストを追加することはできません。どんな助け？これは関数型プログラミングでの最初の話ですので、事前に感謝します。

(define ALU-helper 
    (lambda (selection sub x1 x2 carry-in n) 
     (if (null? x1) 
      (________?) 
      (cons 
       (ALU1 selection sub (car x1) (car x2) carry-in n) 
       (ALU-helper selection sub (cdr x1) (cdr x2) carry-in (- n 1)))))) 

Answer 1

、これは動作するはずです：

(define ALU-helper 
    (lambda (selection sub x1 x2 carry-in n) 
    (if (null? x1) 
     '() 
     (cons 
     (ALU1 selection sub (car x1) (car x2) carry-in n) 
     (ALU-helper selection sub (cdr x1) (cdr x2) carry-in (- n 1)))))) 

あなたが入力リスト上の再帰を行い、そして、新しい出力リストを構築していますその結果、基底ケースはif (null? lst)であり、空のリスト'()を返します。これは、新しい要素がconsのときに結果リストが各ステップで作成されるためです。入力リストの最後の要素に到達すると、すでに出力リストが構築されており、残りの唯一のことは、リスト末尾のマーカー'()を返すことだけです。

より明確に見るには、より簡単な例を試してみてください。再びベースケースはif (null? lst)ある

(define (copy lst) 
    (if (null? lst) 
     '() 
     (cons (car lst) 
      (copy (cdr lst))))) 

(copy '(1 2 3 4 5)) 
> (1 2 3 4 5) 

通知とconsが(cdr lst), the rest of the list. In your case, you perform ALU1`、操作上の繰り返しの結果とリスト(car lst)の現在の要素をESの再帰的ステップ・リストを入力として受信し、この手順は単にコピー2つのリストを同時にトラバースしているときに、両方のリストの現在の要素に適用されます。

Answer 2

再帰 - ここには比喩があります。

あなたが家を動かしているとします。シフトが必要なものがたくさんあり、それが新しい家に到着することを保証する必要があります。

トラックを埋めるためにたくさんの友人を獲得してください。彼らには他の友人がいるでしょう。ホースの人々は他の友人などを持っています。それがトラックにあなたのもののビットを一歩踏み込む一人にまで沸騰するまで。

今や、各人に、トラックの中に何があるのか​​を伝えるための紙が少しずつあります。今すぐあなたは紙のこれらのビットをciollectingによってリストを持っています。

Answer 3

おそらく、空のリストがほしいのですが、nullと書かれています。だから、：x1とx2の両方が正確に同じ長さを持っていると仮定すると

(if (null? x1) 
    null 
    (cons ...)) 

Answer 4

ここにリストの新しいリストを作成する方法があります：本質的に反対の順序。

（ （ラムダ（LAT） （指揮 （（ヌル？LAT）「（）） （それ以外（リスト（envers（CDR LAT））（カーLAT））） ） ） enversを定義します）