functional-programming - 在 Scheme 中定义新的数据类型

Question

我首先需要提到的是，我对 Scheme 很陌生，因此，以下问题可能没有太大意义。

在学校，我们定义了 代数数据类型 ，通常有一个空构造函数和一些内部/外部构造函数。

在这种特殊情况下，我有兴趣制作 BTree二叉树类型(可能是平衡的，在 future 的迭代中)，我想要类似 this 的东西这就是 Haskell 对待构造函数的方式。我之前看过如何在 Scheme 中实现树，here例如，但这是 不是 我想要的是。

我不想只是围绕列表做一个包装。我只是想写一些类似的东西:

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

另外，我欢迎正确缩进我的 Scheme 代码的建议......(并请修改)

Answer 1

在 Scheme 中表示二叉树(和大多数其他数据结构)的规范方法是 using lists . 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)