Get Height of Tree

Question

Given the following Abstact Data Type:

data Tree a = Leaf
              | Node Integer (Tree a) a (Tree a) 
              deriving (Show, Eq)-- where Integer is the height (bottom = 0)

I wrote a function to get a tree's height.

-- Get the height of a tree.
getTreeHeight :: Tree a -> Integer
getTreeHeight Leaf                  = 0
getTreeHeight (Node _ left _ right) = 1 + max (getTreeHeight left) (getTreeHeight right)

Please critique this implementation. In particular, I'm curious if I could've written this with a fold-ing function instead. However, I'm not sure if that would require Tree to have implemented the Foldable typeclass.

Answer 1

First, you should decide if the height of a tree will be a field of Node or not. If yes, then there is no need to compute it. Instead, your tree module should hide the constructors and only expose smart constructors:

data Tree a = Leaf
            | Node Integer (Tree a) a (Tree a) 
  deriving (Show, Eq)-- where Integer is the height (bottom = 0)

getTreeHeight :: Tree a -> Integer
getTreeHeight Leaf = 0
getTreeHeight (Node h _ _ _) = h

leaf :: Tree a
leaf = Leaf

node :: Tree a -> a -> Tree a -> Tree a
node l x r = Node (1 + max (getTreeHeight l) (getTreeHeight r)) l x r

In this case, getTreeHeight just accesses the pre-computed height.

---

Or you might want to keep Node without the height, and compute it separately. Implementing Foldable won't help, as it only exposes the elements of a data structure, while you need to examine the structure, not the elements.

What you can do is to create a generalized folding function over Tree, so called catamorphism, which allows you to express functions that consume trees:

data Tree a = Leaf
            | Node (Tree a) a (Tree a) 
  deriving (Show, Eq)-- where Integer is the height (bottom = 0)

treeFold :: (r -> a -> r -> r) -> r -> Tree a -> r
treeFold f z = h
  where
    h Leaf         = z
    h (Node l x r) = f (h l) x (h r)
{-# INLINE treeFold #-}

-- Get the height of a tree.
getTreeHeight :: Tree a -> Integer
getTreeHeight = treeFold (\l _ r -> 1 + max l r) 0

Function treeFold allows you to express all kinds of other functions, to give a few examples:

-- Get the size of a tree.
getTreeSize :: Tree a -> Integer
getTreeSize = treeFold (\l _ r -> 1 + l + r) 0

-- Get the number of leaves.
getTreeLeaves :: Tree a -> Integer
getTreeLeaves = treeFold (\l _ r -> l + r) 1