sequences

[Robert Will]

On Fri, 9 Apr 2004, Wolfgang Thaller wrote:
>
> 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

I decided to do that Yesterday.  If we could have local constraints à la

class Collection coll a where
    has :: (Eq a) => coll a -> a -> Bool

The class wouldn't even be necessary.  That would really be simple, but
we'll have to see whether it's possible in a "probable sucessor to
Haskell'98".

> Who says the future _shouldn't_ be compatible with the past?

Of course, it should, but sometimes it can't if it should also be a nice
future.  We can make better implementations without changing the
interface, but we cannot make better interfaces without changing the
interface.  It's like the change from ML to Haskell, for example.

> To use Dessy, I'd either have to change a lot of my
> program, or I'd have to import it qualified :-(.

First, you can use it on new Modules only.  Then you can convert existant
Modules one-by-one or in groups (when changing their interface to use
Collections).  Lastly, most Modules can be converted by simple renaming
'head' to 'first' and so on.

> 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 ;-).

I'm ready to fight it, even ready to loose it, but since underscores are
just the better thing (by psychological studies), I'll try to push the
change.

> Absurdness? Ridiculous? Your language is very strong.

Yes.  If I wouldn't think the advantages of a democratic approach are very
big, I couldn't defend such a big change.  Programmers that are used to
all the intricacies and non-consistencies in current tools and libraries
don't usually notice how much time they spend on small errors and problems
due to this.  I think, that _much_ time is lost, and sometimes it even
makes big problems because all the small problems distract from the big
ones.  Of course, the problems are even bigger for beginners who have to
learn all this...

> 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...

I think that the "default" mechanism, well-implemented (especially
with good error-messages), can compensate for this.

You'll have
> [1,2,3] :: Seq Int
for the beginner and
> [1,2,3] :: (Sequence seq a, Num a) => seq a
for the advanced.

> b) [lists] have a very low constant factor[s].

Yes, but other implementations can have that, too.  And of course, the
"Stream" data type preserves all the good (laziness) properties of lists.

> 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.
>
> About your Stream module: I don't see the point - I thought you already
> had an instance for Prelude.[] in your Collections module?

Streams are exactly like the old "lists", just with a more fitting name
and without exceptional syntax: Tree a, Set a, Stream a -- that's
consistent.  Your example makes explicitly use of the "Stream" property of
lists, so Streams it what it should use.

I explain in section "Transition towards ubiquitous Collections" in the
Collections manifest, lists are used for many, many different things, and
the new approach separates out all these.  Of course that has the
disadvantage that one has to think a little bit --what do I really want?--
before choosing an appropriate Collection.  But the advantage is better
documentation.  For a function returning [a] I don't know whether that
result is produced lazily or not (i.e. what is the running time of "head"
on the result), with abstract Collections (well-used) the result is lazy
exactly if it has type "Stream a".  (Of course we can still use the
Collection's functions without worrying about the concrete type, that
decision is taken later -- as it should with separation of concerns.(

> > 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.

They are very important, because they give developers a feel for what is
"expensive" and what is "cheap".  When deriving programs from executable
specifications, all you do is make them more efficient.  That's the
essence of programming from a formal point of view.  To have the right
feel for expensive versus cheap, the model must be as simple as possible
so that people think less about performance and more about functionality.

> ... why shouldn't the running time of operations on other sequences be
> defined relative to lists?

If every programmer has to learn that 'last' takes time O(N) before he
learns that better implementations exist, this will certainly be no good.

> 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.

Yes, that's one of my design principles.  But a more important one is that
of the least surprise: the default is the smallest possible worst-case
asymptotical running time.  Making some operations faster, requires making
others slower.  This chould be done explicitly so that a user can make
sure he doesn't use the more expensive operations in critical places.
That's why neither Deques nor Streams are my default.

> Sorry for the long post,

I think that such a difficult topic cannot be treated briefly.  Your post
contained nothing superfluous, so it had to be so long.  I hope we can
maintain this high standard, even when we get a "religious war"...  (I'll
try to put all arguments pro and con on the web-page, so we don't need to
repeat ourselves...)

Robert