Определение новых типов данных в схеме

Question

Сначала мне нужно упомянуть, что я совершенно новичок в схеме, и поэтому следующий вопрос может не иметь слишком большого смысла.

В школе мы определили Алгебраические типы данных, как правило, имел нультарный конструктор, а также некоторые внутренние/внешние.

В этом конкретном случае я заинтересован в создании 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

Канонический способ представлять двоичные деревья (и большинство других структур данных) в схеме - по Использование списков. Анкет Некоторые реализации схемы обеспечивают возможность определения новых типов данных, как в стиле Структов C. В Mzscheme (Теперь ракетка), новый тип данных двоичного дерева может быть определен как:

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