목록 형식으로 하위 목록 유지

Question

DAG를 탐색하기 위해 숙제를 수행 중이며 최단 경로를 찾습니다. 몇 가지 SO 답변 덕분에 꽤 많은 부분이 있습니다. 즉, 데이터를 추가로 처리해야하는 것처럼 하위 목록을 반환하는 함수를 가져 오는 데 문제가 있습니다.

((B3 B5를 57 : 데이터 파일 내가 실행하면 (? 아이들이 'B3), 내가 좋아 보이는 결과를 얻을 형태의 하위 목록의 목록 (노드 1 노드 2 무게)

(define (children? node) 
    (define list '(1)) 
    (map (lambda (x) 
     (cond 
      ((equal? (car x) node) 
      (if (equal? list '(1)) 
       (set-car! list x) 
      (append! list x))))) 
    data) 
(if (equal? list '(1)) 
    #f 
    list)) 

(define (append! lst . lsts) 
    (if (not (null? lsts)) 
    (if (null? (cdr lst)) 
     (begin 
     (set-cdr! lst (car lsts)) 
     (apply append! (car lsts) (cdr lsts))) 
     (apply append! (cdr lst) lsts)))) 

있다 실제로

((B3, B5 57) (B3 B4 81) (B3 B10 55) (B3 B14 61) (

같아야) B3 B4 81 B3 B10 55 B3 B14 61 B3 B13 66)

b3 b13 66))

누구든지 li 여기 내 문제에 불을 붙이세요?

미리 도움을 주셔서 감사합니다.

Answer 1

들여 쓰기를 수정, 코드는 머리 감시 트릭을 사용

(define (children? node) 
    (define list '(1)) 

된다. 좋은 잘...). 그러나 그 목적이 외과 적으로 변경 될 예정이므로, 데이터는 인용되지 않고 새로 작성되어야합니다.

(define list (list 1)) 

무엇을 기다려야합니까? 두 list? 이것은 Common Lisp이 아닙니다. 그렇습니까? Scheme은 Lisp-1이 아니라 Lisp-2입니다. 함수와 값의 이름은 같은 네임 스페이스에 있습니다. 그래서; 하지마. 연속

(define lst (list 1)) 

    (map (lambda (x) 
     (cond 
      ((equal? (car x) node) 
       (if (equal? list '(1)) 
        (set-car! list x) 
        (append! list x))))) 

두 조건은 단지 and이지만, 더 중요한 것은, 머리 감시 트릭은 (cdr lst)으로 진정한 결과를 반환 할 수 있습니다 의미, 그래서 머리의 내용을 변경할 필요가 없습니다. 그런 다음 코드가 단순화됩니다. 첫 번째 위치에서 헤드 센티널을 사용하는 것이 목적입니다.

대체 절이 없습니다. 일반적으로 눈살을 찌푸 리지 만, 여기에서는 부작용에 대한지도를 작성합니다. 따라서 이이 아니라면 map의 결과를 사용하면됩니다. 쉽게하지만 단지 항상이

(map (lambda (x) 
     (if (equal? (car x) node) 
      (append! lst x) ; append two lists together... (see below) 
      #f)) 
     data) 

data처럼, 습관과 좋은 스타일의 문제로 대체 절을 처리하는 것입니다? 그게 뭐야? 다른 형식 매개 변수로 children?을 추가해야합니다.

(if (equal? lst '(1)) 

equal?? 왜? 우리가 그것을 변경했을 여부를 확인하기 위해서는 충분한 단지

(if (null (cdr lst)) 

이상 행동 원칙이다 ...

 #f 
     (cdr lst))) ; cdr carries the true payload 

(그러니까 기본적으로,

(define (children? node data) 
    (let ((res (filter (lambda (x) (equal? (car x) node)) 
         data))) 
     (if (not (null? res)) 
     res 
     #f))) 

). 좋은. 그렇지? 글쎄요, 다음 작업에 따라 달라집니다. 그것은

(define (append! lst . lsts) 
    (if (not (null? lsts)) 
     (if (null? (cdr lst)) 
     (begin 
      (set-cdr! lst (car lsts)) 
      (apply append! (car lsts) (cdr lsts))) 

이 목록을 추가, 그래서 (append! (list 1) (list 2))는 (list 1 2) 및 (append! (list 1) (list 2 3))(list 1 2 3) 같은 같은 결과를 반환합니다. 목록 끝에 (2과 같은) 항목을 추가하려면 먼저 다른 목록에 넣어야했습니다. 따라서 추가되는 항목이 자체 목록 인 경우 '(2 3)과 같이 '(1 (2 3))을 다시 가져오고 싶습니다. 그리고 그것을 위해, 항목은 추가되기 전에 목록에 동봉되어야합니다. 그래서 당신의 기능을 수정해야합니다.

 (apply append! (cdr lst) lsts)))) 

그리고 여기 당신의 마지막 셀, 다시 다시 각 항목에 대한 추가되고를 찾기 위해 (성장) 결과 목록을 검색합니다. 마지막 셀 포인터를 직접 유지하고 직접 사용하여이를 해결할 수 있습니다. 그 "포인터"는 무엇입니까? 그것은 lst입니다.이 때마다 cdr은 append!입니다. 그래서 직접 (set-cdr! lst (list item))을 할 수 있습니다. 물론 lst 변수를 사용할 수는 없습니다 (왜?).

Answer 2

귀하의 코드는 Algol 프로그래밍 경험 (C 또는 Java와 같은)의 지식을 적용하여 Scheme을 배우는 것으로 보입니다. Scheme에서 그렇게 할 이유가 없다면 돌연변이가없는 프로그래밍을 시도해야합니다. 절차의 대부분을 순수하게 유지하는 것이 테스트하기가 쉽다는 것을 의미합니다.

명명 규칙은 중요하며 끝나는 절차는 무엇입니까? 는 술어이므로 과 같이 #t 또는 #f과 같은 두 값 중 하나를 반환해야 Algol 언어로 true/false을 반환해야합니다.

;; graph constructor/accessors not not use car, cadr, etc 
;; later you can change it to boxes 
(define (make-graph from to weight) 
    (list from to weight)) 
(define graph-from car) 
(define graph-to cadr) 
(define graph-wight cddr) 

;; gets the graphs that has node as starting point 
(define (graphs-from node graphs) 
    ; match? returns #t if graph starting point is the same as node 
    ; since it's symbols we use eq? 
    (define (match? graph) 
    (eq? node (graph-from graph))) 

    ; filters data by starting point 
    ; this is the tail expression and thus the result of this procedure 
    (filter match? graphs)) 

(define data (list (make-graph 'x 'y 20) 
        (make-graph 'y 'x 30) 
        (make-graph 'w 'e 20) 
        (make-graph 'x 'e 13))) 

(graphs-from 'x data) 
; ==> ((x y 20) (x e 13)) 

(graphs-from 'a data) 
; ==>()