Choosing how to compare
editExercises |
---|
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
editExercises |
---|
(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
|
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
editExercises |
---|
|
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 toconst
, in order. Asconst
always returns its first argument,uncurry const
returns the first element of the pair; in other words, it isfst
in disguise.curry fst
convertsfst
, which returns the first element of a pair, into a function of two arguments which returns the first one; therefore,curry fst
is equivalent toconst
.- Alternatively,
curry
anduncurry
are inverses (that is, they undo each other;curry . uncurry
amounts toid
), and so ifuncurry const
isfst
it is evident thatcurry fst
isconst
. - A third approach is noting that, given the types of
curry
andfst
type ofcurry fst
is ana -> b -> a
function. The only possible function with this type isconst
; therefore,curry fst
must be equivalent to it.
- Alternatively,
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 toflip (,)
.
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)