Haskell中yield/await函数的延续单子

Question

我想用这样的类型创建一个自动机类型:

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

我知道这是自动机箭的类型，但我不是在找箭。我想让它成为单子，所以它的类型应该是

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

使用如下函数:

yield :: o -> Auto i o i

因此，当我从Auto单子中调用"yield"时，"runAuto"函数返回由"yield"参数和延续函数组成的一对。当应用程序调用延续函数时，参数将在单子中作为"yield"的结果返回。

我知道这将需要延续单子的一些味道，但是尽管在过去与延续争吵，我不知道如何编写这个。

我也知道这很像Michael Snoyman的导管单子，除了他把"屈服"one_answers"等待"分开了。对于每个输入，这个单子必须只有一个输出。

背景:我正在写一些代码，以复杂的方式响应GUI事件。而不是把它变成一个手工编码的状态机，我希望能够编写代码，接受一系列的输入，作为回报，产生更新的屏幕作为用户交互的进展。

编辑

这一切都被证明是微妙的错误。我编写了peter Pudlák在他的回复中建议的代码，它似乎可以工作，但是"yield"操作总是产生先前 yield的输出。这很奇怪。

盯着屏幕看了很久之后，我终于明白我需要粘贴在这里的代码。关键的区别在于AutoF类型。把下面的和彼得提出的比较一下。

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

Answer 1

那是粉碎机。请参阅https://hackage.haskell.org/package/machines-0.5.1/docs/Data-Machine-Mealy.html获取一系列实例-但请注意，Monad实例总是很慢，因为它需要根据monad定律对角化。

听起来你真正想要的是auto包

Answer 2

您可以按照Conduit的精神扩展您的自动机，即允许它退出并在有限多个输入上返回一个值:

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

然后你可以定义一个monad实例，使用>>=连接两个自动机:当第一个自动机完成时，第二个自动机继续。

好消息是你不需要自己实现它。使用函子返回值或嵌套正是free monad所做的(请参阅其haddock文档)。我们来定义

{-# 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)

那么原始的Auto类型可以定义为别名:

type Auto i o = Free (AutoF i o)

这将自动为您提供Free的所有实例，您还可以定义您的原始函数:

-- | 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, ()))

注意，对FreeT使用相同的函子可以得到相应的单子转换器:

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, ()))
...