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