How to concisely express function iteration?

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.

Edit Report

1 Answer

Although this is not as concise as jmcejuela's answer (which I prefer), there is another way in scala to express such a function without the Function module. It also works when n = 0.

def iterate[T](f: T=>T, n: Int) = (x: T) => (1 to n).foldLeft(x)((res, n) => f(res))

To overcome the creation of a list, one can use explicit recursion, which in reverse requires more static typing.

def iterate[T](f: T=>T, n: Int): T=>T = (x: T) => (if(n == 0) x else iterate(f, n-1)(f(x)))

There is an equivalent solution using pattern matching like the solution in Haskell:

def iterate[T](f: T=>T, n: Int): T=>T = (x: T) => n match {
  case 0 => x
  case _ => iterate(f, n-1)(f(x))
}

Finally, I prefer the short way of writing it in Caml, where there is no need to define the types of the variables at all.

let iterate f n x = match n with 0->x | n->iterate f (n-1) x;;
let f5 = iterate f 5 in ...

answered 2013-04-18T12:06:09.523

How to concisely express function iteration?

1 Answer

Your Answer