A file ending with `.hs`

is assumed to be Haskell code. It can contain comments using this syntax:

```
-- Double dash for a line comment
{- Delimited comments like
this that can go on for multiple lines.
-}
```

But instead of a regular Haskell file, you can save your file ending with `.lhs`

, which stands for Literate Haskell. What that means is that you’re typing comments **by default**. To embed some code, you add `>`

to the left margin of each line:

` > square x = x*x`

There’s no need for you to use Literate Haskell in this course, but I wanted you to understand how I’m using it to produce notes and assignment solutions. When viewing web pages on my site that are produced with Literate Haskell, you’ll see a link to the source just above the table of contents – which is in the upper right or the bottom of the page. As long as the filename ends in `.lhs`

, you can load that source directly into `ghci`

or use `runghc`

on it.

Let’s focus on `mapLeaves`

.

Here was the data type:

```
data Tree lv bv
= Leaf {leafValue :: lv}
| Branch {branchValue :: bv, left, right :: Tree lv bv}
deriving (Show, Eq)
```

This is the signature we want:

`mapLeaves :: (lv1 -> lv2) -> Tree lv1 bv -> Tree lv2 bv`

The `->`

represents the type of a function. When you have `a -> b -> c`

you can treat that as a function with two parameters (`a`

and `b`

) and the result type `c`

. Or, the default way that the `->`

is parenthesized is right-associative `(a -> (b -> c))`

. Any function with >1 parameter can be used this way – it is called **partial application.**

```
ghci> f x y = 3*x + 2*y -- A function with two parameters
ghci> :t f -- Its type:
f :: Num a => a -> a -> a -- Think of it as (Num -> (Num -> Num))
ghci> f 5 6 -- Complete application produces number
27
ghci> f 5 -- Partial application produces function
f 5 :: Num a => a -> a -- which has type (Num -> Num)
ghci> g = f 5 -- Can bind function to new variable
ghci> g 6 -- And then provide next parameter
27
ghci> g 8
31
```

Here is our implementation of `mapLeaves`

:

```
mapLeaves fn (Leaf lv) = Leaf (fn lv)
mapLeaves fn (Branch bv left right) =
Branch bv (mapLeaves fn left) (mapLeaves fn right)
```

You should notice that most of these recursive functions on trees follow the same structure. There are two cases, the base case for `Leaf`

and a recursive case for `Branch`

. The recursive case actually uses recursion twice, on both `left`

and `right`

. Then it does some other stuff outside of the recursion to merge the results together somehow.

```
ghci> mapLeaves (+5) (Branch 'A' (Leaf 9) (Branch 'C' (Leaf 10) (Leaf 12)))
Branch {branchValue = 'A',
left = Leaf {leafValue = 14},
right = Branch {branchValue = 'C',
left = Leaf {leafValue = 15},
right = Leaf {leafValue = 17}}}
```

In that example, we’re applying `(+5)`

to each leaf. So the values start as numbers and remain numbers. But `mapLeaves`

is also capable of changing the type. Here we use `show`

to convert the numbers to strings:

```
ghci> mapLeaves show (Branch 'A' (Leaf 9) (Branch 'C' (Leaf 10) (Leaf 12)))
Branch {branchValue = 'A',
left = Leaf {leafValue = "9"},
right = Branch {branchValue = 'C',
left = Leaf {leafValue = "10"},
right = Leaf {leafValue = "12"}}}
```

Or here’s an interesting example using the `const`

function. `const`

takes two parameters but returns its first one. With partial application, we can create a function that always returns the same result. So we can keep the same tree structure and branch values but replace every leaf value with the same string.

```
ghci> :t const
const :: a -> b -> a
ghci> const 9 3
9
ghci> const 9 "hello"
9
ghci> p = const "hello"
ghci> p "bye"
"hello"
ghci> p pi
"hello"
ghci> mapLeaves (const "BOO") (Branch 'A' (Leaf 9) (Branch 'C' (Leaf 10) (Leaf 12)))
Branch {branchValue = 'A',
left = Leaf {leafValue = "BOO"},
right = Branch {branchValue = 'C',
left = Leaf {leafValue = "BOO"},
right = Leaf {leafValue = "BOO"}}}
```

A stack is a last-in first-out (LIFO) sequence with operations to `push`

, `pop`

, `top`

