试图在双向链表ocaml前面添加元素

Question

我正在尝试将元素添加到双向链接列表的前面，但是，我得到的输出形式正确，但是cycle节点的值显示：{content = }只需说。

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

这是我的问题。

在您的函数中，head是对单元格的引用。该功能应更新单元格，而不是对该单元格的引用。因此，当您分配给头部时，您想这样做：

!head := <new value>

不是这个：

head := ref (<new value>)

我写了一些遵循这种模式的代码，它得到了您认为正确的答案。

（这与在C语言中正确获取*取消引用的数量完全相同。这是功能代码如此令人愉快的原因之一：-）

Answer 2

写作时

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

您首先要创建一个新的参考，因此不能在列表的后面显示。然后，当您使用[]更新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})})})}