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

proc {SetTest F}
   A = {F.insert 1 F.empty}
   B = {F.insert 2 A}
   C = {F.insert 4 B}
   D = {F.insert 3 C}
in
   {Browse D}
   {Browse {F.member 3 D}}
   {Browse {F.member 5 D}}
end

% 2.1 Stack
STACK =
   functor
   export
      empty   : Empty
      isEmpty : IsEmpty
      cons    : Cons
      head    : Head
      tail    : Tail
   define
      Empty = nil
      fun {IsEmpty L} L == Empty end
      fun {Cons X L} X|L end
      fun {Head L} L.1 end
      fun {Tail L} L.2 end
   end

[Stack] = {Module.apply [STACK]}

{StackTest Stack}

CUSTOMSTACK =
   functor
   export
      empty   : Empty
      isEmpty : IsEmpty
      cons    : Cons
      head    : Head
      tail    : Tail
   define
      Empty = nil
      fun {IsEmpty L} L == Empty end
      fun {Cons X L} cons(X L) end
      fun {Head L}
         case L
         of cons(H T) then H
         else raise empty end
         end
      end
      fun {Tail L}
         case L
         of cons(H T) then T
         else raise empty end
         end
      end
   end

[CustomStack] = {Module.apply [CUSTOMSTACK]}

{StackTest CustomStack}

fun {Append1 L1 L2}
   if {Stack.isEmpty L1} then
      L2
   else
      {Stack.cons {Stack.head L1} {Append1 {Stack.tail L1} L2}}
   end
end

fun {Append2 L1 L2}
   case L1
   of H|T then H|{Append2 T L2}
   else L2
   end
end

fun {Update L I X}
   case L
   of H|T then
      if I == 0 then
         X|T
      else
         H|{Update T I-1 X}
      end
   else raise subscript end
   end
end

% 2.2 UnbalancedSet
UNBALANCEDSET =
   functor
   export
      initialize : Initialize
      empty      : Empty
      member     : Member
      insert     : Insert
   define
      Element
      proc {Initialize OrderedSet} Element = OrderedSet end
      Empty = nil
      fun {Member X Set}
         case Set
         of tree(A Y B) then
            if {Element.lt X Y} then
               {Member X A}
            elseif {Element.lt Y X} then
               {Member X B}
            else
               true
            end
         else false
         end
      end
      fun {Insert X Set}
         case Set
         of nil then tree(nil X nil)
         [] tree(A Y B) then
            if {Element.lt X Y} then
               tree({Insert X A} Y B)
            elseif {Element.lt Y X} then
               tree(A Y {Insert X B})
            else
               Set
            end
         end
      end
   end

ORDEREDVALUE =
   functor
   export
      eq : EQ
      lt : LT
      leq : LEQ
   define
      fun {EQ X Y} X == Y end
      fun {LT X Y} X < Y end
      fun {LEQ X Y} X =< Y end
   end
[OrderedValue] = {Module.apply [ORDEREDVALUE]}

[UnbalancedSet] = {Module.apply [UNBALANCEDSET]}
{UnbalancedSet.initialize OrderedValue}
{SetTest UnbalancedSet}