TRS Chapter #05 Examples in Oz

      %%%%%%%%%%%%%%%%%%%%%%%%%%% From CTM Chapter 9 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

      % Lazy problem solving (Solve)

      % This is the Solve operation, which returns a lazy list of solutions
      % to a relational program.  The list is ordered according to a
      % depth-first traversal.  Solve is written using the computation space
      % operations of the Space module.

      fun {Solve Script}
         {SolStep {Space.new Script} nil}
      end

      fun {SolStep S Rest}
         case {Space.ask S}
         of failed then Rest
         [] succeeded then {Space.merge S}|Rest
         [] alternatives(N) then
            {SolLoop S 1 N Rest}
         end
      end

      fun lazy {SolLoop S I N Rest}
         if I>N then Rest
         elseif I==N then
            {Space.commit S I}
            {SolStep S Rest}
         else Right C in
            Right={SolLoop S I+1 N Rest}
            C={Space.clone S}
            {Space.commit C I}
            {SolStep C Right}
         end
      end

      fun {SolveOne F}
         L = {Solve F}
      in
         if L==nil then nil else [L.1] end
      end

      fun {SolveAll F}
         L = {Solve F}
         proc {TouchAll L}
            if L==nil then skip else {TouchAll L.2} end
         end
      in
         {TouchAll L}
         L
      end

      fun {SolveN N F}
         L = {Solve F}
      in
         {List.take L N}
      end

      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 5.2
fun {AppendTRS L S}
   case L
   of nil then S
   [] H|T then H|{AppendTRS T S}
   else fail
   end
end