. We’ll implement a *bounded* stack where the number of elements is limited to some number specified when the stack is created.

```
data BoundedStack a
= BoundedStack { capacity :: Int, elements :: [a] }
deriving Show
```

To design this, it can be helpful to first specify all the signatures of the functions. **Note:** compared to what we did in class, I changed the order of the two parameters to `push`

. Passing the stack *after* the new element to add makes some of the composition syntax easier.

```
new :: Int -> BoundedStack a
push :: a -> BoundedStack a -> BoundedStack a
pop :: BoundedStack a -> BoundedStack a
top :: BoundedStack a -> a
```

Creating a new stack means we specify the capacity but let the initial list of elements be the empty list.

`new n = BoundedStack { capacity = n, elements = [] }`

In order to push, we need to ensure (with a guard) that the capacity is positive. Then when we create the `BoundedStack`

, we decrement the capacity and shove the new `elem`

onto the front of the list.

```
push elem (BoundedStack cap elems)
| cap > 0 = BoundedStack (cap-1) (elem:elems)
| otherwise = error "Sorry, stack is full"
```

For now, if the precondition `cap > 0`

is not satisfied, we’ll just use `error`

to throw an exception with a custom message. Here are some examples using `new`

and `push`

.

```
ghci> s1 = new 3
ghci> s2 = push 7 s1
ghci> s3 = push 8 s2
ghci> s4 = push 9 s3
ghci> s4
BoundedStack {capacity = 0, elements = [9,8,7]}
ghci> s5 = push 10 s4
ghci> s5
*** Exception: Sorry, stack is full
CallStack (from HasCallStack):
error, called at /home/league/c/c/cs695/20170928.lhs:160:19 in main:Main
```

**Note** that we don’t see the exception right after the last `push`

, but only once we try to *inspect* the result. This is a result of *laziness* in Haskell, which we’ll discuss later.

We used separate variable names (`s1`

, `s2`

, `s3`

) for each stage of the computation, just so we can inspect them more easily. But if you don’t need to do that, you can sequence them together with normal function composition; such as:

```
ghci> push 9 (push 8 (push 7 (new 3)))
BoundedStack {capacity = 0, elements = [9,8,7]}
ghci> push 9 $ push 8 $ push 7 $ new 3
BoundedStack {capacity = 0, elements = [9,8,7]}
ghci> (push 9 . push 8 . push 7) (new 3)
BoundedStack {capacity = 0, elements = [9,8,7]}
```

You should try to write `pop`

and `top`

. Here are some placeholders:

```
pop = error "pop : not implemented yet"
top = error "top : not implemented yet"
```

There is the `error`

function that takes a string and causes the program to halt (with an exception) and displays the string. That’s a really blunt tool.

We generally don’t like error because it turns the function you’re writing into a “partial function” – one that doesn’t respond properly for every possible input. (The built-in `head`

and `tail`

are partial functions.)

If you do use `error`

, it’s a good idea to make sure the string is searchable within the code:

` error "BoundedStack: pop: not implemented"`

vs

` error "not implemented"`

or

` error "OOPS"`

which will make those messages harder to find.

`Maybe`

typeThis type is Haskell’s answer to “null pointers”. It’s equivalent to this data type:

```
data Maybe a
= Just a
| Nothing
```

A function in the standard Haskell prelude that produces a maybe value is `lookup`

. It searches through a list of key-value pairs for a matching key. This type of list is often called an **association list**.

```
friends :: [(String,Int)]
friends = [("Bob",1989), ("Alice",1993), ("Carla",1979)]
```

```
ghci> lookup "Alice" friends
Just 1993
ghci> lookup "Doug" friends
Nothing
```

What if we want to *act* on a value that has a `Maybe`

type? You can use the `case`

/`of`

construct, which does pattern-matching on the result of an expression, much like we do when writing functions with multiple cases.

```
ageOf :: String -> [(String,Int)] -> Maybe Int
ageOf name people =
case lookup name people of
Nothing -> Nothing
Just year -> Just (2017 - year)
```

So the above function performs the lookup of the name to retrieve a year, and then subtracts the year from 2017 to determine the person’s age. But if the lookup fails, it handles that and also just returns `Nothing`

for the person’s age.

```
ghci> ageOf "Alice" friends
Just 24
ghci> ageOf "Bob" friends
Just 28
ghci> ageOf "Doug" friends
Nothing
```

