Repeat a function N times in Julia (composition)

Question

I'm trying to make a function that compose a function f(x) by itself N times, something like that:

function CompositionN(f,N)
             for i in 1:N
                f(x) = f(f(x))
             end
return f(x)

I need that the function CompositionN returns another function, not a value.

Answer 1

You can take advantage of the ∘ function, which allows you to compose multiple functions:

julia> composition(f, n) = ∘(ntuple(_ -> f, n)...)
composition (generic function with 1 method)

julia> composition(sin, 3)(3.14)
0.001592651569876818

julia> sin(sin(sin(3.14)))
0.001592651569876818

Answer 2

The solution with ntuple and splatting works very well up to a certain number of compositions, say 10, and then falls off a performance cliff.

An alternative solution, using reduce, is fast for large numbers of compositions, n, but comparatively slow for small numbers:

compose_(f, n) = reduce(∘, ntuple(_ -> f, n))

I think that the following solution is optimal for both large and small n:

function compose(f, n)
    function (x)  # <- this is syntax for an anonymous function
        val = f(x)
        for _ in 2:n
            val = f(val)
        end
        return val
    end
end

BTW: it is the construction of the composed function which is faster in the approach suggested here. The runtimes of the resulting functions seem to be identical.

Answer 3

Here's a recursive approach:

julia> compose(f, n) = n <= 1 ? f : f ∘ compose(f, n-1)
compose (generic function with 1 method)

julia> compose(x -> 2x, 3)(1)
8

If we're willing to do a little type piracy, we can use the power operator ^ on functions to represent n-th order self-composition:

julia> Base.:^(f::Union{Type,Function}, n::Integer) = n <= 1 ? f : f ∘ f^(n-1)

julia> f(x) = 2x
f (generic function with 1 method)

julia> (f^3)(1)
8