Haskell 中 yield/await 函数的延续 monad

Question

我想创建一个类型如下的自动机类型：

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

我知道这是 Automata arrow 的类型，但我不是在寻找箭头。我想把它变成一个 monad，所以大概它会有一个像

这样的类型

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

具有这样的功能：

yield :: o -> Auto i o i

因此，当我从 Auto monad 中调用 "yield" 时，"runAuto" 函数 return 是一对由 "yield" 的参数和延续函数组成的对。当应用程序调用延续函数时，作为 "yield".

的结果，参数会在 monad 中被 returned

我知道这将需要一些延续 monad 的风格，但尽管过去曾与延续争论不休，但我看不出如何编写这个代码。

我也知道这很像 Michael Snoyman 的 Conduit monad，只是他将 "yield" 和 "await" 分开了。这个 monad 必须对每个输入都有一个输出。

背景：我正在编写一些以复杂方式响应 GUI 事件的代码。我希望能够编写代码来接受 return 中的一系列输入，以便随着用户交互的进行对屏幕进行更新，而不是将其变成手动编码的状态机。

编辑

所有这一切都被证明是微妙的错误。我写了 Petr Pudlák 在他的回复中建议的代码，它似乎有效，但是 "yield" 操作总是产生 previous yield 的输出。这很奇怪。

盯着屏幕看了好久，我终于明白我需要粘贴在这里的代码。关键区别在于 AutoF 类型。将下面的那个与 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

Answer 1

那个型号是 Mealy 机器。见 https://hackage.haskell.org/package/machines-0.5.1/docs/Data-Machine-Mealy.html 的一堆实例 - 但请注意 Monad 实例总是会很慢，因为它需要根据 monad 法则进行对角化。

听起来您真正想要的是 auto package。

Answer 2

您可以本着 Conduit 的精神扩展您的自动机，即允许它退出并 return 有限多个输入的值：

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

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

好消息是您不需要自己实施。返回值或使用函子嵌套正是 free monad does (see its haddock docs)。所以让我们定义

{-# 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 相同的仿函数，您会得到相应的 monad 转换器：

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

...

Haskell 中 yield/await 函数的延续 monad

Continuation monad for a yield/await function in Haskell

haskell

monads

continuation