如何实现不可变双向链表的add功能？

Question

这个问题仅具有理论动机（当然，在现实开发中有多种方法可以避免它）。

让我们引入一个不可变的双向链表，如下 OCaml 类型。

type t =
  | Link of 
     { value : int; 
        next : t; 
        prev : t 
     }
  | End 

我们可以轻松地在 OCaml 允许的（非功能）值的递归定义中创建包含三个元素的实例：

let _123 = 
  let rec a = Link { value = 1; next = b; prev = End }
  and     b = Link { value = 2; next = c; prev = a   }
  and     c = Link { value = 3; next = End; prev = b } in
  a

我们可以用下图来表示“_123”：

这很好，但是如果没有动态创建列表（包含任意数量的项目）的能力，那就没什么了不起。所以，我声明了这个函数：

let add x = function
  | End       -> Link { value = x; next = End; prev = End }
  | Link tail -> let rec head = Link { value = x; next = tail'; prev = End }
                 and tail' = Link { tail with prev = head } in
                 head

并尝试使用它：

let _123 = 
  End |> add 3 
      |> add 2 
      |> add 1

结果不是我所期望的：

它包含额外的项目和损坏的链接。我明白为什么会这样。由于会产生额外的项目，因此不可能基于“尾部”创建新版本的列表。看起来只有一种方法可以做到这一点 - 就是为每个新添加的项目从头开始重新创建列表。好的。但如何做到这一点呢？如何实现不可变双向链表的add函数？

Answer 1

不可变双向链表无法增量创建。 考虑单列表元素列表：

let singleton value = Link { value; next = End; prev = End }

由于此列表的前一个元素是

End

，因此它不能是任何具有多个元素的列表的一部分。长度为 n 的列表也存在同样的问题：此类列表不包含任何长度为 k 的列表的子列表 < n.

换句话说，要创建一个包含 n 个元素的列表，需要同时创建列表的

n

链接，如果没有突变，这是不可能的。特别是，相互递归定义是在幕后使用单个突变初始化来实现的。

但这也意味着，如果我们接受这个约束，我们可以通过使用可观察到的不可见突变来拥有双重链接持久列表：

type 'a l =
  | End
  | Link of { prev: 'a l; value:'a; next: unit -> 'a l }

在这里，将 next 的类型替换为

unit -> 'a l

为我们提供了足够的喘息空间来逐步创建列表：

let create l =
  (* precondition: when [create ref_to_prev q] is called [!ref_to_prev ()] will
     be a valid link *)
  let rec create ref_to_prev q () =
    match q with
    | [] -> End
    | value :: q ->
      (* dummy value *)
      let future_self = ref (fun () -> raise Non_initialized) in
      (* next cannot be called yet, but it has not been published yet,
         thus this is fine *)
      let next () = create future_self q in
      let self = Link {
        prev = (* precondition: this is now a valid value *)
          !ref_to_prev ();
        value;
        next;
      } in
      (* we backpatch the [prev] argument for [next], now that we have a [self] link *)
      future_self := (fun () -> self);
      (* [next] can now be called, and [self] is a valid link
         that we can publish to the outside world *)
      self
  in
  create (ref (Fun.const End)) l ()

这里，create 具有预期的类型

'a list -> 'a l

。我们可以检查我们是否具有正确的有向图结构

let rec backward_list = function
  | End -> []
  | Link l ->
    l.value :: backward_list l.prev


let rec forth_and_back = function
  | End -> []
  | Link lk as l ->
    match lk.next () with
    | End -> backward_list l
    | l ->  lk.value :: forth_and_back l

let test = forth_and_back (create [1;2;3;4])

按预期返回

[1;2;3;4;3;2;1]

。

我们有一个持久的双向链表：从外部观察不到任何变化，但列表的元素实际上存储在 thunk 中：

let next () = create future_self q in

每当我们调用时，我们都会动态构建列表的下一个元素

next

字段。 我们可以通过替换来构建一次列表

  next: unit -> 'a l;

由

  next: 'a l Lazy.t;

在类型构造函数的定义中

'a l

。