gpt4 book ai didi

graph - 在 OCaml 中定义带有循环的图形节点变体

转载 作者:行者123 更新时间:2023-12-03 08:39:52 24 4
gpt4 key购买 nike

我正在尝试实现 NFA 转换器的正则表达式。我已经编写了大部分代码,但我正在努力寻找一种方法来构建一个循环图,给出我对状态(节点)和边的表示。

我的图形表示如下:

type state =
| State of int * edge list (* Node ID and outgoing edges *)
| Match (* Match state for the NFA: no outgoing edges *)
and edge =
| Edge of state * string (* End state and label *)
| Epsilon of state (* End state *)

我将正则表达式转换为 NFA 的函数基本上是正则表达式类型的模式匹配,接受正则表达式类型和“最终状态”(NFA 的所有传出边都将到达的位置)并返回“该正则表达式的(部分构建的)NFA 的“开始状态”。 NFA 片段是通过返回一个用其出边列表构造的状态来构建的,其中每个边的结束状态都是通过递归调用构造的。

大部分代码都很简单,但我在为 Kleene star 和 + 构建 NFA 时遇到了问题,这需要图中的循环。鉴于我的陈述,我最终得到类似的东西:

let rec regex2nfa regex final_state =
match regex with
... (* Other cases... *)
| KleeneStar(re) ->
let s = State(count, [Epsilon(regex2nfa r s); Epsilon(final_state)]) in
s

显然这不能编译,因为此时 s 是未定义的。但是我也不能添加“rec”关键字,因为类型检查器将(正确地)拒绝这种递归定义的类型,而且我无法通过使用 Lazy 来解决这个问题,因为强制评估“s”将递归地强制它(再次然后再次...)。基本上我这里有一个先有鸡还是先有蛋的问题——我需要在“状态”引用完全构建到另一个状态之前传递它,这个状态将有一个返回它的边缘,但当然原始状态必须完全构建才能通过在递归调用中。

有没有办法不使用引用/可变记录来做到这一点?我真的很想尽可能地保持它的功能,但在这种情况下我看不出解决这个问题的方法......有人有建议吗?

最佳答案

您可以使用惰性类型或函数创建带循环的数据结构,而无需显式引用。事实上,它们都隐藏了某种形式的可变性。

这是一个最简单的惰性结构的例子,它比列表更复杂

type 'a tree = 'a tr Lazy.t
and 'a tr = Stem of 'a * 'a tree * 'a tree

let rec tree_with_loop : int tree =
lazy (Stem (42,tree_with_loop,tree_with_loop))

但是,您应该明白,对于这种结构(即包含循环的结构),您正在步入一个不牢固的无限基础,因为您所有的遍历函数现在都发散了。

这是相同的示例,但没有惰性:

type 'a tree = unit -> 'a tr
and 'a tr = Stem of 'a * 'a tree * 'a tree

let rec tree_with_loop : int tree =
fun () -> Stem (42,tree_with_loop,tree_with_loop)

这里是一个稍微不那么无限的树的例子:

type 'a tree = 'a tr Lazy.t
and 'a tr =
| Node of 'a
| Tree of 'a tree * 'a tree

let rec tree_with_loop : int tree =
lazy (Tree (tree_with_loop,
lazy (Node 42)))

关于graph - 在 OCaml 中定义带有循环的图形节点变体,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23509728/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com