About PFDS The following Oz code is derived from the examples provided in the book:
      "Purely Functional Data Structures" by Chris Okasaki.
      http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html

PFDS Chapter #08 Examples in Oz
% Utility functions for tests
proc {QueueTest F}
   A = F.empty
   B = {F.snoc A 1}
   C = {F.snoc B 2}
   D = {F.snoc C 3}
in
   {Browse D}
   {Browse {F.head D}}
   {Browse {F.head {F.tail D}}}
   {Browse {F.head {F.tail {F.tail D}}}}
end

proc {DequeTest F}
   A = F.empty
   B = {F.cons 2 A}
   C = {F.snoc B 1}
   D = {F.cons 3 C}
in
   {Browse D}
   {Browse {F.head D}}
   {Browse {F.head {F.tail D}}}
   {Browse {F.head {F.tail {F.tail D}}}}
   {Browse {F.last D}}
   {Browse {F.last {F.init D}}}
   {Browse {F.last {F.init {F.init D}}}}
end

% 8.2 HoodMelvilleQueue
HOODMELVILLEQUEUE =
   functor
   export
      empty   : Empty
      isEmpty : IsEmpty
      snoc    : Snoc
      head    : Head
      tail    : Tail
   define
      Empty = 0#nil#idle#0#nil
      fun {IsEmpty Q=LenF#F#State#LenR#R}
         LenF == 0
      end
      fun {Exec State}
         case State
         of reversing(Ok X|F Fp Y|R Rp) then reversing(Ok+1 F X|Fp R Y|Rp)
         [] reversing(Ok nil Fp [Y] Rp) then appending(Ok Fp Y|Rp)
         [] appending(0 Fp Rp) then done(Rp)
         [] appending(Ok X|Fp Rp) then appending(Ok-1 Fp X|Rp)
         else State
         end
      end
      fun {Invalidate State}
         case State
         of reversing(Ok F Fp R Rp) then reversing(Ok-1 F Fp R Rp)
         [] appending(0 Fp X|Rp) then done(Rp)
         [] appending(Ok Fp Rp) then appending(Ok-1 Fp Rp)
         else State
         end
      end
      fun {Exec2 Q=LenF#F#State#LenR#R}
         case {Exec {Exec State}}
         of done(NewF) then LenF#NewF#idle#LenR#R
         [] NewState then LenF#F#NewState#LenR#R
         end
      end
      fun {Check Q=LenF#F#State#LenR#R}
         if LenR =< LenF then
            {Exec2 Q}
         else
            local
               NewState = reversing(0 F nil R nil)
            in
               {Exec2 (LenF+LenR)#F#NewState#0#nil}
            end
         end
      end
      fun {Snoc Q=LenF#F#State#LenR#R X}
         {Check LenF#F#State#(LenR+1)#(X|R)}
      end
      fun {Head Q=LenF#F#State#LenR#R}
         case F
         of H|T then H
         else raise empty end
         end
      end
      fun {Tail Q=LenF#F#State#LenR#R}
         case F
         of H|T then {Check (LenF-1)#T#{Invalidate State}#LenR#R}
         else raise empty end
         end
      end
   end

[HoodMelvilleQueue] = {Module.apply [HOODMELVILLEQUEUE]}

{QueueTest HoodMelvilleQueue}

% 8.4 BankersDeque
BANKERSDEQUE =
   functor
   export
      initialize : Initialize
      empty   : Empty
      isEmpty : IsEmpty
      cons    : Cons
      head    : Head
      tail    : Tail
      snoc    : Snoc
      last    : Last
      init    : Init
   define
      C
      proc {Initialize Cx} C = Cx end
      Empty = 0#nil#0#nil
      fun {IsEmpty Q=LenF#F#LenR#R}
         LenF+LenR == 0
      end
      fun {Check Q=LenF#F#LenR#R}
         if LenF > C*LenR+1 then
            local
               I = (LenF+LenR) div 2
               J = LenF + LenR - I
               Fp = {List.take F I}
               Rp = {Append R {Reverse {List.drop F I}}}
            in
               I#Fp#J#Rp
            end
         elseif LenR > C*LenF + 1 then
            local
               J = (LenF+LenR) div 2
               I = LenF + LenR - J
               Rp = {List.take R J}
               Fp = {Append F {Reverse {List.drop R J}}}
            in
               I#Fp#J#Rp
            end
         else
            Q
         end
      end
      fun {Cons X Q=LenF#F#LenR#R}
         {Check (LenF+1)#(X|F)#LenR#R}
      end
      fun {Head Q=LenF#F#LenR#R}
         case F#R
         of nil#nil then raise empty end
         [] nil#(X|_) then X
         [] (X|Fp)#_ then X
         end
      end
      fun {Tail Q=LenF#F#LenR#R}
         case F#R
         of nil#nil then raise empty end
         [] nil#(X|_) then nil
         [] (X|Fp)#_ then {Check (LenF-1)#Fp#LenR#R}
         end
      end
      fun {Snoc Q=LenF#F#LenR#R X}
         {Check LenF#F#(LenR+1)#(X|R)}
      end
      fun {Last Q=LenF#F#LenR#R}
         case F#R
         of nil#nil then raise empty end
         [] (X|_)#nil then X
         [] _#(X|Fp) then X
         end
      end
      fun {Init Q=LenF#F#LenR#R}
         case F#R
         of nil#nil then raise empty end
         [] (X|_)#nil then nil
         [] _#(X|Rp) then {Check LenF#F#(LenR-1)#Rp}
         end
      end
   end

[BankersDeque] = {Module.apply [BANKERSDEQUE]}
{BankersDeque.initialize 2}

{DequeTest BankersDeque}

% 8.4 RealTimeDeque
REALTIMEDEQUE =
   functor
   export
      initialize : Initialize
      empty   : Empty
      isEmpty : IsEmpty
      cons    : Cons
      head    : Head
      tail    : Tail
      snoc    : Snoc
      last    : Last
      init    : Init
   define
      C
      proc {Initialize Cx} C = Cx end
      Empty = 0#nil#nil#0#nil#nil
      fun {IsEmpty Q=LenF#F#Sf#LenR#R#Sr}
         LenF+LenR == 0
      end
      fun {Exec1 S}
         case S
         of H|T then T
         else S
         end
      end
      fun {Exec2 S}
         {Exec1 {Exec1 S}}
      end
      fun {RotateRev S R A}
         case S
         of nil then {Append {List.reverse R} A}
         [] H|T then
            {fun lazy {$} H|{Append {RotateRev T {List.drop R C} {List.reverse {List.take R C}}} A} end}
         end
      end
      fun {RotateDrop F J R}
         if J < C then
            {RotateRev F {List.drop R J} nil}
         else
            local
               X|Fp = F
            in
               {fun lazy {$} X|{RotateDrop Fp J-C {List.drop R C}} end}
            end
         end
      end
      fun {Check Q=LenF#F#Sf#LenR#R#Sr}
         if LenF > C*LenR+1 then
            local
               I = (LenF+LenR) div 2
               J = LenF+LenR-I
               Fp = {List.take F I}
               Rp = {RotateDrop R I F}
            in
               I#Fp#Fp#J#Rp#Rp
            end
         elseif LenR > C*LenF+1 then
            local
               J = (LenF+LenR) div 2
               I = LenF+LenR-J
               Rp = {List.take R J}
               Fp = {RotateDrop F J R}
            in
               I#Fp#Fp#J#Rp#Rp
            end
         else
            Q
         end
      end
      fun {Cons X Q=LenF#F#Sf#LenR#R#Sr}
         {Check (LenF+1)#(X|F)#{Exec1 Sf}#LenR#R#{Exec1 Sr}}
      end
      fun {Head Q=LenF#F#Sf#LenR#R#Sr}
         case F#R
         of nil#nil then raise empty end
         [] nil#(X|_) then X
         [] (X|Fp)#_ then X
         end
      end
      fun {Tail Q=LenF#F#Sf#LenR#R#Sr}
         case F#R
         of nil#nil then raise empty end
         [] nil#(X|_) then nil
         [] (X|Fp)#_ then {Check (LenF-1)#Fp#{Exec2 Sf}#LenR#R#{Exec2 Sr}}
         end
      end
      fun {Snoc Q=LenF#F#Sf#LenR#R#Sr X}
         {Check LenF#F#{Exec1 Sf}#(LenR+1)#(X|R)#{Exec1 Sr}}
      end
      fun {Last Q=LenF#F#Sf#LenR#R#Sr}
         case F#R
         of nil#nil then raise empty end
         [] (X|_)#nil then X
         [] _#(X|Rp) then X
         end
      end
      fun {Init Q=LenF#F#Sf#LenR#R#Sr}
         case F#R
         of nil#nil then raise empty end
         [] (X|_)#nil then nil
         [] _#(X|Rp) then {Check LenF#F#{Exec2 Sf}#(LenR-1)#Rp#{Exec2 Sr}}
         end
      end
   end

[RealTimeDeque] = {Module.apply [REALTIMEDEQUE]}
{RealTimeDeque.initialize 2}

{DequeTest RealTimeDeque}

Chris Rathman / Chris.Rathman@tx.rr.com