I'm very new to haskell and I just can't seem to understand this code:
data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)
-- animals tree
animals :: Tree String
animals = Node "elephant"
(Node "bat"
(Leaf "aardvark")
(Node "cow"
(Leaf "chicken")
Empty))
(Node "hare"
(Node "fox"
Empty
(Leaf "goat"))
(Leaf "jackal"))
Specifically, creating that data type its more complex than simple data types I attempted in class. The animals function creates the tree but how does it utilize that type to do so?
Then traversing it with this function:
traverse :: (Tree a) -> [a]
traverse Empty = []
traverse (Leaf x) = [x] --leaf returns list of 1 item
traverse (Node x left_sub_tree right_sub_tree) =
(traverse left_sub_tree) ++
[x] ++
(traverse right_sub_tree)
I'm not sure how this code works, probably because I'm not sure how that data type allows us to make trees. What I can't see is basically the "links" beteen the type creates and how this algorithm uses those function types to create a tree.
Help to understand this would be incredible, thanks!
The data type defines a tree recursively. A tree is composed of cells, each of which can be either "Empty", a "Leaf", or a "Node". The "Node" case has 2 children which are trees as well, this is the recursive definition. The idea is that a tree can either be empty, or a single element, or a single element attached to two other trees.
The traverse code also works recursively. If it encounters the empty tree, it returns an empty list. If it encounters a single element, it returns it. If it encounters a "Node", then it runs recursively for the two subtrees, and then combines the results with the ++ operator.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments