Abstract Sequences, was: Heirarchical name space allocation
robertw at stud.tu-ilmenau.de
Thu Apr 15 11:49:48 EDT 2004
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)
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
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.
More information about the Libraries