尝试将元素添加到双向链表ocaml的前面

Question

我正在尝试将一个元素添加到双向链表的前面，但是，我得到了正确的输出形式，但是循环节点的值说：{content = < cycle >}当它应该说< cycle >时。

add_head: (float * 'a) -> ('a lcell) ref -> unit

(* The type of linked lists. *)
type 'a llist =
| Nil
| Cons of (float * 'a) * 'a lcell * 'a lcell
and 'a lcell = ('a llist) ref
let add_head x head = 
match !(!head) with
|Nil -> head := !(singleton x)
|Cons (e, prev, next) -> 
let first = ref (Cons (x, ref Nil, ref !(!head))) in
prev := !first;
head := first   

输出应如下所示：

{contents =
Cons ((3.3, "c"), {contents = Nil},
{contents =
Cons ((1.2, "b"), <cycle>,
{contents = Cons ((2.2, "a"),<cycle>, {contents = Nil})})})}}

这是我的输出：

{contents =
Cons ((3.3, "c"), {contents = Nil},
{contents =
Cons ((1.2, "b"), {contents =<cycle>},
{contents = Cons ((2.2, "a"), {contents =<cycle>}, {contents = Nil})})})}}

对为什么会发生这种情况有任何帮助，以及我不明白什么？

Answer 1

当你写的时候

let first = ref (Cons (x, ref Nil, ref !(!head))) in

您正在为 First 创建一个新的引用，因此该引用不会显示在列表的后面。 然后，当您prev使用

prev := !first;

您指出prev新引用的内容。因此prev指向一个周期，但它不是周期的一部分。

在想要避免这种间接关系时，您需要重用现有的prev引用，而不是创建新的引用：

let add_head x head = 
match !(!head) with
| Nil -> head := !(singleton x)
| Cons (e, prev, next) -> 
let first = Cons (x, ref Nil, !head) in
prev := first;
head := prev;;   

然后你应该得到：

# let r= ref (ref Nil);;
# add_head (0., 0) r;;
# add_head (1., 1) r;;
# add_head (2., 2) r;;
# !r;;
{contents =
Cons ((2., 2), {contents = Nil},
{contents =
Cons ((1., 1), <cycle>,
{contents = Cons ((0., 0), <cycle>, {contents = Nil})})})}

Answer 2

这是我对这个问题的看法。

在函数中，head是对单元格的引用。该函数应更新单元格，而不是对单元格的引用。因此，当您分配给头部时，您要执行此操作：

!head := <new value>

不是这个：

head := ref (<new value>)

我编写了一些遵循此模式的代码，它得到了您说正确的答案。

(这与在 C 中获取*取消引用的数量完全相同。这就是为什么函数式代码如此令人愉快的原因之一：-(