[Haskell-cafe] Composition Operator
Dan Weston
westondan at imageworks.com
Mon Sep 24 21:47:05 EDT 2007
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
>>
>>
>
>
More information about the Haskell-Cafe
mailing list