/* 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 X<Y;
		= {Y|merge {X|Xs} Ys} if X>Y;
		= {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);