5

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

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

我知道这是Automata 箭头的类型，但我不是在寻找箭头。我想让它成为一个单子，所以大概它会有一个像

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

具有这样的功能：

yield :: o -> Auto i o i

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

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

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

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

编辑

这一切都被证明是微妙的错误。我编写了 Petr Pudlák 在他的回复中建议的代码，它似乎可以工作，但是“yield”操作总是会产生上一个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
4

2 回答 2

4

这种类型是 Mealy 机器。有关一堆实例，请参见https://hackage.haskell.org/package/machines-0.5.1/docs/Data-Machine-Mealy.htmlMonad - 但请注意，实例总是会很慢，因为它需要根据单子定律对角化。

听起来你真正想要的是自动包装。

于 2015-07-11T19:38:23.087 回答
3

您可以本着 的精神扩展您的自动机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可以获得相应的 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, ()))

...
于 2015-07-12T16:19:12.163 回答