[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