我试图用不相交的并集和记录来表示一个图。以下代码导致语法错误。当两个变量相互引用时,如何定义它们?
type 'a vertex =
|Empty
|Vertex of 'a * 'a list;; (*a tuple consisting of any type of element and a list of vertex*);
let v0 = Vertex(0,[v1]) in
let v1=Vertex(1,[v0]);;
如果我将代码修改为:
let rec v0 = Vertex(0,[v1]) and v1=Vertex(1,[v0]);;
我将获得v0:
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex (1,
[Vertex (0,
[Vertex
(1,
[Vertex
(0,
[Vertex
(1,
[Vertex
(0,
[Vertex
(1,
[Vertex
(0,
[Vertex
(1,
[Vertex
(0,
[Vertex
(1,
[Vertex
(0,
[Vertex
(1,
[Vertex
(0,
[Vertex
(1,
[Vertex
(0,
[Vertex
(1,
[Vertex
(0,
[...])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])]
这似乎不是我想要的。。。
定义包含顶点列表或数组的图形记录的最佳方式是什么?显然我不能这样做:
type graph = {
vertex_set:array};;
我收到以下消息:
Error: The type constructor array expects 1 argument(s),
but is here applied to 0 argument(s)
类型定义中存在错误。我很确定你想要的是:
type 'a vertex =
|Empty
|Vertex of 'a * 'a vertex list
您可以使用let rec
:定义此类型的值
let rec v0 = Vertex(0, [v1]) and v1 = Vertex(1, [v0])
根据我的经验,处理这种值很困难。OCaml是一种热切的语言,所以很难用循环值进行计算。
对于第二个问题,编译器试图告诉您array
本身不是一个类型。您需要说明它是的数组。
type 'a vertices = {
vertex_set: 'a vertex array;
}
如果你想要一个顶点列表而不是一个数组(可能是个好主意),它看起来像这样:
type 'a vertices = {
vertex_set: 'a vertex list;
}
在我看来你有两个问题。首先,您需要学习如何在OCaml中指定类型和值。这并不难,你可以在这里得到好的建议。其次,您需要决定使用什么数据结构来表示图形。这更难,而且没有总体上最好的方法。你可能不想使用本身就是图的数据结构(如上所述)。更现实的可能性是:一个邻接矩阵,或者一个顶点的集合,带有它们的传出边列表。为了避免创建循环结构,您可以引用到顶点,而不是直接将它们包含在边列表中。例如,如果顶点在一个数组中,则可以通过数组索引引用它们。
有一个名为ocamlgraph的库,它可能是比我能想到的任何东西都更好的想法来源!