Proposal: Make intersperse lazier

[Christian Maeder]

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

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