haskell - Haskell中的有限状态传感器？

Question

我一直想知道是否有一种方法可以以惯用的方式在Haskell中定义和使用finite state transducers。

您可以将FST用作生成器(生成类型为{x1，x2}的输出)或识别器(给定类型为{x1，x2}的输入，如果它属于理性关系，则将其识别)，或作为翻译器(给定输入磁带，它会将其转换为输出磁带。表示会根据方法改变吗？

还可以通过指定重写规则来生成FST的方式来建模吗？例如，创建DSL来建模重写规则，然后创建函数createFST :: [Rule] -> FST。

我能找到的最接近的是Kmett，Bjarnason和Cough的machines库:
https://hackage.haskell.org/package/machines

但是我似乎还没有意识到如何用Machine为FST建模。我想正确的做法与他们定义Moore和Mealy机器的方式类似:将FST定义为不同的实体，但提供Automaton实例以将其用作机器。

我也找到了其他一些选项，但是它们以一种直接的方式进行定义(例如https://hackage.haskell.org/package/fst中)。这并不能说服我太多，因为我想知道是否有一种更好的方法可以惯用Haskell类型系统的优势(例如在machines库中定义Moore和Mealy机器的方式)。

Answer 1

Mealy 机器从输入a的流中交替读取a，并将b输出到输出流。它先读取，然后在每次读取后输出一次。

newtype Mealy a b = Mealy { runMealy :: a -> (b, Mealy a b) }

Moore 机器将 b交替输出到输出流，并从输入流中读取输入的 a。它从 b的输出开始，然后在每个输出之后读取一次。

data Moore a b = Moore b (a -> Moore a b)

FST从其输入读取，写入其输出或停止。它可以连续读取任意多次，也可以连续写入任意多次。

data FST a b
    = Read  (a -> FST a b)
    | Write (b,   FST a b)
    | Stop

来自机器的 FST的等效项是 Process 。它的定义有点分散。为了简化讨论，我们现在暂时忽略 Process并从内而外进行探索。

基本函子

为了描述 Process是什么，到目前为止，我们将首先在所有三台机器中注意到一个模式。他们每个人递归地引用自己的“下一步做什么”。我们将用任何类型的 next替换“下一步做什么”。 Mealy机器在将输入映射到输出时，还提供了 next机器来运行。

newtype MealyF a b next = MealyF { runMealyF :: a -> (b, next) }

Moore机器在输出并请求输入之后，找出要运行的 next机器。

data MooreF a b next = MooreF b (a -> next)

我们可以用相同的方式编写 FST。当我们从输入中输入 Read时，我们将根据输入确定要执行的操作 next。当我们在输出中使用 Write时，我们还将在输出后提供 next的操作。当我们 Stop时，接下来无事可做。

data FSTF a b next
    = Read  (a -> next)
    | Write (b,   next)
    | Stop

这种消除显式递归的模式在Haskell代码中反复出现，通常称为“基本函子”。在机器程序包中，基本函子是 Step 。与我们的代码相比， Step将输出的类型变量重命名为 o， r旁边的操作，读取 Await，并写入 Yield。

data Step k o r
  = forall t. Await (t -> r) (k t) r
  | Yield o r
  | Stop

Await比 Read复杂一点，因为 Machine 可以从多个来源读取。对于只能从单个来源读取的 Process es， k是应用于特定类型的 Is ，这证明第二种类型 Is是第一种类型。对于 Process读取输入 a， k将为 Is a。

data Step (Is a) o r
  = forall t. Await (t -> r) (Is a t) r
  | Yield o r
  | Stop

存在量化 forall t.是 implementation detail for dealing with Source s。见证了 a ~ t之后，它变成了。

data Step (Is a) o r
  = forall t ~ a. Await (t -> r) Refl r
  | Yield o r
  | Stop

如果我们将 t与 a统一，并删除始终相同的 Refl构造函数，则它看起来像我们的 FSTF。

data Step (Is a) o r
  = Await (a -> r) r
  | Yield  o    r
  | Stop

在 r中下一步要做的额外 Await是没有更多输入时下一步要做什么。

机械变压器`MachineT`

机器转换器 MachineT 使 Step看起来几乎像我们的 FST。它说:“在某个monad m上运行的机器是在该monad中执行的操作以获得下一个 Step。在每个步骤之后要做的 next事情是另一个 MachineT。”

newtype MachineT m k o = MachineT { runMachineT :: m (Step k o (MachineT m k o)) }

总体而言，专门针对我们的类型，这看起来像

newtype MachineT m (Is a) o = 
    MachineT m (
        Await (a -> MachineT m (Is a) o) (MachineT m (Is a) o)
      | Yield  o   (MachineT m (Is a) o)
      | Stop
    )

Machine是纯 MachineT。

type Machine k o = forall m. Monad m => MachineT m k o

对所有 Monad的 m进行通用量化是另一种表示计算不需要基础 Monad进行任何计算的方法。这可以通过用 Identity 代替 m来看到。

type Machine k o = 
    MachineT Identity (
        Await (a -> MachineT Identity k o) (MachineT Identity k o)
      | Yield  o   (MachineT Identity k o)
      | Stop
    )

工艺流程
Process或 ProcessT是仅读取一种类型的输入 Machine， MachineT的 a或 Is a。

type Process    a b = Machine    (Is a) b
type ProcessT m a b = MachineT m (Is a) b

除去所有始终相同的中间构造函数后， Process具有以下结构。该结构与 FST完全相同，不同之处在于，在没有更多输入的情况下，它添加了“下一步操作”。

type Process a b =
    Await (a -> Process a b) (Process a b)
  | Yield  b   (Process a b)
  | Stop

ProcessT变量的周围包裹着 m，因此它可以在每一步中作用于monad。
Process对状态转换器进行建模。