如何动态分配循环数据？

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