#4282: Data.List.intersperse not lazy enough
----------------------------------+-----------------------------------------
Reporter: daniel.is.fischer | Owner:
Type: proposal | Status: new
Priority: normal | Component: libraries/base
Version: 6.12.3 | Keywords: intersperse, laziness
Testcase: | Blockedby:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: Other
----------------------------------+-----------------------------------------
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.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4282>
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
