/* General Utilities Copyright (c) 2008 by Libor Spacek */

//General mathematical iterators over one and two indices
MathIter1 op i1 i2 f = foldl1 op (map f (i1..i2));

MathIter2 op i1 i2 j1 j2 f =
                foldl1 op (map (uncurry f) [x,y | x = i1..i2; y = j1..j2]);

//Examples on how to use the mathematical iterators
Sigma i1 i2 f = MathIter1 (+) i1 i2 f;
Pi i1 i2 f = MathIter1 (*) i1 i2 f;
Factorial n = Pi 1L n id;

//Binomial using (k, n-k) symmetry and bignum division
Binomial n k = (Pi (k+1L) n id) div (Pi 2L (n-k) id) if n-k < k;
                  = (Pi (n-k+1L) n id) div (Pi 2L k id);

// Euclid's recursive greatest common factor algorithm for ints and bignums
Gcf x 0 | Gcf x 0L = x;
Gcf x y = Gcf y (x mod y);

//(2) List Processing
// take the head of a list and put it at the end
rotate (h:t) = reverse (h:(reverse t));

// take n items from the front and put them at the end (n positive 0<=n<=#n)
protate 0 l = l;
protate n::int l = cat [(drop n l),(take n l)];

// rotate n items, cf. "rotate n bits instruction" (n can now also be negative)
// example applied to clocks: >head (nrotate (-33) (0..23));
// what time is 33 hrs before midnight? Answer: 15 hrs.
nrotate  n::int l
   = protate nm l when ll = #l; nm = ll + (n mod ll) end if n<0;
        = protate nm l when nm = n mod #l end;