Haskell 中的有限状态传感器？

Question

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

您可以将 FST 作为 generators（它生成 {x1,x2} 类型的输出），或作为 recognizers（给定{x1,x2} 类型的输入，如果它属于有理关系，它会识别它），或者作为 translators（给定输入磁带，它将其转换为输出磁带）。表示会根据方法改变吗？

是否也可以通过指定重写规则生成 FST 的方式对 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

A 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，我们首先要注意到目前为止所有三台机器中的一个模式。他们每个人都递归地引用自己 "what to do next"。我们将用任何类型 next 替换 "what to do 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 代码中反复出现，通常称为 "base functor"。在 machines 包中，基本仿函数是 Step。相对于我们的代码，Step将输出的类型变量重命名为o，接下来要做什么r，读取到Await，写入[=54] =].

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

Awaiting比Read稍微复杂一点，因为一个Machine can read from multiple sources. For Processes that can only read from a single source, k is 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 Sources。在亲眼目睹 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

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

机器变压器`MachineT`

机器变压器 MachineT，使 Step 看起来几乎像我们的 FST。它说，"A machine operating over some monad m is what to do in that monad to get the next Step. The next thing to do after each step is another 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

对所有 Monads 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
    )

进程

A 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

A Process 在删除所有始终相同的中间构造函数后具有以下结构。这个结构和我们的FST完全一样，只是在没有更多输入的情况下多了一个"what to do next"

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

ProcessT 变体有一个 m 包裹着它，这样它就可以在每个步骤中作用于 monad。

Process 模拟状态传感器。

Haskell 中的有限状态传感器？

Finite State Transducers in Haskell?

haskell

state-machine

transducer

基函子

机器变压器`MachineT`

进程