High Level Function Confusion with Lambda/LINQ exp

Question

Unsure how to describe this question so the title might be wrong.

Am reading over some code examples and am confused over the following return function:

Func<Func<int , bool>, Func<int , int>, Func<int , int>> Loop = null ;
Loop = (c , f ) => n => c(n) ? Loop(c , f ) ( f (n)): n;
Func<int , int> w = Loop(n => n < 10 , n => n + 2); 
var r = w(2); 
var s = w(3);
Console . WriteLine ("{0} {1}" , r , s );

I understand that this function is returning the Loop when c(n) evaluates to true, but I don't understand how Loop(c,f) (f(n)) evaluates - are they both being passed back into Loop? I have tried running dumps in Linqpad and I just don't get how that bit is running.

Any help would be appreciated, understand this is probably a dumb question!

Answer 1

"I understand that this function is returning the Loop when c(n) evaluates to true, but I don't understand how Loop(c,f) (f(n)) evaluates" - the function doesn't return Loop. The function is Loop and it returns a Func<int, int>.

So, Loop is a function that takes two functions as input and returns a third function. It has the signature Func<Func<int , bool>, Func<int , int>, Func<int , int>> which show this.

Now, Loop = null in the first line so that the when Loop is actually defined on the second line it can recursively call itself.

Then, Loop is basically a function that returns the function n => c(n) ? Loop(c, f)(f(n)) : n. That is Loop will return a function that, given an n in the future, will return Loop(c, f)(f(n)) when c(n) is true and n when it is false;

w is then the return function from Loop when with the parameters n => n < 10 & n => n + 2.

So, substituting those in to Loop you could define w like this:

Func<int, int> w = null;
w = n => n < 10 ? w(n + 2) : n;

Now that can be re-written as this:

int w(int n)
{
    while (n < 10)
    {
        n += 2;
    }
    return n;
}

And hopefully that progression is easy to see.

Answer 2

One way to try to understand it is start small: have basic loop 1-10 with +1 increment.

 Func<int,int> basicLoop = null;
 basicLoop = n => n < 10 ? basicLoop(n+1) : n;

That's pretty simple - basicLoop is function that based on parameter n returns n (for n >= 10) or calls itself with incremented parameter. So basicLoop(8) is computed as:

• basicLoop(8) 8 < 10, so calls basicLoop(8+1) to get result
• basicLoop(9) 9 < 10, so calls basicLoop(9+1) to get result
• basicLoop(10) 10 == 10, so returns n which is 10.
• basicLoop(9) got result 10 (from basicLoop(10)) and returns it
• basicLoop(8) got result 10 (from basicLoop(9))and returns it

Now we want to pass condition as parameter to the loop. That means our "loop" Func will need to pass that condition around on every iteration:

Type of that condition is clearly (similar to n<10) - Func<int, bool>. So now we have something that takes Func<int,bool> as argument and returns same value as our original basicLoop. Hence it will be Func of one argument and one result:

Func<Func<int, bool>, Func<int,int>> condLoop = null;

condLoop is function of one argument - so when defining we take argument: condLoop = (condition) => ....

We need to replace condition in our original basicLoop: n => n < 10 ? ... becomes n => condition(n) ? ....

The last part is replacing basicLoop(n+1) - we have condLoop function that returns equivalent of basicLoop when you pass condition to it. Fortunately our condition does not change between iterations and we already have it - condLoop(condition) is equivalent of basicLoop. Getting it all together:

condLoop = (condition) =>
   n => condition(n) ? 
      condLoop(condition) (n + 1) :
      n; 

Tracing through calls condLoop(x => x < 5)(4)

• condLoop(x => x < 5)(4) - condition is x => x < 5, n = 4 so when condition(4) is called x = 4, 4 < 5 is true - calling condLoop with same condition and increased n - condLoop(x => x < 5)(4 + 1) to get result
• condLoop(x => x < 5)(5) - condition is x => x < 5, n = 5 so when condition(5) is called x = 5, 5 < 5 is false - returning n which is 5
• back to condLoop(x => x < 5)(4) - returning 5 as result of condLoop(x => x < 5)(5)

With similar logic adding function that increments value - on every iteration now you need to pass condition and increment function (c and f in original post).

Answer 3

C#'s anonymous delegate declaration syntax leads to confusion, so I'm going to rewrite it in F#'s function type syntax.

(int -> bool) -> (int -> int) -> (int -> int)

So this is a function that takes two functions and returns a function. The first function it accepts is a predicate, the second is likely a map, and finally it returns a function that accepts an int to return an int.

Loop = (c , f ) => n => c(n) ? Loop(c , f ) ( f (n)): n;

The implementation of the above signature. It takes two parameters, as expected, as c and f. We expect it to return a function, and here it is:

n => c(n) ? Loop(c,f) (f (n)) : n;

I can imagine the Loop(c,f) (f (n)) part is throwing you the most. The result of calling Loop is a function that accepts an integer and returns an integer. n is an integer, and f is a function that takes an integer and returns an integer. In the terms of w it increments that integer by 2. So, given an n of 2, as in the first example, you would pass the result of f(n), 2 + 2, as a new n. So long as c(n) resolves true, you will continue to iterate, with n increasing by 2 each time until greater than or equal to 10.