NIAL(ID:1242/nia001)

• Array

matprod IS TR f g
operation a b (EACH f
((EACH g) cart (rows a)(cols b)) }
X Y ( X matprod [plus, times] Y )
76 47 42 28 26 16 20 24 80 13 81 63
46 30 26 65 39 64 96 44 26 37 14 22

Close
Listing 1
Quicksort
qsort IS OPERATION A { IF tally A <= 1 THEN
A ELSE
Firstpart := A < first A sublist A;
Secondpart := A match first A sublist A;
Thirdpart := A > first A sublist A;
link (qsort Firstpart) Secondpart (qsort Thirdpart) ENDIF }
Explanation:
IF tally A <= 1 THEN A         gives the array argument if it has only 0
or 1 element.
Firstpart is defined to be the elements of the array argument less than the first element.  Secondpart is the elements of the array argument which match the first element.  Thirdpart is the elements of the array argument which are greater than the first element,  link yields an array consisting of the elements of its arguments linked together, first those less than the first element, then those which match it, and finally those greater than the first element,  qsort Is invoked recursively on the Firstpart and Thirdpart until they are reduced to only one element.  The sorted array is displayed by omitting a semicolon from the expression link (qsort Firstpart) Secondpart (qsort Thirdpart). Q'Nial has a sort primitive, so this qsort operation is not needed but is provided to Illustrate recursion.
Time for an array consisting of 100 elements was 42 sec using the above qsort operation and 1.4 sec using the sort predefined operation of version 3.04. In version 3,06 and following, sort is to be a predefined transformer, and its performance should be improved.

Close
Quicksort
Sieve of Eratosthenes
sieve IS OPERATION N {
Candidates := rest count N;
Primes := Null;
WHILE not empty Candidates DO
Primes := Primes append first Candidates;
Candidates := not (Candidates mod first Candidates match 0)
sublist Candidates; ENDWHILE; .    -Primes }
Explanation:
count N                                      -   gives array of numerals from 1 through N.
rest count N                                   gives array of numerals from 2 through N.
Primes := Null                               initializes array Primes to empty array.
Candidates mod first Candidates
gives array of remainders after dividing
elements of Candidates by first element. Candidates ... match 0     gives a bitstring true for elements which
match 0, false otherwise, not ... match 0)                           gives bitstring with true changed to false
and false to true.
Candidates := ... sublist Candidates
. gives an array which is a sublist of Candidates consisting of the elements of Candidates which correspond to the true bits in the bitstring, and assigns it to Candidates.
Primes := Primes append first Candidates
appends the first element of the array Candidates to the array Primes.
The WHILE loop starts with an array called Candidates, consisting of the numerals from 2 through N. It first appends 2 to the array Primes, then replaces Candidates with an array consisting of the elements of the previous array not divisible by the first element of that previous array, initially 2, and appends the first element of that new array to the array Primes. The loop terminates when no more elements remain in the array Candidates.  On a Fortune 32:16 with 1MB of RAM and one user logged on, the time for N = 1000 was 51 sec.

Close
Listing 2