prelude2.pure

/*
 Dubiousjim's prelude2
*/

// permit pattern-matching on these
nonfix false true NULL inf nan;

using lists;
using trees23;
using merge;
using functor;


/*
  Using the existing {} for `nothing`.

  I'm now tempted to just use '{x}, '{x,y} etc for single x, pair x y.
  One downside: currently pattern-matching on {} crashes (fixed post-0.55)
                have to use `m::matrix = ... if null m` instead
  Another: should the nothing be {}---which would be continuous with '{x} and so on?
           or should it be ()---the result of void and so on?
  Another: printf and friends expect their argv sequences as tuples
           anything else in the stdlibs?
  Another: '{M,N} is a bit slower than pair M N, and you want M and N to be evaluated first
  Why '{x,y} is any better than '(x,y)?
     we have a nesting single: {x} ~= x, '{{x}} ~= {x}
     contiguously allocated
  Space:
    {1,2,3} is 3 cells
    '{1,2,3} is 4 cells (so too '{1,2,{3}})
    triple 1 2 3 is 7 cells (so too 1:2:3)
    '(1,2,3) is 9 cells
    [1,2,3] is 9 cells
*/

using nonsplicing;

public either either2 either3;
// contrast: e || alt, which requires e to be an int
// and: e ~== 0 || alt, which coerces e to 0 or 1
// infixr (||) |||
// def exp ||| alt = if c === 0 then alt else c when c = exp end;

// `either` expects e to be boxed in a vector
// combines unboxing and short-circuiting of alternate
// all of these are defined only on (long-enough) vectors and {}
def either e alt = fst e with
    fst v::matrix = alt if null v;
                  = v!0;
end;

def either2 e alt = snd e with
    snd v::matrix = alt if null v;
                  = v!1 if #v >= 2;
end;

def either3 e alt = trd e with
    trd v::matrix = alt if null v;
                  = v!2 if #v >= 3;
end;


// accepts non-int conditions
// note that msg is supplied by name, so it can be e.g. (sprintf fmt args...)
// and won't be invoked until the assertion fails
public assert failed_assert;
nonfix failed_assert;
def assert exp msg
    = if c === 0 then throw (failed_assert msg) else c
      when c = exp end;

/* From getopt: A macro to evaluate a series of terms and return the result of the first
   term which doesn't throw an exception. This is handy if we have to match a
   number of different expressions against corresponding patterns. Maybe this
   should go into the prelude. */
public try;
def try [x] = x;
def try (x:xs) = catch (\_->try xs) x;


public odd even log2;

type nat x::int = x>=0;
type nat x::bigint = x>=0;

type odd x::nat = x mod 2;
type even x::nat = x mod 2 == 0;
odd x = typep odd x; // turns type tag into type predicate
even x = typep even x; // could also do: `even = typep ('even)`, quoting needed to prevent looping


// from http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
namespace __C;
%<
extern int floorlog2 (unsigned int v) {
  static const char log_2[256] = {
   -1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
    5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
    6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
    6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
  };
  unsigned r = 0;
  register unsigned int t, tt;
  if ((tt = v >> 16)) {
    r = (t = tt >> 8) ? 24 + log_2[t] : 16 + log_2[tt];
  }
  else {
    r = ((t = v >> 8)) ? 8 + log_2[t] : log_2[v];
  }
  return r;
}
%>
namespace;
log2 x::int = __C::floorlog2 x if x > 0;


// http://www.haskell.org/haskellwiki/Prime_numbers#Linear_merging
// see also pure-lang mailing list starting 6 Dec 2011
primes = 2 : primes with
  primes = 3 : minus (5:7..inf) (join [p*p:p*p+2*p..inf | p = primes]) &;
  join ((x:xs):t) = x : union xs (join t) &;
  minus (x:xs) (y:ys) = x : minus  xs  (y:ys) & if x<y;
                      =     minus (x:xs)  ys    if y<x;
                      =     minus  xs     ys    otherwise;
  minus  xs     _     = xs;

  union (x:xs) (y:ys) = x : union  xs  (y:ys) & if x<y;
                      = y : union (x:xs)  ys  & if y<x;
                      = x : union  xs     ys  & otherwise;
  union  xs     []    = xs;
  union  []     ys    = ys;
end;