Is there a standard higher order function for applying a transform multiple times?

Question

I think of a function like this:

> let applyN (initial : 't) (n:int) (f : 't -> 't) = seq {1..n} |> Seq.fold (fun s _ -> fs) initial;; val applyN : initial:'t -> n:int -> f:('t -> 't) -> 't > applyN 0 10 (fun x -> x + 1);; val it : int = 10 

Note. The code is F #, but I marked the question with the haskell, ocaml and ml labels, because if the function does not exist in the F # libraries, but exists in other languages, I would like to use the same name

Answer 1

You would get a (very close) answer using, for example, Hayoo (or Hoogle, but Hoogle is not so flexible - iterateN not found):

• searching Int -> (a -> a) -> a -> a showed several functions that do what you want, but are not part of stdlib.

• a applyN search returned a function of the exact same name with the type you are looking for.

• decreasing the return value, instead of looking for Int -> (a -> a) -> a (note the missing -> a at the end), you get the function iterateN :: Int -> (a -> a) -> a -> Seq a , which erdeszt already mentioned.

PS Hoogle seems to be more capable of reversing the order of the arguments: (a -> a) -> Int -> a -> Seq a successfully returns' iterateN :: Int → (a → a) → a → Seq a`, which is not in Hayoo

Answer 2

There is an iterateN function for Haskell in the Data.Sequence module, which is similar to the one you are looking for.

This is actually just a combination of iteration + take: let iterateN nfx = take n (iterate fx) Here is the F # version of the iteration ( from here ), Seq.take is part of the F # standard library:

 let rec iterate f value = seq { yield value yield! iterate f (f value) } 

Answer 3

Possible Solution:

 > import Data.Monoid > import Debug.SimpleReflect -- not really needed, just for showing the result > (appEndo . mconcat . replicate 5 . Endo $ f) a f (f (f (f (fa)))) 

Other (already mentioned):

 > iterate fa !! 5 f (f (f (f (fa)))) 

(add lambdas if you want to turn it into a function)

However, do not forget that Haskell is lazy: the above methods will first build a thunk by adding f many times and only then start evaluating. Sometimes f could be repeated in constant space, for example. when f :: Int -> Int (and f itself works in constant space), but the above approaches work only in linear space.

I would define using my own line iterator combinator, for example:

 iter :: Int -> (a -> a) -> a -> a iter 0 _ x = x iter nfx = iter (pred n) f $! fx 

or even,

 iter nfx = foldl' (flip $ const f) x [1..n] 

which is more of a translation by Haskell of what has already been posted in the question.

Alternatively, we can define a strict version of iterate (which IMHO must already exist ...)

 iterate' :: (a -> a) -> a -> [a] iterate' fx = x : (iterate' f $! fx) 

Answer 4

To add to the list of other ways to do this,

 import Control.Monad.State.Lazy applyN initial n = flip execState initial . replicateM_ n . modify