Trees

We'll skip arrays because arrays are implemented in C via Haskell's foreign function interface—they cannot be implemented in Haskell itself—and thus most operations on arrays must also be implemented in C. This leaves binary trees and Reader. First trees. Here's the type again:

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

Again, we want to apply the given function to every element in the tree. If the tree is empty, we should get an empty tree back. If the tree is non-empty, then the root of the resulting tree should be obtained by applying the function to the root of the input tree. The left and right subtrees should be produced by recursively applying the function to all elements in the left and right subtrees of the input tree. Thus,

instance Functor Tree where
    fmap f = go
      where
        go Empty        = Empty
        go (Node l x r) = Node (go l) (f x) (go r)

Exercise

Verify the functor laws for the Tree functor.

Solution

Equational reasoning with inner functions, such as go, is tricky because they have "hidden arguments", namely the arguments of their surrounding functions. Here, we could rewrite fmap without inner functions, but this doesn't always work either. So let's agree on the following notation: For an inner function, say go, we will write go[f=id] to mean that we're applying go in a context where the argument of the surrounding function fmap is f=id.

Identity:

fmap id Empty = go[f=id] Empty                 -- Definition of fmap
              = Empty                          -- First equation of go
              = id Nothing                     -- Definition of id

fmap id (Node l x r)
    = go[f=id] (Node l x r)                    -- Definition of fmap
    = Node (go[f=id] l) (id x) (go[f=id] r)    -- Second equation of go
    = Node (go[f=id] l) x (go[f=id] r)         -- Definition of id
    = Node (fmap id l) x (fmap id r)           -- Definition of fmap
    = Node (id l) x (id r)                     -- Induction because l and r are
                                               -- smaller than Node l x r
    = Node l x r                               -- Definition of id
    = id (Node l x r)                          -- Definition of id

Composition:

fmap (f . g) Empty
    = go[f=(f.g)] Empty             -- Definition of fmap
    = Empty                         -- First equation of go
    = go[f=f] Empty                 -- First equation of go
    = go[f=f] (go [f=g] Empty)      -- First equation of go
    = fmap f (fmap g Nothing)       -- Definition of fmap
    = (fmap f . fmap g) Nothing     -- Definition of function composition

fmap (f . g) (Node l x r)
    = go[f=(f.g)] (Node l x r)
    -- Definition of fmap

    = Node (go[f=(f.g)] l) ((f.g) x) (go[f=(f.g)] r)
    -- Second equation of go

    = Node (fmap (f.g) l) ((f.g) x) (fmap (f.g) r)
    -- Definition of fmap

    = Node ((fmap f . fmap g) l) ((f.g) x) ((fmap f . fmap g) r)
    -- Induction because l and r are smaller than Node l x r

    = Node (fmap f (fmap g l)) (f (g x)) (fmap f (fmap g r))
    -- Defintition of function composition

    = Node (go[f=f] (fmap g l)) (f (g x)) (go[f=f] (fmap g r))
    -- Definition of fmap

    = go[f=f] (Node (fmap g l) (g x) (fmap g r))
    -- Second equation of go

    = fmap f (Node (go[f=g] l) (g x) (go[f=g] r))
    -- Definition of fmap

    = fmap f (go[f=g] (Node l x r))
    -- Second equation of go

    = fmap f (fmap g (Node l x r))
    -- Definition of fmap

    = (fmap f . fmap g) (Node l x r)
    -- Definition of function composition

Exercise

For this exercise, it will be useful to be able to print trees on screen, so we can inspect the result of applying functions to trees. To do this, we need to make Tree an instance of the Show type class:

GHCi

>>> :{
  | data Tree a = Empty
  |             | Node (Tree a) a (Tree a)
  |   deriving Show
  |
  | instance Functor Tree where
  |     fmap f = go
  |       where
  |         go Empty = Empty
  |         go (Node l x r) = Node (go l) (f x) (go r)
  | :}

Now let's define a tree of strings:

GHCi

>>> tree = Node (Node (Node Empty "Haskell" Empty) "programming" (Node Empty "is" Empty)) "fun" Empty
>>> tree
Node (Node (Node Empty "Haskell" Empty) "programming" (Node Empty "is" Empty)) "fun" Empty

Visually, this is the following tree:

A visual representation of the tree Node (Node (Node Empty "Haskell" Empty) "programming" (Node Empty "is" Empty)) "fun" Empty

Transform this tree into a tree where each node's string has been replaced by the string's length:

Node (Node (Node Empty 7 Empty) 11 (Node Empty 2 Empty)) 3 Empty

Next try to convert each string to uppercase:

Node (Node (Node Empty "HASKELL" Empty) "PROGRAMMING" (Node Empty "IS" Empty)) "FUN" Empty

For this, you need to import the Data.Char module to gain access to its toUpper function.

Solution

GHCi

>>> import Data.Char
>>> fmap length tree
Node (Node (Node Empty 7 Empty) 11 (Node Empty 2 Empty)) 3 Empty
>>> fmap (fmap toUpper) tree
Node (Node (Node Empty "HASKELL" Empty) "PROGRAMMING" (Node Empty "IS" Empty)) "FUN" Empty

The first example should be obvious: we simply apply the function length to every string in the tree. The second example is more interesting. We use fmap twice here. Those are two different fmaps. The outer one is the one for the Tree type. The inner one is the one for the list type.

To convert a string to uppercase, we need to apply toUpper to every character in the string. Since a string is just a list of characters, we can thus convert a string to uppercase using fmap toUpper. We now want to apply this function to every string stored in our tree. So we need to fmap this function over our tree. This gives fmap (fmap toUpper) tree.