How to concisely express function iteration?

Question

Is there a concise, idiomatic way how to express function iteration? That is, given a number n and a function f :: a -> a, I'd like to express \x -> f(...(f(x))...) where f is applied n-times.

Of course, I could make my own, recursive function for that, but I'd be interested if there is a way to express it shortly using existing tools or libraries.

So far, I have these ideas:

• \n f x -> foldr (const f) x [1..n]
• \n -> appEndo . mconcat . replicate n . Endo

but they all use intermediate lists, and aren't very concise.

The shortest one I found so far uses semigroups:

• \n f -> appEndo . times1p (n - 1) . Endo,

but it works only for positive numbers (not for 0).

Primarily I'm focused on solutions in Haskell, but I'd be also interested in Scala solutions or even other functional languages.

Answer 1

Because Haskell is influenced by mathematics so much, the definition from the Wikipedia page you've linked to almost directly translates to the language.

Just check this out:

Now in Haskell:

iterateF 0 _ = id iterateF n f = f . iterateF (n - 1) f 

Pretty neat, huh?

So what is this? It's a typical recursion pattern. And how do Haskellers usually treat that? We treat that with folds! So after refactoring we end up with the following translation:

iterateF :: Int -> (a -> a) -> (a -> a) iterateF n f = foldr (.) id (replicate n f) 

or point-free, if you prefer:

iterateF :: Int -> (a -> a) -> (a -> a) iterateF n = foldr (.) id . replicate n 

As you see, there is no notion of the subject function's arguments both in the Wikipedia definition and in the solutions presented here. It is a function on another function, i.e. the subject function is being treated as a value. This is a higher level approach to a problem than implementation involving arguments of the subject function.

Now, concerning your worries about the intermediate lists. From the source code perspective this solution turns out to be very similar to a Scala solution posted by @jmcejuela, but there's a key difference that GHC optimizer throws away the intermediate list entirely, turning the function into a simple recursive loop over the subject function. I don't think it could be optimized any better.

To comfortably inspect the intermediate compiler results for yourself, I recommend to use ghc-core.

Answer 2

In Scala:

Function chain Seq.fill(n)(f) 

See scaladoc for Function. Lazy version: Function chain Stream.fill(n)(f)