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)

Answer 1

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.

Answer 2

[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)

Answer 3

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