在C＃中使用Y Combinator

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

这是第一个定义：

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

这是减少的定义：

 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 。我首先尝试使用usedef它，但这不起作用 ，所以现在用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组合器的原始forms和简化forms），我最终都会出现堆栈溢出exception。 从我可以推测使用简化forms，似乎它最终调用Y(factorial(Y(factorial(Y(factorial(...并且永远不会最终进入阶乘lambda）。

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

如果它很重要，这个问题的灵感来自于试图用C＃写这个问题的单行答案。

我的解决方案如下：

 static IEnumerable 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 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，以便我可以将它插入AllSubstrings的SelectMany并从AllSubstrings创建一个AllSubstrings 。

我的问题如下：

1. 在C＃中Y组合器是否可行？ 如果是这样，我在实施中做错了什么？
2. 如果在C＃中可以使用Y组合器 ，那么如何使我的解决方案解决子串问题（ AllSubstrings函数）的问题呢？
3. 无论在C＃中是否无法使用Y组合器，是否还有其他编程方法可以实现AllSubstrings ？

Answer 1

这是我在c＃中使用的Y-combinator的实现：

 public delegate T S(S s); public static T U(S s) { return s(s); } public static Func Y(Func, Func> f) { return U>(r => a => f(U(r))(a)); } 

我可以像以下一样使用它：

 var fact = Y(_ => x => x == 0 ? 1 : x * _(x - 1)); var fibo = Y(_ => x => x <= 1 ? 1 : _(x - 1) + _(x - 2)); 

它真的让我很害怕，所以我将把你问题的下两部分留给你，以此为出发点。

---

我对这个function有所了解。

这里是：

 var allsubstrings = Y> (_ => 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代码似乎错过了一堆排列。