Scheme：從嵌套列表中檢索元素

Question

對於Scheme而言，我很新，而且我在編寫作業的一部分時遇到了麻煩。我有一個圖G給我一個列表，格式如下:(（node1 node2 weight1）（node3 node4 weight2）...）。我試圖編寫一個函數，以這種格式返回此圖中所有節點（V）的列表：（node1 node2 node3 ...）。該函數只能將圖（G）作爲輸入。

所以我想我可以通過增加內G中的每個嵌套列表的第一個和第二個元素，五，遞歸地做到這一點這裏是我寫：

(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），第二次涉及（caar G），並且返回值將僅由開始時的第二個語句（如果我沒有弄錯）設置。

add-to-set是我之前爲作業寫的一個函數，它添加一個元素到列表中，如果它沒有在列表中存在。 （例如：add-to-set n S，這會將n加到S上）

有人能幫助我嗎？ （順便說一句，我不允許使用多個讓我們，讓*或設置）

Answer 1

那麼，你是對的，你可以遞歸地做到這一點，你的代碼是非常接近。回想一下，每個遞歸過程都需要知道答案的基本狀態，並且每次遞歸時都要減少問題的複雜性。

在處理列表的情況下，您的基本情況是空列表，這就是爲什麼您要檢查爲空。然後，縮減公式將打破列表中的一部分，然後調用剩餘部分的過程。所以，就像我說的，你很接近。

然後意識到，既然你的數據是定期結構化的，你可以把你的圖表當作一個正常的列表。您不需要遞歸到列表中的每個元素，只需要對每個元素執行兩個操作並將結果放入列表中。

(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 

你也可以使用一個let如果你想..

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

在你的情況，你會用add-to-set這裏我用cons。一旦我們達到基本情況，所有對add-to-set的調用都將能夠從最後一個開始評估，然後將堆棧回退到第一個。

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