Understanding Function Composition

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 fWhat 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

- x :: s given
- f :: a -> b given
- (g f) is a function whose input is x so, (g f) :: s -> t
- since (g f) is a function, g is a function with 2 inputs
- 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:

*You think dogs will not be
in heaven? I tell you, they will be there long before any of
us.*

**Robert Louis Stevenson**

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