Henry Laxen July 10, 2011

Since I was a math major in college, I alway thought that I understood function composition, but apparently I was wrong. I've spent the past few days trying to wrap my head around continuation passing style and the continuation monad, and decided I'd better start with function composition, which I thought was pretty easy. So, I decided to try a few examples.

> f :: a -> b
> f = undefined
> -- :t f :: a -> b
> -- :t (.) :: (b -> c) -> (a -> b) -> a -> c
> f1a g   = g . f
> f1b     = \g -> g . f
> f1c g x = g (f x)
> -- :t f1a :: (b -> c) -> a -> c

So, the f1 family, which are all equivalent, are functions that take two arguments. The first argument is a function, the second, an arbitrary type. Let's walk through the definition of f1c:

f1c g x = g (f x)
Say x is of type a, then f x is of type b. Thus g is a function, that takes a type b as input, and produces a (possibly) different type c. Thus g :: (b -> c). So f1c's first argument is of type (b -> c), it's second argument is of type a, so f1c's type signature is (b -> c) -> a -> ?. Can "?" be anything? Well no, because "?" is the result of applying g to something, and we know that g returns a c, so "?" must be c. Thus the final type signature of f1c is (b -> c) -> a -> c

Great! We understand function composition. Let's look at another example. 
> f2a g   = g f
> f2b g x = g f x
> f2c g x = g (f x)
> f2d g x = (g f) x
> f2e     = \g -> g f
What do you suppose the types of the f2's are? An even more basic question is how many arguments does each f2 have? Let's ask ghci: 
> -- f2a :: ((a -> b) -> t) -> t
> -- f2b :: ((a -> b) -> t1 -> t) -> t1 -> t
> -- f2c :: (b -> t) -> a -> t
> -- f2d :: ((a -> b) -> t1 -> t) -> t1 -> t
> -- f2e :: ((a -> b) -> t) -> t

If none of those type signatures surprise you, feel free to skip the rest of this article. For me, most of them came as quite a surprise. Let's get rid of a few that aren't surprising. First, f2c is our old friend, f1c, which is just regular function composition. Second, f2a and f2e should be the same, since f2 g = whatever is the same as f2 = \g -> whatever. Finally, f2b and f2d should be the same, since functions associate from the left. That leaves us with f2a and f2b to understand.

Now would be a good time to remember some basic truths in Haskell, and in fact in mathematics. All functions take one argument. Even a function like our venerable addition, namely "+" takes one argument, it just that when it takes one argument it returns a function. Let's remember another thing too. If g is a function, and if we can figure out the type of the input to g, say a, then the most general thing g can do is take the a to a b, ie (a -> b). Thus if we know the input to g is an Integer, we can write the type of g as (Integer -> b).

Perhaps this should be obvious, but when I first looked at the type of f2a, it wasn't for me. Now keeping this in mind, let's work out the type of f2a. f2a is a function, hence it's most general type is (a -> b). Do we know anything about a? Yes, it is an f. f has type a -> b, so now we are setting ourselves up to get confused. Let's keep the type of f as a -> b, and rewrite the type of f2a as c -> d, which is the same as a -> b except wearing different clothes. So f2a has type c -> d and we know that c is a function. Why? Because in the definition of f2a we see g being applied to f. Thus g is a function, and c, which is the type of g, must be a function. Let's call that type s -> t. Okay, let's regroup. We have f2a :: c -> d, we have g :: s -> t, and we have f :: a -> b. Now what is the input to g? Well, it is f, which as type a -> b (think Integer or String). Thus c (the input to f2a) has type s -> t (the type of g) and s (the input of g) has type a -> b so the input to f2a has type (a -> b) -> t. Great, that's progress, so the type of f2a is now:

f2a g = g f
((a -> b) -> t) -> d
Input to f2a = g output of f2a

Can we say more? Well, yes we can. g is a function whose result is a t. g (of something) is also the result of f2a, ie the final function, so the output of f2a must be the same as the output of g. But the output of g is a t, so the output of f2a is also a t. Thus the final type signature of f2a is ((a -> b) -> t) -> t

Who knew it could be so complicated? Let's do the same thing now for f2d, which is defined as f2d g x = (g f) x which is the same as g f x. At first glance, I expected f2d to be the same as f2a g = g f because of currying. How many times have I defined a function of x, and then rewritten it in point free style, which usually involves dropping the last argument (x) from both sides of the equation. Well, here you can't do that. While f2a has one argument, clearly f2d has at least two. Let's say x has type s. g is a function as is (g f).

f2d g x = (g f) x

  1. x :: s given
  2. f :: a -> b given
  3. (g f) is a function whose input is x so, (g f) :: s -> t
  4. since (g f) is a function, g is a function with 2 inputs
  5. thus g :: (a -> b) -> s -> t since (g f) :: s -> t and f :: a -> b
thus f2d :: ((a -> b) -> s -> t) -> s -> t
thus f2d :: type of g x result

Okay, I guess that's all for now about function composition. I hope you found it educational.

This file is also available as an lhs file if you want to play with it.

Quote of the day:
No man can be condemned for owning a dog. As long as he has a dog, he has a friend; and the poorer he gets, the better friend he has.
Will Rogers

Sitemap
Go up to Haskell Go up to Home Page of Nadine Loves Henry
Go back to Cheat Sheet for JinJings MPS Stuff Continue with A look at Heist, MVars and Anansi