laziness of intersperse

Reid Barton rwbarton at
Sat Aug 16 10:51:14 EDT 2008

(This is the same issue as 
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 

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?

Reid Barton

More information about the Libraries mailing list