Recursively applied 1D function

General Usage
1

Hello,

I am trying to compose the same function with itself n times efficiently. I found a way of doing that using macros, but it gave me a lot of problems when being used within functions and using elements that were not parts of the global scope. So, an example that was working well, before using it in a local scope was:

macro recur(map_name, iter_num, val_input)
	eval(Meta.parse(string(string(map_name, "(")^iter_num, val_input, ")"^iter_num)))
end

and then using, for instance:

g(x) = x^2

@recur g 10 1.001

which yields: 2.7828855056543795. I also did a similar thing using a function, but the core concept remains the same.

My question is: What would be a better way of doing this? Is there some built-in way of manipulating composition of function, without having to write up explicitly the composition, like g(g(g(g(g(g(g(g(g(g(1.001)))))))))) or (g∘g∘g∘g∘g∘g∘g∘g∘g∘g)(1.001)?

Thanks!

2

The first note I’d make is that it’s ~never necessary to use string manipulation, eval, or Meta.parse inside a macro. One of the many reasons not to use eval in particular is that it causes your code to be run when the macro is expanded, which is almost never what you want:

julia> macro recur(map_name, iter_num, val_input)
               eval(Meta.parse(string(string(map_name, "(")^iter_num, val_input, ")"^iter_num)))
       end
@recur (macro with 1 method)

julia> f() = @recur g 10 1.001
ERROR: LoadError: UndefVarError: g not defined

This fails (in a new Julia session) because eval tries to call g(...) when you define f, which is definitely wrong.

Fortunately, it’s easy to avoid strings, eval and Meta.parse because Julia’s built-in expression objects are much easier to work with. A macro similar to yours but with none of those red flags might be:

julia> macro recur(map_name, iter_num, val_input)
         expr = :($(esc(map_name)))  # start with a single call
         for i in 2:iter_num
           expr = :($(esc(map_name)) ∘ $expr)  # turn `f` into `f \circ f`
         end
         return quote # return an expression which computes the result
           $(expr)($(esc(val_input))) 
         end
       end
@recur (macro with 1 method)

However, I don’t really think there’s any need for metaprogamming here at all. Instead, I’d just write a function:

julia> function recur(f, iter_num, val)
         @assert iter_num >= 1
         output = f(val)
         for i in 2:iter_num
           output = f(output)
         end
         return output
       end
recur (generic function with 1 method)

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

julia> recur(g, 10, 1.001)
2.7828855056543795

Or, if you want something without a loop, then we can use, well, recursion…

julia> function recur(f, iter_num, val)
         @assert iter_num >= 1
         if iter_num == 1
           f(val)
         else
           f(recur(f, iter_num - 1, val))
         end
       end
recur (generic function with 1 method)

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

julia> recur(g, 10, 1.001)
2.7828855056543795
3 Likes
3

Note that ∘ accepts any number of arguments, so you can do this (even if you probably shouldn’t):

julia> Base.:^(f::Function, n::Int) = ∘(ntuple(_ -> f, n)...)

julia> sin^3
sin ∘ sin ∘ sin

julia> ((!)^17)(true)
false
2 Likes
4

This great post by @FedericoStra, might be of interest.
Applying it to OP’s case:

g(x) = x^2
Gn(x, n) = foldl((y,_) -> g(y), 1:n; init=x)
Gn(1.001, 10)
2.7828855056543795
2 Likes