laziness of intersperse

[Duncan Coutts]

On Sat, 2008-08-16 at 10:51 -0400, Reid Barton wrote:
> (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?

I think I've brought this up before too. While doing laziness testing
(as part of the list fusion work) Don and I discovered that our new
intersperse implementation was less strict than the H98 report version.

We used:

intersperse :: a -> [a] -> [a]
intersperse _   []       = []
intersperse sep (x0:xs0) = x0 : go xs0
  where
    go []     = []
    go (x:xs) = sep : x : go xs

which is more lazy and also faster than the standard implementation.

It's pretty clear that the Haskell-prime List spec should use a version
with this strictness property since the principle (as I understand it)
was for the List module functions to be as lazy as possible.

Duncan