sequences

[Wolfgang Thaller]

Ross Paterson wrote:

> To have something concrete to discuss, I've placed a structure based on
> Edison at
> docs: http://www.soi.city.ac.uk/~ross/seq/
> code: http://www.soi.city.ac.uk/~ross/seq.tar.gz

Looks nice. It's nice and simple, and I could start using it quickly, 
without breaking too much of my code.
Some naming nitpicks:
* reduce1 and reducel are nice names, but they look almost 
indistinguishable in some fonts. Luckily, I don't use such a font for 
programming, but my browser does for displaying the docs.
* indexM: I feel that 'M' stands for 'Monad', not 'Maybe'. What about 
'Mb' instead?

The main difference to Robert's approach, aside from his anti-list 
propaganda ;-), seems to be that it uses a Haskell98-compatible 
single-parameter type class.
This means that concrete Sequence instances can't add an Ord context 
later - Are we sure that there are no useful implementations of the 
Sequence class that require their members to be instances of Ord? I 
definitely can't think of any, but perhaps someone else can?
Also, we might really want to add an abstract collection framework 
later; that will have to use MPTCs, and we will probably want Sequence 
to be a subclass of that. Also, sooner or later we will move empty and 
isEmpty to the general Collection class, won't we?
Are there many people who will want to use the new framework but stay 
with plain Haskell98?

Robert Will wrote:

> So here is a short argument in favour of my choices:
>
> 1. The class "OperationalSequence" in the Abstract Collections is an 
> MPTC
> that makes no restrictions on the element type.  I dubbed it
> "Operational", because without an equality over Sequences we can't give
> executable algebraic specifications.

Hmmm... so why should that fact be recorded in the name? Let's keep the 
names simple. I'd rather rename your 'Collection' class to something 
like CollectionEq, because

> 2. Also the names are choosen not to be compatible with the past, but 
> to
> be combatible with the future: the names of the Sequence operations fit
> well with those of all other Collections.  Many names are shared and 
> have
> the same semantics on all Collections.

Who says the future _shouldn't_ be compatible with the past? This is 
one reason why I wouldn't want your libraries as they are now to be 
"the future"; With Ross's proposal, I can start using it in the few 
places in my programs where lists are not appropriate, without breaking 
much of the rest. To use Dessy, I'd either have to change a lot of my 
program, or I'd have to import it qualified :-(.

Another problem I have with the names are those names_with_underscores. 
All the Haskell libraries, and all other Haskell code I've worked with, 
has always used namesWithoutUnderscores. If you want to replace part of 
the Prelude with something that used names_with_underscores, prepare 
for a religious war ;-).

> The absurdness of the "list-compatible" approach shows in the 
> ridiculous
> default running times for 'cons' O(1) and 'snoc' O(n), really what's 
> the
> big difference between those operations?

Absurdness? Ridiculous? Your language is very strong. Or should I say 
It's ridiculously strong and you are absurdly sure of your own opinion 
;-) ? (Sorry, couldn't resist to use the same language on you...).

Let me say something in favour of lists:
a) They have simple built-in syntax. Changing the [1,2,3] syntax to use 
a type class will make types even more problematic for beginners... 
Anyway, it won't happen soon.
b) They have a very low constant factor.
c) They are perfectly suited for many tasks. When I write something 
like this:
 > readFile "foo" >>= print . sum . map (product . words) . lines
Then lists are *exactly* what I want. Incidentally, code like this 
accounts for a large part of my use of lists.
I often think of a list as a ForwardIterator from C++'s STL. I agree 
that a singly-linked list is often a bad idea as a data structure for a 
sequence, but we use lists much more often that non-Haskell programmers 
use sequences. Most of our lists are just iterators or streams.

About your Stream module: I don't see the point - I thought you already 
had an instance for Prelude.[] in your Collections module?

> I would
> propose the following time bounds:
>
> Defaults for Sequences:
>   O(logN) for all operations, except
>   O(1) for "atomic queries" (is_empty, first, last, size (or length))

Why are we arguing about "default running times"? It's not like they 
have any observable effect outside the documentation. Lists have been 
used a lot in Haskell, and they will continue to be used a lot. Lists 
are the most "normal" sequences in Haskell, so why shouldn't the 
running time of operations on other sequences be defined relative to 
lists? In fact, I'd say that I should get the default running times 
"for free" and different (in many cases, asymptotically better) running 
times if I am willing to pay a constant factor for that.

Sorry for the long post, but I've followed the discussion long enough, 
and it's always tempting to add my 0.02 euros, so I finally couldn't 
resist anymore...

Cheers,

Wolfgang