`Either`

typeThis is another way to signal errors or unusual conditions in Haskell.

```
data Either a b
= Left a
| Right b
```

Typically, the `Right`

constructor is used as the correct result, and the `Left`

constructor is used for some erroneous result. But we can also just use `Either`

and the `Left`

/`Right`

constructors to unify two types into a common one. Recall that lists must contain elements of the same type, so it’s an error to try to have a list containing both numbers and characters:

```
ghci> [5,7,8]
[5,7,8]
ghci> ['a','b','c']
"abc"
ghci> ['a',7,8,'c']
<interactive>:260:6: error:
• No instance for (Num Char) arising from the literal ‘7’
```

One way around this is to construct a list of `Either`

values, where we use `Left`

to tag characters, or `Right`

to tag numbers.

```
ghci> stuff = [Left 'a', Right 7, Right 8, Left 'c']
ghci> :t stuff
stuff :: Num b => [Either Char b] -- List of either char or number
```

To use `Either`

for errors, we can define a special-purpose version of `lookup`

that produces a custom error message tagged with `Left`

if the key is not found.

```
myLookup :: String -> [(String,a)] -> Either String a
myLookup key list =
case lookup key list of
Nothing -> Left ("key not found: " ++ key)
Just value -> Right value
```

```
ghci> myLookup "Alice" friends
Right 1993
ghci> myLookup "Bob" friends
Right 1989
ghci> myLookup "Doug" friends
Left "key not found: Doug"
```

Here’s an interesting function that keeps all the `Right`

values in a list and throws away all the `Left`

values.

```
rights :: [Either a b] -> [b]
rights [] = []
rights (Left _ : xs) = rights xs
rights (Right x : xs) = x : rights xs
```

In Haskell, `Functor`

is a type class. That means it describes a set of types that have particular properties or functions. You can think of `Functor`

as describing types that are **mappable**: Lists are mappable; `Maybe`

is mappable; and the right side of `Either`

is mappable.

```
ghci> :t map -- map is specific to lists
map :: (a -> b) -> [a] -> [b]
ghci> :t fmap -- fmap works for any functor
fmap :: Functor f => (a -> b) -> f a -> f b
ghci> map (+4) [1..5]
[5,6,7,8,9]
ghci> fmap (+4) [1..5] -- on lists, fmap same as map
[5,6,7,8,9]
ghci> fmap (+4) (Just 5) -- Maybe is a functor
Just 9
ghci> fmap (+4) Nothing
Nothing
ghci> fmap (+4) (Right 5) -- Either is a functor,
Right 9
ghci> fmap (+4) (Left 5) -- but only on a Right value
Left 5
```

Let’s specify that Tree is a functor instance. Like `Either`

, the `Tree`

takes two type variables. To simplify, we’ll demonstrate this using a new type `Tree1`

that just takes one type variable. It won’t store any data at the branches, just at the leaves.

```
data Tree1 a
= Leaf1 a
| Branch1 (Tree1 a) (Tree1 a)
deriving Show
```

```
instance Functor Tree1 where
fmap fn (Leaf1 a) = Leaf1 (fn a)
fmap fn (Branch1 left right) =
Branch1 (fmap fn left) (fmap fn right)
```

```
exampleTree :: Tree1 Int
exampleTree =
Branch1 (Branch1 (Leaf1 5) (Leaf1 6))
(Branch1 (Branch1 (Leaf1 7) (Leaf1 8))
(Leaf1 9))
```

```
ghci> fmap (*2) exampleTree
Branch1 (Branch1 (Leaf1 10) (Leaf1 12))
(Branch1 (Branch1 (Leaf1 14) (Leaf1 16)) (Leaf1 18))
ghci> fmap show exampleTree
Branch1 (Branch1 (Leaf1 "5") (Leaf1 "6"))
(Branch1 (Branch1 (Leaf1 "7") (Leaf1 "8")) (Leaf1 "9"))
ghci> fmap (const "Yow") exampleTree
Branch1 (Branch1 (Leaf1 "Yow") (Leaf1 "Yow"))
(Branch1 (Branch1 (Leaf1 "Yow") (Leaf1 "Yow")) (Leaf1 "Yow"))
```

I’m not using this for anything, but if you compile this with `runghc`

, it requires a `main`

, so here it is.

`main = return ()`