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