On 2008.08.16 10:51:14 -0400, Reid Barton
(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
I assume you mean something like this (setting up for QC and removing some aliasing in intersperse') {-# LANGUAGE NoMonomorphismRestriction #-} import Test.QuickCheck (quickCheck) intersperse :: a -> [a] -> [a] intersperse _ [] = [] intersperse _ [x] = [x] intersperse sep (x:xs) = x : sep : intersperse sep xs intersperse' :: a -> [a] -> [a] intersperse' _ [] = [] intersperse' sep (x:xs) = x : intersperseWithPrefix xs where intersperseWithPrefix [] = [] intersperseWithPrefix (y:ys) = sep : y : intersperseWithPrefix ys prop = \x y -> intersperse x y == intersperse' x y ---- Well, I ran a few thousand QuickChecks. Looks good to me, although I'm not thrilled with the lost of clarity - intersperse' to me is less immediately understandable than intersperse. (Although I don't suppose it's really all that important.) -- gwern Nash CIO VIA SHAPE Fax 767 Middleman schloss ASDIC CIA-DST