Going through the example code for System.Console.GetOpt got me thinking about the type of foldl (flip id)
Specifically, the second example Interpreting flags as transformations of an options record. The code is using this to combine all of the command-line args into a record of the args as a whole.
I was confused about how foldl (flip id) has the type it does
and how it works. The rest of this document goes over that in detail.
First, the types of the functions involved, using type variable names that don't collide for clarity:
id :: (a -> a)
flip :: (b -> c -> d) -> c -> b -> d
foldl :: (e -> f -> e) -> e -> [f] -> e
(For a while now foldl has been generalized for Foldable,
but let's pretend it's all about lists for this exercise.)
There's a problem right away. flip's first argument must be an
at least two-arg function. If we pass id here it doesn't have
enough arguments to flip. What gives?
We need id's type to change. In other words, we need (a -> a)
to unify with (b -> c -> d)
a needs to equal b but a also needs to equal (c -> d)
That means b must also be equal to (c -> d), which is a valid
type for id if it's applied to a function. These are the same
thing:
id :: a -> a
id :: (c -> d) -> c -> d
Plug in id's new type above (with c's and d's) as flip's first
argument. Now it has enough arguments so that they can be flipped
around.
flip :: ((c -> d) -> c -> d) -> c -> (c -> d) -> d
flip id :: c -> (c -> d) -> d
Note that this type is flipped function application.
Prelude> :t ($)
($) :: (a -> b) -> a -> b
That's no accident, but let's move on.
Notice, from earlier, that the fold function passed to foldl
must have type (e -> f -> e), the first argument and the result
types must be the same. Bearing that in mind, it's valid to say that
(flip id)'s type could consist of the same types everywhere:
flip id :: c -> (c -> c) -> c
Let's plug this latest type for (flip id) into foldl
foldl :: (c -> (c -> c) -> c) -> c -> [(c -> c)] -> c
foldl (flip id) :: c -> [(c -> c)] -> c
And this is almost exactly what GHCi reports as its type:
Prelude> :t foldl (flip id)
foldl (flip id) :: Foldable t => b -> t (b -> b) -> b
Simplifying this so that the t is specificlly lists, it's the same type:
foldl (flip id) :: c -> [c -> c] -> c
The second argument to foldl (flip id) is a list of
functions. Suppose we pass it some starting value x and a small
list of functions. "Unrolling" the function applications the fold
is doing looks like:
foldl (flip id) x [f,g,h] == h (g (f x))
f is applied to x and then g is applied to the result of that and
so on. The result of the last function is the final result. This
function application is the flipped function application noted above.
What you have is a neat, one-line, pure state transformer where
x above is the starting state and the whole sequence of functions
is applied in order. Each function in the list has a "crack"
at the result of the prior function and the end result is the
combined modifications.
For example, perform some math:
Prelude> foldl (flip id) 1 [(+ 2), (* 4)]
12
And in the case of the GetOpt example code, it's being used to
combine all of the args together into one data structure, preserving
the intermediate ones along the way.
Dino Morelli dino@ui3.info
Many thanks to Betty Diegel for helping me to understand type unification.