laziness of intersperse
duncan.coutts at worc.ox.ac.uk
Sat Aug 16 12:29:49 EDT 2008
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-
> 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
> 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.
intersperse :: a -> [a] -> [a]
intersperse _  = 
intersperse sep (x0:xs0) = x0 : go xs0
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.
More information about the Libraries