lib/mlton/queue/explicit-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 functor ExplicitAppendReverse(): APPEND_REVERSE =
   9 struct
  10
  11 structure L = StrictList
  12 structure I = L.I
  13
  14 datatype 'a t =
  15    List of 'a L.t
  16  | Cons of 'a * 'a t ref
  17  | Rotated of 'a t * 'a L.t * 'a L.t
  18
  19 fun empty() = List(L.empty())
  20
  21 exception Destruct and Rotate
  22 fun destruct(List l) = (case L.destruct l of
  23                            NONE => NONE
  24                          | SOME(x, l) => SOME(x, List l))
  25   | destruct(Cons(x, r)) = (force r ; SOME(x, !r))
  26   | destruct _ = raise Destruct
  27 and force r = (case !r of
  28                   Rotated lra => r := rotate lra
  29                 | _ => ())
  30 and rotate(l, r, a) =
  31    (case (destruct l, L.destruct r) of
  32        (NONE, SOME(x, _)) => List(L.cons(x, a))
  33      | (SOME(x, l), SOME(x', r)) =>
  34           Cons(x, ref(Rotated(l, r, L.cons(x', a))))
  35      | _ => raise Rotate)
  36
  37 fun appendReverse(l, r) = rotate(l, r, L.empty())
  38
  39 fun isEmpty r = case destruct r of
  40    NONE => true
  41  | SOME _ => false
  42
  43 fun length(List l) = L.length l
  44   | length(Rotated(l, r, a)) = length l + L.length r + L.length a
  45   | length(Cons(x, ref r)) = length r + 1
  46
  47 fun output(r, sep, outElt, out) =
  48    let val print = Out.outputc out
  49       fun outputList l = L.output(sep, outElt)(l, out)
  50       fun output(List l) = outputList l
  51         | output(Rotated(l, r, a)) = (print "Rotated(" ;
  52                                     output l ;
  53                                     print ", [" ;
  54                                     outputList r ;
  55                                     print "], " ;
  56                                     outputList a ;
  57                                     print ")")
  58         | output(Cons(x, ref r)) = (outElt(x, out) ;
  59                                    print sep ;
  60                                    output r)
  61    in output r
  62    end
  63
  64 end