Verwendung des Y-Kombinators in C#

Question

Ich versuche herauszufinden, wie rekursive Funktionen (z. B. Fakultät, obwohl meine Funktionen sind viel komplizierter) in einer Zeile schreiben. Um dies zu tun, dachte ich an die Verwendung der Lambda Calculus'Y combinator.

Hier ist die erste Definition:

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

Hier ist die reduzierte Definition:

Y g = g(Y g) 

Ich versuchte sie, wie dies in C# zu schreiben:

// 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 ist ein Func<dynamic, dynamic> Ich habe zuerst versucht, es mitzu schreiben, aber that didn't work, es ist mit delegate dynamic Lambda(dynamic arg);) von here

Mein faktorielles Lambda sieht wie folgt aus (angepasst so jetzt definiert):

Lambda factorial = f => new Lambda(n => n == 1 ? 1 : n * f(n - 1)); 

Und ich es so nennen:

int result = (int)(Y(factorial))(5); 

jedoch In beiden Fällen (ursprüngliche und reduzierte Form des Y-Kombinators) habe ich eine Stapelüberlauf-Ausnahme. Von dem, was ich von der Verwendung der reduzierten Form vermuten kann, scheint es, als ob es am Ende ruft Y(factorial(Y(factorial(Y(factorial(... und endet nie tatsächlich Eingabe die faktorielle Lambda.

Da ich nicht viel Erfahrung Debuggen C# Lambda-Ausdrücke kann als ich sicherlich nicht viel von dem Lambda-Kalkül verstehen, ich weiß nicht wirklich, was los ist oder wie man es beheben.

Falls es darauf ankommt, wurde diese Frage dadurch angeregt, dass Sie in C# eine einzeilige Antwort auf this question schreiben wollten.

Meine Lösung ist folgende:

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

Mein Ziel ist es getPermutations als einzeilige selbst rekursive Lambda zu schreiben, so dass ich es in die SelectMany in AllSubstrings einfügen können und einen Einzeiler ausmachen von AllSubstrings.

Meine Fragen sind:

1. Ist Y Combinator möglich in C#? Wenn ja, was mache ich bei der Implementierung falsch?
2. Wenn der Y-Kombinator in C# möglich ist, wie würde ich meine Lösung für das Teilstrings-Problem (die AllSubstrings-Funktion) ein Einzeiler machen?
3. Ob der Y-Kombinator ist nicht in C# möglich, gibt es andere Methoden der Programmierung, die für One-Lining AllSubstrings ermöglichen würde?

Answer 1

Hier ist die Umsetzung des Y-Combinator, die ich in C# verwenden:

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

Ich mag es verwenden kann:

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

Ich werde Es erschreckt mich wirklich, so lassen die nächsten beiden Teile deiner Frage an dich, ausgehend davon.

---

Ich hatte einen Riss bei der Funktion.

Hier ist sie:

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

Natürlich führen Sie es wie folgt aus:

allsubstrings("abcd"); 

aus dem ich dieses Ergebnis bekam:

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 

Es dass Ihr nicht scheint -Y-Combinator Code in Ihrer Frage verpasste eine Reihe von Permutationen.