What general structure does this type have?

Question

While hacking something up earlier, I created the following code:

newtype Callback a = Callback { unCallback :: a -> IO (Callback a) }

liftCallback :: (a -> IO ()) -> Callback a
liftCallback f = let cb = Callback $ \x -> (f x >> return cb) in cb

runCallback :: Callback a -> IO (a -> IO ())
runCallback cb =
    do ref <- newIORef cb
       return $ \x -> readIORef ref >>= ($ x) . unCallback >>= writeIORef ref

Callback a represents a function that handles some data and returns a new callback that should be used for the next notification. A callback which can basically replace itself, so to speak. liftCallback just lifts a normal function to my type, while runCallback uses an IORef to convert a Callback to a simple function.

The general structure of the type is:

data T m a = T (a -> m (T m a))

It looks much like this could be isomorphic to some well-known mathematical structure from category theory.

But what is it? Is it a monad or something? An applicative functor? A transformed monad? An arrow, even? Is there a search engine similar Hoogle that lets me search for general patterns like this?

Answer 1

The term you are looking for is free monad transformer. The best place to learn how these work is to read the "Coroutine Pipelines" article in issue 19 of The Monad Reader. Mario Blazevic gives a very lucid description of how this type works, except he calls it the "Coroutine" type.

I wrote up his type in the transformers-free package and then it got merged into the free package, which is its new official home.

Your Callback type is isomorphic to:

type Callback a = forall r . FreeT ((->) a) IO r

To understand free monad transformers, you need to first understand free monads, which are just abstract syntax trees. You give the free monad a functor which defines a single step in the syntax tree, and then it creates a Monad from that Functor that is basically a list of those types of steps. So if you had:

Free ((->) a) r

That would be a syntax tree that accepts zero or more as as input and then returns a value r.

However, usually we want to embed effects or make the next step of the syntax tree dependent on some effect. To do that, we simply promote our free monad to a free monad transformer, which interleaves the base monad between syntax tree steps. In the case of your Callback type, you are interleaving IO in between each input step, so your base monad is IO:

FreeT ((->) a) IO r

The nice thing about free monads is that they are automatically monads for any functor, so we can take advantage of this to use do notation to assemble our syntax tree. For example, I can define an await command that will bind the input within the monad:

import Control.Monad.Trans.Free

await :: (Monad m) => FreeT ((->) a) m a
await = liftF id

Now I have a DSL for writing Callbacks:

import Control.Monad
import Control.Monad.Trans.Free

printer :: (Show a) => FreeT ((->) a) IO r
printer = forever $ do
    a <- await
    lift $ print a

Notice that I never had to define the necessary Monad instance. Both FreeT f and Free f are automatically Monads for any functor f, and in this case ((->) a) is our functor, so it automatically does the right thing. That's the magic of category theory!

Also, we never had to define a MonadTrans instance in order to use lift. FreeT f is automatically a monad transformer, given any functor f, so it took care of that for us, too.

Our printer is a suitable Callback, so we can feed it values just by deconstructing the free monad transformer:

feed :: [a] -> FreeT ((->) a) IO r -> IO ()
feed as callback = do
    x <- runFreeT callback
    case x of
        Pure _ -> return ()
        Free k -> case as of
            []   -> return ()
            b:bs -> feed bs (k b)

The actual printing occurs when we bind runFreeT callback, which then gives us the next step in the syntax tree, which we feed the next element of the list.

Let's try it:

>>> feed [1..5] printer
1
2
3
4
5

However, you don't even need to write all this up yourself. As Petr pointed out, my pipes library abstracts common streaming patterns like this for you. Your callback is just:

forall r . Consumer a IO r

The way we'd define printer using pipes is:

printer = forever $ do
    a <- await
    lift $ print a

... and we can feed it a list of values like so:

>>> runEffect $ each [1..5] >-> printer
1
2
3
4
5

I designed pipes to encompass a very large range of streaming abstractions like these in such a way that you can always use do notation to build each streaming component. pipes also comes with a wide variety of elegant solutions for things like state and error handling, and bidirectional flow of information, so if you formulate your Callback abstraction in terms of pipes, you tap into a ton of useful machinery for free.

If you want to learn more about pipes, I recommend you read the tutorial.

Answer 2

The general structure of the type looks to me like

data T (~>) a = T (a ~> T (~>) a)

where (~>) = Kleisli m in your terms (an arrow).

---

Callback itself doesn't look like an instance of any standard Haskell typeclass I can think of, but it is a Contravariant Functor (also known as Cofunctor, misleadingly as it turns out). As it is not included in any of the libraries that come with GHC, there exist several definitions of it on Hackage (use this one), but they all look something like this:

class Contravariant f where
    contramap :: (b -> a) -> f a -> f b
 -- c.f. fmap :: (a -> b) -> f a -> f b

Then

instance Contravariant Callback where
    contramap f (Callback k) = Callback ((fmap . liftM . contramap) f (f . k))

Is there some more exotic structure from category theory that Callback possesses? I don't know.