OCaml中循环双向链表的实现

Question

我正在尝试使用 OCaml 类型声明来实现一个循环双向链表。这是我所拥有的：

type 'a cList = 
{ 
mutable value : 'a; 
mutable left : 'a cList option; 
mutable right : 'a cList option 
}
;;

当我需要声明包含单个元素的第一个列表时，问题就出现了。因为元素在被赋值之前不能被引用，所以我不能让单元格的左右成员指向它自己。到目前为止，我唯一的解决方法是允许左右成员为 option 类型，将它们设置为 None 然后修改它们，使它们指向单元格本身。

let unitClist v = let a = {
                      value = v; 
                      left = None; 
                      right = None
                      }
              in
              a.left <- Some a; 
              a.right <- Some a;
              a
;;

它可以工作，但是当您确定有一个值时，必须使用选项类型有点绑定。有没有更好的方法来做到这一点？提前致谢。

Answer 1

显然，您也可以直接使用记录定义递归值。通过使用rec绑定，您可以在定义中递归引用绑定（在某些情况下）：

type 'a cList = {
  mutable value : 'a; 
  mutable left : 'a cList; 
  mutable right : 'a cList 
}

let unitClist v =
  let rec a = {
    value = v; 
    left = a; 
    right = a
  }
  in a

这记录在OCaml 手册的第 8.1 章