在C#中使用Y Combinator

Question

我试图弄清楚如何在一行中编写递归函数(例如阶乘,尽管我的函数要复杂得多).为此,我想到了使用Lambda Calculus的 Y组合器.

这是第一个定义:

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>.我首先尝试用它来键入它using,但这不起作用,所以现在它定义了delegate dynamic Lambda(dynamic arg);)

我的阶乘lambda看起来像这样(改编自这里):

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(...并且永远不会最终进入阶乘lambda.

由于我没有多少经验调试C#lambda表达式,我当然不太了解lambda演算,我真的不知道发生了什么或如何解决它.

如果它很重要,这个问题的灵感来自于试图用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. 在C#中Y组合器是否可行？如果是这样,我在实施中做错了什么？
2. 如果在C#中可以使用Y组合器,那么如何使我的解决方案对子串问题(AllSubstrings函数)成为单线程？
3. 无论是否Y组合是不是可以在C#中,有没有任何编程等方法将允许一个衬AllSubstrings？

Answer 1

这是我在c#中使用的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代码似乎错过了一堆排列.