#4282: Proposal: make Data.List.intersperse and intercalate less strict
---------------------------------------------------+------------------------
Reporter: daniel.is.fischer | Owner:
Type: proposal | Status: new
Priority: normal | Milestone:
Component: libraries/base | Version: 6.12.3
Keywords: intersperse, laziness, intercalate | Testcase:
Blockedby: | Difficulty:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: Other
---------------------------------------------------+------------------------
Old description:
> Investigating a space leak in Data.Text.Lazy.replace, I found that
> Data.List.intersperse is not lazy enough.
> {{{
> intersperse :: a -> [a] -> [a]
> intersperse _ [] = []
> intersperse _ [x] = [x]
> intersperse sep (x:xs) = x : sep : intersperse sep xs
> }}}
> If a is for example a list-like type and the list elements are lazily
> produced one after the other, intersperse requires each element to be
> completely constructed and whether a next one follows to be determined
> before it delivers anything. Thus it forces O(size element) space
> behaviour. This also affects intercalate.
> {{{
> intersperse _ [] = []
> intersperse sep (x:xs) = x : intersperse' xs
> where
> interpserse' [] = []
> intersperse' (y:ys) = sep : y: intersperse' ys
> }}}
> would fix it.
New description:
It is proposed that `intersperse` and `intercalate` be changed to be less
strict.
Period of discussion: Two weeks, until 30 Sep. 2010.
A patch is attached to this ticket. See also the
[http://www.haskell.org/pipermail/libraries/2010-September/014293.html
mailing list discussion thread].
This change is in keeping with the spirit of the Haskell98 List module,
which is for list functions to be as lazy as possible (unless there are
good reasons otherwise). There are use cases where the current overly-
strict versions are problematic. In addition, the more lazy versions are
slightly more efficient.
current implementation:
{{{
intersperse :: a -> [a] -> [a]
intersperse _ [] = []
intersperse _ [x] = [x]
intersperse sep (x:xs) = x : sep : intersperse sep xs
}}}
current strictness properties:
{{{
intersperse _ _|_ = _|_
intersperse _ (x :_|_) = _|_
intersperse sep (x:y:_|_) = x : sep : _|_
}}}
proposed implementation:
{{{
intersperse :: a -> [a] -> [a]
intersperse _ [] = []
intersperse sep (x:xs) = x : go xs
where
go [] = []
go (y:ys) = sep : y : go ys
}}}
strictness properties after change:
{{{
intersperse _ _|_ = _|_
intersperse _ (x:_|_) = x : _|_
intersperse sep (x:y:_|_) = x : sep : y : _|_
}}}
current and proposed implementation of `intercalate`:
{{{
intercalate :: [a] -> [[a]] -> [a]
intercalate sep xss = concat (intersperse sep xss)
}}}
current strictness properties:
{{{
intercalate _ _|_ = _|_
intercalate _ (xs:_|_) = _|_
intercalate sep (xs:ys:_|_) = xs ++ sep ++ _|_
}}}
strictness properties after proposed change to `intersperse`:
{{{
intercalate _ _|_ = _|_
intercalate _ (xs:_|_) = xs ++ _|_
intercalate sep (xs:ys:_|_) = xs ++ sep ++ ys ++ _|_
}}}
--
Comment(by duncan):
Proposal description updated (edited on behalf of Daniel who cannot edit
the ticket description).
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4282#comment:8>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
