Continuation monad for a yield/await function in Haskell

Question

I want to create an automata type with a type like this:

newtype Auto i o = Auto {runAuto :: i -> (o, Auto i o)}

I know this is the type of the Automata arrow, but I'm not looking for an arrow. I want to make this a monad, so presumably its going to have a type like

newtype Auto i o a = ???? What goes here?

with a function like this:

yield :: o -> Auto i o i

So when I call "yield" from within the Auto monad the "runAuto" function returns a pair consisting of the argument to "yield" and the continuation function. When the application program calls the continuation function the argument is then returned within the monad as the result of "yield".

I know this is going to require some flavour of continuation monad, but despite having wrangled with continuations in the past I can't see how to code this one.

I also know that this rather resembles Michael Snoyman's Conduit monad, except that he splits up "yield" and "await". This monad has to have exactly one output for every input.

Background: I'm writing some code that responds to GUI events in a complicated way. Rather than turning this into a hand-coded state machine I'm hoping to be able to write code that accepts a series of inputs in return for yielding updates to the screen as the user interaction progresses.

Edit

All this turned out to be subtly wrong. I wrote the code suggested by Petr Pudlák in his reply, and it seemed to work, but the "yield" operation always yielded the output from the previous yield. Which was wierd.

After much staring at the screen I finally figured out that I needed the code pasted here. The crucial difference is in the AutoF type. Compare the one below with the one proposed by Petr.

import Control.Applicative
import Control.Monad
import Control.Monad.IO.Class
import Control.Monad.State.Class
import Control.Monad.Trans.Class
import Control.Monad.Trans.Free
import Data.Void

class (Monad m) => AutoClass i o m | m -> i, m -> o where
   yield :: o -> m i

data AutoF i o a = AutoF o (i -> a)

instance Functor (AutoF i o) where
   fmap f (AutoF o nxt) = AutoF o $ \i -> f $ nxt i

newtype AutoT i o m a = AutoT (FreeT (AutoF i o) m a)
   deriving (Functor, Applicative, Monad, MonadIO, MonadTrans, MonadState s)

instance (Monad m) => AutoClass i o (AutoT i o m) where
   yield v = AutoT $ liftF $ AutoF v id

runAutoT :: (Monad m) => AutoT i o m Void -> m (o, i -> AutoT i o m Void)
runAutoT (AutoT step) = do
   f <- runFreeT step
   case f of
      Pure v -> absurd v
      Free (AutoF o nxt) -> return (o, AutoT . nxt)


-- Quick test
--
-- > runTest testStart
testStart :: Int -> AutoT Int Int IO Void
testStart x = do
   liftIO $ putStrLn $ "My state is " ++ show x
   y <- liftIO $ do
      putStrLn "Give me a number: "
      read <$> getLine
   v1 <- yield $ x + y
   liftIO $ putStrLn $ "I say " ++ show v1
   v2 <- yield $ 2 * v1
   testStart v2

runTest auto = do
   putStrLn "Next input:"
   v1 <- read <$> getLine
   (v2, nxt) <- runAutoT $ auto v1
   putStrLn $ "Output = " ++ show v2
   runTest nxt

Damoiselle

Answer 1

You could extend your automaton in the spirit of Conduit, that is, allow it to exit and return a value on finitely many inputs:

data Auto i o a
    = Step (i -> (o, Auto i o a))
    | End a

Then you can define a monad instance that concatenates two automata using >>=: When the first one finishes, the second one continues.

The good news is that you don't need to implement it yourself. Returning a value or nesting using a functor is exactly what the free monad does (see its haddock docs). So let's define

{-# LANGUAGE DeriveFunctor #-}
import Control.Monad.Free
import Data.Void

-- | A functor describing one step of the automaton
newtype AutoF i o t = AutoF (i -> (o, t))
  deriving (Functor)

Then the original Auto type can be defined just as an alias:

type Auto i o = Free (AutoF i o)

This automatically gives you all the instances of Free, and you can also define your original functions:

-- | If @a@ is 'Void', the machine runs forever:
runAuto :: Auto i o Void -> i -> (o, Auto i o Void)
runAuto (Pure v)  _         = absurd v
runAuto (Free (AutoF f)) i  = f i

yield :: o -> Auto i o ()
yield x = liftF (AutoF $ \_ -> (x, ()))

Note that using the same functor with FreeT you get the corresponding monad transformer:

import Control.Monad.Trans.Free

type AutoT i o = FreeT (AutoF i o)

yieldT :: (Monad m) => o -> AutoT i o m ()
yieldT x = liftF (AutoF $ \_ -> (x, ()))

...

Ola

Almost exactly what I wanted, except that "yield" also takes in a new input for the next state transition, so it should be "yield :: o -> Auto i o i". So presumably "yield x = liftF (AutoF $ \v -> (x, v))". However, thanks for the great insight that free monads are what I needed. I've read about them in the past, but didn't connect them with this particular problem. Now, of course, its blindingly obvious. – Damoiselle

Indeed, this would be the correct definition of yield with the semantic you want. – Ola

Also you might consider using Codensity for better asymptotic performance. – Ola

Answer 2

That type is a Mealy machine. See https://hackage.haskell.org/package/machines-0.5.1/docs/Data-Machine-Mealy.html for a bunch of instances - but note that the Monad instance is always going to be slow, because it's required to diagonalize by the monad laws.

It sounds like what you really want is the auto package anyway.

Seaver