ocaml - 在 Queue 数据结构中使用惰性求值有什么好处？

Question

我正在阅读 Chris Okasaki 编写的 Purely Functional Data Structures。

在第 6 章，本书向我们介绍了惰性求值，我比较了两个版本

(*
https://github.com/mmottl/pure-fun/blob/master/chp5.ml#L47
*)
module BatchedQueue : QUEUE = struct
  type 'a queue = 'a list * 'a list

  let empty = [], []
  let is_empty (f, _) = f = []

  let checkf (f, r as q) = if f = [] then List.rev r, f else q

  let snoc (f, r) x = checkf (f, x :: r)
  let head = function [], _ -> raise Empty | x :: _, _ -> x
  let tail = function [], _ -> raise Empty | _ :: f, r -> checkf (f, r)
end

懒惰的版本是:

(*
https://github.com/mmottl/pure-fun/blob/master/chp6.ml#L128
*)
module BankersQueue : QUEUE = struct
  type 'a queue = int * 'a stream * int * 'a stream

  let empty = 0, lazy Nil, 0, lazy Nil
  let is_empty (lenf, _, _, _) = lenf = 0

  let check (lenf, f, lenr, r as q) =
    if lenr <= lenf then q
    else (lenf + lenr, f ++ reverse r, 0, lazy Nil)

  let snoc (lenf, f, lenr, r) x =
    check (lenf, f, lenr + 1, lazy (Cons (x, r)))

  let head = function
    | _, lazy Nil, _, _ -> raise Empty
    | _, lazy (Cons (x, _)), _, _ -> x

  let tail = function
    | _, lazy Nil, _, _ -> raise Empty
    | lenf, lazy (Cons (_, f')), lenr, r -> check (lenf - 1, f', lenr, r)
end

这两个版本非常相似，check函数都需要反转列表，理论上是 O(n)。

似乎这两个版本具有相同的时间复杂度，我想知道在 Queue 数据结构中使用惰性求值有什么好处？

Answer 1

懒人版check函数(因此 snoc )实际上是 O(1)，因为它使用惰性操作执行反向操作，即 (++)和 reverse都是懒惰的。那是给予信用的地方。拿走就开始付钱head或 tail .此外，由于隐藏的可变性(懒惰实际上是受限可变性的一种变体)，即使您有不同的 future ，您也只需为此信用支付一次。有一个很有趣的blog post在银行家队列(和批处理队列)上，这可能会帮助您理解为什么这会有所不同。