[Haskell-cafe] How do I avoid stack overflows?
Claus Reinke
claus.reinke at talk21.com
Thu Mar 15 18:41:36 EDT 2007
> 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
More information about the Haskell-Cafe
mailing list