The category design pattern

Re:The category design pattern by Tekmo on Sunday November 08, 2015 @09:40AM (#10528576)

The generic benefit of a category is the proof that it satisfies the identity and associativity laws. This lets you write "generic proofs" that work for any category.

For example, take the following example type:

    newtype Example f c a b = Example (f (c a b))

    instance (Applicative f, Category c) => Category (Example f c) where
        id = Example (pure id)

        Example f . Example g = Example (liftA2 (.) f g)

You can prove that if `c` satisfies the `Category` laws and `f` satisfies the `Applicative` laws, then `Example f c` also satisfies the `Category` laws.

This in turn lets you take any `Category` and keep extending it with as many `Applicative`s as you want in any order, confident in the knowledge that your extended `Category` still satisfies the `Category` laws.

This is a common pattern in code that is organized around category theory and/or abstract algebra and I wrote a post showing a simpler example of this phenomenon (using `Monoid` instead of `Category`): http://www.haskellforall.com/2014/07/equational-reasoning-at...

[ Parent | on HN ]

Re:The category design pattern by lmm on Sunday November 08, 2015 @02:22PM (#10529480)

You're just telling me how the abstraction gives rise to more abstractions. That seems to be getting even further away from where the rubber hits the road. I want to see a program that does something directly useful, something there's an actual business case for, that would take more code to implement without the Category abstraction.

[ Parent | on HN ]

Re:The category design pattern by Kutta on Sunday November 08, 2015 @03:44PM (#10529811)

Categories are just an utterly pared-down notion of composability, so most of the time you don't even recognize them in the wild (like the associativity of monads, which on an abstract level says that only the sequence of instructions matters, but not their grouping - it's something that you expect to be true in any imperative language!), or only recognize the absence of categories as horrible design.

If you haven't already, you should play around with the pipes library, because it makes very heavy use of categories and it's an extreme positive example of composability.

As another practical example, Haskell's class constraints form a thin category, with constraint entailment as arrows. This means that instance resolution never depends on ordering of imports, local bindings, or basically anything other than the raw set of available instances, and also any two instances at the same type must be equal. This buys us great scalability and refactorability, most notably in comparison to Scala, where alphabetizing module imports sometimes breaks programs.

That said, in category theory one rarely works with vanilla categories but rather other abstractions formulated in categorical language. Similarly, in Haskell vanilla categories aren't as useful as the many well-known categorical abstractions (basically, the core Functor - Applicative - Monad hierarchy is directly category-theory inspired, and they've proven to be insanely useful).

[ Parent | on HN ]

Re:The category design pattern by lmm on Monday November 09, 2015 @05:22AM (#10532196)

I don't think the class example works, because you wouldn't operate on a class hierarchy in code. Pipes is all well and good but unless I'm implementing it myself I don't need to care about the examples.

If you want to sell this to ordinary programmers you need to take another step down to the concrete level. Show two generic functions that take a category and show how they are useful for two different categories (heck, I think I can think of one myself: it should be easy to write a function that takes a type-aligned list [c a b, c b d, ... c y z] and combines them as a single c a z). If it's a useful abstraction then that really shouldn't be hard.

[ Parent | on HN ]