Re: [Haskell-cafe] Composition Operator

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