## Choosing how to compare

Exercises
Write `insensitive`, such that `quickSort insensitive dictionary` gives `["a", "for", "have", "I", "Linux", "thing"]`
```import Data.Char (toUpper)
insensitive string1 string2 = compare (map toUpper string1) (map toUpper string2)
```

Instead of comparing the two strings directly, we compare the all uppercase version. The order of the original two strings is then based on the order of the uppercase versions.

## Higher-Order Functions and Types

Exercises

(Challenging) The following exercise combines what you have learned about higher order functions, recursion and I/O. We are going to recreate what is known in imperative languages as a for loop. Implement a function

```for :: a -> (a -> Bool) -> (a -> a) -> (a -> IO ()) -> IO ()
for i p f job = -- ???```

An example of how this function would be used might be

`for 1 (<10) (+1) print`

which prints the numbers 1 to 9 on the screen.

The desired behaviour of `for` is: starting from an initial value `i`, `for` first checks `p i`, if it evaluates to true it then executes `job i`, else it stops and does nothing. if `job i` was executed, it then uses `f` to modify this value and checks to see if the modified value `f i` satisfies some condition `p`. If it doesn't, it stops; otherwise, the for loop continues, using the modified `f i` in place of `i`.

1. Implement the for loop in Haskell.
2. The paragraph just above gives an imperative description of the for loop. Describe your implementation in more functional terms.

Some more challenging exercises you could try

1. Consider a task like "print the list of numbers from 1 to 10". Given that `print` is a function, and we an to apply it to a list of numbers, using `map` sounds like the natural thing to do. But would it actually work?
2. Implement a function `sequenceIO :: [IO a] -> IO [a]`. Given a list of actions, this function runs each of the actions in order and returns all their results as a list.
3. Implement a function `mapIO :: (a -> IO b) -> [a] -> IO [b]` which given a function of type `a -> IO b` and a list of type `[a]`, runs that action on each item in the list, and returns the results.
This exercise was inspired from a blog post by osfameron. No peeking!

Part 1:

1. A for loop in Haskell:

```for :: a -> (a -> Bool) -> (a -> a) -> (a -> IO ()) -> IO ()
for i p f job =
if p i
then do
job i
for (f i) p f job
else return ()
```
```*Main> for 0 (<3) (+1) (print)
0
1
2

```

2. `for i p f job` is an `IO` action built recursively. At the beginning of each recursive step, the boolean `p i` is checked. The base case, reached when `p i` is `False`, the result is the do-nothing action, `return ()`. In the recursive case, the result is an action consisting of `job i` followed by `for` called with `f i` instead of `i` and with the same function arguments as before.

Part 2:

1. The naïve solution, `map print [1..10]`, would not work. The type of `map print [1..10]` is `[IO String]`, a list of actions. There is nothing wrong with that per se, as actions are Haskell values like any others. However, a list of actions is not an action, and so it cannot e.g. be put in an `IO` do-block and executed through `main`.

2.

```sequenceIO :: [IO a] -> IO [a]
sequenceIO [] = return []
sequenceIO (a:as) = do
v <- a              -- runs the first action; binds the result to v.
vs <- sequenceIO as -- recursive call; binds the other results to vs.
return (v : vs)     -- returns all results.
```

3.

```mapIO :: (a -> IO b) -> [a] -> IO [b]
mapIO f [] = return []
mapIO f (x:xs) = do
y <- f x
ys <- mapIO f xs
return (y : ys)
```

Alternatively, `mapIO` can be implemented in terms of `sequenceIO`:

```mapIO :: (a -> IO b) -> [a] -> IO [b]
mapIO f xs = sequenceIO (map f xs)
```

## Function manipulation

Exercises
1. Write implementations for `curry`, `uncurry` and `const`.
2. Describe what the following functions do without testing them:
• `uncurry const`
• `curry fst`
• `curry swap`, where `swap :: (a, b) -> (b, a)` swaps the elements of a pair. (`swap` can be found in `Data.Tuple`.)
3. (Very hard) Use `foldr` to implement `foldl`. Hint: begin by reviewing the sections about `foldr` and `foldl` in Lists III. There are two solutions; one is relatively boring and the other is truly interesting. For the interesting one, think carefully about how you would go about composing all functions in a list.

1.

```myUncurry :: (a -> b -> c) -> (a, b) -> c
myUncurry f (x, y) = f x y

myCurry :: ((a, b) -> c) -> a -> b -> c
myCurry f x y = f (x, y)

myConst :: a -> b -> a
myConst x _ = x
```

A stylistic alternative is using lambdas to emphasise that a function is being returned. If you ever get confused while trying to implement a function-returning function, doing that might make it easier to see what the implementation should be.

```myUncurry :: (a -> b -> c) -> ((a, b) -> c)
myUncurry f = \(x, y) -> f x y

myCurry :: ((a, b) -> c) -> (a -> b -> c)
myCurry f = \x y -> f (x, y)

myConst :: a -> (b -> a)
myConst x = \_ -> x
```

