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.