/* stdlib.q: library of standard Q functions
   $Id: stdlib.q,v 1.10 2005/07/11 23:43:29 agraef Exp $ */

/* originally written by Albert Graef 12-31-1992 */

/* This file is part of the Q programming system.

   The Q programming system is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   The Q programming system is distributed in the hope that it will be
   useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */

/* Most of the definitions included here have been adopted from Richard Bird
   and Philip Wadler: "Introduction to Functional Programming", Prentice Hall,
   1988. Note that some of the definitions here are actually overridden by the
   clib module, but they are still in here for historical reasons. */

/* abs. Absolute value of a number: */

public abs X;
abs X:Num		= X if X>=0;
                	= -X otherwise;

/* all. Verifies that all members of a list satisfy a given predicate: */

public all P Xs;
all P []		= true;
all P [X|Xs]		= P X and then all P Xs;

/* any. Verifies that any member of a list satisfies a given predicate: */

public any P Xs;
any P []		= false;
any P [X|Xs]		= P X or else any P Xs;

/* append. Appends an element to a list or tuple: */

public append Xs Y;
append [] Y		= [Y];
append [X|Xs] Y		= [X|append Xs Y];
append () Y		= (Y,);
append (X|Xs) Y		= (X|append Xs Y);

/* apply. Applies a function to an argument: */

/* DEPRECATED -- use built-in ($) operator instead. */

public apply X Y;
apply X Y		= X Y;

/* cat. Concatenates a list of lists: */

public foldl F A Xs;

public cat Xs;
cat Xs:List		= foldl (++) [] Xs;

/* Just for the record, here's a better, i.e., a linear time implementation
   using recursive list traversal. Note that the naive implementation above
   (repeated concatenation) takes quadratic time.

   cat []		= [];
   cat [[]|Yss]		= cat Yss;
   cat [[X|Xs]|Yss]	= [X|cat [Xs|Yss]]; */

/* compose. Function composition: */

/* DEPRECATED -- use built-in (.) operator instead. */

public compose X Y;
compose X Y Z		= X (Y Z);

/* cons. Prepends an element to a list or a tuple: */

public cons X Xs;
cons X Xs:List		= [X|Xs];
cons X Xs:Tuple		= (X|Xs);

/* cst. Constant-valued function: */

public cst X;
cst X _			= X;

/* curry. Convert an uncurried function operating on pairs to a curried
   function with two arguments: */

public curry F;
curry F X Y		= F (X,Y);

/* curry3. Curry with three arguments: */

public curry3 F;
curry3 F X Y Z		= F (X,Y,Z);

/* do. Applies a function to every member of a list, returns (): */

public do F Xs;
do F []			= ();
do F [X|Xs]		= F X || do F Xs;

/* drop. Selects a final segment of a list: */

public drop N Xs;
drop N:Int []		= [];
drop N:Int [X|Xs]	= drop (N-1) Xs if N>0;
			= [X|Xs] otherwise;

/* dropwhile. Removes the longest initial segment of a list all of whose
   elements satisfy a given predicate: */

public dropwhile P Xs;
dropwhile P []          = [];
dropwhile P [X|Xs]      = dropwhile P Xs if P X;
			= [X|Xs] otherwise;

/* eq. Checks whether two terms are syntactically equal: */

public eq X Y;
eq X X			= true;
eq _ _			= false otherwise;

/* filter. Filters a list with a predicate: */

public filter P Xs;
filter P []             = [];
filter P [X|Xs]         = [X|filter P Xs] if P X;
			= filter P Xs otherwise;

/* foldl. Fold-left: */

public foldl F A Xs;
foldl F A []            = A;
foldl F A [X|Xs]        = foldl F (F A X) Xs;

/* foldl1: Fold-left over nonempty lists: */

public foldl1 F Xs;
foldl1 F [X|Xs]         = foldl F X Xs;

/* foldr. Fold-right: */

public foldr F A Xs;
foldr F A []            = A;
foldr F A [X|Xs]        = F X (foldr F A Xs);

/* foldr1. Fold-right over non-empty lists: */

