Lists representations (was: What does FP do well? (was ...))

[Jerzy Karczmarczuk]

[I removed private addresses from the header, and I invite cordially
all you folks *not* to send your posting simultaneously to the Haskell
list and to the guy who reads the list as well, otherwise the exchange
would never take place...]


Just 3 centimes [former French currency, survived ; nobody will say
euro-cents here...]

Claus Reinke:

...
> But the moral for the current discussion: a more intelligent list
> representation could have substantially more benefits for the
> average Haskell program than any compiler optimization twiddling,
> and I'd really like to see someone (PhD student?) investigating that
> topic seriously, as the answers are unlikely to be obvious.
> 
> The representation chosen in the reduction systems could be a first
> hint, but as Jerzy points out, things may be more complicated in the
> context of Haskell.  For comparison, Haskell array performance was
> somewhere between non-existent and terrible in those days (another
> clear win for both the compiled and the interpreted reduction
> systems) and has only recently improved somewhat. That needs to
> continue and, please, someone do the same for lists.
...

Alastair Reid:

...
> Zhong's work [1] was in the context of a strict language (SML) which
> meant that you can know how long a list is as you are building it so
> you can use the Cons4 cells a lot.
> 
> Cordy's work [2] was in the context of a lazy language (Haskell) which
> meant that you usually don't know the length of a list (if it is even
> finite) as you are building it.  This requires a bit of cunningness to
> overcome.
> 
> IIRC, the key part of that cunningness was that Cordy does the most
> interesting stuff near the tail of the list while Zhong does the most
> interesting things near the head of the list.
...


Maestros,
I know you know all that, but some of the new readers migh have some
doubts since for years and years people pose the same question: why
all this damned lazy business is about?! <<Cui bono>>?. The laziness
seems to be such a nuisance that it seems incredible that it is still
there.

So, please recall the following:

    In a lazy program it is not an issue the fact that "I don't know"
    the length of my list.
    I DON'T WANT TO KNOW!!!
    The very notion of length is or may be spurious, it depends on the
    list consumer, not on its creator.

    Lazy structures may - in my workbenches they always do - represent
    iterative, dynamic, sometimes wildly interacting processes.
    They may emulate backtracking. 
    Lazy continuations may be used to implement coroutines, dataflow
    control structures, etc. etc.

===

OK, for me the moral is now - I wouldn't say clean [pun intended], but
quite clear:

Strict data structures in Haskell should belong to different types than 
the co-recursive ones. With different implementation, in particular, 
for arrays.



Jerzy Karczmarczuk