在队列数据结构中使用惰性求值有什么好处？

Question

我正在阅读 Chris Okasaki 撰写的纯函数式数据结构。

书中第六章介绍了惰性求值，我比较了两个版本

(*
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)。

两个版本的时间复杂度似乎一样，我想知道在队列数据结构中使用惰性求值有什么好处？

Answer 1

惰性版本的 check 函数（因此 snoc）实际上是 O(1)，因为它使用惰性操作执行反向操作，即 (++) 和 [=13= 】都懒。那就是给予信用的地方。当您服用 head 或 tail 时，您开始付款。此外，由于隐藏的可变性（懒惰实际上是受限可变性的一种变体），即使您有不同的未来，您也只需为这笔信用支付一次。有一个非常有趣的 blog post on bankers queue（和 batch queue）可以帮助你理解为什么这会有所不同。

在队列数据结构中使用惰性求值有什么好处？

What's the advantage using lazy evaluation in Queue data structure?

ocaml

lazy-evaluation