> I don't know whether this is really good design; but I think it's
> fairly clear, and in practice my hashtable and btree libraries are
> working quite nicely and easy to work with. To be honest, "fold" isn't
> a very meaningful word to me, and I wouldn't use it in naming
> functions.  I think in terms of iterators, ordering functions, and
> reversed iterators, not in terms of folding operations.  likewise
> "reversible" is a word that can mean any of dozens of things; what I'm
> asking is whether an operation is sublinear time or constant time and
> I'd use those keywords in naming performance predicates.

Please read olegs initial post on folding versus iteration.  There are
very very good reasons to not take that approach.

<many functions deleted>
>   ;; the following items are performance predicates.
> (sublinear-first? dict)
> (constant-first? dict)
> (sublinear-last? dict)
> (constant-last? dict)
>    ;; these refer to the performance of the reversed
>    ;; iterator.
> (sublinear-prev? dict)
> (constant-prev? dict)
>

The problem with the majority of the functions you propose is first that
there are far too many, more than are needed.   Secondly, they don't
generalize well to all dictionaries.  The primary goal of any
collections API is to unify datastructures so that they are
interoperable and so that the operations that exist have a well defined
meaning on all members.

Beyond that, much of what you specify already exists in the SRFI, with
small naming differences of course.  For example:

>
> (define htable (create-hashtable hfunc))
> (define alyst (create-alist))
> (define pqueue (create-priority-queue < ))
> (define btree (create-binary-tree < ))
> (define olist (create-ordered-alist < ))
>
> (dictionary? htable) => #t
> (dictionary? pqueue) => #t
> (dictionary? btree) => #t
> (dictionary? olist) => #t
> (dictionary? alyst) => #t
>
> (ordered-dict? htable) => #f
> (ordered-dict? alyst) => #f
> (ordered-dict? olist) => #t
> (ordered-dict? btree) => #t
> (ordered-dict? pqueue) => #t

All of the above already exists in the SRFI.

>
> Finally there's considerations of efficiency: Additional predicates
> tell which general classes of operations are constant, sublinear, or
> linear.

These fall under the category of 'not within the scope of this SRFI'.
These would fall into the same hypothetical SRFI as Bradd's dynamic
programming extensions.  As with most of Scheme, efficiency concerns are
largely an implementation detail.  If you want to determine them
programmatically, it really should be defined separately from this SRFI,
which seeks to provide API and semantic specifications.

	Scott