> 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?
Yes, break is very expensive due to its pairing up of results for every
character consumed. You didn't mention the accumulating parameter version:
lines :: String -> [String]
lines s = lines' s ""
where
lines' [] acc = [acc]
lines' ('\n':s) acc = reverse acc : lines' s ""
lines' (c:s) acc = lines' s (c:acc)
This one is more than twice as fast as the foldr version, despite the fact
that it needs to reverse the accumulating parameter for each line.
Cheers,
Simon
