Apply function repeatedly a specific number of times

Question

If you have a function, is there an easy or built-in way to apply it n times, or until the result is something specific. So, for example, if you want to apply the sqrt function 4 times, with the effect of:

julia> sqrt(sqrt(sqrt(sqrt(11231))))
1.791229164345863

you could type something like:

repeatf(sqrt, 11231, 4)

Matthieu

how about recursion? repeatf(fn, x, n) = n == 1 ? fn(x) : repeatf(fn, fn(x), n-1) – Suffruticose

Answer 1

[Edit: See bottom for simple solution without Iterators, though I suggest using it and all the useful functions inside the package]

With Iterators package, the following could be a solution:

julia> using Iterators   # install with Pkg.add("Iterators")
julia> reduce((x,y)->y,take(iterate(sqrt,11231.0),5))
1.791229164345863

iterate does the composition logic (Do ?iterate on the REPL for description). The newer version of Iterators (still untagged) has a function called nth, which would make this even simpler:

nth(iterate(sqrt,11231.0),5)

As a side note, the (x,y)->y anonymous function could nicely be defined with a name since it could potentially be used often with reduce as in:

first(x,y) = x
second(x,y) = y

Now,

julia> reduce(second,take(iterate(sqrt,11231.0),5))
1.791229164345863

works. Also, without recursion (which entails stack allocation and waste), and allocation proportional to the depth of iteration, this could be more efficient, especially for higher iteration values than 5.

Without the Iterators package, a simple solution using foldl is

julia> foldl((x,y)->sqrt(x),1:4, init=11231.0)
1.791229164345863

As before, the reduction operation is key, this time it applies sqrt but ignores the iterator values which are only used to set the number of times the function is applied (perhaps a different iterator or vector than 1:4 could be used in the application for better readability of code)

Tampon

Cool, so you can do it with reduce - I tried that but it said it wanted a binary operator... – Matthieu

Answer 2

I dont know of such a function but you could use this

julia> repeatf(f, x, n) = n > 1 ? f(repeatf(f, x, n-1)) : f(x)

julia> repeatf(sqrt, 11321, 4)
 106.40018796975878

also, even comfier

repeatf(n, f, x...) = n > 1 ? f(repeatf(n-1, f, x...)...) : f(x...)

for functions with more than one arguement

Pointtopoint

Answer 3

I'm a fan of defining that ^ operator to work on Functions and Ints

julia> (^)(f::Function, i::Int) = i==1 ? f : x->(f^(i-1))(f(x))
^ (generic function with 1 method)

julia> (sqrt^1)(2)
1.4142135623730951

julia> (sqrt^2)(2)
1.189207115002721

julia> (sqrt^3)(2)
1.0905077326652577

As @DNF points out, because julia has no Tail Call Optimization, it is better to do this iteratively;

    julia> function (∧)(f::Function, i::Int)
               function inner(x)
                  for ii in i:-1:1
                     x=f(x)
                  end
               x
               end
           end


After warmup:

    julia> @time((sqrt ∧ 1_000)(20e300)) #Iterative
      0.000018 seconds (6 allocations: 192 bytes)
    1.0
    
    julia> @time((sqrt ^ 1_000)(20e300)) #Recursive
      0.000522 seconds (2.00 k allocations: 31.391 KB)
    1.0
    
    #########
    
    julia> @time((sqrt ∧ 10_000)(20e300)) #Iterative
      0.000091 seconds (6 allocations: 192 bytes)
    1.0
    
    
    julia> @time((sqrt ^ 10_000)(20e300)) #Recursive
      0.003784 seconds (20.00 k allocations: 312.641 KB)
    1.0
    
    #########
    
    julia> @time((sqrt ∧ 30_000)(20e300)) # Iterative
      0.000224 seconds (6 allocations: 192 bytes)
    1.0

    julia> @time((sqrt ^ 30_000)(20e300)) #Recursive
      0.008128 seconds (60.00 k allocations: 937.641 KB)
    1.0
    
    
    #############
   
    julia> @time((sqrt ∧ 100_000)(20e300)) #Iterative
      0.000393 seconds (6 allocations: 192 bytes)
    1.0

    julia> @time((sqrt ^ 100_000)(20e300)) #Recursive
    ERROR: StackOverflowError:
     in (::##5#6{Base.#sqrt,Int64})(::Float64) at ./REPL[1]:1 (repeats 26667 times)



The overhead isn't too bad in this case, but that `StackOverflowError` at the end is a kicker.

Molnar

That's pretty cool. I took your idea and implemented it as a repeated application in a loop, thinking that since Julia does not have tail call optimization it would be more efficient. The @code_native output is much shorter for my code than yours, but the performance is identical (down to a hundredth of a microsecond) for sqrt applied 1000 times. – Luminosity

@Luminosity that is because you 1000 is not enough. I'll update the answer – Molnar

I did try with 10^6 too, though, and still no difference. How many do you think is needed? – Luminosity

what version are you on? I was using v0.5rc0. 10^6 just stack-overflows for me. – Molnar

Hmm. Using 0.5 release version. – Luminosity

Why not use higher order functions? (^)(f::Function, n::Integer) = x -> reduce((x, _) -> f(x), 1:n; init = x) – Kisumu

You can also avoid the lambda function by using the \circ operator and support the i=0 case with identity: (^)(f::Function, i::Int) = i==0 ? identity : f^(i-1)∘f – Levis

Answer 4

function apply(f, x, n=1)
    for _ in 1:n
        x = f(x)
    end
    return x
end

Luminosity

Answer 5

I find neither of the above answers satisfying. They all work, but none of them are truly elegant. My personal favorite is this:

Base.repeat(f::Function, n::Integer) = reduce(∘, fill(f, n))

Of course, you don't even need to define repeat, you can just use the reduce(...) construct directly.

And this is how it would be used in the case of the original example:

julia> repeat(sqrt, 4)(11231)
1.791229164345863

or

julia> reduce(∘, fill(sqrt, 4))(11231)
1.791229164345863

Kisumu