Defining new data types in Scheme

Question

I first need to mention that I'm quite new to Scheme and as such, the following question might not make too much sense.

At school, we've defined algebraic data types, that typically had a nullary constructor and some internal/external ones as well.

In this particular case, I'm interested in making a BTree binary tree type (perhaps balanced, in a future iteration) and I'd like something like this which is how Haskell treats constructors. I've previously seen how to implement trees in Scheme, here for instance, but this is not what I want.

I don't want is to just make a wrapper around lists. I simply want to write something like:

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

and then have it know what I mean by:

flattenTree: BTree -> List

and then, I would define it to be (assuming left, right, key are defined):

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

Also, I welcome suggestions for properly indenting my Scheme code... (and be kindly modded up)

Answer 1

The canonical way to represent binary trees (and most other data structures) in Scheme is by using lists. Some implementations of Scheme provide a facility to define new data types as in the style of C structs. In MzScheme (now Racket), a new binary tree data type could be defined as:

(define-struct btree (key left right))

The environment will automatically create constructor, accessor and mutator procedures for the new struct.

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

On top of this infrastructure, you can define additional procedures that manipulate the 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)