public foldr1 F Xs;
foldr1 F [X]            = X;
foldr1 F [X,Y|Xs]       = F X (foldr1 F [Y|Xs]);

/* fst. Returns the first element of a tuple: */

public fst Xs;
fst (X|_)		= X;

/* hd. Returns the head element of a list: */

public hd Xs;
hd [X|_]               = X;

/* hds. Extracts all head elements from a list of lists: */

public null Xs;

public hds Xss;
hds []			= [];
hds [Xs|Xss]		= hds Xss if null Xs;
			= [hd Xs|hds Xss] otherwise;

/* id. Identity function: */

public id;
id X			= X;

/* init. Returns a list without its last element: */

public init Xs;
init [X]                = [];
init [X|Xs]             = [X|init Xs] otherwise;

/* iter. Constructs the list of the first N values A, F A, F (F A), ... */

public iter N F A;
iter N:Int F A		= [A|iter (N-1) F (F A)] if N>0;
			= [] otherwise;

/* last. Returns the last element of a list: */

public last Xs;
last [X]                = X;
last [X|Xs]             = last Xs otherwise;

/* map. Applies a function to every element of a list: */

public map F Xs;
map F []                = [];
map F [X|Xs]            = [F X|map F Xs];

/* max. Returns the maximum of two values: */

public max X Y;
max X Y                 = X if X>=Y;
                        = Y otherwise;

/* min. Returns the minimum of two values: */

public min X Y;
min X Y                 = X if X<=Y;
                        = Y otherwise;

/* mklist. Creates a list of given length: */

public mklist X N;
mklist X N:Int		= [] if N<=0;
			= [X|mklist X (N-1)] otherwise;

/* neg. Negates a predicate: */

public neg P X;
neg P X			= not P X;
				
/* neq. Checks whether two terms are syntactically inequal: */

public neq X Y;
neq X X			= false;
neq _ _			= true otherwise;

/* null. Tests whether a string, list or tuple is empty: */

public null Xs;
null ""			= true;
null _:String		= false otherwise;
null []			= true;
null _:List		= false otherwise;
null ()			= true;
null _:Tuple		= false otherwise;

/* nums. Generates a list of numbers in a given range: */

public while P F A;

public nums N M;
nums N:Num M:Num	= while (<=M) (+1) N;

/* numsby. Generates a list of numbers with a given step size: */

public numsby K N M;
numsby K:Num N:Num M:Num
			= while (<=M) (+K) N if K>0;
			= while (>=M) (+K) N if K<0;

/* pair. Constructs a pair: */

public pair X Y;
pair X Y		= (X,Y);

/* pop. Removes the head element from a list or tuple: */

public pop Xs;
pop [_|Xs]		= Xs;
pop (_|Xs)		= Xs;

/* prd. Product of a list of numbers: */

public prd Xs;
prd Xs:List		= foldl (*) 1 Xs;

/* push. Prepends an element to a list or tuple (cons with arguments
   reversed): */

public push Xs X;
push Xs:List X		= [X|Xs];
push Xs:Tuple X		= (X|Xs);

/* reverse. Reverses a list: */

public reverse Xs;
reverse Xs:List		= foldl push [] Xs;

/* scanl. Applies foldl to every initial segment of a list: */

public scanl F A Xs;
scanl F A []		= [A];
scanl F A [X|Xs]	= [A|scanl F (F A X) Xs];

/* scanl1. Applies foldl1 to every nonempty initial segment of a list: */

public scanl1 F Xs;
scanl1 F []		= [];
scanl1 F [X|Xs]		= scanl F X Xs;

/* scanr. Applies foldr to every final segment of a list: */

public scanr F A Xs;
scanr F A []		= [A];
scanr F A [X|Xs]	= [F X Y|Ys] where Ys = scanr F A Xs, [Y|_] = Ys;

/* scanr1. Applies foldr1 to every nonempty final segment of a list: */

public scanr1 F Xs;
scanr1 F []		= [];
scanr1 F [X]		= [X];
scanr1 F [X|Xs]		= [F X Y|Ys] where Ys = scanr1 F Xs, [Y|_] = Ys;

/* sgn. Sign of a number: */

