我试图弄清楚如何在一行中编写递归函数（例如阶乘，尽管我的函数要复杂得多）。为此，我想到了使用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>。我第一次尝试用 typedef 它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一个单行自递归 lambda，这样我就可以将它插入到SelectManyinAllSubstrings并制作一个单行AllSubstrings.
我的问题如下：
- 在 C# 中是否可以使用 Y 组合器？如果是这样，我在实施中做错了什么？
- 如果 Y 组合器在 C# 中是可能的，我将如何使我对子字符串问题（
AllSubstrings函数）的解决方案单行？ - 在 C# 中是否不可能使用 Y 组合器，是否还有其他允许单线的编程方法
AllSubstrings？