Unterlisten in Listenform halten

Question

Ich arbeite an einer Hausaufgabe, um eine DAG zu durchqueren und den kürzesten Weg zu finden. Mit Hilfe einiger SO-Antworten habe ich einige Stücke an Ort und Stelle. Davon abgesehen habe ich Probleme, eine Funktion zur Rückgabe einer Liste von Unterlisten zu erhalten, so dass ich mich weiter mit den Daten befassen muss. Die Datendatei hat eine Liste von Unterlisten in der Form (node1 Knoten2 Gewicht)

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

Wenn ich laufe (Kinder b3?), Ich ein Ergebnis erhalten, die wie folgt aussieht: 57

((b3 b5) b3 b4 81 b3 b10 55 b3 b14 61 b3 b13 66)

Wenn es tatsächlich wie

aussehen sollte

((b3 b5 57) (b3 b4 81) (b3 b10 55) (b3 b14 61) (b3 b13 66))

Kann jemand eine Li scheinen Licht auf mein Problem hier?

Vielen Dank im Voraus für Ihre Hilfe.

Answer 1

den Einzug Fixing, Ihr Code wird

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

den Trick Kopf Sentinel verwenden. Gut (gut ...). Aber da sein Zweck ist es, chirurgisch verändert werden, sollte es frisch, nicht zitiert Datum sein:

(define list (list 1)) 

warten, was? Zwei list s? Das ist nicht Common Lisp, oder? Schema ist ein Lisp-1, nicht Lisp-2; Die Namen von Funktionen und Werten befinden sich im selben Namensraum. damit; nicht.

(define lst (list 1)) 

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

Zwei Bedingungen in einer Reihe ist nur ein and, aber noch wichtiger ist, der Kopf Sentinel-Trick bedeutet, dass Sie das wahre Ergebnis als (cdr lst) zurückkehren, so gibt es keine Notwendigkeit, den Kopf um den Inhalt zu ändern. Der Code vereinfacht dann, das ist der ganze Zweck des Kopf Sentinel an erster Stelle der Verwendung:

(map (lambda (x) 
     (if (equal? (car x) node) 
      (append! lst x)))  ; changed the name 

keine alternative Klausel? Im Allgemeinen, verpönt, aber hier machen Sie die Karte für ihre Nebenwirkung, also, solange Sie nicht das Ergebnis map verwenden, geht es Ihnen gut. Einfacher ist, obwohl nur immer die alternative Klausel als eine Frage der Gewohnheit und guten Stil handhaben, wie

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

data? Was ist das? Es sollte als weiterer formaler Parameter von children? hinzugefügt werden.

(if (equal? lst '(1)) 

equal?? Warum? Um zu sehen, ob wir es geändert haben, ist es genug, nur

(if (null (cdr lst)) 

die kleinsten Wirkung Prinzip ...

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

(Also im Grunde

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

). Gut. Ist es? Nun, es hängt davon ab, dass folgendes richtig funktioniert.

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

Es anhängt Listen, so (append! (list 1) (list 2)) wird das gleiche Ergebnis wie (list 1 2) und (append! (list 1) (list 2 3)) die gleiche wie (list 1 2 3) zurückzukehren. Um ein Element (wie 2) am Ende einer Liste hinzuzufügen, mussten wir es zuerst in eine andere Liste einfügen. Wenn also unser hinzugefügter Eintrag selbst eine Liste ist, wie '(2 3), wollen wir '(1 (2 3)) zurückbekommen. Dazu muss ein Gegenstand vor dem Anhängen in eine Liste eingeschlossen werden. Also muss Ihre Funktion geändert werden, um dies zu tun.

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

Und hier scannen Sie durch Ihre (wachsenden) Ergebnisliste seine letzte Zelle zu finden, die wieder und wieder für jedes Element hinzugefügt wird. Sie können Abhilfe schaffen, indem Sie den letzten Zellenzeiger selbst pflegen und direkt verwenden. Was ist das für ein "Zeiger"? es ist lst, die Sie cdr jedes Mal Sie append! etwas dazu; so können Sie (set-cdr! lst (list item)) direkt yoursef tun. Sie können natürlich nicht lst Variable dafür verwenden (warum?).

Answer 2

Ihr Code sieht aus, dass Sie Scheme lernen, indem Sie Wissen aus der Algol-Programmiererfahrung (wie C oder Java) anwenden. In Scheme sollten Sie versuchen, Ihre Programmierung ohne Mutation zu tun, es sei denn, Sie haben einen wirklich guten Grund, dies zu tun. Wenn Sie die meisten Verfahren rein halten, ist es einfacher zu testen.

Namenskonvention ist wichtig und eine Prozedur, die endet? ist ein Prädikat und daher sollte es einen von zwei Werten zurückgeben, #t oder #f genau wie isString sollte true/ in Algol Sprachen zurückgeben.

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