在Scheme中定义新数据类型

Question

我首先需要提一下,我对Scheme很新,因此,下面的问题可能没有多大意义.

在学校,我们已经定义了代数数据类型,它们通常具有一个无效的构造函数和一些内部/外部的构造函数.

在这种特殊情况下,我感兴趣的是一个BTree二叉树类型(也许平衡,在未来的迭代),我想类似这样是哈斯克尔如何对待构造函数.我曾经看到过如何实现树方案,这里例如,但这不是我想要的.

我不想只是围绕列表做一个包装器.我只想写下这样的东西:

nil: -> BTree
node: BTree x T x BTree -> BTree

然后让它知道我的意思:

flattenTree: BTree -> List

然后,我将定义它被(假设left,right,key被定义):

(define flattenTree
  (lambda (t)
    (node (flattenTree (left t))
          (key t)
          (flattenTree (right t)))))

另外,我欢迎有关正确缩进我的计划代码的建议......(并且请加以修改)

Answer 1

在Scheme中表示二叉树(以及大多数其他数据结构)的规范方法是使用列表.Scheme的一些实现提供了一种用于定义C数据结构样式的新数据类型的工具.在MzScheme(现在的Racket)中,新的二叉树数据类型可以定义为:

(define-struct btree (key left right))

环境将自动为新结构创建构造函数,访问器和更改器过程.

> (define tree (make-btree 1 null null))
> (btree-key tree)
=> 10
> (set-btree-key! tree 10)

在此基础结构之上,您可以定义操作btree的其他过程:

(define (btree-insert! t key)
  (if (< key (btree-key t))
      (if (null? (btree-left t))
          (set-btree-left! t (make-btree key null null))
          (btree-insert (btree-left t) key))
      (if (null? (btree-right t))
          (set-btree-right! t (make-btree key null null))
          (btree-insert (btree-right t) key))))

(define (btree-flatten t)
  (define (flatten t result)
    (if (not (null? t))
        (begin
          (append result (append (flatten (btree-left t) ()) 
                                 (list (btree-key t)))
                  (flatten (btree-right t) ())))
        t))
  (flatten t ()))

;; test

> (define tree (make-btree 10 null null))
> (btree-insert! tree 12)
> (btree-insert! tree 9)
> (btree-insert! tree 8)
> (btree-insert! tree 15)
> (btree-flatten tree)
=> (8 9 10 12 15)