如何动态分配循环数据？

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

如何动态分配循环数据？

How can I dynamically allocate cyclic data?

haskell

memory-management

recursive-datastructures