/* Some basic equational definitions. Start out with these examples to get an
   idea how Q programs look like. */

// two simple function definitions

/* Note that variables are capitalized, to distinguish them from function
   names. Function application is just juxtaposition, no parentheses are
   required. Parentheses are used for grouping expressions and tuples only.
   E.g., foo(X) is just the same as foo X, bar X Y applies a function bar to
   two parameters X and Y, while bar (X,Y) applies bar to a single argument (a
   pair) (X,Y). */

double X		= 2*X;
square X		= X*X;

// global variable definition, gives a value to a "free" variable

def PI = 4*atan 1;

// area of a circle, uses the variable from above

area R			= PI*square R;

// conditional equations (sign of a number)

/* Note that the left-hand side of an equation can be omitted to just repeat
   the left-hand side from the preceding equation. */

sign X			= -1 if X<0;
			=  0 if X=0;
			=  1 otherwise;

// ditto, with recursion (the factorial)

fact N			= N*fact (N-1) if N>0;
			= 1 otherwise;

// the same, but using tail recursion (a.k.a. "looping") with an "accumulating
// parameter"

fact_loop P N		= fact_loop (P*N) (N-1) if N>0;
			= P otherwise;

fact2 N			= fact_loop 1 N;

// local variable definitions a.k.a. "where" clauses (Fibonacci numbers)

fib N			= A where (A,B) = fibs N;
fibs N			= (B,A+B) where (A,B) = fibs (N-1) if N>0;
			= (0,1) otherwise;

/* Higher-order functions. ************************************************/

/* The filter function used in the following (as well as the foldl function
   used in the algebraic data type example below) is an example of a
   higher-order function (HOF) which is already defined in the standard
   library. The standard library contains many more such generic list
   functions which have proven to be useful in many contexts. In particular,
   you should take a look at stdlib.q in which most of these functions are
   defined. */

/* Divisibility predicate (does M divide N?). */

divides M N		= (N mod M=0);

/* Employ Erathosthenes' sieve to compute all primes up to a given number N.
   Note that the predicate `neg (divides N)' returns true iff its argument is
   _not_ divisible by N. The `neg' function is also defined in stdlib.q. It
   negates a predicate, in this case a "curried" form of the divisibility
   predicate defined above. This is used to filter the list of remaining
   candidates. */

primes N		= sieve [2..N];
sieve [N|Ns]		= [N|sieve (filter (neg (divides N)) Ns)];
sieve []		= [];

/* Algebraic data types. **************************************************/

/* A simple binary search tree data type with nil and bin constructors and an
   insertion operation. (See searchtree.q for a more elaborate example.) */

type BinTree = const nil, bin X T1 T2;

insert nil Y		= bin Y nil nil;
insert (bin X T1 T2) Y	= bin X (insert T1 Y) T2 if X>Y;
			= bin X T1 (insert T2 Y) otherwise;

// construct a tree from a list (uses the foldl function from stdlib.q)

bintree Xs		= foldl insert nil Xs;

// enumerate the members of a tree as a list, using inorder traversal

members nil		= [];
members (bin X T1 T2)	= members T1 ++ [X] ++ members T2;

/* Unlike languages like ML and Haskell, Q does _not_ have a rigid distinction
   between "constructor" and "defined" function symbols, and actually we don't
   have to explicitly declare the constructor symbols at all. However, if we
   do, then we can use the type name as a "guard" on variables, as in the
   following definition of a "tree union" operation: */

T1:BinTree + T2:BinTree	= foldl insert T1 (members T2);

// Example:

def T1 = bintree [17,5,26,5], T2 = bintree [8,17], T = T1+T2;