Scheme : 중첩 목록에서 요소 가져 오기

Question

저는 Scheme을 처음 사용하고 숙제의 일부로 함수를 작성하는 데 어려움을 겪고 있습니다. 나는 그래프 G를 다음과 같은 형식으로리스트에 넣었다 : ((node1 node2 weight1) (node3 node4 weight2) ...). 이 그래프에서 모든 노드 (V)의 목록을 다음 형식으로 반환하는 함수를 작성하려고합니다. (node1 node2 node3 ...). 함수는 그래프 (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)))))) 

나는이 같은,하지만 잘못된 생각 :

그래서 나는 여기에 내가 쓴거야 내가 V.에, G 내의 각 중첩 목록의 제 1 및 제 2 요소를 추가하여 반복적으로이 작업을 수행 할 수 있습니다 생각 첫 번째 재귀는 (cadar G) 만 포함하고 두 번째는 (caar G)를 포함하고, 반환 값은 begin (두 번째 문이 잘못 입력되지 않은 경우)에 의해 설정됩니다.

add-to-set은 숙제를 위해 이전에 작성한 기능으로, 목록에 요소가없는 경우 요소를 목록에 추가합니다. (예 : add-to-set n S, 이것은 S에 n을 더합니다)

아무도 도와 줄 수 있습니까? (btw 나는 여러개의 let 's를 사용할 수 없다. * 또는 set)

Answer 1

글쎄, 당신은 재귀 적으로 할 수 있고 코드는 꽤 가깝다. 모든 재귀 프로 시저에는 응답을 알고있는 기본 상태와 재발 할 때마다 문제의 복잡성을 줄이는 방법이 필요합니다.

목록을 처리하는 경우 기본 사례는 빈 목록이므로 null을 확인해야합니다. 그런 다음 축소 수식은 나머지 부분에 대해 프로 시저를 호출 한리스트의 일부를 잘라 버릴 것입니다. 그래서, 내가 말했듯이, 당신은 가깝습니다.

귀하의 데이터가 규칙적으로 구성되어 있으므로 그래프를 일반 목록으로 취급 할 수 있습니다. 목록의 모든 요소에 대해 반복 할 필요는 없으며 모든 요소에 대해 두 가지 작업을 수행하고 결과를 목록에 넣기 만하면됩니다. 원하는 경우

(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)