laziness of intersperse

[Gwern Branwen]

On 2008.08.16 10:51:14 -0400, Reid Barton <rwbarton at math.harvard.edu> scribbled 1.3K characters:
> (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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/libraries/attachments/20080816/be02518b/attachment.bin