Apply function repeatedly a specific number of times
[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),11231.0,1:4)
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)
I'm a fan of defining that ^
operator to work on Function
s and Int
s
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.
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