This entry will try to describe a little haskell gem I learned while reading the getOpt docs for the next part in the series.
In one of the example usages of getOpt was this innocent looking expression: foldl (flip id) v fs. The types are v :: A and fs :: [A -> A] for some type A (in the getOpt example A was some type about options). This expression applies the functions in fs one by one starting with the first one and using the accumulator of foldl as the argument to the functions. The output of one function is the input to the next. It's a processing pipeline that send the initial value v through the first function in fs, the result of that to the next function in fs and so on.
I got that quickly. What baffled me was the fact that haskell didn't complain about feeding id to flip. Because looking with ghci at types we have:
Prelude> :t flip flip :: (a -> b -> c) -> b -> a -> c Prelude> :t id id :: a -> a
This shows that flip's first argument is a binary function and id is a unary function. Of course in haskell all functions are unary through currying, so the nice folks on the #haskell irc.freenode.net channel clued me in on how this works in this case and how this expression is typed correctly. (btw, the #haskell channel is highly recommended, the coolest, most patient experts hang out there, answering anything beginners like me throw at them).
The expression flip id is valid if the types of id and a -> b -> c can be unified. What I missed is that they easily can.
a -> b -> c is a -> (b -> c). If we feed (b -> c) to id it will return (b -> c). So in this case id :: (b -> c) -> (b -> c). The a from a -> (b -> c) can be anything, so it can be (b -> c) also. Done, expression has valid type.
Let's also look why the expression foldl (flip id) v fs does what we claimed it does, namely send v through the list of functions fs, applying the next function to the result of the previous.
If we wanted to implement this behavior ourselves, we would recognize quickly that foldl is what we want because it eats through the list from left to right. In our case the list is a list of functions and the accumulator in foldl is the argument we want to give to the functions on each application. The complication comes from the fact that the accumulator in foldl is on the left, so it's the first argument. Therefore we cannot directly combine it with functions in fs expecting function application. We have to reverse (flip) the arguments first.
We could therefore write something like this expression: foldl (\x f -> f x) v fs.
Looking closer at the lambda expression there, it takes the value as first parameter and then the function that we want to apply to the value (this is the order in which foldl gives it to us). The lambda expression flips it and does the application. Aha, flips it. Maybe we can use flip. But flip alone won't do it (foldl flip v fs doesn't even have valid type). Well, flip takes 3 arguments, the first of which is a function. Function application is left-associative. So this first argument is a function that will end up being applied to the function f that comes out of fs. The result of that will be applied to the accumulator. In the end we want f applied to the accumulator. Which function when applied to f will return f again, id of course.
Voila, we have foldl (\x f -> f x) v fs be the same as foldl (flip id) v fs.
Leave a comment