在 Haskell 中将流转换器函数转换为 Mealy 自动机
Convert stream transformer function into Mealy automaton in Haskell
我使用流:
data Stream a = Cons a (Stream a)
特别是,流转换器功能:
f :: Stream a -> Stream b
我想用这样的函数制作一个 Mealy 自动机:
data Mealy a b = Mealy (a -> (b, Mealy a b))
有没有办法写这样的函数?
toMealy :: (Stream a -> Stream b) -> Mealy a b
我找不到办法。虽然另一种方式很容易工作:
toStreamTransformer :: Mealy a b -> Stream a -> Stream b
也许我遗漏了一些微不足道的东西?
如果您假设传递给 toMealy
的流变换器是 "deterministic",那么您可以启动 Mealy 机器,在输入 a
时,传递 a : e : e : ...
到流转换器(其中 e = error "input stream transformer is not deterministic"
),并输出输出流的第一个元素 b
。然后修改您的流转换器以在其输入前添加 a
并删除其输出的第一个元素(大概是 b
)并递归。
或者,如果您愿意,可以改用输入 a : a : a : ...
;然后你会得到一个总函数,它不检测输入是否是确定性的,而是产生一个 Mealy 机器,它只在确定时生成原始流转换器。
这种方法将花费您想要 运行 Mealy 机器的步数的二次方时间;可能会有更聪明的东西。
这个答案利用了 streaming 包提供的 Stream
抽象。这个抽象:
- 是一个monad转换器,所以你可以把任何monad放在它下面。
- 具有与流生成的元素分开的 return 类型。这种类型的值在流耗尽时 returned。
想象一下你有一个像这样的函数:
module Main where
import Streaming
import Streaming.Internal (Stream(Effect,Step,Return))
import Streaming.Prelude
transformation :: Monad m => Stream (Of Int) m r -> Stream (Of String) m r
transformation = undefined -- your code here
transformation
将 Int
值流更改为 String
值流。它在基础 monad 上是多态的,这意味着转换本身是纯粹的。它在 return 类型 r
上是多态的,这意味着转换总是耗尽源流。
现在我们写下这些辅助定义:
data Feed a = Input a | EOF
trickster :: Monad m => Stream (Of a) (Stream ((->) (Feed a)) m) ()
trickster = do
r <- Effect (Step (Return . Return)) -- request a `Feed a` value
case r of
Input a -> Step (a :> trickster)
EOF -> Return ()
trickster
有点奇怪。在外层,它是一个产生 a
值的流。但在下面,我们有类似 Free (->)
monad 的东西(这里也用 Stream
实现),它接受 a
值并在外层发出它们。
如果我们将 trickster
应用到 transformation
,然后使用 unseparate
函数合并两个 Stream
层,会发生什么情况?
machine :: Stream (Sum (Of String) ((->) (Feed Int))) Identity ()
machine = unseparate (transformation trickster)
我们可以使用 inspect
函数
通过 machine
前进
inspect :: (Functor f, Monad m) => Stream f m r -> m (Either r (f (Stream f m r)))
这是一个可怕的类型:
ghci> :t runIdentity (inspect machine)
runIdentity (inspect machine)
:: Either
()
(Sum
(Of String)
((->) (Feed Int))
(Stream (Sum (Of String) ((->) (Feed Int))) Identity ()))
它基本上意味着在给定的步骤机器要么终止(但是 trickster
的实现确保它永远不会这样做,除非我们通过 EOF
)或者它产生一个 String
,或要求我们输入 Int
值。
(如果没有 unseparate
,我们也可以完成,但是剥离两个 Stream
层的过程会更加混乱。)
(另请参阅 Paul Chiusano 的博客 post Programmatic translation to iteratees from pull-based code,了解此代码背后的原始想法。)
我使用流:
data Stream a = Cons a (Stream a)
特别是,流转换器功能:
f :: Stream a -> Stream b
我想用这样的函数制作一个 Mealy 自动机:
data Mealy a b = Mealy (a -> (b, Mealy a b))
有没有办法写这样的函数?
toMealy :: (Stream a -> Stream b) -> Mealy a b
我找不到办法。虽然另一种方式很容易工作:
toStreamTransformer :: Mealy a b -> Stream a -> Stream b
也许我遗漏了一些微不足道的东西?
如果您假设传递给 toMealy
的流变换器是 "deterministic",那么您可以启动 Mealy 机器,在输入 a
时,传递 a : e : e : ...
到流转换器(其中 e = error "input stream transformer is not deterministic"
),并输出输出流的第一个元素 b
。然后修改您的流转换器以在其输入前添加 a
并删除其输出的第一个元素(大概是 b
)并递归。
或者,如果您愿意,可以改用输入 a : a : a : ...
;然后你会得到一个总函数,它不检测输入是否是确定性的,而是产生一个 Mealy 机器,它只在确定时生成原始流转换器。
这种方法将花费您想要 运行 Mealy 机器的步数的二次方时间;可能会有更聪明的东西。
这个答案利用了 streaming 包提供的 Stream
抽象。这个抽象:
- 是一个monad转换器,所以你可以把任何monad放在它下面。
- 具有与流生成的元素分开的 return 类型。这种类型的值在流耗尽时 returned。
想象一下你有一个像这样的函数:
module Main where
import Streaming
import Streaming.Internal (Stream(Effect,Step,Return))
import Streaming.Prelude
transformation :: Monad m => Stream (Of Int) m r -> Stream (Of String) m r
transformation = undefined -- your code here
transformation
将 Int
值流更改为 String
值流。它在基础 monad 上是多态的,这意味着转换本身是纯粹的。它在 return 类型 r
上是多态的,这意味着转换总是耗尽源流。
现在我们写下这些辅助定义:
data Feed a = Input a | EOF
trickster :: Monad m => Stream (Of a) (Stream ((->) (Feed a)) m) ()
trickster = do
r <- Effect (Step (Return . Return)) -- request a `Feed a` value
case r of
Input a -> Step (a :> trickster)
EOF -> Return ()
trickster
有点奇怪。在外层,它是一个产生 a
值的流。但在下面,我们有类似 Free (->)
monad 的东西(这里也用 Stream
实现),它接受 a
值并在外层发出它们。
如果我们将 trickster
应用到 transformation
,然后使用 unseparate
函数合并两个 Stream
层,会发生什么情况?
machine :: Stream (Sum (Of String) ((->) (Feed Int))) Identity ()
machine = unseparate (transformation trickster)
我们可以使用 inspect
函数
machine
前进
inspect :: (Functor f, Monad m) => Stream f m r -> m (Either r (f (Stream f m r)))
这是一个可怕的类型:
ghci> :t runIdentity (inspect machine)
runIdentity (inspect machine)
:: Either
()
(Sum
(Of String)
((->) (Feed Int))
(Stream (Sum (Of String) ((->) (Feed Int))) Identity ()))
它基本上意味着在给定的步骤机器要么终止(但是 trickster
的实现确保它永远不会这样做,除非我们通过 EOF
)或者它产生一个 String
,或要求我们输入 Int
值。
(如果没有 unseparate
,我们也可以完成,但是剥离两个 Stream
层的过程会更加混乱。)
(另请参阅 Paul Chiusano 的博客 post Programmatic translation to iteratees from pull-based code,了解此代码背后的原始想法。)