Search code examples
haskelltreealgebraic-data-types

Finding the value of a node in a Haskell tree

I am currently messing with some Haskell trees. I am new to Haskell (coming from C) and am wondering how I can find the individual value of a Node (what I've been calling a leaf) from the tree. If my tree is say: (root) power, (branchLeft) 2, (branchRight) 3

If I want to read this as, 2 to the power of three, how should I go about this? I'm starting from scratch and have been messing with code now for the past 3 hours and have not got very far.

Any tips/ideas?

Solution

  • You can model a binary tree with a binary operator in the inner nodes using an algebraic data type:

    data Tree a = Leaf a | InnerNode (a -> a -> a) (Tree a) (Tree a)

    The function a -> a -> a is the binary operator. For example, a simple tree of integers could be defined as 

    tree :: Tree Integer
tree = InnerNode (+) (InnerNode (^) (Leaf 3) (Leaf 2)) (Leaf 5)

    To evaluate or interpret the tree in the way you describe you can write a function

    interpretTree :: Tree Integer -> Integer

    To write that function, you will probably want to use pattern matching and recursion:

    interpretTree (Leaf x) = x           -- the base case
interpretTree (InnerNode f l r) = ...  -- use recursion here

    For the second case, you can recursively compute the results for the subtrees and combine them using the function f.