如何动态分配循环数据？

Question

如何动态分配循环数据？

haskellmemory-managementrecursive-datastructures

15

举个例子，让我们定义一个玩具自动机类型：

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

这个结构是设计成循环的，我们可以把每个Automaton想象成一个状态，其中包含成功和失败转移到其他状态。因此，有限自动机必须递归地定义。例如，这是最简单的自动机：

sink =
  Auto sink sink

它由一个状态组成，该状态始终转移到自身。如果需要，我们可以创建更复杂的自动机：

-- 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，因为一旦引入就无法控制。

有没有一种好的方式可以动态分配像我想要的循环结构？

- Wheat Wizard

2

严谨地说，你的“Automaton”类型并不是很有用，因为没有办法区分一个值和另一个值。所以，“fromTransition _ = let a = Auto a a in a”在技术上来说是正确的答案。当然，向“Automaton”添加一些字段，比如一个“Int”，就不再是简单的问题了。 - chi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Li-yao Xia · Accepted Answer

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

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