Haskell crosses a tree

Question

I have the following Haskell data definition:

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

and I wrote the following programs to pre-order the trees, order and order:

 preorder(Leaf n) = n preorder(Node n t0 t1) = [n] ++ preorder t0 ++ preorder t1 inorder(Leaf n) = n inorder(Node n t0 t1) = inorder t0 ++ [n] ++ inorder t1 postorder(Leaf n) = n postorder(Node n t0 t1) = postorder t0 ++ postorder t1 ++ [n] 

The error I am getting is:

 - Type error in application *** Expression : preorder t0 ++ preorder t1 *** Term : preorder t1 *** Type : Int *** Does not match : [a] 

I need to return a list containing all integers in the appropriate order. Any help is much appreciated as I am new to Haskell.

Answer 1

You return Int from the base code, but [Int] from the constructive case. Sheets should also be lists.

Answer 2

Error:

 preorder(Leaf n) = n 

Must be:

 preorder(Leaf n) = [n] 

And the same goes for order and post-order.

Answer 3

Changing functions fixes the error, but you can only insert elements into pairs in Tree .

Better change it to:

 data Tree = Leaf | Branch Int Tree Tree deriving Show inorder Leaf = [] inorder (Branch n left right) = inorder left ++ [n] ++ inorder right -- etc. 

A good page to familiarize yourself with the implementation of the algorithms in different languages ​​is the Rosetta Code, which has a Tree Walks page, including on Haskell.