Does this function already exist in one of the standard modules?
Does this function already exist in one of the standard modules? It computes f(f(f(...f(x))). I suspect it is a common function, but I can't find it, even using Hoogle. applyMany :: Int -> (a -> a) -> a -> a applyMany 0 f x = x applyMany n f x = applyMany (n-1) f (f x)
On Sat, Aug 08, 2009 at 03:01:34PM -0500, I. J. Kennedy wrote:
Does this function already exist in one of the standard modules? It computes f(f(f(...f(x))). I suspect it is a common function, but I can't find it, even using Hoogle.
applyMany :: Int -> (a -> a) -> a -> a applyMany 0 f x = x applyMany n f x = applyMany (n-1) f (f x)
applyMany n f x = iterate f x !! n -- Felipe.
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.
On Sat, Aug 8, 2009 at 3:38 PM, Felipe Lessa
On Sat, Aug 08, 2009 at 03:01:34PM -0500, I. J. Kennedy wrote:
Does this function already exist in one of the standard modules? It computes f(f(f(...f(x))). I suspect it is a common function, but I can't find it, even using Hoogle.
applyMany :: Int -> (a -> a) -> a -> a applyMany 0 f x = x applyMany n f x = applyMany (n-1) f (f x)
applyMany n f x = iterate f x !! n
-- Felipe. _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
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.
Am Samstag 08 August 2009 22:01:34 schrieb I. J. Kennedy:
Does this function already exist in one of the standard modules? It computes f(f(f(...f(x))). I suspect it is a common function, but I can't find it, even using Hoogle.
applyMany :: Int -> (a -> a) -> a -> a applyMany 0 f x = x applyMany n f x = applyMany (n-1) f (f x)
Not directly, I think. But we have iterate :: (a -> a) -> a -> [a] iterate f x = x:iterate f (f x) so applyMany n f x = iterate f x !! n Most of the time you either need different numbers of iterations for the same starting value, then iterate is what you want, or the same number of iterations for different values, then you use something like let g = foldl (.) id (replicate n f) in ...
participants (3)
-
Daniel Fischer -
Felipe Lessa -
I. J. Kennedy