Tuesday, May 26, 2009

C# Puzzle No.16 (advanced)

Anonymous delegates are used extensively in C#. Can you imagine Linq without anonymous delegates?

No matter if an anonymous delegate is defined using "delegate" keyword or as a lambda expression, the delegate does not have any "name" you could use to reference it elsewhere. And frankly, there's no point for an anonymous delegate to have a name ... or maybe there is?

Your goal is to be able to define recursive anonymous delegate in a single expression, so for example you can use such recursive anonymous delegate in Linq.

Specifically, following code should compile and produce a result according to the specification:

   1: List<int> list = new List<int>() { 1,2,3,4,5 };
   2:  
   3: foreach ( var item in
   4:     list.Select( i => [....] ) )
   5:  
   6:    Console.WriteLine( item );
   7:  
   8: /* in the above line, the [....] should be replaced with a body of
   9:    an anonymous recursive delegate defined as follows:
  10: 
  11:    f(i) = 1 when i <= 1
  12:    f(i) = f(i-1) when i>1
  13: 
  14:    ( f(i) is always 1 when i >= 1 )
  15: 
  16:    You can add any auxiliary code under one condition:
  17:    the definition of the recursive delegate can only occur in place of [....]
  18: */
And yes, this is possible in C#.

7 comments:

Deto said...

I'm very creative :))


List<int> list = new List<int>() { 1,2,3,4,5 };
foreach (var item in list.Select( i => {
if(i<=1)
return 1;
StackTrace callStack = new StackTrace();
StackFrame frame = callStack.GetFrame(0);
MethodBase method = frame.GetMethod();

return (int)method.Invoke(null,new object[]{ i-1});

}) ) {
Console.WriteLine( item );
}

Wiktor Zychla said...

what a great solution :) I would never think of anything like that.

can you do it without reflection?

hint:

you should dig around fixed point operator of lambda expressions, known as the "Y operator". Derived by Curry/Turing, the Y operator is used to define recursion in pure lambda calculus. What's less obvious - the Y operator can be defined and used in C#.

Unknown said...

I use google and that's the product: (but I'm not sure)

static void Main(string[] args)
{
List<int> list = new List<int>() { 1,2,3,4,5 };

foreach (var item in list.Select(Y<int,int>(f => i => i <= 1 ? 1 : f(i-1))))
Console.WriteLine(item);
}

delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);

static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
{
Recursive<A, R> rec = r => a => f(r(r))(a);
return rec(rec);
}

Wiktor Zychla said...

That's exactly the solution I've been thinking of. I think it's surprisingly ellegant.

Nonetheless, Deto's solution was indeed very creative.

Mojo said...

Who the what now? Where can I find more information about this wacky Y operator?

Wiktor Zychla said...

http://blogs.msdn.com/wesdyer/archive/2007/02/02/anonymous-recursion-in-c.aspx

http://www.dreamsongs.com/NewFiles/WhyOfY.pdf

http://blogs.msdn.com/madst/archive/2007/05/11/recursive-lambda-expressions.aspx

Mojo said...

Thanks! That's kind of a hard term to google effectively.