Finding the value of a node in a Haskell tree

Question

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?

Accepted Answer

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`.

Finding the value of a node in a Haskell tree

Solution

Problem