Various Questions about Trees in Haskell

Question

I'm just picking up Haskell and have a few questions about tree notation

First, I'm dealing with the following definition of a tree:

data Tree a = Leaf a | Branch [Tree a]

1) I understand that this definition allows for an infinite number of substrees. But what does the "a" beside the Tree mean? I think it means this Tree can be any data type, correct?

2) How does one define a Tree to test a function in Haskell? For example if I were to pass an array to a function, I would have Foo [1,2,3]. What would it look like for the tree definition above?

3) How would I find the sum of a simple tree (with the tree definition above)?

Thanks for your help in advance!

Answer 1

1) Yes. The "a" is a type parameter, so we can have a Tree Int or Tree String. Note, however, that these two are not the same types.

2) You can define examples of Tree to test a function by just setting a variable equal to it, like so

tree1 = Leaf "hello"
tree2 = Branch [Branch [tree1]]

3) To find the sum, you make a function to recurse over the structure of the tree. It should pattern match on the two different types of Tree (Leaf and Branch) and extract the values from the Branches. Note, that this function would be restricted to Tree a's where a is a type that can be added.