{Browse 2#{AppendTRS [a b c] [d e]}}

% 5.3
{Browse 3#{AppendTRS [a b c] nil}}

% 5.4
{Browse 4#{AppendTRS nil [d e]}}

% 5.5
try
   _ = {AppendTRS a [d e]}
catch _ then
   skip
end

% 5.6
{Browse 6#{AppendTRS [d e] a}}

% 5.9
fun {Appendo L S Out}
   choice
      S = Out
      L = nil
   [] H T Res in
      L = H|T
      _ = {Appendo T S Res}
      H|Res = Out
   end
end

% 5.10
{Browse 10#
   {SolveAll fun {$} X in {Appendo [cake] [tastes yummy] X} end}}

% 5.11
{Browse 11#
   {SolveAll fun {$} X Y in {Appendo [cake with ice Y] [tastes yummy] X} end}}

% 5.12
{Browse 12#
   {SolveAll fun {$} X Y in {Appendo [cake with ice cream] Y X} end}}

% 5.13
{Browse 13#
   {SolveOne fun {$} X Y in {Appendo cake|with|ice|cream|Y [d t] X} end}}

% 5.14
{Browse 14#
   {SolveOne fun {$} X Y in _ = {Appendo cake|with|ice|cream|Y [d t] X} Y end}}

% 5.16
{Browse 16#
   {SolveN 5 fun {$} X Y in {Appendo cake|with|ice|cream|Y [d t] X} end}}

% 5.17
{Browse 17#
   {SolveN 5 fun {$} X Y in _ = {Appendo cake|with|ice|cream|Y [d t] X} Y end}}

% 5.20
{Browse 20#
   {SolveN 5 fun {$} X Y in {Appendo cake|with|ice|Y [d t Y] X} end}}

% 5.21
{Browse 21#
   {SolveAll fun {$} X Z in {Appendo [cake with ice cream] d|t|Z X} end}}

% 5.23
{Browse 23#
   {SolveN 6 fun {$} X Y in _ = {Appendo X Y [cake with ice d t]} X end}}

% 5.25
{Browse 25#
   {SolveN 6 fun {$} X Y in _ = {Appendo X Y [cake with ice d t]} Y end}}

% 5.27
{Browse 27#
   {SolveN 6
      fun {$} R X Y in
         _ = {Appendo X Y [cake with ice d t]}
         [X Y] = R
      end}}

% 5.29
%% {Browse 29#
%    {SolveN 7
%%       fun {$} R X Y in
%          _ = {Appendo X Y [cake with ice d t]}
%%          [X Y] = R
%       end}}

% 5.31
fun {Appendo2 L S Out}
   choice
      S = Out
      L = nil
   [] H T Res in
      L = H|T
      H|Res = Out
      {Appendo2 T S Res}
   end
end

% 5.32
{Browse 32#
   {SolveN 7
      fun {$} R X Y in
         _ = {Appendo2 X Y [cake with ice d t]}
         [X Y] = R
      end}}

% 5.33
{Browse 33#
   {SolveN 7
      fun {$} X Y Z in
         _ = {Appendo2 X Y Z}
         X
      end}}

% 5.34
{Browse 34#
   {SolveN 7
      fun {$} X Y Z in
         _ = {Appendo2 X Y Z}
         Y
      end}}

% 5.36
{Browse 36#
   {SolveN 7
      fun {$} X Y Z in
         _ = {Appendo2 X Y Z}
         Z
      end}}

% 5.37
{Browse 37#
   {SolveN 7
      fun {$} X Y Z in
         _ = {Appendo2 X Y Z}
         Z
      end}}

% 5.38
fun {Swappendo L S Out}
   choice
      H T Res in
      L = H|T
      H|Res = Out
      {Swappendo T S Res}
   [] S = Out
      L = nil
   end
end

% 5.39
%% {Browse 39#
%    {SolveOne
%%       fun {$} X Y Z in
%          _ = {Swappendo X Y Z}
%%          Z
%       end}}

% 5.41
fun {Unwrap X}
   case X
   of H|_ then {Unwrap X.1}
   else X
   end
end
{Browse 41#{Unwrap [[[[pizza]]]]}}

% 5.42
{Browse 42#{Unwrap [[[[pizza pie] with]] extra cheese]}}

% 5.45
fun {Unwrapo X Out}
   choice
      H in
      X = H|_
      {Unwrapo H Out}
   [] X = Out
   end
end

% 5.46
{Browse 46#{SolveAll fun {$} X in {Unwrapo [[[pizza]]] X} end}}

% 5.48
%%{Browse 48#{SolveOne fun {$} X in {Unwrapo X pizza} end}}

% 5.49
%%{Browse 48#{SolveOne fun {$} X in {Unwrapo [[X]] pizza} end}}

% 5.52
fun {Unwrapo2 X Out}
   choice
      X = Out
   [] H in
      X = H|_
      {Unwrapo2 H Out}
   end
end

% 5.53
{Browse 53#{SolveN 5 fun {$} X in _ = {Unwrapo2 X pizza} X end}}

% 5.54
{Browse 54#{SolveN 5 fun {$} X in _ = {Unwrapo2 X [[pizza]]} X end}}

% 5.55
{Browse 55#{SolveN 5 fun {$} X in _ = {Unwrapo2 [[X]] pizza} X end}}

% 5.58
fun {Flatten S}
   case S
   of nil then nil
   [] H|T then {AppendTRS {Flatten H} {Flatten T}}
   else [S]
   end
end
{Browse 58#{Flatten [[a b] c]}}

% 5.59
fun {Flatteno S Out}
   choice
      S = nil
      nil = Out
   [] H T ResH ResT in
      S = H|T
      _ = {Flatteno H ResH}
      _ = {Flatteno T ResT}
      {Appendo ResH ResT Out}
   [] [S] = Out
   end
end

% 5.60
{Browse 60#{SolveOne fun {$} X in {Flatteno [[a b] c] X} end}}

% 5.61
{Browse 61#{SolveOne fun {$} X in {Flatteno [a [b c]] X} end}}

% 5.62
{Browse 62#{SolveAll fun {$} X in {Flatteno [a] X} end}}

% 5.64
{Browse 64#{SolveAll fun {$} X in _ = {Flatteno [[a]] X} X end}}

% 5.66
{Browse 66#{SolveAll fun {$} X in _ = {Flatteno [[[a]]] X} X end}}

% 5.68
{Browse 68#{SolveAll fun {$} X in _ = {Flatteno [[a b] c] X} X end}}

% 5.71
%%{Browse 71#{SolveAll fun {$} X in _ = {Flatteno X [a b c]} X end}}

% 5.73
fun {Flattenrevo S Out}
   choice
      [S] = Out
   [] S = nil
      nil = Out
   [] H T ResH ResT in
      S = H|T
      _ = {Flattenrevo H ResH}
      _ = {Flattenrevo T ResT}
      {Appendo ResH ResT Out}
   end
end

% 5.75
{Browse 75#{SolveAll fun {$} X in _ = {Flattenrevo [[a b] c] X} X end}}

% 5.76
{Browse 76#{Reverse {SolveAll fun {$} X in _ = {Flattenrevo [[a b] c] X} X end}}}

% 5.77
{Browse 77#{SolveN 2 fun {$} X in _ = {Flattenrevo X [a b c]} X end}}

% 5.79
%%{Browse 79#{SolveN 3 fun {$} X in _ = {Flattenrevo X [a b c]} X end}}

% 5.80
{Browse 80#{Length {SolveAll fun {$} X in _ = {Flattenrevo [[[[a [[[b]]] c]]] d] X} X end}}}