[Haskell-beginners] Does this function already exist in one of the standard modules?

[Daniel Fischer]

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.