Использование Y Combinator в C#

Question

Я пытаюсь понять, как писать рекурсивные функции (например, факториал, хотя мои функции намного сложнее) в одной строке. Для этого я подумал об использовании Lambda Calculus'Y combinator.

Вот первое определение:

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

Вот приведенное определение:

Y g = g(Y g) 

Я попытался записать их в C# как это:

// 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 является Func<dynamic, dynamic> . Сначала я попытался набрать его., но that didn't work, так что теперь он определен с delegate dynamic Lambda(dynamic arg);)

Мой факторный лямбда выглядит следующим образом (адаптировано из here):

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

И я называю это так:

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

Однако , в обоих случаях (оригинальные и уменьшенные формы Y-комбинатора), я получаю исключение переполнения стека. Из того, что я могу предположить, используя приведенную форму, кажется, что она просто заканчивается вызовом Y(factorial(Y(factorial(Y(factorial(... и никогда не заканчивается фактически , вводя факториал лямбда.

Так как у меня нет большого опыта отладки C# лямбда-выражений, а я , конечно, не понимают большую часть лямбда-исчисления, я действительно не знаю, что происходит или как это исправить.

В случае, если это имеет значение, этот вопрос был вдохновлен попыткой написать однострочный ответ на this question в C#.

Мое решение заключается в следующем:

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(); 

Моя цель состоит в том, чтобы написать getPermutations как один линии само-рекурсивное лямбда, так что я могу вставить его в SelectMany в AllSubstrings и сделать одну гильзу из от AllSubstrings.

Мои вопросы следующие:

1. ли Y возможно комбинатор в C#? Если да, то что я делаю неправильно в реализации?
2. Если комбинатор Y является возможным в C#, как бы я сделал свое решение проблемы с подстроками (функция AllSubstrings) одним слоем?
3. Независимо от того, является ли комбинатор Y , а не Возможны ли в C#, есть ли какие-либо другие методы программирования, которые позволяли бы однострочный AllSubstrings?

Answer 1

Вот реализация Y-комбинатора, который я использую в 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)); 
} 

я могу использовать его как:

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

Это действительно пугает меня, так что я оставлю следующие две части вашего вопроса вам, учитывая это как отправную точку.

---

У меня была трещина в функции.

Здесь:

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()); 

Конечно, вы запустите его так:

allsubstrings("abcd"); 

Из которых я получил этот результат:

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 

кажется, что ваш не -Y-Комбинаторный код в вашем вопросе пропустил кучу перестановок.