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

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

Здесь первое определение:

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

Здесь приведенное определение:

Y g = g(Y g)

Я попытался записать их на С# следующим образом:

// 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>. Сначала я попытался набрать его с помощью using, но который не работал, поэтому теперь он определен с помощью delegate dynamic Lambda(dynamic arg);)

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

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

И я называю это следующим образом:

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

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

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

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

Мое решение следующее:

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.

Мои вопросы таковы:

  • Возможно ли Y combinator в С#? Если да, то что я делаю неправильно в реализации?
  • Если в С# возможно Y combinator, как бы я сделал решение проблемы с подстроками (функция AllSubstrings) одним слоем?
  • Можно ли использовать Y combinator в С#, есть ли какие-либо другие методы программирования, которые позволяли бы однострочный AllSubstrings?

Ответы

Ответ 1

Здесь реализация Y-combinator, которую я использую в С#:

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-Combinator в вашем вопросе пропустил кучу перестановок.