[Haskell-cafe] How do I avoid stack overflows?

[oleg at pobox.com]

DavidA wrote:
> I'm trying to write some code which involves lots of matrix multiplications,
> but whenever I do too many, I get stack overflows (in both GHCi 6.4.2, and
> Hugs May 2006).

By placing a couple of strictness annotations, your test' gives the
expected answer (given some time) on Hugs. GHCi unfortunately runs
into some kind of bug (it says so itself), an unimplemented opcode.
The test'' below gives that bug instantly...


import List (transpose)

-- not needed here
-- foldl' f z [] = z
-- foldl' f z (h:t) = (foldl' f $! f h z) t
-- sum' l = foldl' (+) 0 l

map' f [] = []
map' f (h:t) = scons (f h) (map f t)

-- strict cons. Could be associated with an infix op, e.g., :$
scons :: a -> [a] -> [a]
scons x l | x `seq` l `seq` False = undefined
scons x l = x:l


u <.> v = sum $ zipWith (*) u v

a <<*>> b = multMx a (transpose b)
        where
                multMx [] _ = []
                multMx (u:us) bT = scons (map' (u <.>) bT) (multMx us bT)

id3 = [[1,0,0],[0,1,0],[0,0,1]]

-- test = iterate (<<*>> id3) id3 !! 1000000

iterate' f x = x : seq x' (iterate' f x') where x' = f x
test' = iterate' (<<*>> id3) id3 !! 1000000

test'' = head $ drop 1000000 $ iterate' (<<*>> id3) id3