[Haskell-beginners] Stack Overflow with foldl'

[Daniel Fischer]

Am Samstag 23 Januar 2010 14:05:42 schrieb Cyril Pichard:
> Hi,
>
> I don't understand why the following code always result in a Stack space
> overflow error. I'm using foldl' and think the main algorithm is tail
> recursive. Am I wrong ? I've read the
> http://www.haskell.org/haskellwiki/Stack_overflow Any help would be
> greatly appreciated.
>
> Thanks
>

Because the 'seq' in foldl' evaluates its argument only to the outermost 
constructor.

So in foldl' bboxAddt bb triangles@(t1:tail), it starts evaluating

bboxAddt bb t1

~> bboxAddb bb (boundingBox t)

now bb must be matched against (BBox mxb mnb) and boundingBox t must be 
matched against (BBox mxt mnt) if the first match succeeds (which it does).
Now boundingBox t = BBox calculatelater1 calculatelater2, so that match 
succeeds too.
Then the definition of bboxAddb says the result of

bboxAddt bb t1

is z' = BBox (max mxb calculatelater1) (min mnb calculatelater2)

The next step in foldl' is

z' `seq` foldl' bboxAddt z' tail

but z' `seq` something only evaluates z' far enough to see it's a 
(BBox _ _), the components remain happily unevaluated.
And so on. At the end of the list, you have the result

BBox hugeThunk1 hugeThunk2

When you try to evaluate one of these thunks, the stack overflows.

You need to force the evaluation of the components in each step.
The easiest way is to make the data structures strict. For this case, it is 
sufficient to make BBox and Point strict:

data Point = Point { x, y, z :: !Double } deriving (Eq, Show)
data BBox = BBox { bbmax, bbmin :: !Point } deriving (Eq, Show)

though it's probably a good idea to make Triangle strict, too.
Then BBox can't have undefined components, evaluating a BBox to the 
outermost constructor (weak head normal form) forces the evaluation of its 
component Points to their outermost constructor, which in turn forces the 
evaluation of their respective components; those are Doubles and thus 
evaluating them to their outerost constructor evaluates them completely.

Now bb`seq` something evaluates bb completely (to normal form) when 
something is demanded, no huge thunks, no stack overflow anymore :)

Of course, if you need the possibility to have (BBox undefined undefined) 
without the programme aborting, you can't make the datatypes strict and 
have to make the folding function stricter, e.g.

import Control.DeepSeq -- from package deepseq

instance NFData Point where
    rnf (Point x y z) = x `seq` y `seq` z `seq` ()

instance NFData BBox where
    rnf (BBox mx mn) = rnf mx `seq` rnf mn

bbAddt' bb t = bb `deepseq` bbAddt bb t

foldl' bbAddt' newBBox triangles

>
> module Main where
>
> import Data.List
>
> -- Data structures
> data Point = Point { x::Double, y::Double, z::Double } deriving(Eq,
> Show) data Triangle = Triangle { p1::Point, p2::Point, p3::Point }
> deriving(Eq, Show) data BBox = BBox { bbmax::Point,  bbmin::Point }
> deriving(Eq,Show)
>
> -- Construct a default triangle
> newTriangle :: Triangle
> newTriangle = Triangle (Point 1 0 0) (Point 0 1 0) (Point 0 0 1)
>
> -- Construct a default BBox
> newBBox = BBox (Point 0 0 0) (Point 0 0 0)
>
> -- Defines min and max for Point
> instance Ord Point where
>    max a b = Point ( max (x a ) (x b) ) ( max (y a) (y b) ) ( max (z a)
> (z b) ) min a b = Point ( min (x a ) (x b) ) ( min (y a) (y b) ) ( min
> (z a) (z b) )
>
> -- Create a list of triangles
> makeTriangles :: Double -> [Triangle]
> makeTriangles 0 = []
> makeTriangles n = [ Triangle (Point v 0 0) (Point 0 v 0) (Point 0 0 v) |
> v <- [1..n] ]
>
> -- Compute the bounding box of a triangle
> boundingBox :: Triangle -> BBox
> boundingBox t = BBox pmax pmin
>                 where pmax = max (p3 t) (max (p1 t) (p2  t))
>                       pmin = min (p3 t) (min (p1 t) (p2  t))
>
> -- Compute the bounding box of two bounding boxes
> bboxAddb :: BBox -> BBox -> BBox
> bboxAddb (BBox bb1max bb1min) (BBox bb2max bb2min) = BBox (max bb1max
> bb2max) (min bb1min bb2min)
>
> -- Compute the bounding box of a triangle and a bounding box
> bboxAddt :: BBox -> Triangle -> BBox
> bboxAddt b t = bboxAddb b (boundingBox t)
>
> main = do print $ foldl' bboxAddt newBBox triangles;
> 		  where triangles = makeTriangles 610000
>
>
>
> error returned :
> Stack space overflow: current size 8388608 bytes.
> Use `+RTS -Ksize' to increase it.
>
> ghc version 6.10.3 on MacOsX Snow Leopard