Ch4, Ex17

% First generate primes then solve hamming problem
declare
proc {Touch L N}
   if N > 0 then
      {Touch L.2 N-1}
   else skip
   end
end
fun lazy {Filter Xs F}
   case Xs of nil then nil
   [] X|Xr andthen {F X} then X|{Filter Xr F}
   [] X|Xr then {Filter Xr F}
   end
end
fun lazy {Integers N}
   N|{Integers N+1}
end
fun lazy {Sieve Xs}
   case Xs
   of nil then nil
   [] X|Xr then Ys in
      thread Ys={Filter Xr fun {$ Y} Y mod X \= 0 end} end
      X|{Sieve Ys}
   end
end
% Generate list of first k primes; k >=1
fun {GeneratePrimes K}
   Ps = {Sieve {Integers 2}}
   fun {Iter K Ps}
      if K==0 then nil
      else
         case Ps of P|Pr then P|{Iter K-1 Pr} end
      end
   end
in
   {Iter K Ps}
end

% Test, Generating first 10 primes
{Browse {GeneratePrimes 10}}

% Generalized Hamming Problem
declare
fun lazy {Times N H}
   case H of X|H2 then N*X|{Times N H2} end
end
fun lazy {Merge Xs Ys}
   case Xs#Ys of (X|Xr)#(Y|Yr) then
      if X<Y then X|{Merge Xr Ys}
      elseif X>Y then Y|{Merge Xs Yr}
      else X|{Merge Xr Yr}
      end
   end
end
fun {Hamming K}
   fun {Recur Ps H}
      case Ps of P|nil then {Times P H}
      [] P|Pr then
         {Merge {Times P H} {Recur Pr H}}
      end
   end
   H
in
   H = 1|{Recur {GeneratePrimes K} H}
   H
end

% Test, Compare results from both, they should be equal
local X in
   X = {Hamming 3}
   {Touch X 10}
   {Browse X}
end

local H in
   H=1|{Merge {Times 2 H}
         {Merge {Times 3 H}
         {Times 5 H}}}
   {Browse H}
   {Touch H 10}
end