Where Haskell category composition is used regardless of instance?

355 views Asked by At

I think I almost figured out what Category class represents. However at this level of abstraction it makes me wonder where I could find generic use for it.

What code using . or id from Control.Category has found practical uses for different instances?

1

There are 1 answers

1
J. Abrahamson On

A common one of late is the Mealy machine. Consider an infinite stream

data Stream a = Stream a (Stream a)

right now we can write infinite streams which can be consumed, like [1..]

oneUpTo :: Stream Int
oneUpTo = go 1 where go n = Stream n (go (n+1))

but sometimes it's useful to write streams which can be affected by input as well. To do this we'll hide the next "step" of the stream behind a function

data Mealy b a = Mealy (b -> (a, Mealy b a))

And now we can write somewhat more exotic responses, like echo

echo :: a -> Mealy (Maybe a) a
echo a = Mealy go where
  go Nothing   = (a,  echo a )
  go (Just a') = (a', echo a')

which allows input to switch the internal "state" of the Stream. Of course, this is something more powerful now. I called it a Mealy machine because it forms a certain kind of (in-)finite state automata.

What's a little unobvious, however, is that Mealy forms a Category.

instance Category Mealy where
  id = Mealy (\a -> (a, id))
  Mealy bc . Mealy ab = Mealy $ \a -> case ab a of
    (b, nab) -> case bc b of
      (c, nbc) -> (c, nbc . nab)

In this case, we combine two Mealy machines by building a third which feeds its inputs into the first machine, takes the first machine's outputs to the second machine, and then returns the final output along with updated composed pair.

If this is interesting and you don't mind exploring a large package with fairly sparse documentation, then it's all available in the machines package on Hackage.