Определение новых типов данных в схеме - PullRequest
Новая
       19

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

5 голосов
/ 15 декабря 2010

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

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

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

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

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

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

1 Ответ

12 голосов
/ 15 декабря 2010

Канонический способ представления двоичных деревьев (и большинства других структур данных) в схеме - это с использованием списков .Некоторые реализации Scheme предоставляют возможность определять новые типы данных, как в стиле структур Си.В 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)
...