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

Question

我遇到了一个双端队列的实现：

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所说的内容，这是一个双端队列（或双端队列）的直接可变实现，就像你用普通指针（如C）编写的语言一样。

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

1. 在双端队列的每一端都有一个标题（@Lee称之为哨兵）。因此空的双端队列中有两个节点。由于双向链接，每个节点指向另一个节点。 （这可能是你所指的递归。）
2. 因为OCaml是强类型的，所以节点都必须是相同的类型，甚至是最后的头。由于标题中没有值，因此需要使用'a option作为值。换句话说，您需要允许没有值的节点。
3. put_between的调用者需要提供两个相邻节点，但它们可以按任意顺序提供。
4. 代码使用“物理相等”（==）来测试节点的身份。这在OCaml中是一件危险的事情，但这里是正确的。可以将可变值与==进行比较，或多或少地比较命令式语言中指针的结果。

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