Anwendung Funktion über Baumknoten in Schema

Question

Ich verwende Simply Scheme in Dr. Racket.

Das Problem besteht darin, tree-map zu schreiben, analog zu deep-map, aber für Bäume, mit Datums- und Kinderselektoren. Dies ist tief-Karte:

(define (deep-map f structure) 
    (cond ((word? structure) (f structure)) 
     ((null? structure) '()) 
     (else (cons (deep–map f (car structure)) 
        (deep–map f (cdr structure)))))) 

Dies ist mein Versuch an den Baum-Karte so weit:

(define (tree-map f structure) 
    (cond ((leaf? structure) 
     (f (datum structure))) 
     (else 
     (cons (tree-map f (car (children structure))) 
       (tree-map f (cdr (children structure))))))) 

Dies sind die Konstrukteure und Selektoren für den Baum:

(define (make-node datum children) 
    (cons datum children)) 

(define (datum node) 
    (car node)) 

(define (children node) 
    (cdr node)) 

(define (leaf datum) 
    (make-node datum '())) 

(define (leaf? node) 
    (null? (children node))) 

Für meine Testfall Ich verwende diesen Zahlenbaum mit einer Funktion, z. B. Quadrat:

(define number-tree 
    (make-node 
    '56 
    (list (make-node 
      '2 
      (children '(34 25 7 89))) 
     (make-node 
      '32 
      (list (make-node 
       '27 
       (children '(13 55 80))) 
       (make-node 
       '1098 
       (children '(45 785 98))) 
       (make-node '123 (children '(9046))))) 
     (make-node '23 (children '(1 9))) 
     (make-node '867 
      (children '(1 3 5 78))) 
     (make-node 
      '0 
      (list 
      (make-node '78 (children '(984))) 
      (make-node '45 
       (children '(23 46 78467))) 
      (make-node '3 (children '(2)))))))) 

Die Fehlermeldungen, die ich bekomme, sind Dinge wie 'cdr, Vertragsverletzung, erwartetes Paar'. Ich hatte bisher nicht zu viel Probleme damit, mit Listen in Scheme zu arbeiten - ich scheine sie zu bekommen. Aber das Übersetzen zu Bäumen verursacht mir ein Problem - es gibt etwas, was ich im Prinzip nicht verstehe, was bedeutet, dass ich diese listenbezogenen Fehlermeldungen bei Baumproblemen bekomme. Ich versuche, den abstrakten Typ (Baum und Knoten) zu verwenden, ohne über Listen nachzudenken. Gehe ich in der richtigen Weise? Jede Hilfe, um zu verstehen, was ich vermisse, um mit Bäumen gut zu arbeiten, wird sehr geschätzt.

Answer 1

Ihre Prozedur children ist ein Accessor, kein Konstruktor. dies so:

(make-node 
      2 
      (children '(34 25 7 89)) 

Sollte waren:

(make-node 2 
      (list (leaf 34) 
       (leaf 25) 
       (leaf 7) 
       (leaf 89))) 

Sie könnten wie in dem Buch zu tun und eine Möglichkeit haben, Blätter zu machen, vielleicht so:

(define (leafs lst-values) 
    (map leaf lst-values)) 

(make-node 2 (leafs '(34 25 7 89))) 

Ihr Baumknoten das sind keine Blätter haben Werte, wie 2 in meinem Knoten Beispiel, während allgemeine Baumstruktur ein Blatt ist alles außer ein Paar und ein Paar ist ein Knoten mit zwei Kindern. Hier ist ein tree-map, die von make-node gemacht auf den Bäumen funktioniert:

(define (tree-map proc tree) 
    (let aux ((tree tree)) 
    (make-node (proc (datum tree)) 
       (map aux (children tree))))) 

Beachten Sie, dass für einen leaf Knoten (children tree) wäre '() und (map anything '()) immer wird ‚(), so dass die make-node ein neues Blatt machen würde. Die Rekursion erfolgt über eine Karte, da dieser Baum mehrere untergeordnete Elemente hat, während die Baumstruktur nur zwei untergeordnete Elemente aufweist. Aufgrund der strengen Struktur können die Werte dieses Baumes auch Paare sein.