Haskell/Solutions/Higher-order functions

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.

Implement the for loop in Haskell.
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

Consider a task like "print the list of numbers from 1 to 10". Given that print is a function, and we want to apply it to a list of numbers, using map sounds like the natural thing to do. But would it actually work?
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.
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.

Or using foldr:

sequenceIO :: [IO a] -> IO [a]
sequenceIO = foldr (\a seqio -> do v  <- a
                                   vs <- seqio
                                   return (v:vs))
                   (return [])

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)

Or point-free:

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

Function manipulation

Exercises

Write implementations for curry, uncurry and const.
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.)
(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 flips 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)