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