CODEWITHSUNDEEP
haskellfunctional-programmingbinary-treetree-traversalpreorder
Martin
Martin

Reputation: 1538

Haskell preorder traversal of binary tree

I'm trying to write a function that will traverse a binary tree and return a list of the integers encountered. My data Tree declaration is as follows:

data Tree = Node Int Tree Tree | Leaf Int
   deriving (Eq,Show)

My first idea was to start the function off with:

preorder :: Tree -> [a]  --take in tree, return list of ints

But I've seen some people solving this problem online by using a function declaration format similar to:

preorder :: (a -> c) -> (b -> c) -> Tree -> [c]

And I don't really understand what this line is doing, is it taking multiple inputs?

Thanks

Upvotes: 0

Views: 547

Answers (1)

nicodp
nicodp

Reputation: 2392

It will depend on the underlying definition of the tree. They might be using another tree definition, a common one is like:

data Tree a b = Leaf b | Branch a (Tree a b) (Tree a b)

So they might need to get functions that map values of type a and b to the type c. As your tree definition only has elements of type Int, it would suffice for the preorder function to be of type Tree -> [Int].

UPDATE:

If you want a generalization of your trees in the type of their elements, you can declare this datatype:

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

and with this definition, you can define the type of the preorder function as follows:

preorder :: Tree a -> [a]

Upvotes: 3

Related Questions