Définition de nouveaux types de données dans Scheme

Question

Je dois tout d'abord préciser que je suis assez novice dans le domaine de Scheme et que, par conséquent, la question qui suit n'a peut-être pas beaucoup de sens.

À l'école, nous avons défini types de données algébriques qui ont typiquement un constructeur nullaire et quelques constructeurs internes/externes également.

Dans ce cas particulier, je souhaite faire un BTree (peut-être équilibré, dans une prochaine itération) et j'aimerais quelque chose comme cette ce qui correspond à la façon dont Haskell traite les constructeurs. J'ai vu précédemment comment implémenter des arbres dans Scheme, ici par exemple, mais il s'agit de no ce que je veux.

Je ne veux pas que l'on se contente de faire une enveloppe autour des listes. Je veux simplement écrire quelque chose comme :

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

et de le faire savoir ce que j'entends par :

flattenTree: BTree -> List

et ensuite, je le définirais comme étant (en supposant que) left , right , key sont définis) :

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

Je suis également ouvert aux suggestions pour indenter correctement mon code Scheme... (et être gentiment moddé)

Answer 1

La manière canonique de représenter les arbres binaires (et la plupart des autres structures de données) en Scheme est la suivante l'utilisation de listes . Certaines implémentations de Scheme permettent de définir de nouveaux types de données, à la manière des structs du langage C. En MzScheme (aujourd'hui Racket), un nouveau type de données d'arbre binaire peut être défini comme suit :

(define-struct btree (key left right))

L'environnement créera automatiquement des procédures de construction, d'accès et de mutation pour la nouvelle structure.

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

En plus de cette infrastructure, vous pouvez définir des procédures supplémentaires qui manipulent l'arborescence :

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