RE: Help: Stack-overflow and tail-recursive functions
Note that there is essentially no difference between f1 and f2. When you $! in f2, all it does is ensure that the argument isn't undefined. It doesn't evaluate any of the list. Try $!! from the DeepSeq module or write your own list-forcing function. For me, the following works: f1 0 l = l f1 n l = f1 (n-1) $!! (take 3 $ l ++ [0,1]) f $!! x = force x `seq` f x where force [] = () force (x:xs) = x `seq` force xs whereas it doesn't without the $!!. -- Hal Daume III | hdaume@isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume
-----Original Message----- From: haskell-cafe-admin@haskell.org [mailto:haskell-cafe-admin@haskell.org] On Behalf Of Koji Nakahara Sent: Wednesday, June 18, 2003 5:18 PM To: haskell-cafe@haskell.org Subject: 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?
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskel> l-cafe
On Wed, 18 Jun 2003 17:36:28 -0700
"Hal Daume"
Note that there is essentially no difference between f1 and f2. When you $! in f2, all it does is ensure that the argument isn't undefined. It doesn't evaluate any of the list. Try $!! from the DeepSeq module or write your own list-forcing function.
Thank you very much. I understand. However my original program still (or maybe from the beginning) stack-overflows at another point, in the middle of the evaluation of "forpaintbdry". Please give me some advice. ----------- -- snippet of the program for painting a random matrix from its boundary. module Main where import System import Random import Array import Ix import List main = putStrLn $ show $ forpaintbdry $ rmat 200 forpaintbdry m = [(pos, Live) | pos <- (uncurry bdryidxlist) $ bounds m , isUnknown $ m ! pos ] bdryidxlist :: (Int, Int) -> (Int, Int) -> [(Int, Int)] bdryidxlist (a1, a2) (b1, b2) = nub $ [(ab, j) | ab <- [a1, b1], j <- [a2..b2]] ++ [(i, ab) | ab <- [a2, b2], i <- [a1..b1]] rmat n = listArray ((1,1),(n,n)) $ map ct (randoms (mkStdGen 1) ::[Bool]) where ct True = Unknown ct False = Dead data CellColor = Live | Unknown | Dead isUnknown Unknown = True isUnknown _ = False instance Show CellColor where show Live = "Live" show Unknown = "Unknown" show Dead = "Dead"
participants (2)
-
Hal Daume -
Koji Nakahara