On Sat, 2008-08-16 at 10:51 -0400, Reid Barton wrote:
(This is the same issue as http://www.haskell.org/pipermail/haskell/ 2004-March/013739.html but there was no follow-up at that time.)
The intersperse library function is not as lazy as it could be. The current definition of intersperse is
intersperse :: a -> [a] -> [a] intersperse _ [] = [] intersperse _ [x] = [x] intersperse sep (x:xs) = x : sep : intersperse sep xs
For any list (x:xs) not containing _|_, intersperse sep (x:xs) is a list of the form (x:...); yet intersperse sep (x:_|_) = _|_ because the pattern match on the second equation diverges. A better definition would be
intersperse _ [] = [] intersperse sep (x:xs) = x : intersperseWithPrefix xs where intersperseWithPrefix [] = [] intersperseWithPrefix (x:xs) = sep : x : intersperseWithPrefix xs
(slightly modified from http://www.haskell.org/pipermail/haskell/2004- March/013741.html)
An application: There was a question on #haskell about how to compute the "ruler" sequence [1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,...]. The definition
ruler = fix ((1:) . intersperse 1 . map (1+))
works with the properly lazy intersperse, but not with the intersperse in Data.List.
Comments on this new definition? Can it get added to Data.List?
I think I've brought this up before too. While doing laziness testing (as part of the list fusion work) Don and I discovered that our new intersperse implementation was less strict than the H98 report version. We used: intersperse :: a -> [a] -> [a] intersperse _ [] = [] intersperse sep (x0:xs0) = x0 : go xs0 where go [] = [] go (x:xs) = sep : x : go xs which is more lazy and also faster than the standard implementation. It's pretty clear that the Haskell-prime List spec should use a version with this strictness property since the principle (as I understand it) was for the List module functions to be as lazy as possible. Duncan