举个例子,让我们定义一个玩具自动机类型:
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
,因为一旦引入就无法控制。
有没有一种好的方式可以动态分配像我想要的循环结构?