/* Some stream programming examples. 2006-06-07 AG */
import hdict;
/* Helper function to print a stream. E.g.: `print primes'. */
print = do (\X.printf "%s\n" $ str X || flush);
/* Implicit definition of {1..}, following SICP (http://mitpress.mit.edu). */
ones = repeat 1;
ints = {1|zipwith (+) ints ones};
/* The same as a variable, evaluated lazily (with memoizing). This is much
faster since the stream is built in-place, by "chasing its own tail". This
works because Q's global variable environment uses dynamic binding, and the
(unevaluated) instance of `ints2' on the right-hand side of the definition
will not be evaluated before the variable has already been defined. Thus
the stream effectively includes a circular reference to itself. */
var ints2 = lazy {1|zipwith (+) ints2 ones};
/* Hamming sequence, using the same idea as above. (Original version
contributed 05-08-1994 by Klaus Barthelmann.) Note that if you leave out
the `var' in front then the tails grow exponentially due to the repeated
recursive invocations of `hamming', with the obvious undesirable
consequences on running time and memory requirements. */
var hamming = lazy {1|merge (map (2*) hamming)
(merge (map (3*) hamming) (map (5*) hamming))};
merge {X|Xs} {Y|Ys}
= {X|merge Xs {Y|Ys}} if XY;
= {X|merge Xs Ys} otherwise;
/* Fibonacci numbers. Again the same "chase your own tail" idea at work
here. */
var fibs = lazy {0,1|zipwith (+) fibs (tl fibs)};
/* Another implementation of the stream of Fibonacci numbers with global
hashing. */
special hashed X; def H = ref emptyhdict;
hashed X = get H!'X if member (get H) 'X;
= put H (update (get H) 'X Y) || Y where Y = X;
fibs2 = lazy {0,1|zipwith (+) (hashed fibs2) (tl (hashed fibs2))};
/* Erathosthenes' prime sieve using stream comprehensions. */
primes = sieve {2..};
sieve {N|Ns} = {N|sieve {M:M in Ns,M mod N<>0}};
/* The same without using stream comprehensions (not quite as elegant, but
faster). */
primes2 = sieve2 {2..};
sieve2 {N|Ns} = {N|sieve2 (filter (neg (divides N)) Ns)};
divides M N = (N mod M=0);
/* Another sieve algorithm. This one computes the stream of Kth powers without
using multiplication. (Contributed 04-03-1993 by Klaus Barthelmann.) */
powers K = pow_sieve K {0..} if K>=1;
pow_sieve 1 Xs = Xs;
pow_sieve K Xs = pow_sieve (K-1) (scanl (+) 0 (dropmod K 0 Xs)) if K>1;
dropmod K I {X|Xs}
= dropmod K (I+1) Xs if I mod K = 0;
= {X|dropmod K (I+1) Xs} otherwise;
/* A nice 8 queens algorithm, literal translation of a Haskell program that
can be found on the web. */
queens8 = queens 8;
queens 0 = {[]};
queens N = {[Q|B] : B in queens (N-1), Q in [0..7], safe Q B};
safe Q B = not any (checks Q B) [0..(#B-1)];
checks Q B I = (Q=B!I) or else (abs(Q-B!I)=I+1);
/* Another stream comprehension example. Compute the stream of all
permutations of the given list Xs. */
permute [] = {[]};
permute Xs = {[Y|Ys] : Y in Xs, Ys in permute (filter (neq Y) Xs)};
/* The same implemented directly, without using stream comprehensions.
Essentially, this just saves one nested map and hence is a bit faster,
but also less readable and not as straightforward to write. */
permute2 [] = {[]};
permute2 Xs = streamcat
(map (\X.map (cons X) (permute2 (filter (neq X) Xs))) Xs);