Proposal: Make intersperse lazier
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.
>> 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
>> 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
> Cheers Christian
>> changes the semantics from
>> intersperse (x : _|_) = _|_
>> intersperse (x : _|_) = x : _|_
>> apart from that, I think only the run-time behaviour is changed.
>> Period of discussion: Two weeks, until 30 Sep. 2010.
More information about the Libraries