Utilizzando la Y Combinator in C#

Question

Sto cercando di capire come scrivere funzioni ricorsive (ad esempio fattoriale, anche se le mie funzioni sono molto più complicato) in una sola riga. Per fare questo, ho pensato di usare la Lambda Calculus'Y combinator.

Ecco la prima definizione:

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

Ecco la definizione ridotta:

Y g = g(Y g) 

ho cercato di scrivere in C# come questo:

// 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 è un Func<dynamic, dynamic> Per prima cosa ho provato a digitarlo con using, ma that didn't work, così ora è definito con delegate dynamic Lambda(dynamic arg);)

mio lambda fattoriale simile a questa (adattato da here):

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

E io lo chiamo così:

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

Tuttavia , in entrambi i casi (forme originali e ridotte del combinatore Y), alla fine con un'eccezione di overflow dello stack. Da quello che posso supporre di utilizzare la forma ridotta, sembra come se finisce solo per chiamare Y(factorial(Y(factorial(Y(factorial(... e mai finisce in realtà entrare lambda fattoriale.

Poiché non ho molta esperienza nel debug di espressioni C# lambda e I certamente non capisco molto del calcolo lambda, non so davvero cosa sta succedendo o come risolverlo.

Nel caso in cui è importante, questa domanda è stato ispirato, cercando di dare una risposta a una linea per this question in C#.

La mia soluzione è la seguente:

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

Il mio obiettivo è quello di scrivere getPermutations come lambda auto-ricorsiva di una riga in modo che possa inserirla nella SelectMany in AllSubstrings e fare una battuta fuori di AllSubstrings.

Le mie domande sono le seguenti:

1. È il combinatore Y possibile in C#? Se sì, cosa sto sbagliando nell'implementazione?
2. Se il combinatore Y è possibile in C#, come potrei rendere la soluzione al problema delle sottostringhe (la funzione AllSubstrings) a un liner?
3. Se il combinatore Y è non possibile in C#, ci sono altri metodi di programmazione che consentirebbero il rivestimento singolo AllSubstrings?

Answer 1

Ecco l'attuazione della Y-Combinator che uso 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)); 
} 

posso usarlo come:

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

Mi spaventa veramente, quindi lascio le prossime due parti della tua domanda a te, dato questo come punto di partenza.

---

Ho avuto una crepa alla funzione.

Eccolo:

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

Naturalmente, lo si esegue in questo modo:

allsubstrings("abcd"); 

da cui ho ottenuto questo risultato:

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 

La tua non -Y-Il codice Combinator nella tua domanda ha mancato un mucchio di permutazioni.