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

[Claus Reinke]

> 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). The following code exhibits the problem.
.. 
> I tried to fix the problem using seq, as follows:
> 
> iterate' f x = x : seq x' (iterate' f x') where x' = f x

since you're working with lists, and nested at that, seq isn't going to buy much
(it'll evaluate the matrix to being non-empty, without forcing its rows, let alone
elements). you might find the recent thread on avoiding temporary arrays interesting:

http://www.haskell.org/pipermail/haskell-cafe/2007-March/023286.html

if you like to stay with binary lists, you might want to consider using strict lists
(no unevaluated heads or tails. i happen to have some strict list code lying around 
from that earlier thread which addresses your problem:-)

hth,
claus

import List (transpose)

u <.> v = summulS u v

a <<*>> b = multMx a (transposeS b)
 where
  multMx Nil _ = Nil
  multMx (u:<us) bT = mapS (u <.>) bT :< multMx us bT

id3 = fromList $ map fromList [[1,0,0],[0,1,0],[0,0,1]]

iterate' f x = x : seq x' (iterate' f x') where x' = f x

test' = toList $ mapS toList $ iterate' (<<*>> id3) id3 !! 1000000

-------------- copy in strict list type and operations

data SL a = Nil | !a :< !(SL a) deriving Show -- head- and spine-strict lists

headS (h:<t) = h
tailS (h:<t) = t

type VectorS a = SL a
type MatrixS a = SL (VectorS a)

foldS f n Nil     = n
foldS f n (x:<xs) = f x (foldS f n xs)

mapS f = foldS ((:<).f) Nil
sumS   = foldS (+) 0

zipWithS op (a:<as) (b:<bs) = (a`op`b) :< zipWithS op as bs
zipWithS op Nil     Nil     = Nil

transposeS  :: SL (SL a) -> SL (SL a)
transposeS Nil   = Nil
transposeS (Nil :< xss)   = transposeS xss
transposeS ((x:<xs) :< xss) = (x :< mapS headS xss) :< transposeS (xs :< mapS tailS xss)

fromList = foldr (:<) Nil
toList   = foldS (:) []


-- avoid intermediate strict list in: sumS $ zipWithS (*) v1 v2
summulS Nil     Nil     = 0
summulS (a:<as) (b:<bs) = a*b+summulS as bs