Am Sonntag 09 August 2009 00:17:46 schrieb I. J. Kennedy:
I'm surprised there's no standard function for this. Using iterate f x !! n is ok I suppose, but:
If I try to calculate the millionth fibonacci number like this
fibStep (a,b) = (b,a+b) iterate fibStep (0,1) !! 1000000
I get a stack overflow, but if I use applyMany
applyMany 1000000 fibStep (0,1)
it works.
I can't reproduce that, I get a stack overflow for both (as it should be*). Both work, with about the same performance, if I use stricter versions: sfibStep :: (Integer,Integer) -> (Integer,Integer) sfibStep (a,b) = let c = a+b in c `seq` (b,c) applyMany' :: Int -> (a -> a) -> a -> a applyMany' 0 _ x = x applyMany' n f x = applyMany (n-1) f $! (f x) iterate' :: (a -> a) -> a -> [a] iterate' f x = x:(iterate' f $! f x) With the lazy original fibStep, both strict versions (applyMany' and iterate') work, but take much longer (roughly 20 times). [*] Both, iterate and the original applyMany build a thunk of one million nested function calls, that needs a larger stack than the default.