[Haskell-cafe] category design approach for inconvenient concepts

[wren ng thornton]

On 12/17/12 9:45 PM, Christopher Howard wrote:
> 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.

I don't know about this particular case, but often when "it should be 
associative but isn't" problems come up, it helps to rephrase things. 
For example, consider plain old Haskell, but where we make application 
explicit. On the one hand, we can have:

     f $ (g $ x)

and that's fine. But it's not equivalent to:

     (f $ g) $ x

But the problem here isn't that we don't have associativity; the problem 
is that function application isn't the associative operator. The 
associative operator is function composition. Thus, we can rephrase the 
above as:

     f . (g . const x)

Which is indeed equivalent to:

     (f . g) . const x

Note that in order to dispense with ($) entirely, we had to replace "x" 
by "const x" in order to make it a function just like everything else. 
This is akin to the trick we use in category theory to get away from 
talking about "values" or "elements". If your category has a terminal 
object, which I'll call (), then we can represent the "elements" of A by 
morphisms ()->A. By terminality there's no "interesting" structure in 
(), thus, the only information in ()->A is however we're selecting our 
"element" of A.

This is, of course, the same exact thing that happens in vector spaces 
and the like. If I write (*.) for scaling a vector, then we have:

     x *. (y *. a) == (x * y) *. a

which should look suspiciously similar to:

     f $ (g $ x) == (f . g) $ x


But from your description, it sounds like the above may not be the 
source of your problem. The second sort of non-associativity problem 
that's common is when dealing with a function of multiple arguments (or 
similar). That is, there are two separate kinds of "whitespace for 
application" in Haskell. This is easy to see if we switch to the 
Applicative paradigm:

    f <$> x <*> y

Now, for Applicatives this happens because the f above is pure. But we 
also run into it with plain functions--- namely, we can have our 
functions curried or not. We can freely switch between these different 
representations, but we can't get away from the fact that they both 
exist. Thus, there's a sort of inherent difference between the 
juxtaposition of a function and it's (first) argument, vs the 
juxtaposition of multiple arguments. Regardless of whether we view the 
latter as tupling or as subsequent-application, both of those 
perspectives are distinct from the initial-application.

The solution here, I think, is just to recognize what's going on. If you 
need two operators, then you need two operators, and that's fine. With 
the examples above it comes from dealing with a cartesian closed 
category, but there are certainly other structures your operators may be 
examples of.

-- 
Live well,
~wren