laziness of intersperse
Reid Barton
rwbarton at math.harvard.edu
Sat Aug 16 10:51:14 EDT 2008
(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?
Regards,
Reid Barton
More information about the Libraries
mailing list