Haskell Tree в список - обходе

Question

Учитывая следующую структуру дерева в Haskell:

data Tree = Leaf Int | Node Int Tree Tree deriving Show 

Как я могу получить Haskell, чтобы вернуть список данных в предзаказа?

например. дано дерево:

Node 1 (Leaf 2) (Leaf 3) 

возвращение что-то вроде:

preorder = [1,2,3] 

Answer 1

Ok, извините о позднем ответе, но я получил эту работу следующим образом:

preorder(Leaf n) = [n] 
preorder(Node n treeL treeR) = [n] ++ preorder treeL ++ preorder treeR'code' 

Это, однако, не работает для меня еще

preorder (Leaf n) = [n] 
preorder (Node n a b) = n:(preorder a) ++ (preorder b) 

Answer 2

Используйте шаблон соответствия

preorder (Leaf n) = [n] 
preorder (Node n a b) = n:(preorder a) ++ (preorder b) 

Answer 3

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

import qualified Data.Foldable as F 

data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving Show 

instance F.Foldable Tree where 
    foldr f z (Leaf x) = f x z 
    foldr f z (Node k l r) = f k (F.foldr f (F.foldr f z r) l) 

С этим, вы будете иметь возможность использовать каждую функцию, которая работает на Foldable типов, как elem, foldr, foldr , sum, minimum, maximum и такие (см. here для справки).

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

*Main> let t = Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5) 
*Main> F.toList t 
[1,2,3,4,5] 
*Main> F.foldl (\a x -> a ++ [x]) [] t 
[1,2,3,4,5] 
*Main> F.foldr (\x a -> a ++ [x]) [] t 
[5,4,3,2,1] 
*Main> F.sum t 
15 
*Main> F.elem 3 t 
True 
*Main> F.elem 12 t 
False