haskell - making a tree

[artemis_f]

Hello,

I want to create a tree structure in haskell so that later I can do a depth first search on it to find something.

Here is an example I have thought of to try and understand the concept -

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

createTree :: ([String],Int) -> Tree ([String],Int)
createTree ([],0) = Nil
createTree ([x],n) = Node x (createTree removeOne ([x],n)) (createTree removeOne ([x],n))


removeOne :: ([String],Int) -> ([String],Int)
removeOne ([],0) = ([],0)
removeOne (x:xs, n)= (xs, n-1)

does this make sense? Can I do this? Have a stopping condition when the node should not be made and meanwhile keep making nodes?

At the moment I am getting an error:

ERROR "C:\Documents and Settings\Parul Sharma\Desktop\t.hs":7 - Type error in application
*** Expression : createTree removeOne ([x],n)
*** Term : createTree
*** Type : ([String],Int) -> Tree ([String],Int)
*** Does not match : a -> b -> c

How can I resolve this? Or am I going about constructing a tree and its branches incorrectly?

Thanks

[thoughtcoder]

You're missing parentheses around removeOne ([x],n) . Even then I'm not sure if that'll give what you want, but that's the cause of your current error -- the compiler thinks you're trying to pass too many arguments to createTree.

[artemis_f]

Thanks for pointing that out. I am still having trouble though -

Main> createTree (["r","p","q","w","e"], 5)

Program error: pattern match failure: createTree (["r","p","q","w","e"],5)

If I change my code to:

createTree :: ([String],Int) -> Tree ([String],Int)
createTree (_,0) = Nil
createTree([],_) = Nil
createTree ([x],n) = Node ([x],n) (createTree (removeOne ([x],n))) (createTree (removeOne ([x],n)))

I still get the same error...

[thoughtcoder]

So.. what do you expect to happen when you pass a list of length greater than 1?

[artemis_f]

Well my removeOne function is meant to decrease one from n and take off the first thing from the list each time it is called. I have tested it and it works fine.

For e.g. Main> removeOne (["r","p","q","w","e"],5)
(["p","q","w","e"],4)

Here is what I think I have said haskell to do:

//if n is 0 I don't care what the list has don't create a node
createTree (_,0) = Nil
// if list is empty I don't care what n is don't create a node
createTree([],_) = Nil
//if list is not empty and n is not zero then create two branches. Both these branches will have a list of length one less and n one less than before. This keeps happening till the stopping condition above is fulfilled
createTree ([x],n) = Node ([x],n) (createTree (removeOne ([x],n))) (createTree (removeOne ([x],n)))

so I expect that createTree would again and again create a branch for me and each time the branch created would have a number n that is less than the branch above and a list of string whose length is less than the branch above.

But after reading your comment I tried
Main> createTree (["r"],1)
Node (["r"],1) Nil Nil
and so it seems it only takes a list of length one and n=1.

[thoughtcoder]

//if list is not empty and n is not zero then create two branches. Both these branches will have a list of length one less and n one less than before. This keeps happening till the stopping condition above is fulfilled
createTree ([x],n) = Node ([x],n) (createTree (removeOne ([x],n))) (createTree (removeOne ([x],n)))

This is where you're wrong. The pattern "[x]" matches only lists of length 1. The element in the list gets bound to the variable x.

If you want the pattern to match any list, use "createTree (xs, n) = ...".

Or just "createTree pair = ..."

Your createTree function still seems a little funky so we'll see if you have more questions.

[artemis_f]

Ah! I understand my mistake now! I was putting the [x] so it was thinking the list should have only one element.

And I also realise now that I don't even have to go xs n because it isn't like I am making any changes on that line that I am calling removeOne. When something removeOne pair is called removeOne will know what type the structure of pair is and sort things out itself.

So yay because now I get what I wanted to see:
Main> createTree (["r","p"],6)
Node (["r","p"],6) (Node (["p"],5) Nil Nil) (Node (["p"],5) Nil Nil)

I am not spotting any thing else weird going on. If you just mean why in the world I would want to create a tree that has both branches the same that is only because I was thinking of a simple example to understand the concept...

Thanks very much for helping me come to terms with the concept!

[thoughtcoder]

If you just mean why in the world I would want to create a tree that has both branches the same that is only because I was thinking of a simple example to understand the concept...

Yaeah, that's what I was wondering :)