Shin-Cheng Mu <[EMAIL PROTECTED]>
is puzzled why the derived foldr version of lines
is significantly faster than the prelude version,
which he recognises as an unfold:
> I am curious why the Prelude version is less efficient than the
> your fold version? It seems to me the fold version construct a
> cons cell and deconstruct it immedately everytime it glues a
> character to the first line, while the Prelude version only
> wastes a pair cell for every line.
I am surprised that none of the experts has taken this on.
So I have experimented a little bit further,
first assuming that ``break (== '\n')'' might be a lot slower
than ``span (/= '\n')'' or even ``span ('\n' /=)'' --
but the running time differences are small.
So here is my --- maybe superficial --- conclusion,
somewhat illuminated by the animations
now to be found on my ``lines page'' at:
http://ist.unibw-muenchen.de/Lectures/FT2000/FP/Lines.html
* In the unfold definition,
the pair cell is constructed and destructed for every character,
and every construction of the pair cell
induces two destructive accesses,
via different evaluation paths, and at different times
* In the fold definition,
the cons cell is destructed locally in one step.
This is also illustrated by the fact that the HOPS animations
for an optimised version of the prelude definition
have essentially just one step more per character of the input string
than those for the fold definition.
Does this sound plausible to the experts?
Wolfram
