Constructs for programming with sequences

[Mikael Djurfeldt <mdj@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?