minimum height in tree

Question

I'm trying to optimize the code:

data Tree = Empty | Node Integer Tree Tree
minHeight Empty = -1
minHeight (Node _ Empty Empty) = 0
minHeight (Node _ l     r    ) = (min (minHeight l) (minHeight r)) + 1

My goal is to not calculate the branches whose depth will be higher than the already known one.

Answer 1

You can use Peano Nats instead of Integers and let laziness do the job:

data Nat = S Nat | Z deriving (Eq)

instance Ord Nat where
    min (S n) (S m) = S (min n m)
    min  _     _    = Z

instance Enum Nat where
    fromEnum  Z    = 0
    fromEnum (S n) = fromEnum n + 1

data Tree = Empty | Node Integer Tree Tree

minHeight  Empty        = Z
minHeight (Node _  l r) = S (min (minHeight l) (minHeight r))

tree = Node 0 (Node 1 tree Empty) tree

main = print $ fromEnum $ minHeight tree -- 2

Answer 2

Here's a solution, which doesn't calculate the branches, whose depth will be higher then the already known one:

data Tree = Empty | Node Integer Tree Tree

minHeight :: Tree -> Int
minHeight =
  loop Nothing 0
  where
    loop defaultDepth depth tree =
      case defaultDepth of
        Just x | x <= depth ->
          x
        _ ->
          case tree of
            Empty -> depth
            Node _ left right ->
              loop (Just (loop defaultDepth (succ depth) left)) (succ depth) right