Abstract Sequences, was: Heirarchical name space allocation

[Robert Will]

On Fri, 2 Apr 2004, Christian Maeder wrote:
>
> How many implemenations to you want? Eventually I suspect about 3
> implemenations to be useful.

Dessy currently has (and none of them is useless):
Streams (the only possible lazy implementation)
Real-time Queues
Deques
Write-only Sequences (like the OrdList)
Democratic Sequences (the default)

> I don't know if the size of a class matters, but some code duplication
> could be avoided by a minimal class (empty, isEmpty, cons, head, tail)
> as well.

With these primitives you would just mimick the concrete [] data type,
making efficient implementations of almost all other functions impossible.

As I argue in
http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/democratic/

a "core" consisting of (concat front back) efficiently implemented (i.e.
logN each) will permit every other function to be implemented in O(logN).
However, most implementations will also provide constant-time (is_empty
size first last), and some implementations will also provide constant-time
(add_first add_last but_first but_last).

Furthermore we need of course 'fold', but also many implementations can
implement (apply filter) faster (albeit only by a constant factor) than
the default implementation:
apply  f = fold empty (single . f) (<+>)
filter p = fold empty (\x -> if p x then single x else empty) (<+>)

Thus, a minimal class will not be small.  But I already explained last
time, that this is really no problem.

Robert