在C＃中使用Y Combinator [英] Using the Y Combinator in C#

问题描述

我试图弄清楚如何在一行中编写递归函数（例如阶乘，尽管我的函数更复杂）。为此，我考虑使用 Lambda微积分 Y combinator 。

以下是第一个定义：

  Y =λf。（λx.f（xx））（λx.f（xx））
  

下面是精简定义：

  Y g = g（Y g）
  

我试图用C＃编写它们： p>

  //原始
 Lambda Y = f => （新Lambda（x => f（x（x）））（新Lambda（x => f（x（x）））））; 
 //减少
 Lambda Y = null; Y = g =>克（Y（克））; 
  

（ Lambda 是 Func< dynamic，dynamic> 。我首先尝试使用，但不起作用，所以现在用委托动态Lambda（动态参数） code>）





我的阶乘lambda看起来像这样（改编自 here ）：

  Lambda factorial = f =>新的λ（n => n == 1？1：n * f（n-1））; 
  

我称之为：

  int result =（int）（Y（factorial））（5）; 
  

然而，在这两种情况下（Y组合器的原始形式和简化形式）堆栈溢出异常。从我从使用简化形式中可以推测出来的结果看起来好像它最终只是调用 Y（factorial（Y（factorial（Y（factorial（... ）而从不）因为我没有太多的调试C＃lambda表达式的经验，而且当然 当然 em>不太了解lambda演算，我真的不知道发生了什么或如何解决它。

如果有问题，这个问题是灵感来自于试图写一个单行答案给这个问题在C＃中。

我的解决方案如下：

 静态IEnumerable< string> AllSubstrings（字符串输入）
 {
返回值（来自Enumerable.Range中的i（0，input.Length）
从Enumerable.Range中的j（1，input.Length  -  i）
 select input.Substring （i，j））
 .SelectMany（substr => getPermutations（substr，substr.Length））; 
} 
 static IEnumerable< string> getPermutations（字符串输入，int长度）
 {
返回长度== 1？ input.Select（ch => ch.ToString（））：
 getPermutations（input，length  -  1）.SelectMany（
 perm => input.Where（elem =>！perm.Contains （elem）），
（str1，str2）=> str1 + str2）; 
 
 //这样调用：
 string [] result = AllSubstrings（abcd）。ToArray（）; 
  

我的目标是写 getPermutations 作为一行自递归lambda，以便我可以将它插入到 AllSubstrings 中的 SelectMany 中并创建一个单行 AllSubstrings 。

我的问题如下：

1. C＃中的Y组合器是否可行？如果是这样，我在做什么错误？


2. 如果在C＃中Y组合器是可能的，我将如何使我的解决方案的子字符串问题 AllSubstrings 函数）是单行的吗？


3. 是否可以在 C＃中，是否还有其他编程方法可用于单线程 AllSubstrings ？

解决方案

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

 <$ c $公共代理T S（T T）; T T（S T）。 
 
 public static T U< T>（S> s）
 {
 return s（s）; 
} 
 
 public static Func< A，Z> Y< A，Z>（Func ，Func > 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 （_ => x => x< = 1？1：_（x-1）+ _（x-2））; 
  

真的让我害怕，所以我会把你的问题的下两部分留给你，给定这是一个出发点。

---

我对这个函数有了一个破解。

这里是：

  var allsubstrings = 
 Y< string，IEnumerable< string> > 
（_ => x => x.Length == 1 
？new [] {x} 
：可枚举
 .Range（0，x.Length）
 .SelectMany（i => 
 _（x.Remove（i，1））
 .SelectMany（z => new [] {xSubstring（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组合代码错过了一堆排列组合。

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.

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:

// 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);)

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.

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.

In case it matters, this question was inspired by trying to write a one-line answer to this question in 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.

My questions are the following:

1. Is the Y combinator possible in C#? If so, what am I doing wrong in the implementation?
2. If the Y combinator is possible in C#, how would I make my solution to the substrings problem (the AllSubstrings function) a one-liner?
3. 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?

解决方案

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

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.

这篇关于在C＃中使用Y Combinator的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！