lib/mlton/queue/append-reverse.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 (*                           AppendReverse                           *)
   9 (*-------------------------------------------------------------------*)
  10
  11 functor LazyAppendReverse(): APPEND_REVERSE =
  12 struct
  13
  14 structure L' = LazyListLength(LazyList)
  15
  16 open L'
  17
  18 structure L = L'
  19
  20 end
  21
  22 functor IncrementalAppendReverse(): APPEND_REVERSE =
  23 struct
  24
  25 structure L' = LazyListLength(LazyList)
  26
  27 open L'
  28
  29 val appendReverse = L'.appendReverseIncremental
  30
  31 structure L = L'
  32
  33 end
  34
  35 functor ExplicitAppendReverse(): APPEND_REVERSE =
  36 struct
  37
  38 val {error, ...} = Error.errors("queue", "append-reverse")
  39
  40 structure L = StrictList
  41 structure I = L.I
  42
  43 datatype 'a t =
  44    List of 'a L.t
  45  | Cons of 'a * 'a t ref
  46  | Rot of 'a t * 'a L.t * 'a L.t
  47
  48 fun empty() = List(L.empty())
  49
  50 fun destruct(List l) = (case L.destruct l of
  51                            NONE => NONE
  52                          | SOME(x, l) => SOME(x, List l))
  53   | destruct(Cons(x, r)) = (force r ; SOME(x, !r))
  54   | destruct _ = error "destruct"
  55 and force r = (case !r of
  56                   Rot lra => r := rot lra
  57                 | _ => ())
  58 and rot(l, r, a) =
  59    (case (destruct l, L.destruct r) of
  60        (NONE, SOME(x, _)) => List(L.cons(x, a))
  61      | (SOME(x, l), SOME(x', r)) =>
  62           Cons(x, ref(Rot(l, r, L.cons(x', a))))
  63      | _ => error "rot")
  64
  65 fun appendReverse(l, r) = rot(l, r, L.empty())
  66
  67 fun isEmpty r = case destruct r of
  68    NONE => true
  69  | SOME _ => false
  70
  71 fun length(List l) = L.length l
  72   | length(Rot(l, r, a)) = length l + L.length r + L.length a
  73   | length(Cons(x, ref r)) = length r + 1
  74
  75 fun output(r, sep, outElt, out) =
  76    let val print = Out.outputc out
  77       fun outputList l = L.output(l, sep, outElt, out)
  78       fun output(List l) = outputList l
  79         | output(Rot(l, r, a)) = (print "Rot(" ;
  80                                 output l ;
  81                                 print ", [" ;
  82                                 outputList r ;
  83                                 print "], " ;
  84                                 outputList a ;
  85                                 print ")")
  86         | output(Cons(x, ref r)) = (outElt(x, out) ;
  87                                    print sep ;
  88                                    output r)
  89    in output r
  90    end
  91
  92 end