Function Composition: The Case of Multiple Parameters

Posted on 2014-11-10 by fp
Send us your comments.

Function composition is somewhat like magic, if you stumble from the imperative world into the point-free style fashioned so much in the Haskell world. And most astonishing, the pinacle of it all the .-operator looks completely innocent in its implementation: (.) f g x = f (g x). Composition of two functions is exactly as we learned in school, the application of the first function onto the result of the second function.

What could be more easy? Try your luck with some functions on the haskellwiki page on point free style and then come tell me, why the type of (+).(+) is a-> (a->a) -> a -> a and why y z -> f (g x y z) is the same as ((f.).).g? It turns out, it is actually quite simple, once you wrap your head around it.

My way of wrapping and towards something resembling enlightenment finally came to the point where I simply expanded the equation of the function composition of two numeric addition operations as follows:

((+).).(+) = (.) ((+).) (+)
           = (\x -> ((+).) ((+) x))
           = (\x -> (.) (+) ((+) x))
           = (\x -> (\y -> (+) (x + y)))
           = (\x y z -> (x + y) + z)

Let us do this in stop motion. The definition of function composition was simply the sequential application of functions (.) f g x. Exkbdssing this in lambda notation we derive the partial application of the second function, namely (+) onto a variable x which is then feed to the first function, namely ((+).). The strong operator kbdcedence of (.) lets us rewrite this to (.) (+) which we then know how to evaluate: apply the second function to the variable, which we named y and feed this to the first function, which is now only (+). This leaves us with something that takes two parameters, namely x and y and maps onto a partially applied (+)-operation of type Num a => a -> a. Thus we can rewrite the whole function as a function taking three parameters.

Having established this, I am not yet sure I understand how the typesystem establishes this from

(.):: (b->c) -> (a->b) -> a -> c
.

END—–