Simon Marlow writes:
> You didn't mention the accumulating parameter version:
[[[with correction pointed out by Koen Claessen:]]]
> lines :: String -> [String]
> lines s = lines' s ""
> where
> lines' [] acc = [reverse 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.
According to my measurements,
with HBC it is twice as fast as the prelude version,
and on the whole it is slightly faster then the foldr version.
However, it can still be sped up: Just use the old trick of
avoiding reverse by using a functional accumulator:
> lines :: String -> [String]
> lines s = lines' s id
> where
> lines' [] acc = [acc []]
> lines' ('\n':s) acc = acc [] : lines' s id
> lines' (c:s) acc = lines' s (acc . (c:))
(Interestingly, this is the only optimisation that HBC
does not gratefully take advantage of.)
As Koen Claessen pointed out furthermore,
neither this nor my foldr definition are fully lazy.
I produced a first lazified variant of my foldr definition,
and it has running times similar to those of the prelude variants.
All the stuff on is on the updated page:
http://ist.unibw-muenchen.de/Lectures/FT2000/FP/Lines.html
So the interesting question is whether we can get laziness
without these continuously reconstructed pairs.
Cheers,
Wolfram
