wolfgang.thaller at gmx.net
Fri Apr 9 16:04:16 EDT 2004
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
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
> 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
> be combatible with the future: the names of the Sequence operations fit
> well with those of all other Collections. Many names are shared and
> 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
> default running times for 'cons' O(1) and 'snoc' O(n), really what's
> 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
> 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
More information about the Libraries