在計劃中跨樹節點應用函數

Question

我在Dr.Retet中使用Simply Scheme。

問題是編寫樹圖，類似於深度圖，但對於樹，使用數據和子選擇器。這是深圖：

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

這是我在樹的地圖嘗試至今：

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

這些是樹的構造函數和選擇：

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

對於我測試用例我正在使用此功能的數字樹，例如square：

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

我收到的錯誤消息是'cdr，違反合同，期望的對'。到目前爲止，我還沒有太多處理Scheme中的列表的問題 - 我似乎得到了它們。但是，轉化爲樹會導致我遇到問題 - 原則上我得不到這些東西，這意味着我不斷收到有關樹問題的與這些列表相關的錯誤消息。我試圖繼續使用抽象類型（樹和節點）而不考慮列表。 我正在以正確的方式解決這個問題嗎？任何幫助理解我錯過了與樹木一起工作很好，非常感謝。

Answer 1

您的過程被稱爲children是一個訪問器，而不是構造函數。因此，這樣的：

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

本來應該是：

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

你可以做的書中，有一個方法，使葉子，或許是這樣的：

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

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

你的樹節點那些不是葉子的值，在我的節點示例中是2，而一般樹結構葉子是除了一對之外的任何東西，一對是具有兩個子元素的節點。這裏是一個tree-map是由make-node作出的樹木的工作原理：

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

注意的leaf節點(children tree)將'()和(map anything '())始終成爲「（），以便make-node將使新的一頁。遞歸是通過映射，因爲這棵樹有多個孩子，而樹結構只有兩個孩子。由於嚴格的結構，這棵樹的值也可以是成對的。