Proposal: Make intersperse lazier

[Daniel Fischer]

On Friday 17 September 2010 14:45:12, Christian Maeder wrote:
> Am 17.09.2010 14:21, schrieb Bas van Dijk:
> >
> > One additional benefit about the original proposed implementation is
> > that it applies the static argument transformation: the 'sep' argument
> > is brought into scope of the worker function 'go' which then doesn't
> > need to pass it to each recursion as in the original implementation.

Which, according to the benchmarks I ran today is in this case actually not 
a benefit.
(Not entirely surprising, in http://www.haskell.org/pipermail/glasgow-
haskell-users/2008-June/014987.html, Max Bolingbroke wrote:
"GHC performs the
SAT iff the recursive call is direct (i.e. not on mutually recursive
groups of functions) to reduce code expansion, and if the number of
static arguments is at least 2. The reason for the last criterion is
that moving a parameter to a closure implicitly adds an argument to
all the functions that make reference to that variable, the implicit
argument being the pointer to the closure. Eliminating an actual
function argument just to add a layer of indirection via an allocated
closure would be fairly pointless!"

As far as I know, however, the SAT tends to be beneficial even for a single 
argument if that argument is a function to be applied, as in folds.)

>
> This is the point. Taking the simpler prepend function, do we did not
> write:
>
> prepend :: a -> [a] -> [a]
> prepend sep = go where
>   go [] = []
>   go (x : xs) = sep : x : go xs

That just moves the worker from intersperse to another function, so I 
wouldn't expect you to find it any nicer.
However, I benchmarked some more today, and the results suggest that

intersperse :: a -> [a] -> [a]
intersperse _ [] = []
intersperse s (x:xs) = x : foo s xs

foo :: a -> [a] -> [a]
foo s (x:xs) = s : x : foo s xs
foo _ []  = []

is a little faster than the SATed isgo (about 4-5% in the benchmark).
Compiled with optimisations, it makes no difference whether foo (of course 
we need a better name) is a top-level function or local to intersperse, but 
without optimisations, a top-level function is better.
Also nice is that that gives identical core for all optimisation levels 
(0,1,2) [apart from the strictness/unfolding information, which is absent 
with -O0].
(Tested with 6.12.3 and HEAD.)

So far, the above is IMO the best implementation.
A good name for foo remains to be found.

I don't like 'prepend' because prepend suggests only putting something 
before a list (with the given type, it should be (:)) and not changing 
anything inside.

If it's not to be exported from Data.List (and I don't consider it useful 
enough to be), maybe intersperseLoop wouldn't be too daft.

Cheers,
Daniel