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?

Answer 1

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.

Answer 2

I'll define a data type along the lines you mentioned:

data Tree2 b a = Leaf a | Node b (Tree2 b a) (Tree2 b a)
  deriving Show

so I'll be able to use

example :: Tree2 (Integer -> Integer -> Integer) Integer 
example = Node (^) (Leaf 2) (Leaf 3)

The most general folding function ("catamorphism") you can make on this type is one which recurses down the structure replacing each constructor (Leaf, Node) with a function (foldLeaf, foldNode):

foldTree2 :: (a -> v) -> (b -> v -> v -> v) -> Tree2 b a -> v
foldTree2 foldLeaf foldNode = fold where 
   fold (Leaf a) = foldLeaf a
   fold (Node b left right) 
                 = foldNode b (fold left) (fold right)

so we should be able to define lots of functions using this, but in particular, the evaluation function you were seeking is

inOrderApply :: Tree2 (a -> a -> a) a -> a
inOrderApply = foldTree2 id id

ghci> inOrderApply example
8
ghci> inOrderApply (Node (+) (Node (-) (Leaf 10) (Leaf 5))  (Node (*) (Leaf 3) (Leaf 2)))
11