[Haskell-beginners] Does this function already exist in one of
the standard modules?
daniel.is.fischer at web.de
Sun Aug 9 10:02:57 EDT 2009
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.
More information about the Beginners