Proposal: make Data.List.intersperse and intercalate less strict
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 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 ++ _|_