Proposal: Make intersperse lazier

Christian Maeder Christian.Maeder at dfki.de
Fri Sep 17 04:48:02 EDT 2010


Am 16.09.2010 16:39, schrieb Daniel Fischer:
> The current implementation of Data.List.intersperse causes a space leak 
> under certain not uncommon circumstances.
> Trac ticket: http://hackage.haskell.org/trac/ghc/ticket/4282
> The proposed implementation,
> 
> intersperse             :: a -> [a] -> [a]
> intersperse _   []      = []
> intersperse sep (x:xs)  = x : go xs
>   where
>     go []     = []
>     go (y:ys) = sep : y : go ys

I support this proposal, because it is be more efficient.
However, the (unfortunately so common) use of the auxiliary function
"go" does not look nice to me. It looks less abstract (or declarative)
just for efficiency reasons.

Therefore I proposed the following implementation:

intersperse :: a -> [a] -> [a]
intersperse s l = case l of
  [] -> l
  x : r -> x : if null r then r else
    s : intersperse s r

which looks more intuitive to me, has the same semantic change as below,
and needs no auxiliary function.

My version would check the list "r" twice: 1. by "null r" and 2. in the
recursion "intersperse s r", but I would expect this to be optimized away.

So my question is: Is my "intuitive" code really less efficient than the
proposed code? If so, why? (If not, you may take my code.)

I hate the idea having to write cryptic haskell code just to obtain
efficiency.

Cheers Christian

> 
> changes the semantics from
> 
> intersperse (x : _|_) = _|_
> 
> to
> 
> intersperse (x : _|_) = x : _|_
> 
> apart from that, I think only the run-time behaviour is changed.
> 
> Period of discussion: Two weeks, until 30 Sep. 2010.
> 
> Cheers,
> Daniel


More information about the Libraries mailing list