Defining a generic function for iterated function composition

Question

Let us define any function handle foo:

foo = @(x) x*2

I am trying to write a general function defFun that generates the n-th functional power of the function foo, i.e. n iterative calls of foo, in a way it can be stored in another handle function boo, like this:

boo = defFun(foo,n)

For example,

foo = @(x) x^2;  
boo = defFun(foo,3);

boo(3) will give 6561 [== foo(foo(foo(3)))] and boo(2) will give 256 [== foo(foo(foo(2)))].

I tried this code to write defFun but these handles are tricky to deal with. Any ideas?

function boo = defFun(foo,n)
   h = foo;
   for i=2:n
      h = h(h);
   end
   boo = h
end

Answer 1

My code pretty much resembles your original one. I took the liberty to rename a few of the variables.

Direct approach:

For single input and single output argument you could use the direct approach resembling your code:

function ftoN = fIterate(f, N)
    ftoN = f;
    for i = 2:N
        ftoN = @(x) f(ftoN(x)); 
    end
end

Indirect approach: (possibly faster)

This one will be a lot faster and it will also work for multiple (but same number of) inputs and outputs.

function ftoN = fIterate(f, N)
    ftoN = @(varargin)   fIterateLocal(f, N, varargin{:});
    function varargout = fIterateLocal(f, N, varargin)
        varargout = varargin;
        for i = 1:N
            [varargout{1:nargin-2}] = f(varargout{:});
        end
    end
end

Example:

Both approaches should work with this:

square = @(x) x^2;
square(2)
>> ans = 4

squaresquaresquare = fIterate(square, 3)
squaresquaresquare(3)
>> ans = 6561

Aftermath:

The direct approach will be rather slow and also limited by the Maximum recursion limit of MATLAB.

timeit(@()feval(fIterate(@(X)X+1,400),0))
ans = 1.2160

The indirect approach will give you a lot more speed and flexibility:

timeit(@()feval(fIterate(@(X)X+1,400),0))
ans = 0.0072

Answer 2

The 3 solutions here rely on building a string then using str2func to get a function handle out of it. Different implementations for the same functionality but different readability of the result.

Note that as highlighted in the comment (thanks knedlsepp), the order of recursion n cannot exceed 32.

---

One way is to parse the input function string definition and recreate it recursively in a string before converting that to a function handle:

function boo = defFun(foo,n)

   %% // retrieve the string of the initial function
   A = functions(foo) ;
   fstrfull = A.function ;

   %% // find "input variables" in the header
   [i1 i2] = regexp(fstrfull, '\(([^\)]+)\)' , 'once' ) ;   %// probably can be improved, regexp are not my strong suit
   strVar = fstrfull(i1+1:i2-1) ;  %// =>  strVar='x'       %// to get rid of the parenthesis returned by the regex

   %% // isolate only the function expression (without the header)
   ilast = strfind( fstrfull , ')' )+1 ;  %// ilast= 5      find the last position of the header
   fstr = fstrfull(ilast(1):end) ;        %// fstr='x.^2'   separate only function expression

   %% // replace "variables" by the expression the desired number of time
   strFinalFunction = fstr ;
   for i=2:n
      strFinalFunction = strrep(strFinalFunction, strVar, ['(' fstr ')'] ) ;
   end
   boo = str2func( ['@(' strVar ')' strFinalFunction ] ) ;

end

This will give you:

>> boo = defFun(foo,3)
boo = 
    @(x)((x.^2).^2).^2 // <= your function shows the full expression

>> boo(3)
ans =
        6561

It will work for much more complex cases as long as the input function only take one variable as input.

---

Alternatively, there is a simpler method which should be even more generic. It requires no parsing and thus and will work in the potential case the parsing in the solution above fails. The downside is the function definition become very opaque.

function boo = defFun2(foo,n)

cfoo = {foo} ; %// place the function handle in a cell

%// create a string calling the function on itself N number of times
strFun = ['@(x) ' repmat('cfoo{1}(',1,n) 'x' repmat(')',1,n) ] ;

%// Generate a function handle for the corresponding function
boo = str2func( strFun ) ;

But now your function definition look like this:

>> boo = defFun2(foo,3)
boo = 
    @(x)cfoo{1}(cfoo{1}(cfoo{1}(x))) // <= your function does not show what it does (only the number of time it calls itself)

Much less readable, but it still gives the right results.

---

Lastly, if readability is critical, you can also include the name of the original function in the function definition but you'll have to resort to the controversial eval.

function boo = defFun3(fh,n)

fname = inputname(1) ;        %// get the name of the function which was called
eval( [ fname '={fh};' ] ) ;  %// place the function handle in a cell

strFun = ['@(x) ' repmat([fname '{1}('],1,n) 'x' repmat(')',1,n) ] ; %// create a string calling the function on itself N number of times
boo = str2func( strFun ) ;                                           %// Generate a function handle for the corresponding function

This now gives you:

boo = defFun3(foo,3)
boo = 
    @(x)foo{1}(foo{1}(foo{1}(x))) // <= now you know that boo is the function 'foo' called on itself 3 times.