# Lab Exercise 3 (Higher Order Functions for List Comprehension)

### Lists in Haskell

Before you start implementing the functions in this exercise, you need to understand how lists work in Haskell. Haskell lists are written like a list in math. The Haskell list:

[1,2,3,4,5]

is basically equivalent to the list:
$$
[1,2,3,4,5]
$$
One of the most important things about lists is that you can access the list as a whole and you can access the elements inside the list. One thing you can do is you can concatenate lists using the **`++`** function:

ghci> [1,2,3,4,5] ++ [6,7,8]
[1,2,3,4,5,6,7,8]

You can find the length of the list using the **`length`** function:

ghci> length [1,2,3,4,5]
5

These are the different ways you can access the elements of the list and the sublists in the list:

**`head`** takes a list and returns the first element of the list

ghci> head [1,2,3,4,5]
1

**`tail`** takes a list and returns the same list except the first element of the list

ghci> tail [1,2,3,4,5]
[2,3,4,5]

**`init`** takes a list and returns the same list except the last element of the list

ghci> init [1,2,3,4,5]
[1,2,3,4]

**`last`** takes a list and returns the same list except the last element of the list

ghci> last [1,2,3,4,5]
5

Using these functions you can traverse a list using the head-tail recipe. For example, if you want to add 1 to each of the elements of the array:

addone :: [Int] -> [Int]
addone l = 
  if length l == 0 then []
  else [(head l) + 1] ++ addone (tail l)

Let's dissect this function one by one, for the first line you can see the type signature `[Int]->[Int]` meaning `addone` accepts a list of `Int`s and returns a list of `Int`s. Any type `a` surrounded by brackets is a list of `a`s (`[a]` is a list of `a`'s, `[Char]` is a list of `Chars`, `[[Int]]` is a list of `[Int]`s or a list of list of `Int`s).

In the second line were binding the list we are passing to `l`.

The third line refers to the base case, this happens when the list is empty. When the list is empty we return `[]` which refers to an empty list.

And finally the last line refers to the general case. Here we are see the subexpression `[(head l) + 1]` which is a list containing one element namely, the first element of the list plus 1. And then we are concatenating this one element list to the result of the call `addone (tail l)` which is a recursive call to the rest of add one to the `tail` of l (or the rest of `l`). Assuming `addone` works perfectly, the recursive call `addone (tail l)` will return the tail of the `l` but the elements are added with one. By concatenating `[(head l) + 1]` with the result of this recursive call, we complete the desired result.

- Implement the higher order functions, `my_map`,` my_filter`, and `my_foldl` and `my_foldr`, `my_zip`
- **`my_map :: (a -> b) -> [a] -> [b] `** - The `map` function accepts a function $f$ and a list (with elements of type `A`) $l=[l_1,l_2,l_3,...,l_n]$. It returns the list (with elements of type `B`): $l'=[f(l_1),f(l_2),f(l_3),...,f(l_4)]$. The new list `map` produces is a list which is the image of `l` from the function `f`.
- **`my_filter :: (a -> Bool) -> [a] -> [a] `** - The `filter` function accepts a predicate $f$ and a list $l=[l_1,l_2,l_3,\cdots,l_n]$. `filter` returns a new list $l'$ such that the contents satisfy $f(l_i)$ is true, retaining the order it appears in $l$.
- **`my_foldl :: (a -> a -> a) -> a -> [a] -> a`** - The `foldl` function accepts a function $f$, a list $l=[l_1,l_2,l_3,...,l_n]$ and an initial value $u$. The `foldl` function returns the value $f( f(f(f(u,l_1),l_2),l_3), l_n)$.
- **`my_foldr :: (a -> a -> a) -> a -> [a] -> a`** - The `foldr` function accepts a function $f$, a list $l=[l_1,l_2,l_3,...,l_n]$ and an initial value $u$. The `foldr` function returns the value $f(l_1,f(l_2,f(l_3,f(l_n,u))))$.
- **`my_zip :: (a -> b -> c) -> [a] -> [b] -> [c]`** - THe `zip` function accepts a function $f$ and two lists $l=[l_1,l_2,l_3,...,l_n]$, $m=[m_1,m_2,m_3,...,m_n]$ and returns a new list, $k=[f(l_1,m_1),f(l_2,m_2),f(l_3,m_3),\cdots,f(l_n,m_n)]$
- Without using loops (use the functions above instead), create the following functions.
- Given a list of numbers, return the sum of the squares of the numbers

- Given three lists, a list of first names, A, a list of middle names B, and a list of surnames C. Return a list of whole name strings (list of chars) (`[firstname] [middle initial]. [lastname]`) where the length of the string (including spaces and period) is an even number. Example

    ghci> wholeName ["Foo", "Bar", "Foo"] ["Middle", "Center", "Name"] ["Lastn", "Surname", "Abcd"]
    ["Foo M. Lastn", "Bar C. Surname"]

("Foo S. Abcd" is filtered out because it has 11 characters)