lib/mlton/queue/early.fun

   1 (* Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh
   2  *    Jagannathan, and Stephen Weeks.
   3  *
   4  * MLton is released under a BSD-style license.
   5  * See the file MLton-LICENSE for details.
   6  *)
   7 (*-------------------------------------------------------------------*)
   8 (*                            EarlyQueue                             *)
   9 (*-------------------------------------------------------------------*)
  10
  11 (* Error. on Okasaki93, Okasaki96 *)
  12
  13 (* reverses tail before it is needed *)
  14
  15 functor EarlyQueue(AR: APPEND_REVERSE): BASIC_PERSISTENT_QUEUE =
  16 struct
  17
  18 structure L = AR.L
  19 open L.I
  20
  21 datatype 'a t = T of 'a AR.t * 'a L.t
  22
  23 fun queue(l, r) =
  24    if AR.length l >= L.length r then T(l, r)
  25    else T(AR.appendReverse(l, r), L.empty())
  26
  27 fun empty() = T(AR.empty(), L.empty())
  28
  29 fun isEmpty(T(l, _)) = AR.isEmpty l
  30
  31 fun destruct(T(l, r)) =
  32    case AR.destruct l of
  33       NONE => NONE
  34     | SOME(x, l) => SOME(x, queue(l, r))
  35
  36 fun enque(T(l, r), x) = queue(l, L.cons(x, r))
  37
  38 end