Using the Y Combinator in C#

Question

I'm trying to figure out how to write recursive functions (e.g. factorial, although my functions are much more complicated) in one line. To do this, I thought of using the Lambda Calculus' Y combinator.

Here's the first definition:

Y = λf.(λx.f(x x))(λx.f(x x)) 

Here's the reduced definition:

Y g = g(Y g) 

I attempted to write them in C# like this:

// Original Lambda Y = f => (new Lambda(x => f(x(x)))(new Lambda(x => f(x(x))))); // Reduced Lambda Y = null; Y = g => g(Y(g)); 

(Lambda is a Func<dynamic, dynamic>. I first tried to typedef it with using, but that didn't work, so now it's defined with delegate dynamic Lambda(dynamic arg);)

My factorial lambda looks like this (adapted from here):

Lambda factorial = f => new Lambda(n =>  n == 1 ? 1 : n * f(n - 1)); 

And I call it like this:

int result = (int)(Y(factorial))(5); 

However, in both cases (original and reduced forms of the Y combinator), I end up with a stack overflow exception. From what I can surmise from using the reduced form, it seems as if it just ends up calling Y(factorial(Y(factorial(Y(factorial(... and never ends up actually entering the factorial lambda.

Since I don't have much experience debugging C# lambda expressions and I certainly don't understand much of the lambda calculus, I don't really know what's going on or how to fix it.

In case it matters, this question was inspired by trying to write a one-line answer to this question in C#.

My solution is the following:

static IEnumerable<string> AllSubstrings(string input) {     return (from i in Enumerable.Range(0, input.Length)             from j in Enumerable.Range(1, input.Length - i)             select input.Substring(i, j))             .SelectMany(substr => getPermutations(substr, substr.Length)); } static IEnumerable<string> getPermutations(string input, int length) {     return length == 1 ? input.Select(ch => ch.ToString()) :         getPermutations(input, length - 1).SelectMany(             perm => input.Where(elem => !perm.Contains(elem)),             (str1, str2) => str1 + str2); } // Call like this: string[] result = AllSubstrings("abcd").ToArray(); 

My goal is to write getPermutations as a one-line self-recursive lambda so that I can insert it into the SelectMany in AllSubstrings and make a one-liner out of AllSubstrings.

My questions are the following:

1. Is the Y combinator possible in C#? If so, what am I doing wrong in the implementation?
2. If the Y combinator is possible in C#, how would I make my solution to the substrings problem (the AllSubstrings function) a one-liner?
3. Whether or not the Y combinator is not possible in C#, are there any other methods of programming that would allow for one-lining AllSubstrings?

Answer 1

Here's the implementation of the Y-combinator that I use in c#:

public delegate T S<T>(S<T> s);  public static T U<T>(S<T> s) {     return s(s); }  public static Func<A, Z> Y<A, Z>(Func<Func<A, Z>, Func<A, Z>> f) {     return U<Func<A, Z>>(r => a => f(U(r))(a)); } 

I can use it like:

var fact = Y<int, int>(_ => x => x == 0 ? 1 : x * _(x - 1)); var fibo = Y<int, int>(_ => x => x <= 1 ? 1 : _(x - 1) + _(x - 2)); 

It truly scares me, so I'll leave the next two parts of your question to you, given this as a starting point.

---

I've had a crack at the function.

Here it is:

var allsubstrings =     Y<string, IEnumerable<string>>         (_ => x => x.Length == 1             ? new [] { x }             : Enumerable                 .Range(0, x.Length)                 .SelectMany(i =>                     _(x.Remove(i, 1))                     .SelectMany(z => new [] { x.Substring(i, 1) + z, z }))                 .Distinct()); 

Of course, you run it like this:

allsubstrings("abcd"); 

From which I got this result:

abcd  bcd  acd  cd  abd  bd  ad  d  abdc  bdc  adc  dc  abc  bc  ac  c  acbd  cbd  acdb  cdb  adb  db  acb  cb  ab  b  adbc  dbc  adcb  dcb  bacd  bad  badc  bac  bcad  cad  bcda  cda  bda  da  bca  ca  ba  a  bdac  dac  bdca  dca  cabd  cadb  cab  cbad  cbda  cba  cdab  dab  cdba  dba  dabc  dacb  dbac  dbca  dcab  dcba  

It seems that your non-Y-Combinator code in your question missed a bunch of permutations.