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

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

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

В этом конкретном случае меня интересует создание типа двоичного дерева BTree (возможно, сбалансированного, в будущей итерации), и мне нужно что-то вроде this, как Haskell обрабатывает конструкторы. Ранее я видел, как реализовать деревья в схеме, например здесь, но это не то, что я хочу.

Я не хочу просто делать оболочку вокруг списков. Я просто хочу написать что-то вроде:

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

Кроме того, я приветствую предложения по правильному отступу моего кода схемы ... (и будьте любезно изменены)


functional-programming algebraic-data-types scheme
person Dan Filimon    schedule 14.12.2010    source источник

Ответы (1)


arrow_upward
12
arrow_downward

Канонический способ представления двоичных деревьев (и большинства других структур данных) в 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)
person Vijay Mathew    schedule 15.12.2010
comment
Это просто потрясающий ответ! Большое спасибо! - person Dan Filimon; 15.12.2010