More Trees And Then...

Let's revisit the tree type as defined before.

type Tree a = Empty | Node a (Tree a) (Tree a)

We will define height as follows:

height t =
  case t of
    Empty        -> 0
    Node _ t1 t2 -> 1 + max (height t1) (height t2)

For example:

height Empty = 0
height (Node 0 Empty Empty) = 1
height (Node 0 (Node 1 Empty Empty) Empty) = 2

With this terminology, the height of a Tree t is the number of Nodes along the longest path from the root (i.e. t) to an Empty tree. Equivalently, the height is the number of edges along the longest path from the root to an Empty tree.

Alternatively, we can define height to be the number of edges along the longest path from the root to a "leaf" node (in our case, a Node with two Empty children); the height of Empty would be Nothing and the height of Node 0 Empty Empty would be Just 1. Perhaps this definition is more common and intuitive. In a functional language, however, both definitions are, arguably, reasonable since empty nodes are represented explicitly (i.e. Empty) instead of implicitly as a null pointer to a tree. (In a language like Java, a value of a reference type T is either null or a reference to a value of type T — akin to Maybe (Ref T)).

In any case, let's stick with the first definition above. (We will use it again in Homework 3). Furthermore, let's refer to the depth of a Tree t (with respect to a root Tree) as the number of edges from the root to t. With this terminology, depth in a Tree of height h ranges from 0 to h-1.

MoreTrees.elm contains the code below.

Full Trees

Let's write a function that determines whether a Tree is full.

isFull : Tree a -> Bool

isFull tree =
  let
    h =
      height tree

    foo depth subtree =
      if depth == h {- && subtree == Empty -} then
        True
      else
        case subtree of
          Empty ->
            False
          Node _ t1 t2 ->
            foo (depth+1) t1 && foo (depth+1) t2
  in
  foo 0 tree

Here, we first compute the height h and then use a helper function foo to recursively walk the tree, keeping track of the depth of the subtree under consideration. Empty is allowed only at the bottom-most level; the then branch returns True without discriminating subtree, because it must be Empty based on how height has computed h. At all other levels (handled by the else branch), the subtree is required to be a Node and, if so, its children are recursively traversed.

We should be able to determine whether a Tree is full without having to first compute its height and then making a second pass comparing the depth of Empty nodes against the height. Instead, we need to do is recursively check that every Node has two children of the same height.

We will write the recursive function

maybeFullTreeHeight : Tree a -> Maybe Int

to return

Nothing if the input tree is not full; and
Just h if both subtrees are full and have height h-1.

The integer height is needed internally to help determine fullness, but can then be discarded if we only need the boolean answer:

isFullTree : Tree a -> Bool
isFullTree t =
  case maybeFullTreeHeight t of
    Just _  -> True
    Nothing -> False

We start with Empty trees, which are trivially full:

maybeFullTreeHeight t =
  case t of
    Empty -> Just 0

For inner nodes, both children must be full (maybeFullTreeHeight must not evaluate to Nothing) and of the same height:

    Node _ left right ->
      case maybeFullTreeHeight left of
        Nothing ->
          Nothing
        Just h1 ->
          case maybeFullTreeHeight right of
            Nothing -> Nothing
            Just h2 ->
              if h1 == h2
                then Just (1 + h1)
                else Nothing

Excellent, we have traversed the Tree in a single pass and checked for fullness.

In the recursive case above, the "error plumbing" code is untidy. One attempted remedy is the following:

      case (maybeFullTreeHeight left, maybeFullTreeHeight right) of
        (Just h1, Just h2) ->
          if h1 == h2
            then Just (1 + h1)
            else Nothing
        _ ->
          Nothing

Perhaps this version is more readable, but it no longer shortcuts the second recursive call when its result is not needed.

And Then...

Instead, we can factor out a general pattern of "chaining" together operations on Maybe values:

maybeAndThen : (a -> Maybe b) -> Maybe a -> Maybe b
maybeAndThen f mx =
  case mx of
    Nothing -> Nothing
    Just x  -> f x

This abstraction allows us to chain multiple Maybe computations together using what looks like straight-line code:

    Node _ left right ->
      maybeFullTreeHeight left  |> maybeAndThen (\h1 ->
      maybeFullTreeHeight right |> maybeAndThen (\h2 ->
        if h1 == h2 then Just (1 + h1) else Nothing
      ))

A couple more helper functions...

maybePure : a -> Maybe a
maybePure x = Just x

maybeGuard : Bool -> Maybe ()
maybeGuard b =
  if b
    then Just ()
    else Nothing

... allow us to refactor once more in style:

    Node _ left right ->
      maybeFullTreeHeight left  |> maybeAndThen (\h1 ->
      maybeFullTreeHeight right |> maybeAndThen (\h2 ->
      maybeGuard (h1 == h2)     |> maybeAndThen (\() ->
        maybePure (1 + h1)
      )))

Much better (especially if we chose some shorter names)!

This "and then" pattern for chaining together expressions is rather common and comes with some library support:

Maybe.andThen        : (a -> Maybe b)    -> Maybe a    -> Maybe b
Result.andThen       : (a -> Result x b) -> Result x a -> Result x b
Json.Decoder.andThen : (a -> Decoder b)  -> Decoder a  -> Decoder b
...

Remember how I said I wouldn't say "monad" in this class? Well, if you have not seen them before, you may have just developed a bit of intuition for why... "chains" are useful in programming and why functional programmers think they're such a big deal.

cs223

More Trees And Then...

Full Trees

And Then...