Of course I should have proofread this one more time!

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:

Actually, a point is any one object, for Hask* it is any one monotype (e.g. (), [Int], (Char,Double)). The magic of an *initial* object (i.e. a type with only one nullary constructor such as () that has only one (defined) value) is that there is a *unique* function mapping it to any other type. But that's being greedy, since we don't need a unique function, just any one function. A forgetful function like const doesn't care which type its second argument is. Sorry for the muddle. Dan Weston Dan Weston wrote:

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 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 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Well, I did footnote in my first e-mail that: [1] I used the asterisk in the category name Hask* to exclude undefined values or partial functions [Although I think I may have flipped the asterisk convention.] I see what you mean by const False and const True being two different arrows, but now I don't know how that reconciles with the Wikipedia Example 3 of http://en.wikipedia.org/wiki/Initial_object "In the category of pointed sets (whose objects are non-empty sets together with a distinguished element; a morphism from (A,a) to (B,b) being a function f : A ? B with f(a) = b), every singleton is a zero object [i.e. both initial and final]." I thought I was being safe by "distinguishing" () as my distinguished element. Where did I go wrong? Dan Weston Stefan O'Rear wrote:

On Mon, Sep 24, 2007 at 06:47:05PM -0700, Dan Weston wrote:

...

Of course I should have proofread this one more time!

...

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: Actually, a point is any one object, for Hask* it is any one monotype (e.g. (), [Int], (Char,Double)). The magic of an *initial* object (i.e. a type with only one nullary constructor such as () that has only one (defined) value) is that there is a *unique* function mapping it to any other type. But that's being greedy, since we don't need a unique function, just any one function. A forgetful function like const doesn't care which type its second argument is.

() isn't an initial object.

There are no initial objects in Hask-with-?, since every object admits at least four arrows to Bool (const True, const False, const undefined, and undefined).

Stefan

On Mon, 2007-09-24 at 19:11 -0700, Dan Weston wrote:

Well, I did footnote in my first e-mail that:

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

[Although I think I may have flipped the asterisk convention.]

I see what you mean by const False and const True being two different arrows, but now I don't know how that reconciles with the Wikipedia Example 3 of http://en.wikipedia.org/wiki/Initial_object

"In the category of pointed sets (whose objects are non-empty sets together with a distinguished element; a morphism from (A,a) to (B,b) being a function f : A ? B with f(a) = b), every singleton is a zero object [i.e. both initial and final]."

I thought I was being safe by "distinguishing" () as my distinguished element. Where did I go wrong?

() is terminal, not initial. There exists a unique function to it (ignoring bottoms) from anything, namely, const (). A "point" of A categorically, is just a function from the terminal object to A, () -> A. For the notion of "pointed" that you want, the important thing is that f = g :: A -> B iff for all k :: () -> A, f . k = g . k. I.e. a function is completely determined by its action on points.