Conserver les sous-listes sous forme de liste

Question

Je travaille sur un devoir pour parcourir un groupe de disponibilité de base de données et trouver l'itinéraire le plus court. Avec l'aide de quelques réponses SO, j'ai quelques pièces en place. Cela étant dit, j'ai de la difficulté à obtenir une fonction pour retourner une liste de sous-listes comme j'ai besoin de traiter les données. Le fichier de données a une liste de sous-listes sous la forme (node1 node2 poids)

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

Quand je lance (enfants « b3?), Je reçois un résultat qui ressemble à:

((b3 b5 57) b3 b4 81 b3 B10 55 b3 B14 61 b3 b13 66)

Quand il doit effectivement ressembler

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

Quelqu'un peut-il briller un li ttle lumière sur mon problème ici?

Merci d'avance pour votre aide.

Answer 1

Fixation du retrait, votre code devient

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

En utilisant l'astuce sentinelle de la tête. Bon bien...). Mais puisque son but est d'être modifié par voie chirurgicale, il doit être fraîchement préparé, non cité donnée:

(define list (list 1)) 

attente, quoi? Deux list s? Ce n'est pas du Common Lisp, n'est-ce pas? Le schéma est un Lisp-1, pas Lisp-2; Les noms des fonctions et des valeurs résident dans le même espace de noms; alors; ne fais pas ça.

(define lst (list 1)) 

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

Deux conditions dans une rangée est juste un and, mais plus important encore, l'astuce sentinelle de tête signifie que vous retournerez le vrai résultat que (cdr lst), donc il n'y a pas besoin de modifier le contenu de sa tête. Le code simplifie alors, ce qui est tout le but d'utiliser la sentinelle de la tête en premier lieu:

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

aucune clause autre? En général, désapprouvé, mais ici vous faites la carte pour son effet secondaire, donc, tant que vous ne pas utiliser le résultat map, tout va bien. Plus facile que est juste toujours gérer la clause alternative comme une question d'habitude et un bon style, comme

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

data? Qu'est-ce que c'est? Il devrait être ajouté comme un autre paramètre formel de children?.

(if (equal? lst '(1)) 

equal?? Pourquoi? Pour voir si nous avons modifié, il suffit de juste

(if (null (cdr lst)) 

l'action moins principe ...

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

(Donc, fondamentalement,

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

). Bien. Est-ce? Eh bien, cela dépend du fonctionnement suivant correctement.

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

Il listes ajoute, donc (append! (list 1) (list 2)) retournera le même résultat que (list 1 2) et (append! (list 1) (list 2 3)) les mêmes que (list 1 2 3). Pour ajouter un élément (comme 2) à la fin d'une liste, nous devions le placer dans une autre liste en premier. Donc, si notre article ajouté est lui-même une liste, comme '(2 3), nous voulons obtenir '(1 (2 3)) de retour. Et pour cela, un élément doit être inclus dans une liste avant d'être ajouté. Donc, votre fonction doit être modifiée pour le faire.

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

Et ici vous balayez votre (de plus en plus) la liste des résultats pour trouver sa dernière cellule, encore et à nouveau pour chaque élément ajouté. Vous pouvez y remédier en conservant vous-même le dernier pointeur de cellule et en l'utilisant directement. Quel est ce "pointeur"? c'est lst, que vous cdr chaque fois que vous append! quelque chose à lui; de sorte que vous pouvez faire (set-cdr! lst (list item)) directement yoursef. Vous ne pouvez bien sûr pas utiliser la variable lst pour cela (pourquoi?).

Answer 2

Votre code a l'air d'apprendre Scheme en appliquant les connaissances de l'expérience de programmation Algol (comme C ou Java). Dans Scheme, vous devriez essayer de faire votre programmation sans mutation à moins d'avoir une bonne raison de le faire. Garder la plupart des procédures pures signifie qu'il est plus facile à tester.

La convention de dénomination est importante et une procédure se termine par? est un prédicat et donc il devrait retourner l'une des deux valeurs, #t ou #f tout comme isString devrait retourner true/false en langues Algol.

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