27 votos

¿Alguien puede explicar el Y Combinator?

La Y combinator es un concepto en la programación funcional, tomada del cálculo lambda. Es un punto fijo de combinador. Un punto fijo combinador $G$ es una función de orden superior (funcional, en el lenguaje matemático) que, dada una función de $f$, devuelve un punto fijo de $f$. En el lenguaje matemático,

$$f(G(f)) = G(f)$$

Esto puede considerarse como la definición de la ecuación de un punto fijo combinador.

Tenga en cuenta que $f$ podría ser una función cuyo rango y dominio de sí mismos, son espacios de funciones, de hecho este es el uso más común de un punto fijo combinador: puede definir una función $\alpha$ especificando que es el punto fijo de otra función de $f$, y, a continuación, calcular $\alpha$$G(f)$.

Como matemáticos estamos acostumbrados a las funciones tienen nombres, por ejemplo, $f:x\mapsto x^2$ es la llamada de la función $f$ que se asigna a$x$$x^2$. Pero no hay ninguna razón por qué usted no puede tener la función anónima. Ya que el cálculo lambda trata con estas mucho, hay una notación especial para ellos:

$$\lambda x.x^2$$

es la función que lleva a $x$$x^2$, de modo que, por ejemplo,$(\lambda x.x^2)(2) = 4$. Cuando no hay ambigüedad, podemos escribir la función de la aplicación por concatenación: $(\lambda x.x^2) 2 = 4$, y si definimos $f = \lambda x.x^2$$f\; 2 = 4$.

Bien, ahora llegamos a la carne de la pregunta. La Y combinator es una función de orden superior (funcional) que se define como

$$Y = \lambda f. (\lambda x. f (x\;x)) \; (\lambda x. f (x\;x))$$

Me pueden seguir a través del álgebra y ver que esto es de hecho un punto fijo combinador:

$$\begin{align} Y\; g & = (\lambda f. (\lambda x. f (x\;x)) \; (\lambda x. f (x\;x))) \; g \\ & = (\lambda x. g (x\;x)) \; (\lambda x. g (x\;x)) \\ & = (\lambda y. g (y\;y)) \; (\lambda x. g (x\;x)) \\ & = g \; (\lambda x. g (x\;x)) (\lambda x. g (x\;x)) \\ & = g\; (Y\; g) \end{align}$$

pero no tengo la intuición en cuanto a por qué funciona, o cómo alguien podría haber llegado con él. Más al punto, no veo cómo puede ser prácticamente se utiliza para calcular funciones como fijo-puntos de funcionales.

Alguien tiene un buen 'intuitiva' explicación?

8voto

Pandian Puntos 1

El $Y$ combinator es una función que toma una función $f$ y devuelve algo de lo aplica a sí mismo (específicamente $\lambda x.f(xx)$). Así que si queremos hacer de $Y(f)$ un punto fijo de $f$, $Y(f)$ tiene que ser igual a $f(Y(f))$. Así que queremos algo de $a$ tal que $aa = f(aa)$. Ahora, $a$ tiene acceso a sí misma (que se aplica a sí mismo). Debido a esto, se puede crear directamente un $a$. $$aa=f(aa)$$ $$a=\lambda a.f(aa)$$ $$a=\lambda x.f(xx)$$ $$Y=\lambda f.aa=\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$$ Esencialmente, mediante la aplicación de $a$ a sí mismo, se están dando a $a$ una referencia a sí mismo, permitiendo que se utilice a sí mismo en una manera recursiva. Sin embargo, $a$ es sólo un valor intermedio - no es la función recursiva en sí, como todavía se necesita una referencia a sí mismo para hacer la recursividad. El $Y$ combinador elimina completamente esta necesidad por encontrar el punto fijo - dando una función de su final, de forma recursiva.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by: