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