1

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

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

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

4

1 回答 1

3

为了稍微扩展@Lee 所说的内容，这是一个双端队列（或双端队列）的简单可变实现，就像您用普通指针（如 C）用语言编写的代码一样。

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

  1. 双端队列的每一端都有一个标头（@Lee 称之为哨兵）。所以一个空的双端队列中有两个节点。由于双向联动，每个节点都指向另一个节点。（这可能是您所指的递归。）

  2. 因为 OCaml 是强类型的，所以所有节点都必须是相同的类型，即使是最后的标头。由于标头中没有值，因此您需要使用'a option该值。换句话说，您需要允许其中没有任何值的节点。

  3. 调用者put_between需要提供两个相邻节点，但它们可以按任意顺序提供。

  4. 该代码使用“物理相等”（==）来测试节点的身份。这在 OCaml 中是一件危险的事情，但在这里是正确的。可变值可以与==在命令式语言中比较指针所期望的或多或少的结果进行比较。

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

于 2015-11-27T17:53:37.750 回答