(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
On 2008.08.16 10:51:14 -0400, Reid Barton
(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
A cleaner but still fully lazy version of intersperse might be intersperse sep (x1 : x2 : xs) = x1 : sep : intersperse sep (x2 : xs) intersperse _ l = l (I'd quote to give some context, but gmane says I can't unless I artificially pad the length of my new text. Is there any way to post to this list other than gmane?)
On Sat, Aug 16, 2008 at 7:22 PM, Bart Massey
A cleaner but still fully lazy version of intersperse might be
intersperse sep (x1 : x2 : xs) = x1 : sep : intersperse sep (x2 : xs) intersperse _ l = l
Doesn't that fail on (x:_|_) ? Also it relies on constructor specialisation to be efficient.
(I'd quote to give some context, but gmane says I can't unless I artificially pad the length of my new text. Is there any way to post to this list other than gmane?)
Subscribe? http://www.haskell.org/mailman/listinfo/libraries
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
Hi Reid, On Sat, Aug 16, 2008 at 10:51:14AM -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.)
Since then we have created the library submissions procedure: http://www.haskell.org/haskellwiki/Library_submissions If you follow that then everyone interested can have a say. We can then make the change if there is a consensus for it, without the issue getting forgotten about. Thanks Ian
participants (6)
-
Bart Massey -
Duncan Coutts -
Gwern Branwen -
Ian Lynagh -
Reid Barton -
Thomas Schilling