Notes on the category design pattern

Functional programming \(\subset\) “Compositional programming”

Category theory provides laws that present a rigorous criteria for what “compositional” really means.

Category Theory: A different introduction (composition is the most important piece we care about)

For all Categories, there must exist a composition operator \(\circ\).

Category laws:

• Associative law: \((f \circ g) \circ h = h \circ (g \circ h)\)
• Left identity: \(1 \circ f = f\)
• Right identity: \(f \circ 1 = 1\)

Try to formulate abstractions in this way whenever possible, because it leads to intuitive, easy-to-use, edge-case-free behavior.

Haskell functions form a category:

\[1 = id \\ \circ = (.)\]

Can easily prove the category laws through their definitions.

The Kleisli category

return :: Monad m => a -> m a
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c

\[ 1 = return \\ \circ = (<=<) \]

It’s pretty clear how these relate to normal functions; note that the implementation for <=< is this, which looks an awful lot like the implementation for .:

(f <=< g) x = f =<< (g x)

The category laws for the Kleisli category can be derived the same as the Monad laws and vice versa; they’re the same.

An interesting tidbit:

spawn      ::  IO a  -> IO (IO a)
mapM spawn :: [IO a] -> IO [IO a]
sequence   :: [IO a] -> IO    [a]

concurrentSequence :: [IO a] -> IO [a]
concurrentSequence = sequence <=< mapM spawn

The category of Pipes

\[ 1 = cat \\ \circ = (<-<) \]

data Pipe a b r
  = Pure r
  | Await (a -> Pipe a b r)
  | Yield b (Pipe a b r)

(<-<) :: Pipe b c r -> Pipe a b r -> Pipe a c r
Pure    r  <-< _          = Pure r
Yield b p1 <-< p2         = Yield b (p1 <-< p2)
Await   f  <-< Yield b p2 = f b <-< p2
p1         <-< Await   f  = Await $ \a -> p1 <-< f a
_          <-< Pure    r  = Pure r

cat   :: Pipe a a r
cat = Await $ \a -> Yield a cat

Category laws (Prove as an exercise):

cat <-< p = p                           -- Right identity
p <-< cat = p                           -- Left  identity
(p1 <-< p2) <-< p3 = p1 <-< (p2 <-< p3) -- Associativity

In conclusion:

Composition is great. Define it and use it, as long as it obeys the category laws.

Discussion on reddit