% 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

## Sunday, February 1, 2009

### Ch4, Ex17

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment