14

我一直想知道是否有一种方法可以在 Haskell 中以惯用的方式定义和使用有限状态传感器。

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

是否也可以通过指定重写规则来对 FST 进行建模？例如，创建一个 DSL 来模拟重写规则，然后创建一个函数createFST :: [Rule] -> FST。

我能找到的最接近的是 Kmett、Bjarnason 和 Cough 的machines图书馆： https ://hackage.haskell.org/package/machines

但我似乎无法意识到如何用Machine. 我认为正确的做法类似于他们定义 Moore 和 Mealy 机器的方式：将 FST 定义为不同的实体，但提供一个Automaton能够将其用作机器的实例。

我也找到了一些其他选项，但它们以一种直接的方式定义它（如在https://hackage.haskell.org/package/fst中）。这并没有让我很信服，因为我想知道是否有更好的方法来使用 Haskell 类型系统的优势（比如machines库中如何定义 Moore 和 Mealy 机器）。

4

1 回答 1

28

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

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

Moore机器交替地将 a 输出到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

FSTfrom 机器的等价物是Process. 它的定义有点分散。为了简化讨论，我们将暂时忘记Process并从内到外探索它。

基函子

为了描述 aProcess是什么，我们将首先注意到到目前为止所有三台机器中的一个模式。它们中的每一个都递归地引用自己的“下一步做什么”。我们将用任何类型替换“下一步做什么” 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

Awaiting 比ReadaMachine可以从多个来源读取要复杂一些。对于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.是处理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

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对所有s 的通用量化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 ProcessorProcessT是一个Machineor MachineT，它只读取单一类型的输入a, Is a。

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

Process在删除所有始终相同的中间构造函数后，A具有以下结构。这个结构与我们的 完全相同FST，只是在没有更多输入的情况下添加了“下一步做什么”。

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

该ProcessT变体周围有一个m包裹，因此它可以在每个步骤中在单子中起作用。

Process模型状态传感器。

于 2015-01-17T10:33:47.330 回答