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 };
   3: foreach ( var item in
   4:     list.Select( i => [....] ) )
   6:    Console.WriteLine( item );
   8: /* in the above line, the [....] should be replaced with a body of
   9:    an anonymous recursive delegate defined as follows:
  11:    f(i) = 1 when i <= 1
  12:    f(i) = f(i-1) when i>1
  14:    ( f(i) is always 1 when i >= 1 )
  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#.


Deto said...

I'm very creative :))

List<int> list = new List<int>() { 1,2,3,4,5 };
foreach (var item in list.Select( i => {
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?


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#.

kralu 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))))

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...




Mojo said...

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