ByteString, foldr and lazyness
duncan.coutts at worc.ox.ac.uk
Fri Nov 28 10:18:56 EST 2008
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
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))
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.
More information about the Libraries