First of all I want to say that I like this proposal more than the
original. I would let people get home from the summer holidays before
finalizing the proposal though.

Here are some small things I noticed on a first reading.

  > Folding Enumerators
  > -------------------

  > procedure: collection-keys-fold-left ...
  > procedure: collection-keys-fold-right ...

I prefer collection-fold-keys-increasing and
collections-fold-keys-decreasing.

  > Functional vs Linear Update
  > ---------------------------

  > Functions in this SRFI which modify a collection are provided in
  > two flavors.  Both must be implemented by collections.  Purely
  > functional updating functions must not side effect the input
  > collection, but must return a new collection which reflects the
  > update.  The returned collection may share structure with the
  > input collection, but must be distinct with respect to eq? to the
  > input collection, and the effects of the update must not be
  > reflected in the input collection.

Why must the returned collection be distinct with respect to eq?
Suppose I have a set implementation, where sets are represented
as sorted lists, then it would be natural to let
(union A '()) return A.

  > Functional vs Linear Update
  > ---------------------------
  > _Collections_

  > procedure: *-values collection => list

Why not simply name it collection->list ?
This is similar to vector->list and string->list.

--
Jens Axel Søgaard