OCaml 中的双端队列 - 想法是什么？

Question

我遇到了 deque 的这个实现：

type 'a elem = { mutable l1 : 'a elem; mutable l2 : 'a elem; v : 'a option }
type 'a queue = { mutable front : 'a elem; mutable back : 'a elem }

let init () =
    let rec g1 = { l1 = g1; l2 = g2; v = None}
    and     g2 = { l1 = g2; l2 = g1; v = None}
    in
        { front = g1; back = g2 }

let is_empty q =
    let f = q.front
    and b = q.back
    in
        f.l2 == b

let put_between p q x =
    let r = { l1 = p; l2 = q; v = Some x }
    in begin
        if p.l1 == q then p.l1 <- r else p.l2 <- r;
        if q.l1 == p then q.l1 <- r else q.l2 <- r
    end

我不太明白这个实现的主要思想是什么，主要概念？你能给我解释一下吗？为什么我们要使用这些相互递归的记录？

Answer 1

稍微扩展一下@Lee 所说的内容，这是 double-ended queue（或双端队列）的直接可变实现，就像您用普通指针编写的语言一样（比如 C).

除了保持链接直截了当之外，我只能看到一些具体的想法。

双端队列的每一端都有一个 header（@Lee 称之为哨兵）。所以一个空的双端队列中有两个节点。由于 two-way 链接，每个节点都指向另一个节点。（这可能是您指的递归。）
因为 OCaml 是强类型的，所有节点都必须是同一类型，即使是最后的 headers。由于 header 中没有值，因此您需要使用 'a option 作为值。换句话说，您需要允许其中没有值的节点。
put_between的调用者需要提供两个相邻的节点，但它们可以按任意顺序提供。
代码使用 "physical equality" (==) 来测试节点的身份。这在 OCaml 中是一件危险的事情，但在这里是正确的。可以将可变值与 == 进行比较，结果或多或少与您在命令式语言中比较指针所期望的结果相同。

学习 OCaml 的一个原因是学习函数式编程。这段代码对此没有用，因为（正如我所说）它是一个 mutable 实现。您可以在 Chris Okasaki's PhD thesis 的第 5 章中看到一些实际的函数式双端队列实现。（你也可以买他的书，这是一个常年的最爱。）

OCaml 中的双端队列 - 想法是什么？

A double ended queue in OCaml - what's the idea?

ocaml

imperative-programming

deque