public sgn X;
sgn X:Num		= 1 if X>0;
			= -1 if X<0;
			= 0 otherwise;

/* snd. Returns the second element of a tuple: */

public snd Xs;
snd (_,Y|_)		= Y;

/* sum. Sum of a list of numbers: */

public sum Xs;
sum Xs:List		= foldl (+) 0 Xs;

/* take. Selects an initial segment of a list: */

public take N Xs;
take N:Int []		= [];
take N:Int [X|Xs]	= [X|take (N-1) Xs] if N>0;
			= [] otherwise;

/* takewhile. Selects the longest initial segment of a list all of
   whose elements satisfy a given predicate: */

public takewhile P Xs;
takewhile P []          = [];
takewhile P [X|Xs]      = [X|takewhile P Xs] if P X;
                        = [] otherwise;

/* tl. Removes the head element from a list: */

public tl Xs;
tl [_|Xs]               = Xs;

/* tls. Removes all head elements from a list of lists: */

public tls Xss;
tls []			= [];
tls [Xs|Xss]		= tls Xss if null Xs;
			= [tl Xs|tls Xss] otherwise;

/* top. Returns the head element of a list or tuple: */

public top Xs;
top [X|_]		= X;
top (X|_)		= X;

/* transpose. Transposes a list of lists: */

public transpose Xss;
transpose []		= [];
transpose [Xs|Xss]	= transpose Xss if null Xs;
			= [[hd Xs|hds Xss]|transpose [tl Xs|tls Xss]]
			      otherwise;

/* trd. Returns the third element of a tuple: */

public trd Xs;
trd (_,_,Z|_)		= Z;

/* triple. Constructs a triple: */

public triple X Y Z;
triple X Y Z		= (X,Y,Z);

/* tuplecat. Concatenates a list of tuples: */

public tuplecat Xs;
tuplecat Xs:List	= foldl (++) () Xs;

/* uncurry. Convert a curried function with two arguments to an uncurried
   function operating on pairs: */

public uncurry F;
uncurry F (X,Y)		= F X Y;

/* uncurry3. Uncurry with triples: */

public uncurry3 F;
uncurry3 F (X,Y,Z)	= F X Y Z;

/* until. Applied to a predicate P, function F and a value X, repeats
   applying F to X until P is satisfied: */

public until P F X;
until P F X             = X if P X;
                        = until P F (F X) otherwise;

/* unzip. Transforms a list of pairs into a pair of lists: */

public unzip Xs;
unzip [(X,Y)|Us]	= ([X|Xs],[Y|Ys]) where (Xs,Ys) = unzip Us;
unzip []		= ([],[]);

/* unzip3. Unzip with triples: */

public unzip3 Xs;
unzip3 [(X,Y,Z)|Us]	= ([X|Xs],[Y|Ys],[Z|Zs]) where (Xs,Ys,Zs) = unzip3 Us;
unzip3 []		= ([],[],[]);

/* while. List values A, F A, F (F A), ... while a given predicate P is
   satisfied: */

public while P F A;
while P F A		= [A|while P F (F A)] if P A;
			= [] otherwise;

/* zip. Takes two lists and returns a list of corresponding pairs: */

public zip Xs Ys;
zip [X|Xs] [Y|Ys]	= [(X,Y)|zip Xs Ys];
zip _:List _:List	= [] otherwise;

/* zip3. Zip with three lists: */

public zip3 Xs Ys Zs;
zip3 [X|Xs] [Y|Ys] [Z|Zs]
			= [(X,Y,Z)|zip3 Xs Ys Zs];
zip3 _:List _:List _:List
			= [] otherwise;

/* zipwith. Takes two lists and maps a binary function to corresponding
   elements: */

public zipwith F Xs Ys;
zipwith F [X|Xs] [Y|Ys] = [F X Y|zipwith F Xs Ys];
zipwith F _:List _:List	= [] otherwise;

/* zipwith3. Zipwith with three lists: */

public zipwith3 F Xs Ys Zs;
zipwith3 F [X|Xs] [Y|Ys] [Z|Zs]
			= [F X Y Z|zipwith3 F Xs Ys Zs];
zipwith3 F _:List _:List _:List
			= [] otherwise;