[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