Traversée d'arbres avec Haskell

Question

Salut tout ceci est ma première question ici, je suis très nouveau à Haskell et j'ai besoin de faire une fonction Haskell qui prend un arbre et retourne une liste des éléments dans son nœud dans une traversée de précommande mais Je n'arrive pas à le faire marcher.

Ma définition d'arbres est la suivante:

data Tree a = Node a [Tree a] deriving Show 

et la fonction de pré-commande est:

preorderTree :: Tree a -> [a] 
preorderTree Empty = [] 
preorderTree (Node a l r) = a : (preorderTree l) ++ (preorderTree r) 

En avance je vous remercie beaucoup pour votre aide :)

Answer 1

Dans Haskell, type est un ensemble de valeur s. Nous avons donc à la fois un constructeur de type et un constructeur de valeur. Donc, écrire une fonction de haskell. Nous avons besoin de définir correctement le type (Tree). Traiter chaque valeur (Empty, Node ...) dans le correspondant de type.

Tree a est un type. Sa valeur est soit Empty ou un groupe d'enfants. Ainsi, nous avons

data Tree a = Empty 
      | Node a [Tree a] 

Donc, quand nous écrivons une fonction comme preorderTree :: Tree a -> [a]. Nous traitons typeTree a, donc nous devons traiter avec la valeur Empty et Node a [Tree a]. Nous avons donc

preorderTree :: Tree a -> [a] 
preorderTree Empty = [] 
preorderTree (Node a children) = a : concatMap preorderTree children 

Ceci est un arbre de rose, si vous voulez juste un arbre binaire, il faut changer le constructeur de valeur de type Tree a, parce que [Tree a] est juste trop pour un arbre binaire. Nous avons donc

data Tree a = Empty 
      | Node a (Tree a) (Tree a) 

preorderTree :: Tree a -> [a] 
preorderTree Empty = [] 
preorderTree (Node a left right) = a : preorderTree left ++ preorderTree right 

---

1. https://wiki.haskell.org/Constructor