スキーム：ネストされたリストから要素を取得する

Question

私はかなりSchemeを使い慣れていませんし、宿題の一部として関数を書くのに問題があります。私はグラフGを次の形式のリストとして私に与えました：（（node1 node2 weight1）（node3 node4 weight2）...）。私はこのグラフのすべてのノード（V）のリストをこの形式で返す関数を書こうとしています：（node1 node2 node3 ...）。この関数は、グラフ（G）のみを入力とすることができる。

だから私は、私はVに、G内の各ネストされたリストの第1および第2の要素を追加することにより、再帰的にこれを行うことができますここで私が書いたものだと思った：として、私はこれはしかし間違っていると思う

(define nodes-of 
     (lambda (G) 
     (if (null? G) 
      () 
      (begin (add-to-set (cadar G) (nodes-of (cdr G))) 
        (add-to-set (caar G) (nodes-of (cdr G)))))) 

最初の再帰は（cadar G）のみを含み、2番目の再帰は（caar G）を含み、返り値はbeginの下の2番目の文（私が間違っていない場合）によってのみ設定されます。

add-to-setは宿題のために先に書いた関数ですが、リストに要素がない場合は要素をリストに追加します。 （例：add-to-set n S、これはSにnを加えます）

誰でも助けてくれますか？ （btw私は複数のlet'sを使用することは許されません、*またはset）

Answer 1

まあ、あなたは再帰的に行うことができますし、あなたのコードはかなり近いです。すべての再帰的プロシージャでは、答えを知る基本状態と、繰り返し発生するたびに問題の複雑さを軽減する方法が必要であることを思い出してください。

リストを処理する場合、ベースケースは空のリストであるため、nullをチェックする必要があります。次に、縮小式がリストの一部を分割し、残りの部分でプロシージャをコールします。だから、私が言ったように、あなたは近くにいる。

あなたのデータは定期的に構造化されているので、グラフを通常のリストとして扱うことができます。リストのすべての要素に再帰する必要はありません。すべての要素に対して2つのアクションを実行し、その結果をリストに入れるだけです。あなたが望むなら

(define nodes-of 
    (lambda (G) 
     (if (null? G) ;<-- have we reached the base case yet? 
      '()   ;<-- if yes, return null so our cons will build a list 
      (cons (caar G) (cons (cadar G) (nodes-of (cdr G))))))) ;<-- if not, keep building the list by grabbing the things we want from each element, then reducing the list 

また、あなたは私がconsを使用しましたadd-to-setを使用するあなたのケースでは。..

(define nodes-of 
    (lambda (G) 
     (if (null? G) 
      '() 
      (let ((n1 (caar G)) 
        (n2 (cadar G))) 
       (cons n1 (cons n2 (nodes-of (cdr G)))))))) 

をletを使用することができます。ベースケースに達すると、add-to-setへのすべての呼び出しが評価され、最後のものから最初のものに戻って評価されます。

|cons n3 '()   | 2 => (n3) 
|cons n2 [result of 2] | 1 => (n2 n3) 
|cons n1 [result of 1] | 0 => (n1 n2 n3)