在C#中使用Y组合子

Question

在C#中使用Y组合子

c#functionlambdafunctional-programmingy-combinator

24

我正在尝试弄清如何在一行中编写递归函数（例如阶乘，尽管我的函数要复杂得多）。为了做到这一点，我想使用Lambda演算的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();

我的目标是编写一个一行式的自递归 lambda 函数 getPermutations，以便将其插入到 AllSubstrings 的 SelectMany 中，并让 AllSubstrings 成为一行式。

我的问题如下：

在 C# 中是否可能使用 Y 组合子？如果是，则我在实现中做错了什么？
如果在 C# 中可以使用 Y 组合子，那么我如何使字符串子串问题的解决方案（AllSubstrings 函数）成为一行代码？
无论 Y 组合子是否在 C# 中可行，是否有其他编程方法可以使 AllSubstrings 成为一行代码？

- Jashaszun

3

只有在惰性求值时，Y g = g(Y g) 才是有效的。在急切求值时，解决方法是使用 eta-扩展：Y g = g (\x-> (Y g) x)。或者也许 Y g x = g (\x-> (Y g) x) x 更容易理解。 - Will Ness

1

@WillNess 谢谢！当我将它写成 Lambda y = null; y = g => g(new Lambda(x => (y(g))(x))); 时，它起作用了。好吧，我想这回答了第一个问题。 - Jashaszun

1

如果我给你一个 Haskell 半单行代码，会有帮助吗？它是 concatMap permutations . sequences，其中 sequences (x:xs) = [a | b<-sequences xs, a<-[x:b,b] ] ; sequences [] = [[]]，而 permutations 是一个标准函数。 - Will Ness

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Enigmativity · Accepted Answer

以下是我在C#中使用的Y组合子的实现代码:

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 代码缺少了一些排列组合。