Thread: [pure-lang-svn] SF.net SVN: pure-lang:[857] pure/trunk/pure.1.in (Page 3)
Status: Beta
Brought to you by:
agraef
|
From: <ag...@us...> - 2008-09-25 09:22:02
|
Revision: 857
http://pure-lang.svn.sourceforge.net/pure-lang/?rev=857&view=rev
Author: agraef
Date: 2008-09-25 09:19:21 +0000 (Thu, 25 Sep 2008)
Log Message:
-----------
Update documentation.
Modified Paths:
--------------
pure/trunk/pure.1.in
Modified: pure/trunk/pure.1.in
===================================================================
--- pure/trunk/pure.1.in 2008-09-25 09:06:41 UTC (rev 856)
+++ pure/trunk/pure.1.in 2008-09-25 09:19:21 UTC (rev 857)
@@ -1189,7 +1189,7 @@
a amounts to mapping the function \ex->a*x to x, which can be done as follows:
.sp
.nf
-> a::int * x::matrix = map (\ex->a*x) x;
+> a * x::matrix = map (\ex->a*x) x \fBif\fP not matrixp a;
> 2*{1,2,3;4,5,6};
{2,4,6;8,10,12}
.fi
@@ -1254,27 +1254,20 @@
equations. The algorithm brings a matrix into ``row echelon'' form, a
generalization of triangular matrices. The resulting system can then be solved
quite easily using back substitution. Here is a Pure implementation of the
-algorithm (please refer to any good textbook on numeric mathematics for a
-closer description of the algorithm):
+algorithm:
.sp
.nf
gauss_elimination x::matrix = p,x
\fBwhen\fP n,m = dim x; p,_,x = foldl step (0..n-1,0,x) (0..m-1) \fBend\fP;
-.fi
-.PP
-The actual pivoting and elimination step is a bit involved. x is our matrix, i
-the current row index, j the current column index, and p keeps track of the
-current permutation of the row indices performed during pivoting. The
-algorithm returns the updated matrix x, row index i and row permutation p.
-.sp
-.nf
+
+// One pivoting and elimination step in column j of the matrix:
step (p,i,x) j
= \fBif\fP max_x>0 \fBthen\fP
// updated row permutation and index:
transp i max_i p, i+1,
{// the top rows of the matrix remain unchanged:
x!!(0..i-1,0..m-1);
- // the pivot row, divided by the pivot:
+ // the pivot row, divided by the pivot element:
{x!(i,l)/x!(i,j) | l=0..m-1};
// subtract suitable multiples of the pivot row:
{x!(k,l)-x!(k,j)*x!(i,l)/x!(i,j) | k=i+1..n-1; l=0..m-1}}
@@ -1288,9 +1281,28 @@
\fBend\fP;
.fi
.PP
-We also need the following little helper functions to swap two rows of a
-matrix (this is used in the pivoting step above) and to apply a transposition
-to a permutation (represented as a list):
+The real meat is in the pivoting and elimination step ('step' function) which
+is iterated over all columns of the input matrix. In each step, x is the
+current matrix, i the current row index, j the current column index, and p
+keeps track of the current permutation of the row indices performed during
+pivoting. The algorithm returns the updated matrix x, row index i and row
+permutation p.
+.PP
+Please refer to any good textbook on numeric mathematics for a closer
+description of the algorithm. But here is a brief rundown of what happens in
+each elimination step: First we find the pivot element in column j of the
+matrix. (We're doing partial pivoting here, i.e., we only look for the element
+with the largest absolute value in column j, starting at row i. That's usually
+good enough to achieve numerical stability.) If the pivot is zero then we're
+done (the rest of the pivot column is already zeroed out). Otherwise, we bring
+it into the pivot position (swapping row i and the pivot row), divide the
+pivot row by the pivot, and subtract suitable multiples of the pivot row to
+eliminate the elements of the pivot column in all subsequent rows. Finally we
+update i and p accordingly and return the result.
+.PP
+In order to complete the implementation, we still need the following little
+helper functions to swap two rows of a matrix (this is used in the pivoting
+step) and to apply a transposition to a permutation (represented as a list):
.sp
.nf
swap x i j = x!!(transp i j (0..n-1),0..m-1) \fBwhen\fP n,m = dim x \fBend\fP;
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <ag...@us...> - 2008-09-25 09:36:52
|
Revision: 858
http://pure-lang.svn.sourceforge.net/pure-lang/?rev=858&view=rev
Author: agraef
Date: 2008-09-25 09:36:44 +0000 (Thu, 25 Sep 2008)
Log Message:
-----------
Update documentation.
Modified Paths:
--------------
pure/trunk/pure.1.in
Modified: pure/trunk/pure.1.in
===================================================================
--- pure/trunk/pure.1.in 2008-09-25 09:19:21 UTC (rev 857)
+++ pure/trunk/pure.1.in 2008-09-25 09:36:44 UTC (rev 858)
@@ -1239,9 +1239,9 @@
vectors aren't the same size then you'll get an `out_of_bounds' exception with
the definition above.)
.PP
-The matrix product now boils down to a simple matrix comprehension which just
-multiplies all rows of x with all columns of y (the rows and cols functions
-are prelude operations found in matrices.pure):
+The general matrix product now boils down to a simple matrix comprehension
+which just multiplies all rows of x with all columns of y (the rows and cols
+functions are prelude operations found in matrices.pure):
.sp
.nf
> x::matrix * y::matrix = {u*v | u = rows x; v = cols y};
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <ag...@us...> - 2008-09-25 10:48:27
|
Revision: 862
http://pure-lang.svn.sourceforge.net/pure-lang/?rev=862&view=rev
Author: agraef
Date: 2008-09-25 10:48:21 +0000 (Thu, 25 Sep 2008)
Log Message:
-----------
Update documentation.
Modified Paths:
--------------
pure/trunk/pure.1.in
Modified: pure/trunk/pure.1.in
===================================================================
--- pure/trunk/pure.1.in 2008-09-25 10:15:40 UTC (rev 861)
+++ pure/trunk/pure.1.in 2008-09-25 10:48:21 UTC (rev 862)
@@ -1205,9 +1205,10 @@
.fi
.PP
Second, matrix comprehensions make it easy to express a variety of algorithms
-which would be implemented using `for' loops in conventional programming
-languages. To illustrate the use of matrix comprehensions, here is how we can
-define an operation to create a square identity matrix of a given dimension:
+which would typically be implemented using `for' loops in conventional
+programming languages. To illustrate the use of matrix comprehensions, here is
+how we can define an operation to create a square identity matrix of a given
+dimension:
.sp
.nf
> eye n = {i==j | i = 1..n; j = 1..n};
@@ -1224,14 +1225,12 @@
notation very closely.
.PP
As a slightly more comprehensive example (no pun intended!), here is a
-definition of matrix multiplication in Pure. Let's start out with the simple
-case of the ``dot'' product of two vectors:
+definition of matrix multiplication in Pure. The building block here is the
+``dot'' product of two vectors which can be defined as follows:
.sp
.nf
-> x::matrix * y::matrix = sum [x!i*y!i | i=0..#x-1]
-> \fBif\fP vectorp x && vectorp y;
-> sum = foldl (+) 0;
-> {1,2,3}*{1,0,1};
+> dot x::matrix y::matrix = foldl (+) 0 [x!i*y!i | i=0..#x-1];
+> dot {1,2,3} {1,0,1};
4
.fi
.PP
@@ -1240,11 +1239,11 @@
the definition above.)
.PP
The general matrix product now boils down to a simple matrix comprehension
-which just multiplies all rows of x with all columns of y (the rows and cols
-functions are prelude operations found in matrices.pure):
+which just computes the dot product of all rows of x with all columns of y
+(the rows and cols functions are prelude operations found in matrices.pure):
.sp
.nf
-> x::matrix * y::matrix = {u*v | u = rows x; v = cols y};
+> x::matrix * y::matrix = {dot u v | u = rows x; v = cols y};
> {0,1;1,0;1,1}*{1,2,3;4,5,6};
{4,5,6;1,2,3;5,7,9}
.fi
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <ag...@us...> - 2008-09-27 04:57:43
|
Revision: 880
http://pure-lang.svn.sourceforge.net/pure-lang/?rev=880&view=rev
Author: agraef
Date: 2008-09-27 04:57:33 +0000 (Sat, 27 Sep 2008)
Log Message:
-----------
Add comment which triggers Emacs nroff mode.
Modified Paths:
--------------
pure/trunk/pure.1.in
Modified: pure/trunk/pure.1.in
===================================================================
--- pure/trunk/pure.1.in 2008-09-27 04:41:02 UTC (rev 879)
+++ pure/trunk/pure.1.in 2008-09-27 04:57:33 UTC (rev 880)
@@ -3177,3 +3177,6 @@
.TP
.B Q
Another term rewriting language by yours truly, \fIhttp://q-lang.sf.net\fP.
+Comment] Local Variables:
+Comment] mode: nroff
+Comment] End:
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <ag...@us...> - 2008-09-27 05:35:51
|
Revision: 881
http://pure-lang.svn.sourceforge.net/pure-lang/?rev=881&view=rev
Author: agraef
Date: 2008-09-27 05:35:40 +0000 (Sat, 27 Sep 2008)
Log Message:
-----------
Fix some minor glitches in the documentation.
Modified Paths:
--------------
pure/trunk/pure.1.in
Modified: pure/trunk/pure.1.in
===================================================================
--- pure/trunk/pure.1.in 2008-09-27 04:57:33 UTC (rev 880)
+++ pure/trunk/pure.1.in 2008-09-27 05:35:40 UTC (rev 881)
@@ -416,7 +416,9 @@
``conses'', and `,' produces ``pairs''. As indicated, Pure provides the usual
syntactic sugar for list values in brackets, such as [x,y,z], which is exactly
the same as x:y:z:[]. Moreover, the prelude also provides an infix `..'
-operator to denote arithmetic sequences such as 1..10 or 1.0,1.2..3.0.
+operator to denote arithmetic sequences such as 1..10. Sequences with
+arbitrary stepsizes can be written by denoting the first two sequence
+elements using the `:' operator, as in 1.0:1.2..3.0.
.sp
Pure's tuples are a bit unusual: They are constructed by just ``pairing''
things using the `,' operator, for which the empty tuple acts as a neutral
@@ -914,7 +916,7 @@
.nf
primes n = sieve (2..n) \fBwith\fP
sieve [] = [];
- sieve (p:qs) = p : sieve [q; q = qs; q mod p];
+ sieve (p:qs) = p : sieve [q | q = qs; q mod p];
\fBend\fP;
.fi
.sp
@@ -941,12 +943,12 @@
in check.
.sp
.nf
-queens n = search n 1 [] \fBwith\fP
- search n i p = [reverse p] \fBif\fP i>n;
- = cat [search n (i+1) ((i,j):p); j = 1..n; safe (i,j) p];
- safe (i,j) p = not any (check (i,j)) p;
+queens n = search n 1 [] \fBwith\fP
+ search n i p = [reverse p] \fBif\fP i>n;
+ = cat [search n (i+1) ((i,j):p) | j = 1..n; safe (i,j) p];
+ safe (i,j) p = not any (check (i,j)) p;
check (i1,j1) (i2,j2)
- = i1==i2 || j1==j2 || i1+j1==i2+j2 || i1-j1==i2-j2;
+ = i1==i2 || j1==j2 || i1+j1==i2+j2 || i1-j1==i2-j2;
\fBend\fP;
.fi
.SS Lazy Evaluation and Streams
@@ -1103,7 +1105,7 @@
to denote an upper (or lower) infinite bound for the sequence, e.g.:
.sp
.nf
-> let u = 1..inf; let v = -1.0,-1.2..-inf;
+> let u = 1..inf; let v = -1.0:-1.2..-inf;
> takel 10 u; takel 10 v;
[1,2,3,4,5,6,7,8,9,10]
[-1.0,-1.2,-1.4,-1.6,-1.8,-2.0,-2.2,-2.4,-2.6,-2.8]
@@ -1126,7 +1128,7 @@
appropriate stream result:
.sp
.nf
-> \fBlet\fP rats = [m,n-m; n=2..inf; m=1..n-1; gcd m (n-m) == 1]; rats;
+> \fBlet\fP rats = [m,n-m | n=2..inf; m=1..n-1; gcd m (n-m) == 1]; rats;
(1,1):#<thunk 0xb5fd08b8>
> takel 10 rats;
[(1,1),(1,2),(2,1),(1,3),(3,1),(1,4),(2,3),(3,2),(4,1),(1,5)]
@@ -1139,7 +1141,7 @@
.sp
.nf
all_primes = sieve (2..inf) \fBwith\fP
- sieve (p:qs) = p : sieve [q; q = qs; q mod p] &;
+ sieve (p:qs) = p : sieve [q | q = qs; q mod p] &;
\fBend\fP;
.fi
.sp
@@ -1423,8 +1425,8 @@
.sp
.nf
> \fBusing\fP system;
-> f = [printf "%g\en" (2^x+1); x=1..5; x mod 2];
-> g = void [printf "%g\en" (2^x+1); x=1..5; x mod 2];
+> f = [printf "%g\en" (2^x+1) | x=1..5; x mod 2];
+> g = void [printf "%g\en" (2^x+1) | x=1..5; x mod 2];
> \fBshow\fP f g
f = catmap (\ex -> if x mod 2 then [printf "%g\n" (2^x+1)] else []) (1..5);
g = do (\ex -> if x mod 2 then [printf "%g\n" (2^x+1)] else []) (1..5);
@@ -1447,7 +1449,7 @@
the outermost `catmap' if the list comprehension binds multiple variables:
.sp
.nf
-> u = void [puts $ str (x,y); x=1..2; y=1..3];
+> u = void [puts $ str (x,y) | x=1..2; y=1..3];
> \fBshow\fP u
u = do (\ex -> catmap (\ey -> [puts (str (x,y))]) (1..3)) (1..2);
.fi
@@ -1456,7 +1458,7 @@
a nested list comprehension which expands to a nested `do':
.sp
.nf
-> v = void [void [puts $ str (x,y); y=1..3]; x=1..2];
+> v = void [void [puts $ str (x,y) | y=1..3] | x=1..2];
> \fBshow\fP v
v = do (\ex -> [do (\ey -> [puts (str (x,y))]) (1..3)]) (1..2);
.fi
@@ -1810,12 +1812,12 @@
regularly returns with () to indicate that there is no solution.
.sp
.nf
-queens1 n = catch reverse (search n 1 []) \fBwith\fP
- search n i p = throw p \fBif\fP i>n;
- = void [search n (i+1) ((i,j):p); j = 1..n; safe (i,j) p];
- safe (i,j) p = not any (check (i,j)) p;
+queens1 n = catch reverse (search n 1 []) \fBwith\fP
+ search n i p = throw p \fBif\fP i>n;
+ = void [search n (i+1) ((i,j):p) | j = 1..n; safe (i,j) p];
+ safe (i,j) p = not any (check (i,j)) p;
check (i1,j1) (i2,j2)
- = i1==i2 || j1==j2 || i1+j1==i2+j2 || i1-j1==i2-j2;
+ = i1==i2 || j1==j2 || i1+j1==i2+j2 || i1-j1==i2-j2;
\fBend\fP;
.fi
.PP
@@ -2449,9 +2451,11 @@
.sp
.nf
> \fBshow\fP -g foldl*
+foldl f a x::matrix = foldl f a (list x);
foldl f a s::string = foldl f a (chars s);
foldl f a [] = a;
foldl f a (x:xs) = foldl f (f a x) xs;
+foldl1 f x::matrix = foldl1 f (list x);
foldl1 f s::string = foldl1 f (chars s);
foldl1 f (x:xs) = foldl f x xs;
.fi
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|