How do I avoid stack overflows?
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
Hi, Thanks for the suggestions. A few more questions. The (<<*>>) function is just one of a number of lazy matrix arithmetic functions that I have. If I need them to be evaluated strictly, is it best to modify the matrix code, or the code that's calling it? In this case, it looks like I can fix the problem by modifying the calling code. For example: test3 = iterate' (\m -> sum (map last m) `seq` m <<*>> id3) id3 !! 1000000 This works fine with the *unmodified* version of (<<*>>). However, note that I've had to do some unnecessary work - sum (map last m). Is there a better way? Or, is it better to modify the matrix code itself? Perhaps there's an argument that matrix arithmetic should be strict - after all, integer arithmetic is strict. But it seems potentially useful to have at least (<<+>>) as lazy, so that I can add together infinite matrices. Which is best? Thanks in advance.
You could always make the matrix type itself strict by marking its
components with '!'. That way, any time a matrix is touched, all of
its components will be evaluated. That, for example, is how the
Complex type is implemented.
--
Dan
On 3/17/07, DavidA
Hi,
Thanks for the suggestions. A few more questions.
The (<<*>>) function is just one of a number of lazy matrix arithmetic functions that I have. If I need them to be evaluated strictly, is it best to modify the matrix code, or the code that's calling it?
participants (3)
-
Dan Piponi -
DavidA -
oleg＠pobox.com