[Haskell-cafe] Composition Operator

[Dan Weston]

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