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?
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
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: 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