在Haskell中将流转换器函数转换为粉状自动机

Question

我使用流:

data Stream a = Cons a (Stream a)

特别是流转换器功能:

f :: Stream a -> Stream b

我想用这样一个函数来做一个自动机:

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

也许我错过了一些微不足道的东西?

Answer 1

这个答案利用了流包提供的Stream抽象。这种抽象:

• 是一个单子转换器，所以你可以把任何单子放在下面。
• 返回类型与流产生的元素分离。当流耗尽时返回此类型的值。

假设你有这样一个函数:

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值流。它在基单上是多态的，这意味着转换本身是纯的。它在返回类型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 (->)的单子(这里也用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的博客文章"从基于拉的代码编程转换为迭代器"，了解此代码背后的原始思想。)

Answer 2

如果您假设传递给toMealy的流转换器是"确定性的"，那么您可以通过在输入a时将a : e : e : ...传递给流转换器(其中e = error "input stream transformer is not deterministic")并输出输出流的第一个元素b来启动您的Mealy机器。然后修改您的流转换器，将a前置到其输入，并删除其输出的第一个元素(假设是b)并递归。

或者，如果你喜欢，你可以使用输入a : a : a : ...代替;那么你将得到一个不检测输入是否确定的总函数，但产生一个只在原始流变压器确定时生成原始流变压器的Mealy机器。

此方法将花费您想要运行Mealy机器的步数的二次时间;也许还有更聪明的办法