operator - modulo 2 c#

Usando el Combinador Y en C#

Question

Estoy intentando descubrir cómo escribir funciones recursivas (por ejemplo, factorial, aunque mis funciones son mucho más complicadas) en una línea. Para hacer esto, pensé en usar el combinador Y de Lambda Calculus .

Aquí está la primera definición:

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

Aquí está la definición reducida:

Y g = g(Y g)

Intenté escribirlos en C # así:

// 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 es una función Func<dynamic, dynamic> . Primero traté de escribirla con el using , pero eso no funcionó , por lo que ahora se define con un delegate dynamic Lambda(dynamic arg); )

Mi lambda factorial se ve así (adaptado de aquí ):

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

Y lo llamo así:

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

Sin embargo, en ambos casos (formas original y reducida del combinador Y), termino con una excepción de desbordamiento de pila. Por lo que puedo suponer al usar la forma reducida, parece que acaba llamando a Y(factorial(Y(factorial(Y(factorial(... y nunca termina ingresando al factorial lambda.

Como no tengo mucha experiencia en depurar expresiones C # lambda y ciertamente no entiendo mucho del cálculo lambda, realmente no sé qué está pasando ni cómo solucionarlo.

En caso de que importe, esta pregunta fue inspirada al tratar de escribir una respuesta de una línea a esta pregunta en C #.

Mi solución es la siguiente:

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

Mi objetivo es escribir getPermutations como una lambda recursiva de una sola línea para poder insertarla en SelectMany en AllSubstrings y hacer una sola línea de AllSubstrings .

Mis preguntas son las siguientes:

1. ¿Es posible el combinador Y en C #? Si es así, ¿qué estoy haciendo mal en la implementación?
2. Si el combinador Y es posible en C #, ¿cómo podría hacer que mi solución al problema de subcadenas (la función AllSubstrings ) sea AllSubstrings ?
3. Ya sea que el combinador Y no sea ​​posible en C #, ¿hay algún otro método de programación que permita alinear AllSubstrings ?

Answer 1

Aquí está la implementación del Y-combinator que uso en 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));
}

Puedo usarlo así:

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

Realmente me asusta, así que le dejaré las siguientes dos partes de su pregunta, dado esto como punto de partida.

He tenido un crack en la función.

Aquí está:

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

Por supuesto, lo ejecuta así:

allsubstrings("abcd");

De lo cual obtuve este resultado:

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 

Parece que su código que no es Y-Combinator en su pregunta se perdió un montón de permutaciones.