我一直想知道是否有一种方法可以以惯用的方式在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机器的方式)。
最佳答案
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
对状态转换器进行建模。
关于haskell - Haskell中的有限状态传感器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27997155/