Assignment 4 specification

Tue Oct 9

catMaybes

Write a function catMaybes that will take a list of Maybe values and keep all the values that are Just, unwrapping them in the resulting list. Its type is:

and here are some examples of its usage:

ghci> catMaybes []
[]
ghci> catMaybes [Just 'w', Nothing, Nothing, Just 'o', Just 'w', Nothing]
"wow"
ghci> catMaybes [Nothing, Nothing]
[]
ghci> catMaybes [Nothing, Just 9, Nothing, Just 2]
[9,2]

joinMaybes

Sometimes we can specify operations that can fail at different levels. If failure is represented as a Maybe type, then they could become nested. Write this function to join together nested possible-failures into a single possible-failure:

Here are some examples:

ghci> joinMaybes Nothing           -- "outer" failure
Nothing
ghci> joinMaybes (Just Nothing)    -- "inner" failure
Nothing
ghci> joinMaybes (Just (Just (3+4)))  -- success
Just 7

Safe division

Division by zero is not well-defined. In Haskell, integer division throws an exception:

ghci> 8 `div` 0
*** Exception: divide by zero

Floating-point division returns a special value called Infinity:

ghci> 8 / 0
Infinity

which is not really legitimate, but allows Haskell to get on with the rest of the calculation. The ‘infinity’ value propagates through other operators:

ghci> (8 / 0) + pi*2 - 99
Infinity

Let’s define a ‘safe’ floating-point division operator that protects against division by zero by returning a Maybe value. Its type signature will be:

and here are some sample uses:

ghci> safeDiv 8 0
Nothing
ghci> safeDiv 8 3
Just 2.6666667
ghci> safeDiv 9 3
Just 3.0

To use safeDiv in larger expressions requires working around the Maybe value. You cannot directly use a Maybe as if it were a number:

ghci> safeDiv 8 0 + pi*2
error: No instance for (Num (Maybe Float))
       arising from a use of ‘+’

But you can use case to pattern-match on it, or fmap to apply other operations within it:

ghci> safeDivPlusC 8 0 (pi*2)
Nothing
ghci> safeDivPlusC 8 3 (pi*2)
Just 8.949852
ghci> safeDivPlusF 8 0 (pi*2)
Nothing
ghci> safeDivPlusF 8 3 (pi*2)
Just 8.949852

Now, use your definition of safeDiv to implement the following formula:

\[ \frac{b^2}{a} + \frac{a^2}{b+a} \]

with this type signature:

If either of the divisions returns Nothing, then the result of the whole formula will also be Nothing.

ghci> formula 3 5
Just 9.458333
ghci> formula 0 5
Nothing
ghci> formula 3 (-3)
Nothing
ghci> formula 3 (-4)
Just (-3.6666665)

Trees

Here is a binary tree data type that stores values at the leaves, but not at the interior nodes. It also enforces that every interior node (branch) must have exactly two children.

You can see some diagrams of sample trees created using this datatype. The sample trees will be used in some of the examples below.

Height of a tree

Define a function height that determines the length of the maximum path from root to a leaf. You can consider leaves to have height zero.

Some examples of its behavior on the sample trees:

ghci> height (Leaf 'K')
0
ghci> height (Branch (Leaf 'G') (Leaf 'X'))
1
ghci> height balancedCharTree1
2
ghci> height rightSkewedIntTree1
4

List of leaf values

This function should take a tree and list all its leaves in order from left to right.

Some examples:

ghci> treeToList (Leaf 'K')
"K"
ghci> treeToList (Branch (Leaf 'A') (Leaf 'Z'))
"AZ"
ghci> treeToList (Branch (Leaf 9) (Branch (Leaf 8) (Leaf 10)))
[9,8,10]
ghci> treeToList balancedCharTree1
"ABCD"
ghci> treeToList rightSkewedIntTree1
[2,4,8,16,32]
ghci> treeToList leftSkewedIntTree1
[2,4,8,16,32]

Transform leaf values

This function is very similar to map on lists. It applies a function to the value of each leaf, and returns a tree containing the results.

Examples:

ghci> treeMap succ (Leaf 'A')
Leaf 'B'
ghci> square x = x*x
ghci> treeMap square (Leaf 9)
Leaf 81
ghci> treeMap square (Branch (Leaf 8) (Leaf 5))
Branch (Leaf 64) (Leaf 25)
ghci> treeMap succ balancedCharTree1
Branch (Branch (Leaf 'B') (Leaf 'C')) (Branch (Leaf 'D') (Leaf 'E'))
ghci> treeMap succ leftSkewedIntTree1
Branch (Branch (Branch (Branch (Leaf 3) (Leaf 5)) (Leaf 9)) (Leaf 17)) (Leaf 33)
ghci> treeMap square leftSkewedIntTree1
Branch (Branch (Branch (Branch (Leaf 4) (Leaf 16)) (Leaf 64)) (Leaf 256)) (Leaf 1024)

You can see the result of treeMap succ leftSkewedIntTree1 as a diagram on the sample trees page.

Follow a path

A path in a tree is a list of instructions that tell us whether to go left or right at each branch. The path should end at a leaf. We’ll use the following two types to describe paths.

Write a function followPath that takes a tree and a path, and returns the value at the leaf – assuming the path ends at a leaf. Otherwise, it will return Nothing.

For example, in the balancedCharTree1 on the sample trees page, if you go right and then left, you land on 'C':

ghci> followPath balancedCharTree1 [GoRight, GoLeft]
Just 'C'

If you just go right and then the path ends, we’re not yet at a leaf so that would produce Nothing:

ghci> followPath balancedCharTree1 [GoRight]
Nothing

Also, if the path is too long and continues past a leaf, the result is Nothing:

ghci> followPath balancedCharTree1 [GoLeft, GoRight, GoLeft]
Nothing

Some examples on other trees:

ghci> followPath rightSkewedIntTree1 [GoRight, GoRight, GoLeft]
Just 8
ghci> followPath rightSkewedIntTree1 [GoRight, GoRight, GoRight, GoLeft]
Just 16
ghci> followPath rightSkewedIntTree1 [GoRight, GoRight, GoRight, GoRight]
Just 32
ghci> followPath rightSkewedIntTree1 [GoLeft]
Just 2
ghci> followPath rightSkewedIntTree1 [GoLeft, GoLeft]
Nothing

main

This is here just in case we need a main function!