This is the mail archive of the
guile@cygnus.com
mailing list for the Guile project.
Constructs for programming with sequences
- To: guile@cygnus.com
- Subject: Constructs for programming with sequences
- From: Mikael Djurfeldt <mdj@nada.kth.se>
- Date: Mon, 31 May 1999 20:43:07 +0200 (MET DST)
- Reply-to: Mikael Djurfeldt <djurfeldt@nada.kth.se>
When programming with sequences (lists or vectors), there are three
fundamental operations which you use again and again:
1. Generation
The values from a generating procedure forms a new sequence.
+------+
| PROC |
+------+
/ / \
_/_/ \_
|_|_| . . . |_|
Examples: Generating a list of the numbers 1 to 10.
Generating a vector of random numbers in [0,1].
2. Mapping
A procedure maps each element in the old sequence to an element in
the new sequence.
_ _ _
|_|_| . . . |_|
\ \ /
\ \ /
+------+
| PROC |
+------+
/ / \
_/_/ \_
|_|_| . . . |_|
Example: Mapping a list of strings to a list of their lengths.
3. Combination
A combinator procedure combines elements from a sequence.
_ _ _
|_|_| . . . |_|
\ \ /
\ \ /
+------+
| PROC |
+------+
Examples: Summing a list of numbers.
Computing the maximum in a vector of numbers.
Since these operations are so common, I think Guile should have good
support for them.
On the language level, an algorithm is easier to write and easier to
understand if a lot of the unnecessary details of loop constructs can
be removed.
On the implementation level, it is possible to achieve higher
efficiency if the looping involved in sequence operations can be done
"under the cowling".
We have good support for mapping of lists to lists (map), but the
other operations are missing. Below I will suggest additional
operations to fill in the needs described above.
Of course one could imagine different levels of generality of these
operations. But generality is sometimes achieved at the cost of
simplicity (c.f. the do-form). I've tried to specify simple
operations which are still useful enough for many cases.
1. Generation
(map-index N PROC) --> LIST
(vector-map-index N PROC) --> VECTOR
where
LIST = ((PROC 0) (PROC 1) ... (PROC N-1))
VECTOR = similarly
The motivation for the argument order is to improve code layout:
(map-index 10
(lambda (i)
(+ 1 i)))
2. Mapping
(vector-map PROC VECTOR1) --> VECTOR2
(vector version of map)
3. Combination
(foldl PROC INIT LIST) --> COMBINED
(foldr PROC INIT LIST) --> COMBINED
(vector-foldl PROC INIT VECTOR) --> COMBINED
(vector-foldr PROC INIT VECTOR) --> COMBINED
where foldl yields
COMBINED = (PROC En-1
(PROC En-2
...
(PROC E0 INIT)))
and foldr
COMBINED = (PROC E0
(PROC E1
...
(PROC En-1 INIT)))
(The names comes from the fact that foldl starts from the left and
goes to the right, and vice versa for foldr.)
Opinions/suggestions?