[Haskell-cafe] category design approach for inconvenient concepts

[Ertugrul Söylemez]

Christopher Howard <christopher.howard at frigidcode.com> wrote:

> Say you created a type called "Component" (C for short), the idea
> being to compose Components out of other Components. Every C has zero
> or more connectors on it. Two Cs can be connected to form a new C
> using some kind of composition operator (say, <.>), provided there are
> enough connectors (one on each). Presumably you would need a "Fail"
> constructor of some kind to represent the situation when there is not
> enough connectors.
>
> Say you had a C (coupler) with two connectors, a C (thing) with one
> connector, and a C (gadget) with one connector.
>
> So you could have...
>
> (coupler <.> thing) <.> gadget
>
> Because the coupler and the thing would combine to create a component
> with one spare connector. This would then combine with the gadget to
> make the final component. However, if you did...
>
> coupler <.> (thing <.> gadget)
>
> Then thing and gadget combine to make a component with no spare
> connectors. And so the new component and the coupler then fail to
> combine. Associativity law broken.
>
> So, can I adjust my idea to fit the "category" concept? Or is it just
> not applicable here? Or am I just misunderstanding the whole concept?

You are not misunderstanding the concept.  You just need to learn how to
apply it in this situation.  Pluggable components with multiple slots
are still modelled by regular categories.  Let's say that Comp is such a
component category (I'm using Haskell syntax):

    Comp :: * -> * -> *

To model a component that takes two inputs you just write a component
that takes one (!) tuple of inputs:

    myComp :: Comp (X, Y) Z

For partial application of your component you need a bit more than the
basic category pattern.  Most categories form a family of applicative
functors:

    instance Applicative (Comp a)

Then partial application is really just this:

    partialMyComp :: X -> Comp Y Z
    partialMyComp x = myComp . fmap (\y -> (x, y)) id

Every category that forms such a family of applicative functors is a
profunctor (see the 'profunctors' package by Edward Kmett):

    instance Profunctor Comp

That makes expressing partialMyComp slightly more pleasing:

    partialMyComp x = lmap (\y -> (x, y)) myComp

Finally to save even more keystrokes enable the TupleSections extension:

    partialMyComp x = lmap (x,) myComp

You can get similar description through the Arrow interface:

    instance Arrow Comp

    partialMyComp x = myComp . arr (x,)

However, often the applicative interface is much more pleasing.

Now to the theory:  What does an applicative functor give you?  It
basically extends a categorical concept by the ability to combine
multiple morphisms to a single one.  Given two morphisms,

    c1 :: Comp A B
    c2 :: Comp A C

and a function

    f :: B -> C -> D

an applicative functor gives you a well-defined way to combine c1 and c2
into another morphism of type

    c3 :: Comp A D

An applicative functor provides about the same theoretical soundness as
a category in that such a combination of multiple Comp morphisms is
itself always a Comp morphism, and that the combination operator itself
cannot introduce unwanted effects because of the Applicative laws:

    pure f <*> x = fmap f x
    f <*> pure x = fmap ($ x) f

    pure f <*> pure x = pure (f x)

In other words, all effects are introduced by primitive components.  I
call them "atoms".


Greets,
Ertugrul

-- 
Not to be or to be and (not to be or to be and (not to be or to be and
(not to be or to be and ... that is the list monad.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20121218/720db149/attachment.pgp>