Haskell中的有限状态转换器？ [英] Finite State Transducers in Haskell?
问题描述
我一直在想，是否有一种方法可以在Haskell中以惯用方式定义和使用有限状态转换器您可以将FST作为生成器（它会生成{x1，x2}类型的输出），或者作为识别器（给定类型{x1，x2}的输入可以识别它是否属于理性关系），或者作为译者（给定输入磁带，它将其转换为输出磁带）。表达方式是否会根据方法而改变？
也可以通过指定重写规则来建立FST模型吗？例如，创建一个DSL来为重写规则建模，然后创建一个函数 createFST :: [Rule] - > FST 。
最接近我能找到的是Kmett，Bjarnason和Cough的机器库：
https://hackage.haskell.org/package/machines
但我似乎无法理解如何使用 Machine 建立FST模型。我假设正确的做法与他们如何定义Moore和Mealy机器类似：将FST定义为不同的实体，但提供 Automaton 的实例。我也发现了一些其他的选择，但他们以一种直接的方式定义它（如https://hackage.haskell.org/package/fst ）。这并没有说服我很多，因为我不知道是否有更好的方式来习惯性地使用Haskell类型系统的优势（比如Moore和Mealy机器是如何在机器中定义的 Mealy 机器交替读取 a 从输入流 a 输出，并输出一个 b 到输出流。它首先读取，然后在每次读取后输出一次。
newtype Mealy a b = Mealy {runMealy :: a - > （b，Mealy ab）}
A Moore 机器交替输出一个 b 添加到输出流中，并从输入流中读取输入 a 。它从 b 的输出开始，然后在每次输出后读取一次。
<$ c $数据Moore ab = Moore b（a - > Moore ab）
它是输入，写入其输出，或停止。它可以连续多次读取所需的数据，也可以连续多次写入所需的数据。
数据FST ab
=阅读（a - > FST ab）
|写（b，FST a b）
|停止
相当于机器的 FST 是 过程 。它的定义有点分散。为了简化讨论，现在我们将暂时忘掉 Process 并从内到外探索它。
基函子
为了描述 Process 是什么，我们首先会注意到所有三种模式迄今为止的机器。它们中的每一个递归地将自身称为下一步做什么。我们将用任何类型的 next 替换下一步做什么。 Mealy 机器将输入映射到输出，同时提供下一台机器运行。
newtype MealyF ab next = MealyF {runMealyF :: a - > （b，next）}
Moore 机器输出并请求输入后，计算出下一台机器运行。
data MooreF ab next = MooreF b（a - > next）
我们可以编写 FST 以同样的方式。当我们从输入中读取 Read 时，我们将根据输入找出 next > 。当我们写入到输出时，我们还会在输出后提供 next 的操作。当我们 Stop 时，接下来什么也没有做。
data FSTF ab next
=读取（a - >下一个）
|写（b，下一个）
|停止
这种消除显式递归的模式在Haskell代码中反复出现，通常称为base函子。在机器包中，基函子是 步骤 。与我们的代码相比， Step 已将输出的类型变量重命名为 o ，紧接着 r ，读到等待，并写入 Yield 。 p>
data步骤kor
= forall t。等待（t - > r）（k t）r
|收益率r
|停止
等待 ing有点复杂比阅读因为 Machine 可以从多个来源读取。对于只能从单一来源读取的进程 es， k 为 Is 应用于特定类型，这是第二种类型 Is 第一种类型的证明。对于进程读取输入 a ， k 将是一个。
data步骤（a）或
= forall t。等待（t - > r）（是t）r
|收益率r
|停止
存在性量化 forall t。是处理源 的实现细节。在见证 a〜t 之后，它就变成了。
data Step（Is a）或
= forall t〜a。等待（t - > r）Refl r
|收益率r
|停止
如果我们将 t 与 a 并移除始终相同的 Refl 构造函数，这看起来像我们的 FSTF =等待（a - > r）r（c）c $ c $>
|收益率r
|停止
多余的 r 接下来在 Await 中，当没有更多输入时，接下来要做什么。
机器变量`MachineT` h3>
机器变换器 MachineT ，使得 Step 几乎和我们的 FST 。它说：一台运行在某个monad m 上的机器是在该monad中如何获得下一个 Step 。在每一步之后要做的下一步是另一个 MachineT 。
newtype MachineT mko = MachineT {runMachineT :: m（Step ko（MachineT mko））}
总的来说，我们的类型是专门用于这种类型的，看起来像
newtype MachineT m（Is a）o =
MachineT m（
Await（a - > MachineT m（Is a）o）（MachineT m（Is a）o）
| Yield（MachineT m（Is a）o）
| Stop
）
Machine 是纯粹的 MachineT 。
型机器ko = forall m。 Monad m => MachineT mko
通用量化所有 Monad s m 是另一种说法，即计算不需要底层的 Monad 中的任何内容。这可以通过将 身份 为 m 。
<$ c （MachineT Identity ko）
|收益率（MachineT Identity ko）
|
|停止
）
过程
Process 或 ProcessT 是机器或 MachineT ，它只读取一种类型的输入 a ，是
$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $
FST 完全一样，只是在没有更多输入的情况下它增加了接下来做什么。
类型过程ab =
等待（a - >过程ab）（过程ab）
|收益b（过程a b）
|停止
ProcessT 变量有一个<$
过程包装在它的周围，以便它可以在每一步执行monad。 / code>模型状态传感器。
I've been wondering if there is a way to define and work with finite state transducers in Haskell in an idiomatic way.
You can approach FSTs as generators (it generates an output of type {x1,x2}), or as recognizers (given an input of type {x1,x2} it recognizes it if it belongs to the rational relation), or as translators (given an input tape, it translates it into an output tape). Would the representation change depending on the approach?
Would it also be possible to model a FST in a way that you can produce one by specifying rewriting rules? E.g creating a DSL to model rewriting rules, and then creating a function createFST :: [Rule] -> FST.
The closest I could find is Kmett, Bjarnason and Cough's machines library:
https://hackage.haskell.org/package/machines
But I can't seem to realize how to model a FST with a Machine. I'd suppose that the correct way of doing it would be similar to how they define Moore and Mealy machines: define a FST as a different entity, but provide an instance of Automaton to be able to use it as a machine.
I found some other options too, but they define it in a straightforward way (like in https://hackage.haskell.org/package/fst ). That doesn't convince me much, as I wonder if there's a better way to do so idiomatically using the strengths of Haskell's type system (like how Moore and Mealy machines are defined in the machines library).
A Mealy machine alternately reads an a from a stream of inputs a and outputs a b to a stream of outputs. It reads first and then outputs once after each read.
newtype Mealy a b = Mealy { runMealy :: a -> (b, Mealy a b) }
A Moore machine alternately outputs a b to a stream of outputs and reads an input a from a stream of inputs. It starts with an output of b and then reads once after each output.
data Moore a b = Moore b (a -> Moore a b)
An FST either reads from it's input, writes to its output, or stops. It can read as many times in a row as it wants or write as many times in a row as it wants.
data FST a b
= Read (a -> FST a b)
| Write (b, FST a b)
| Stop
The equivalent of an FST from machines is Process. It's definition is a little spread out. To simplify the discussion we are going to forget about Process for now and explore it from the inside-out.
The base functor
To describe what a Process is, we're going to first notice a pattern in all three machines so far. Each of them recursively refers to itself for "what to do next". We are going to replace "what to do next" with any type next. The Mealy machine, while mapping an input to an output, also provides the next machine to run.
newtype MealyF a b next = MealyF { runMealyF :: a -> (b, next) }
The Moore machine, after outputting and requesting an input, figures out the next machine to run.
data MooreF a b next = MooreF b (a -> next)
We can write the FST the same way. When we Read from the input we'll figure out what to do next depending on the input. When we Write to the output we'll also provide what to do next after outputting. When we Stop there's nothing to do next.
data FSTF a b next
= Read (a -> next)
| Write (b, next)
| Stop
This pattern of eliminating explicit recursion shows up repeatedly in Haskell code, and is usually called a "base functor". In the machines package the base functor is Step. Compared to our code, Step has renamed the type variable for the output to o, what to do next to r, reading to Await, and writing to Yield.
data Step k o r
= forall t. Await (t -> r) (k t) r
| Yield o r
| Stop
Awaiting is a little more complicated than Read because a Machine can read from multiple sources. For Processes that can only read from a single source, k is Is applied to a specific type, which is a proof the second type Is the first type. For a Process reading inputs a, k will be Is a.
data Step (Is a) o r
= forall t. Await (t -> r) (Is a t) r
| Yield o r
| Stop
The existential quantification forall t. is an implementation detail for dealing with Sources. After witnessing that a ~ t this becomes.
data Step (Is a) o r
= forall t ~ a. Await (t -> r) Refl r
| Yield o r
| Stop
If we unify t with a and remove the Refl constructor which is always the same, this looks like our FSTF.
data Step (Is a) o r
= Await (a -> r) r
| Yield o r
| Stop
The extra r for what to do next in Await is what to do next when there's no more input.
The machine transformer `MachineT`
The machine transformer, MachineT, makes Step look almost like our FST. It says, "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)) }
Overall, specialized for our types, this looks like
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 is a pure MachineT.
type Machine k o = forall m. Monad m => MachineT m k o
Universal quantification over all Monads m is another way of saying a computation doesn't need anything from an underlying Monad. This can be seen by substituting Identity for m.
type Machine k o =
MachineT Identity (
Await (a -> MachineT Identity k o) (MachineT Identity k o)
| Yield o (MachineT Identity k o)
| Stop
)
Processes
A Process or ProcessT is a Machine or MachineT that only reads a single type of input a, Is a.
type Process a b = Machine (Is a) b
type ProcessT m a b = MachineT m (Is a) b
A Process has the following structure after removing all the intermediate constructors that are always the same. This structure is exactly the same as our FST, except it has an added "what to do next" in the case that there's no more input.
type Process a b =
Await (a -> Process a b) (Process a b)
| Yield b (Process a b)
| Stop
The ProcessT variant has an m wrapped around it so that it can act in the monad at each step.
Process models state transducers.
这篇关于Haskell中的有限状态转换器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
