Tue Oct 9

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]
```

**Implementation:**

```
catMaybes [] = []
catMaybes (Nothing : xs) = catMaybes xs
catMaybes (Just x : xs) = x : catMaybes xs
```

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

**Implementation:**

```
joinMaybes Nothing = Nothing
joinMaybes (Just Nothing) = Nothing
joinMaybes (Just (Just a)) = Just a
```

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

**Implementation of safeDiv:**

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

**Implementation of formula** using nested

`case`

statements:```
formula a b =
case safeDiv (b**2) a of
Nothing -> Nothing
Just x ->
case safeDiv (a**2) (b+a) of
Nothing -> Nothing
Just y -> Just (x+y)
```

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.

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

**Implementation of height:**

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]
```

**Implementation:**

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.

**Implementation:**

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

**Implementation:**

```
followPath (Leaf x) [] = Just x
followPath (Branch l _) (GoLeft : p) = followPath l p
followPath (Branch _ r) (GoRight : p) = followPath r p
followPath _ _ = Nothing
```

This is here just in case we need a `main`

function!