1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.