Ch3, Ex16

% Using name Convolute1 as Convolute is already
% there in mozart system

declare Append Convolute1 Reverse

%copied from exercise-9
local IterReverse MyAppend in
   fun {MyAppend L1 L2}
      case L1 of nil then L2
      [] X|Y then {MyAppend Y X|L2}
      end
   end
   fun {IterReverse X Y}
      case X of nil then Y
      [] X1|X2 then {IterReverse X2 X1|Y}
      end
   end
   fun{Append Xs Ys}
      {MyAppend {IterReverse Xs nil} Ys}
   end
   fun {Reverse Xs}
      {IterReverse Xs nil}
   end   
end

% Notice the use of dataflow variable Y to make it
% tail-recursive
local
   proc {Convolute2 L1 L2 ?L3}
      case L1 of nil then L3 = nil
      [] XL1|YL1 then XL2 YL2 Y in
         L2 = XL2|YL2
         L3 = {Append [XL1#XL2] Y}
         {Convolute2 YL1 YL2 Y}
      end
   end
in
   fun {Convolute1 L1 L2}
      X in
      {Convolute2 L1 {Reverse L2} X}
      X
   end
end


{Browse {Convolute1 [1 2 3] [1 2 3]}}


/* Another iterative convolute without dataflow
   variable, notice the use of accumulator
   programming. In each recursive call we
   keep on modifying state variable S1, when base
   case is reached, we say its the final state
   by making Sn = S1 */
local
   proc {Convolute2 L1 L2 ?S1 ?Sn}
      case L1 of nil then Sn = S1
      [] XL1|YL1 then XL2 YL2 in
         L2 = XL2|YL2
         {Convolute2 YL1 YL2 {Append [XL1#XL2] S1} Sn}
      end
   end
in
   fun {Convolute1 L1 L2}
      X in
      {Convolute2 L1 {Reverse L2} nil X}
      X
   end
end