在c#中使用Y Combinator。

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.

我想知道如何写递归函数(例如阶乘，尽管我的函数要复杂得多)在一行中。为了做到这一点，我想到了微积分的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:

我试着用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 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);)

(Lambda是一个Func )。我第一次尝试用它来定义它，但那没有用，所以现在它是用委托动态Lambda(动态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.

但是，在这两种情况(Y combinator的原始和简化形式)中，我最后都有一个stack overflow异常。从我可以推测出的使用简化形式，它看起来就好像它只是结束调用Y(阶乘(Y) (Y)永远不会最终进入阶乘。

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.

由于我没有太多调试c# lambda表达式的经验，而且我也不太了解lambda演算，所以我不知道到底发生了什么，也不知道该如何修复它。

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

如果它很重要，这个问题的灵感来自于尝试用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.

我的目标是将getper突变写为一行的自递归，这样我就可以将它插入到AllSubstrings中的SelectMany中，并从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. 在c#中是否可以使用Y combinator ?如果是，那么在实现中我做错了什么?
3. If the Y combinator is possible in C#, how would I make my solution to the substrings problem (the AllSubstrings function) a one-liner?
4. 如果在c#中可以使用Y combinator，那么我如何将我的解决方案应用到子字符串问题(AllSubstrings函数)中呢?
5. 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?
6. 是否在c#中不可能有Y combinator，是否还有其他的编程方法可以让一个内衬的allsubstring ?

1 个解决方案

#1

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

下面是我在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));
}

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.

似乎你的问题中你的非y - combinator代码漏掉了一堆排列。