/* 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;