[Haskell-cafe] Composition Operator

Dan Weston westondan at imageworks.com
Mon Sep 24 20:37:39 EDT 2007


Now you've triggered an addict attack. Remember how Haskell is a gateway 
drug?

Composition (.) may not be an "abstract" function, but it is very 
fundamental one (so be wary of redefining the (.) operator in Haskell!). 
Only the identity function id is more fundamental. [And actually, these 
are polymorphic functions that each name an entire class of functions, 
one for each type of their arguments.]

Together these obey the following very important laws:

id . f     =  f
f  . id    =  f
f  . g . h = (f .  g) . h
            =  f . (g  . h)

If every Haskell type is an "object", and each (strict) function is an 
"arrow" that maps its domain (the type before the first top-level -> in 
the type signature) to its codomain (everything after that first 
top-level -> in the type signature), and from the above laws we see that 
function composition (.) is associative, then these "objects" and 
"arrows" form a category Hask* [1].

Anyway, the above says that how the composition operator transforms 
*types*. The following says how the composed function transforms *values*:

For any x of the appropriate type,

id    $ x = x
f . g $ x = f (g x)

Where did this definition of function composition come from (besides 
matching our intuition)?

Not all categories are pointed, but our Haskell one is. This is the link 
between point-free (stuff before the $) and pointed (including the $ x) 
notation: if you know how each function acts on each value of its 
respective domain, then you know how the composite function acts on 
values in its domain.

What is a point? A point in Hask* is a type with only a single value in 
it, from which all other values can be constructed. Every value x maps 
trivially into a function (const x), and when you apply this function to 
  the (only) value of a point, you get x back. There is a built-in 
Haskell type () whose only value [besides undefined] is also called (), 
so we might as well take the type () as our point:

id      . const x $ () = const x           $ ()
(f . g) . const x $ () = f . (g . const x) $ ()
                        = f .  g . const x  $ ()

But these laws come directly from the definition of a category (identity 
+ associativity), so we see for a pointed category like Hask, 
composition has to be defined the way it is to be worthy of the name!

The above formulation with $ () is the true pointed notation, but since 
flip const () = id, we can trivially apply the (const x) to our point () 
and get back x, so both left and right below are said to be in pointed 
notation:

f . const x $ () = f $ x = f x

Since x is a free variable (any definition of f and g can't guess what x 
will be chosen), we can drop the x as well, resulting in point-free 
notation:

forall x . f x = g x   <==>   f = g.

This defines equality of functions, but there is no generally computable 
way of deciding, given f and g, whether they are equal, without applying 
them both to every possible value of the domain.

Anyway, I think the question you were originally asking is, how do you 
interpret the type signature of (.), or more generally what is the 
domain and codomain of a Haskell function. The algorithm is easy: count 
over to the first arrow (->) that is not inside any parentheses. 
Everything to the left is the domain, everything to the right is the 
codomain:

(.) :: (b -> c)  ->  (a -> b) -> (a -> c)
         domain   |       codomain

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

f . g = (.) f = ((.) f) g :: (a -> c)

Each application of a function to its first argument (whose type is the 
domain) results in a value in the codomain.

You can't go wrong if you stick to the interpretation that every 
function takes at most one argument (it may of course take no 
arguments!) Then you just partially apply each (leftmost) argument to 
peel off the domain, until you are left with no more arguments.

I hope all of the above gave off more light than heat. There is a lot 
more to say about function composition, e.g. it is a monoid operation 
when applied to functions in a single type (a -> a). But this e-mail's 
long enough, and you've probably already stopped reading :) , so I'll 
stop here as well.

Dan Weston

[1] I used the asterisk in the category name Hask* to exclude undefined 
values or partial functions

PR Stanley wrote:
> Ah, I understand now. Let me get this right:
> The resulting (a -> c) is a kind of abstract function formed by the 
> pairing of <a -> b) and (b -> c), hence the lambda \x -> g (f x), correct?
> Thanks, Paul
> 
> At 05:11 22/09/2007, you wrote:
>> Hello,
>>
>> It's probably easiest to think of composition as a function which
>> takes two arguments (both functions), (g :: b -> c) and (f :: a -> b),
>> and returns a new function of type a -> c. We could write this
>> explicitly as
>>
>>     composition :: (b -> c, a -> b) -> a -> c
>>     composition (g,f) = \x -> g (f x)
>>
>> then (.) is the currying of composition:
>>
>>     (.) = curry composition
>>
>> or
>>
>>     (.) g f = \x -> g (f x)
>>
>> -Jeff
>>
>>
>> On 9/21/07, PR Stanley <prstanley at ntlworld.com> wrote:
>> > Hi
>> > (.) :: (b -> c) -> (a -> b) -> (a -> c)
>> > While I understand the purpose and the semantics of the (.) operator
>> > I'm not sure about the above definition.
>> > Is the definition interpreted sequentially - (.) is a fun taht takes
>> > a fun of type (b -> c) and returns another fun of type (a -> b) etc?
>> > Any ideas?
>> > Thanks, Paul
>> >
>> > _______________________________________________
>> > Haskell-Cafe mailing list
>> > Haskell-Cafe at haskell.org
>> > http://www.haskell.org/mailman/listinfo/haskell-cafe
>> >
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
> 




More information about the Haskell-Cafe mailing list