Haskell tree for list - pre-order bypass

Question

Given the following tree structure in Haskell:

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

How can I get Haskell to return a list of data in a preliminary order?

eg. set tree:

 Node 1 (Leaf 2) (Leaf 3) 

return something like:

 preorder = [1,2,3] 

Answer 1

Ok, sorry for the late reply, but I got this work as follows:

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

This, however, does not work for me yet

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

Answer 2

You can use a more general solution and make your data type an instance of Foldable . There is a very similar example in hackage , but this implements a post-order visit. If you want to support pre-orders, you will have to write something like this:

 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 fz (Leaf x) = fxz foldr fz (Node klr) = fk (F.foldr f (F.foldr fzr) l) 

With this, you can use every function that works with Foldable types such as elem , foldr , foldr , sum , minimum , maximum and such (see here for reference).

In particular, the list you are looking for can be obtained using toList . Here are some examples of what you could write with the declaration of this instance:

 *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 (\ax -> a ++ [x]) [] t [1,2,3,4,5] *Main> F.foldr (\xa -> 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 

Answer 3

Use pattern matching

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