ByteString, foldr and lazyness
Hi all, Here's a ghci session, using bytestring-0.9.1.4 and ghc-6.10: Prelude> :m Data.ByteString.Lazy.Char8 Prelude Data.ByteString.Lazy.Char8> :m -Prelude Data.ByteString.Lazy.Char8> foldr (:) [] (concat (Prelude.repeat "a")) Loading package bytestring-0.9.1.4 ... linking ... done. "*** Exception: stack overflow By contrast, using Prelude's foldr and concat: Prelude> foldr (:) [] (concat (repeat "a")) :: String <prints out an infinite list> Each bytestring chunk only contains one letter, so I would expect the foldr of bytestring to behave just like that of the Prelude. Is this a bug? A feature? From looking at the bytestring source code I don't see why the code behaves this way. Many thanks, Mathieu
On Thu, 2008-11-27 at 15:08 +0100, Mathieu Boespflug wrote:
Hi all,
Here's a ghci session, using bytestring-0.9.1.4 and ghc-6.10:
Prelude> :m Data.ByteString.Lazy.Char8 Prelude Data.ByteString.Lazy.Char8> :m -Prelude Data.ByteString.Lazy.Char8> foldr (:) [] (concat (Prelude.repeat "a"))
This does not typecheck. Prelude.repeat "a" :: [String] concat :: [ByteString] -> ByteString hence concat (Prelude.repeat "a") is not well typed. Duncan
Excerpts from Duncan Coutts's message of Fri Nov 28 15:14:46 +0100 2008:
On Thu, 2008-11-27 at 15:08 +0100, Mathieu Boespflug wrote:
Hi all,
Here's a ghci session, using bytestring-0.9.1.4 and ghc-6.10:
Prelude> :m Data.ByteString.Lazy.Char8 Prelude Data.ByteString.Lazy.Char8> :m -Prelude Data.ByteString.Lazy.Char8> foldr (:) [] (concat (Prelude.repeat "a"))
This does not typecheck.
That's a matter of packing, maybe he has the overloaded strings extension. -- Nicolas Pouillard aka Ertai
On Fri, 2008-11-28 at 15:24 +0100, Nicolas Pouillard wrote:
Excerpts from Duncan Coutts's message of Fri Nov 28 15:14:46 +0100 2008:
On Thu, 2008-11-27 at 15:08 +0100, Mathieu Boespflug wrote:
Hi all,
Here's a ghci session, using bytestring-0.9.1.4 and ghc-6.10:
Prelude> :m Data.ByteString.Lazy.Char8 Prelude Data.ByteString.Lazy.Char8> :m -Prelude Data.ByteString.Lazy.Char8> foldr (:) [] (concat (Prelude.repeat "a"))
This does not typecheck.
That's a matter of packing, maybe he has the overloaded strings extension.
Ah yes, quite right. Turns out the bug is in Data.ByteString.foldr: Prelude.head (foldr (:) Prelude.undefined (singleton 3)) *** Exception: Prelude.undefined of course the result should be 3:_|_ not _|_ the cause is excessive strictness in the definition of foldr's inner loop: foldr :: (Word8 -> a -> a) -> a -> ByteString -> a foldr k v (PS x s l) = inlinePerformIO $ withForeignPtr x $ \ptr -> go v (ptr `plusPtr` (s+l-1)) (ptr `plusPtr` (s-1)) where STRICT3(go) go z p q | p == q = return z | otherwise = do c <- peek p go (c `k` z) (p `plusPtr` (-1)) q The STRICT3(go) macro expands to add strictness on all three parameters. In this function it should only be strict in p and q, not z. The go function is already strict in p and q so simply dropping the STRICT3 macro fixes the bug. Unfortunately that also means we build up a chain of thunks, since this foldr is implemented as a foldl' but going from high indexes to low. One more example to show that we should be specifying and testing the strictness properties of our functions. Duncan
participants (3)
-
Duncan Coutts -
Mathieu Boespflug -
Nicolas Pouillard