[Haskell-beginners] Stack space overflow with foldl'

[Daniel Fischer]

On Saturday 11 September 2010 23:30:50, Ryan Prichard wrote:
> > That's probably a different matter, foldl' evaluates the accumulation
> > parameter only to weak head normal form, if it's not of simple type,
> > it can still contain thunks that will overflow the stack when
> > demanded.
>
> I'm using Data.ByteString.ByteString:
>
> Prelude> :info Data.ByteString.ByteString
> data Data.ByteString.Internal.ByteString
>   = Data.ByteString.Internal.PS !(GHC.ForeignPtr.ForeignPtr
>                                     GHC.Word.Word8)
>                                 !Int
>                                 !Int
>
> If I evaluate a value of this type into WHNF, I think the fields are
> also evaluated into WHNF due to the strictness annotations.  That
> should remove thunks from the Int arguments.  I wonder if the
> ForeignPtr field could still have a thunk.

No, the pointer is just a memory address, no thunk there, a (strict) 
ByteString in WHNF is fully evaluated.
The question is what you do with your ByteStrings in the fold.

>
> I suppose I really wanted an NFData instance for ByteString so I could
> use rnf.

In general, you don't need an NFData instance for ByteStrings, since WHNF = 
NF for (strict) ByteStrings and reducing lazy ByteStrings to normal form 
would sort of defeat their purpose. If you need an NFData instance because 
you want to rnf e.g. a Map ByteString stuff, the default implementation of 
rnf is enough.

>
> I looked at the NFData instance for a list. It's just:
>
> instance NFData a => NFData [a] where
>     rnf [] = ()
>     rnf (x:xs) = rnf x `seq` rnf xs
>
> If I just want to evaluate each list element to WHNF, I think I could
> write:
>
> forceList [] = ()
> forceList (x:xs) = x `seq` forceList xs

Yes.

>
> This function is simpler than foldl'2, and it turns into a
> tail-recursive function in Core.  Maybe I could also use
> "forceList = foldr seq ()".
>

Exactly the same. But of course you need to evaluate forceList list to WHNF 
to have it do any work,

case forceList list of
  () -> foo

let !() = forceList list in bar

or something.

> > > I might have fixed my original stack overflow problem.  I was
> > > applying sum to a large list of integers, and sum is lazy.
> >
> > For [Int] and [Integer], sum is specialised, so when compiled with
> > optimisations, ghc should use a strict version for those types.
>
> I retested my original program that used sum.  It overflows the stack
> with -O0, but it doesn't overflow with -O or "-O -fno-strictness". With
> -v4 -ddump-simpl-stats -O, I see
>
> 1 RuleFired
>     1 SPEC Data.List.sum
>
> I don't see this output with -O0 instead of -O.

Specialisations are only used when compiled with optimisations since the 
specialised versions have different names and are inserted via rewrite 
rules. And rewrite rules are ignored with -O0.

So without optimisations, you get the vanilla sum with lazy accumulator.
To avoid stack overflows without optimisations, use foldl' (+) 0 instead of 
sum.

>
> -Ryan