The interesting type of `foldl (flip id)`

System.Console.GetOpt

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.)

Let's attack the type of `id`

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

Substituting the type into `flip`

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.

Substituting the type into `foldl`

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

That's great, but what does it do?

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.

Contact

Dino Morelli [email protected]

Many thanks to Betty Diegel for helping me to understand type unification.

dino-/haskell-flip-id.md

The interesting type of foldl (flip id)