Haskell/Solutions/Higher-order functions and Currying
Choosing how to compare
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
(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
Some more challenging exercises you could try
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
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.
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
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.
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)
mapIO can be implemented in terms of
mapIO :: (a -> IO b) -> [a] -> IO [b] mapIO f xs = sequenceIO (map f xs)
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
uncurry constpasses the elements of a pair to
const, in order. As
constalways returns its first argument,
uncurry constreturns the first element of the pair; in other words, it is
fst, which returns the first element of a pair, into a function of two arguments which returns the first one; therefore,
curry fstis equivalent to
uncurryare inverses (that is, they undo each other;
curry . uncurryamounts to
id), and so if
fstit is evident that
- A third approach is noting that, given the types of
curry fstis an
a -> b -> afunction. The only possible function with this type is
curry fstmust 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
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; y = c; b = y and a = z.
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 right 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
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
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)