ByteString, foldr and lazyness

[Duncan Coutts]

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