Path: news.mathworks.com!not-for-mail
From: Mike Karr <mkarr@mathworks.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Recursive anonymous function
Date: Mon, 09 Mar 2009 13:25:33 -0400
Organization: The MathWorks, Inc.
Lines: 104
Message-ID: <gp3jed$42m$1@fred.mathworks.com>
References: <gp22jh$sif$1@fred.mathworks.com>
NNTP-Posting-Host: mkarr-deb4-64.dhcp.mathworks.com
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: fred.mathworks.com 1236619533 4182 144.212.105.163 (9 Mar 2009 17:25:33 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Mon, 9 Mar 2009 17:25:33 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.8.0.11) Gecko/20070217 Iceape/1.0.8 (Debian-1.0.8-4)
In-Reply-To: <gp22jh$sif$1@fred.mathworks.com>
Xref: news.mathworks.com comp.soft-sys.matlab:523535


Brandon wrote:
> Hello,
> 
> I have been playing with anonymous functions.
> As you cannot have if or while statements, I am trying to see if I can emulate them.
> 
> An if statement can be done with boolean logic
> (I believe this construct is called a binary switch)
> iff = @(cond,t,f)((cond==true).*t + (cond==false).*f);
> 
> As with a m-file version of iff, the downside is that both the true and false conditions need to be evaluated.
> 
> Now my thoughts for doing a while loop is to use recursion.
> my example program is
> function res = sumval(x,i)
>     if i == 1
>        res = x(i);
>     else
>        res = x(i) + sumval(x,i-1);
>     end
> end
> 
> thus sumval(1:5,5) => 15
> 
> As an anonymous function I have got:
> sumval = @(x,i)(x(i) + eval(char(iff(i==1,'0', 'sumval(x,i-1)'))));
> 
> Now my problem is that the anonymous function works inside an m-file
> 
> eg:
> 
> function res = sumv()
>     iff = @(cond,t,f)((cond==true).*t + (cond==false).*f);
>     sumval = @(x,i)(x(i) + eval(char(iff(i==1,'0', 'sumval(x,i-1)'))));
>     res = sumval(1:5,5);
> end
> 
> sumv() => 15
> 
> but just running the 3 statements in the workspace causes an error:
> ??? Error using ==> eval
> Undefined function or method 'sumval' for input arguments of type 'double'.
> 
> This tells me that the scope of the sumval function does not include the workspace scope. However, even if I define iff and sumval to be global, the error still happens.
> 
> How can I make a global anonymous function which is recursive?
> That is: I want to define an anonymous function in the workspace and have it be globally accessable to itself
> 
> Brandon

There is an answer to this question that is, on the one hand, worth 
understanding if you want to know more about the theory of programming 
languages, and on the other, is not really a pragmatic solution.  First, 
start with the conditional part.  They way to do this generically, 
addressing the problem pointed out by Bruno Luong, is to turn a boolean 
value into an index.  The following function handle is designed to take 
three arguments, the first a boolean value, and the second two, function 
handles taking no arguments and yielding a desired result.  Taking these 
arguments via varargin provides a cell that can be indexed:

 >> ifthenelse = @(b,varargin) varargin{2-b}();

You with me?

Now comes the heavy lifting, the part about the theory of programming 
languages.  As background, recall that the "fixed point" x of a function 
F has the property that F(x) = x.  That's easy.  The deep part, which I 
won't explain here, is that recursion can be view as the fixed point of a
function that takes a functional argument.  The idea is to obtain 
recursion by applying a fixed point operator to a more or less obvious 
encoding of the recursive function.  The traditional name for the fixed 
point operator in this context is Y, so for factorial, one would write:

 >> fact = Y(@(fct)@(n)ifthenelse(n==0 ,@()1, @()n*fct(n-1)));

In other words, Y is given a function @(fct)<defn. of factorial>, where 
the <defn. of factorial> just uses the argument fct as if it is a 
function.  It is not too hard to see that, given the above ifthenelse, 
the above encodes the recursive definition of factorial in the obvious way.

Now comes the astonishing part:  it is possible to write Y using 
anonymous functions (both of which must be defined at the prompt 
_before_ the assignment to fact.  The first of these functions is 
essentially feval, just renamed to show that all you really need is 
application of function handles:

 >> apply = @(f,x) f(x);

The Y operator itself is completely unscrutable, at least to me:

 >> Y = @(f) apply(@(g)g(g), @(h)f(@(y) apply(h(h), y)));

I just typed these definitions to R2009a (in the order first, third, 
fourth, second), followed by:

 >>  fact(5)

The result, as you would expect, is the same as gamma(6).

Not pretty anonymous functions, not a fast implementation, but some very 
elegant mathematics.

for your enjoyment,
mike