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

Question

我使用流：

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

也许我遗漏了一些微不足道的东西？

Answer 1

如果您假设传递给 toMealy 的流变换器是 "deterministic"，那么您可以启动 Mealy 机器，在输入 a 时，传递 a : e : e : ... 到流转换器（其中 e = error "input stream transformer is not deterministic"），并输出输出流的第一个元素 b。然后修改您的流转换器以在其输入前添加 a 并删除其输出的第一个元素（大概是 b）并递归。

或者，如果您愿意，可以改用输入 a : a : a : ...；然后你会得到一个总函数，它不检测输入是否是确定性的，而是产生一个 Mealy 机器，它只在确定时生成原始流转换器。

这种方法将花费您想要运行 Mealy 机器的步数的二次方时间；可能会有更聪明的东西。

Answer 2

这个答案利用了 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，了解此代码背后的原始想法。）

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

Convert stream transformer function into Mealy automaton in Haskell

haskell

stream

transformer