如何动态分配循环数据？

Question

为了便于示例，让我们定义一个玩具自动机类型：

data Automaton =
  Auto
    { success ::
      Automaton
    , failure ::
      Automaton
    }

这种结构被设计成通过循环，我们可以将每个Automaton想象成一个具有成功和失败转换到其他状态的状态。因此有限自动机必须递归定义。例如，这里是最简单的自动机：

sink =
  Auto sink sink

它由1个总是过渡到自身的状态组成。如果我们愿意，我们可以制造更复杂的自动机：

-- Transitions to a sink once it encounters a failure
otto1 =
  Auto otto1 sink

-- Mutually recursive automata
otto2 =
  Auto otto2 otto3

otto3 =
  Auto otto3 otto2

这些不错。但是接受用户输入并构建一个自动机可能会很好。例如，也许可以从过渡矩阵中构建一个。这里有一个天真的实现：

fromTransition :: [(Int, Int)] -> Automaton
fromTransition tMatrix =
  go 0
  where
    go n =
      let
        (succ, fail) =
          tMatrix !! n
      in
        Auto (go succ) (go fail)

然而，当我们尝试这样做时，开始出现问题。我们前面的例子是O（1）以遵循转换。然而，由于禁用缓存，因此每次进行转换时都必须对列表进行索引，因此由此产生的自动机是O（n）。此外，输入列表必须保存在内存中，只要该自动机处于活动状态。这基本上比使用转移矩阵作为自动机更糟糕。

我真正想要的是动态构建的自动机，其方法与之前显示的静态构建的自动机一样高性能。我想要一些方法来分析输入，构建一个自动机，然后释放输入。

在一种带有变异的语言中，这很容易做到，因为我们可以一点一点地创建结构，留下漏洞供以后更正。

我也不想把IO拖进去，因为一旦引入，它就无法被包含。

有没有一种像我所希望的那样动态分配循环结构的好方法？

Answer 1

懒惰来拯救。我们可以递归地定义所有子自动机的列表，使得它们的转换索引到相同的列表中：

fromTransition :: [(Int, Int)] -> Automaton
fromTransition m = a !! 0 where
  a = map (\(succ,fail) -> Auto (a !! succ) (a !! fail)) m

在所有转换至少被遍历一次之后，生成的自动机将是您期望的循环图，而不需要任何对矩阵的引用（特别是，转换将在恒定时间内进行）。

我们也可以使用seq提前强制自动机。

fromTransition :: [(Int, Int)] -> Automaton
fromTransition m = forced `seq` (a !! 0) where
  a = map (\(succ,fail) -> Auto (a !! succ) (a !! fail)) m
  forced = foldr (\(Auto x y) r -> x `seq` y `seq` r) () a