CODEWITHSUNDEEP
ocamllazy-evaluation
alwaysday1
alwaysday1

Reputation: 1783

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

I'm reading Purely Functional Data Structures written by Chris Okasaki.

In chapter 6, the book introduces lazy evaluation to us, I compared the two version

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

And the lazy version would be:

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

These two version are very similar, check function both needed to reverse the list, which is O(n) in theory.

It seems that both the version has the same time complexity, I'm wondering what's the advantage using lazy evaluation in Queue data structure?

Upvotes: 4

Views: 522

Answers (1)

ivg
ivg

Reputation: 35210

Lazy version of check function (and thus snoc) is actually O(1), because it performs reverse using lazy operations, i.e., (++) and reverse are both lazy. That is the place where the credit is given. You start to pay when you take head or tail. Moreover, due to hidden mutability (and laziness is actually a variant of restricted mutability) you will pay for this credit only once, even if you have different futures. There is a very interesting blog post on bankers queue (and on a batch queue) that may help you to understand why this make difference.

Upvotes: 3

Related Questions