# Proposal: Make intersperse lazier

Christian Maeder Christian.Maeder at dfki.de
Fri Sep 17 05:25:42 EDT 2010

```Am 17.09.2010 10:48, schrieb Christian Maeder:
> 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.
>> 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.

How about changing the ugly auxiliary function into global useful
function and/or avoiding recursion at all by:

concatMap (\ x -> [sep, x])

(I don't have a good name for it, maybe "prepend")

Would this have an efficiency problem?

> 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
```