Schemeのツリーノード間で関数を適用する

Question

私はDr. Racketの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))) 

テストケース私は関数を持つこの数値木を使用しています。例えば、

(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のような値を持っていますが、一般的なツリー構造の葉はペアを除いたもので、ペアは2つの子を持つノードです。ここでmake-nodeによって作られた木の上で動作tree-mapです：make-nodeは新しい葉になるだろうようleafノード(children tree)のために（）」'()と(map anything '())が常になっただろうと

が

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

注意してください。このツリーは複数の子を持ち、ツリー構造は2つしかないので、再帰はマップ経由です。厳密な構造のため、このツリーの値もペアになります。