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 _ left right ->
      1 + max (height left) (height right)

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. 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.

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, we'll stick with the first definition above. (We will use it again in Homework 3).

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 _ left right ->
            foo (depth + 1) left && foo (depth + 1) right
  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.

One-Pass Version

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. (Remember: we sometimes care about reducing constant factors, especially when easy to do so.)

Instead, we can 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 to "flatten" the nested case expressions:

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

This version is (perhaps) more readable, but it no longer shortcuts the second recursive call when its result is not needed. Being an eager language, Elm completely evaluates the scrutinee expression (maybeFullTreeHeight left, maybeFullTreeHeight right) and then checks the resulting values against the patterns. This is a bummer if maybeFullTreeHeight left evaluates to Nothing and maybeFullTreeHeight right — whose result will have no effect on the output — takes a long time.

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
      ))

Another helper function ...

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

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

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

Much better!

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
Random.andThen       : (a -> Generator b) -> Generator a -> Generator b
Json.Decoder.andThen : (a -> Decoder b)   -> Decoder a   -> Decoder b
Result.andThen       : (a -> Result x b)  -> Result x a  -> Result x b
Task.andThen         : (a -> Task x b)    -> Task x a    -> Task x b
...

I'm not going to say the m-word in this class. But if you have not seen them before, you may have just developed a bit of intuition for why... "chains" are useful and why they come up so often in functional programming.

cs223

More Trees And Then...

Full Trees

One-Pass Version

And Then...