CODEWITHSUNDEEP
haskellrecursiontree
Deindery
Deindery

Reputation: 23

Tree traversal with Haskell

Hi all this is my first question here, I'm very new to Haskell and I need to do a Haskell function which takes a Tree and returns a list of the elements in its node in a preorder traversal but I can't get it to work.

My Tree definition is the following:

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

and the preorder function is:

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

In advance thank you very much for your help :)

Upvotes: 2

Views: 7042

Answers (1)

delta
delta

Reputation: 3818

In Haskell, type is a set of values. So we have both type constructor and value constructor.

So writing a haskell function. We need properly define the type (Tree). Deal every value(Empty, Node ...) in the corresponding type.

Tree a is a type. Its value is either Empty or a bunch of children. Thus we have

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

So when we write a function like preorderTree :: Tree a -> [a]. We are dealing with type Tree a, so we have to deal with value Empty and Node a [Tree a]. So we have

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

This is a rose tree, if you just want a binary tree, we need to change the value constructor of type Tree a, because [Tree a] is just too much for a binary tree. So we have

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

Upvotes: 3

Related Questions