Reid Barton | 16 Aug 16:49
Favicon

laziness of intersperse

(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

Gmane