Help: Stack-overflow and tail-recursive functions
Hi I've written a function that is tail-recursive and takes a list(queue) as one of its arguments. However the function fails because of "Stack space overflow"(GHC) or "ERROR - Garbage collection fails to reclaim sufficient space"(hugs). For example (simplified), both of these results in stack-overflow: f1 100000 [0,1,2], and even f2 100000 [0,1,2], where, f1 0 l = l f1 n l = f (n-1) $ take 3 $ l ++ [0,1] f2 0 l = l f2 n l = f2 (n - 1) $! (take 3 $ l ++ [0,1]) Why f2 overflows? How to avoid this stack-overflow?
I did some experiments and now suspect that the culprit is the infinite list. When I replace rmat with
rmat n = listArray ((1,1),(n,n)) [1..] -- no longer random , print (m ! (300, 300)) where m = rmat 800 fails again.
However, if I use a finite list as the second argument of listArray:
rmat n = listArray ((1,1),(n,n)) [1..(n*n)] , then the program runs without problems.
This definition works as well as oleg's.
rmat n = listArray ((1,1),(n,n)) $!! (take (n*n) $ map ct (randoms (mkStdGen 1) ::[Bool]) ) where ct True = Unknown ct False = Dead
I think: If the list is infinite, listArray doesn't return an array as data. Each time an element of the array is used, the list is evaluated. This lazy evaluation require some stack(and the access time cannot be constant?). Is it correct? Thank you.
participants (1)
-
Koji Nakahara