Content deleted Content added
Capitalization of 1st word in cell |
|||
Line 32:
The [[Fibonacci numbers]] (naive version):
<
fib 0 = 0;
fib 1 = 1;
fib n = fib (n-2) + fib (n-1) if n>1;
</
Better ([[tail-recursive]] and [[linear-time]]) version:
<
fib n = fibs (0,1) n with
fibs (a,b) n = if n<=0 then a else fibs (b,a+b) (n-1);
end;
</
Compute the first 20 Fibonacci numbers:
<
map fib (1..20);
</
An [[algorithm]] for the [[Eight queens puzzle|n queens problem]] which employs a [[list comprehension]] to organize the backtracking search:
<
queens n = search n 1 [] with
search n i p = [reverse p] if i>n;
Line 62:
= i1==i2 || j1==j2 || i1+j1==i2+j2 || i1-j1==i2-j2;
end;
</
While Pure uses [[eager evaluation]] by default, it also supports [[Lazy evaluation|lazy]] data structures such as streams (lazy [[List (computing)|lists]]). For instance, here is a (suboptimal) trial division version of the [[Sieve of Eratosthenes#Trial division|sieve of Eratosthenes]] (attributed to [[David Turner (computer scientist)|David Turner]]<ref>Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975.</ref>) which computes the stream of all [[prime numbers]]:
<
primes = sieve (2..inf) with
sieve (p:qs) = p : sieve [q | q = qs; q mod p] &;
end;
</
Note the use of the <tt>&</tt> operator which turns the tail of the sieve into a [[thunk]] to delay its computation. The thunk is evaluated implicitly and then [[Memoization|memoized]] (using [[call by need]] evaluation) when the corresponding part of the list is accessed, e.g.:
<source>
primes!!(0..99); // yields the first 100 primes
</source>
Pure has efficient support for vectors and matrices (similar to that provided by [[MATLAB]] and [[GNU Octave]]), including vector and matrix comprehensions. E.g., a [[Gaussian elimination]] algorithm with [[partial pivoting]] can be implemented as follows in Pure:
<
gauss_elimination x::matrix = p,x
when n,m = dim x; p,_,x = foldl step (0..n-1,0,x) (0..m-1) end;
Line 113 ⟶ 115:
let x = dmatrix {2,1,-1,8; -3,-1,2,-11; -2,1,2,-3};
x; gauss_elimination x;
</
As a language based on [[term rewriting]], Pure fully supports [[symbolic computation]] with expressions. Here is an example showing the use of local rewriting rules to [[polynomial expansion|expand]] and [[factorization|factor]] simple arithmetic expressions:
<
expand = reduce with
(a+b)*c = a*c+b*c;
Line 130 ⟶ 132:
expand ((a+b)*2); // yields a*2+b*2
factor (a*2+b*2); // yields (a+b)*2
</
Calling [[C (programming language)|C]] functions from Pure is very easy. E.g., the following imports the <tt>puts</tt> function from the [[C library]] and uses it to print the string <tt>"Hello, world!"</tt> on the terminal:
| |||