2.

• `uncurry const` passes the elements of a pair to `const`, in order. As `const` always returns its first argument, `uncurry const` returns the first element of the pair; in other words, it is `fst` in disguise.
• `curry fst` converts `fst`, which returns the first element of a pair, into a function of two arguments which returns the first one; therefore, `curry fst` is equivalent to `const`.
Alternatively, `curry` and `uncurry` are inverses (that is, they undo each other; `curry . uncurry` amounts to `id`), and so if `uncurry const` is `fst` it is evident that `curry fst` is `const`.
A third approach is noting that, given the types of `curry` and `fst` type of `curry fst` is an `a -> b -> a` function. The only possible function with this type is `const`; therefore, `curry fst` must be equivalent to it.
• `swap`, given a pair, produces a pair with swapped elements. `curry swap`, therefore, takes two arguments and pair them in swapped order; it is equivalent to `flip (,)`.

All of the above answers can be rigorously checked by expanding and substituting definitions. Here is how it is done in the first case; we suggest you try it with the other two.

```-- For the sake of mind-numbing explicitness, we will expand all
-- definitions as functions of a single argument, using nested lambdas.
uncurry const
(\f -> \(x, y) -> f x y) const -- Definition of uncurry.
\(x, y) -> const x y           -- Applying to const.
\(x, y) -> (\x -> \_ -> x) x y -- Definition of const.
\(x, y) -> (\_ -> x) y         -- Applying to x.
\(x, y) -> x                   -- Applying to y.
```

3. What follows is a meticulous step-by-step explanation. If you are here because you gave up the exercise, you might still enjoy skipping to the end and trying to understand what the implementation is doing before returning and seeing how it was built.

There are two key insights needed to pull off this trick. The first one is remembering that a left fold

```foldl f acc xs
-- To make things easier to see, we will make xs = [a, b, c]
-- wherever we need a concrete example.
foldl f acc [a, b, c]
```

can be expanded as

```f (f (f acc a) b) c
```

and then realising that if we flip `f` and swap its arguments everywhere

```flip f c (flip f b (flip f a acc)))
```

we get an expression that associates to the right, just like a right fold!

```foldr g acc [x, y, z]
-- can be expanded as
g x (g y (g z acc)))
-- Now make g = flip f; x = c; y = b and z = a.
```

The only problem is that the list elements in our right-associative expression are in the wrong order. The obvious way of fixing that is reversing the input list. That leads us to the first solution:

```boringFoldl :: (b -> a -> b) -> b -> [a] -> b
boringFoldl f acc = foldr (flip f) acc . reverse
```

Reversing the list, however, is rather inelegant and takes time proportional to the length of the list. At this point, the second insight comes into play. By looking at the expression with the nested `flip f` and squinting a little

```flip f c (flip f b (flip f a acc)))
```

we can see we are actually taking `acc` and applying several functions in sequence to it. We can make that transparent by rewriting the expression using `(.)`.

```flip f c . flip f b . flip f a \$ acc
```

If we switch the `(.)` to prefix notation

```(.) (flip f c) ((.) (flip f b) (flip f a)) \$ acc
```

it becomes clear that the function at the left of `\$` can be written as a fold with `(.)`:

```foldr (.) id [flip f c, flip f b, flip f a] \$ acc
```

Another way of thinking about this step is recovering the intuition that `foldr` takes a list and replaces `(:)` with the binary operator and `[]` with the initial accumulator. In our case, `id`, the do-nothing dummy function, is used as the initial accumulator. Next, we factor out the repeated `flip f` using `map`:

```foldr (.) id (map (flip f) [c, b, a]) \$ acc
```

Here we meet the same problem: the list elements are not in the order we would like them to be. The reversal is consistent with the fact that functions composed with `(.)` are applied from right to left. However, this time we can, instead of reversing the list, simply flip `(.)`:

```foldr (flip (.)) id (map (flip f) [a, b, c]) \$ acc
```

Merely flipping the fold operator is not enough to turn `foldr` into `foldl` because in the general case the operator arguments have different types, and so flipping causes a mismatch. Folding a list with `(.)`, however, can only work if the list elements are `a -> a` functions, and `a -> a` functions can be composed in both directions.

By abstracting from the concrete example we get the second solution:

```coolFoldl :: (b -> a -> b) -> b -> [a] -> b
coolFoldl f acc xs = foldr (flip (.)) id (map (flip f) xs) acc
```

If you find this final expression hard to grasp, making it more pointful by removing the `flip`s may help:

```coolFoldl :: (b -> a -> b) -> b -> [a] -> b
coolFoldl f acc xs = foldr (\g h -> h . g) id (map step xs) acc
where
step x = \acc -> f acc x
```

Alternatively, we could make it even more pointfree, though that would be rather excessive.

```coolFoldl :: (b -> a -> b) -> b -> [a] -> b
coolFoldl f acc = (\$ acc) . foldr (flip (.)) id . map (flip f)
```