¿Alguien tiene una buena explicación de "combinators" (Y-combinators etc. y NOTthe company)?Buena explicación de "Combinators" (para no matemáticos)
Estoy buscando uno para el programador práctico que entiende recursividad y funciones de orden superior, pero no tiene una teoría sólida o antecedentes matemáticos.
(Nota: que estoy hablando de these things)
Ésta es una buena article. Los ejemplos de código están en esquema, pero no deberían ser difíciles de seguir.
A menos que esté profundamente en la teoría, puede considerar el combinador Y como un buen truco con funciones, como las mónadas.
Las mónadas le permiten encadenar acciones, el combinador Y le permite definir las funciones recursivas.
Python ha incorporado soporte para las funciones de auto-recursivo, por lo que puede definirlos sin Y:
> def fun():
> print "bla"
> fun()
> fun()
bla
bla
bla
...
fun es accesible dentro fun en sí, por lo que podemos llamar fácilmente.
Pero lo que si Python eran diferentes, y fun no eran accesibles dentro fun?
> def fun():
> print "bla"
> # what to do here? (cannot call fun!)
La solución es pasar fun a sí mismo como un argumento para fun:
> def fun(arg): # fun receives itself as argument
> print "bla"
> arg(arg) # to recur, fun calls itself, and passes itself along
e Y lo hace posible:
> def Y(f):
> f(f)
> Y(fun)
bla
bla
bla
...
lo único que hace es llamar a una función consigo misma como argumento
(no sé si esta definición de Y es 100% correcto, pero yo creo que es la idea general.)
Técnicamente eso es el combinador Omega - el combinador Y real permite que la función de tomar argumentos, también :) –
finalmente entendió la Y-Combinator después de buscar SO durante media hora. Las mejores respuestas en SO son las que son cortas con solo el lenguaje cotidiano. –
Reginald Braithwaite (también conocido como raganwald) ha escrito una gran serie de combinadores en Ruby sobre en su nuevo blog, homoiconic.
Mientras que no (que yo sepa) mira el propio Y-Combinator, que se ve en otros combinadores, por ejemplo:
Sí, he notado esa serie yo mismo. Necesito estudiar los ejemplos un poco más porque no soy fluido en Ruby, pero es genial. – interstar
Estoy bastante corto en teoría, pero puedo darle un ejemplo que despierta mi imaginación, lo que puede ser útil para usted. El combinador más simple e interesante es probablemente "prueba".
espero que sepas Python
tru = lambda x,y: x
fls = lambda x,y: y
test = lambda l,m,n: l(m,n)
Uso:
>>> test(tru,"goto loop","break")
'goto loop'
>>> test(fls,"goto loop","break")
'break'
prueba evalúa al segundo argumento si el primer argumento es cierto, de lo contrario el tercero.
>>> x = tru
>>> test(x,"goto loop","break")
'goto loop'
Se pueden construir sistemas completos a partir de unos pocos combinadores básicos.
(Este ejemplo es más o menos copiado de los tipos y lenguajes de programación por Benjamin C. Pierce)
Cita Wikipedia:
un combinador es una función de orden superior que utiliza sólo la aplicación de funciones y combinadores definidos anteriormente para definir un resultado a partir de sus argumentos.
¿Qué significa esto? Significa que un combinador es una función (la salida está determinada únicamente por su entrada) cuya entrada incluye una función como argumento.
¿Cómo son estas funciones y para qué se utilizan? He aquí algunos ejemplos:
(f o g)(x) = f(g(x))
Aquí o es un combinador que lleva en 2 funciones, f y g, y devuelve una función como su resultado, la composición de f con g, a saber f o g.
Los combinadores se pueden utilizar para ocultar la lógica. Supongamos que tenemos un tipo de datos NumberUndefined, donde NumberUndefined puede tomar un valor numérico Num x o un valor Undefined, donde x a es un Number. Ahora queremos construir suma, resta, multiplicación y división para este nuevo tipo numérico. La semántica es la misma que la de Number, excepto si Undefined es una entrada, la salida también debe ser Undefined y al dividir por el número 0, la salida también es Undefined.
Se podría escribir el código tedioso como a continuación:
Undefined +' num = Undefined
num +' Undefined = Undefined
(Num x) +' (Num y) = Num (x + y)
Undefined -' num = Undefined
num -' Undefined = Undefined
(Num x) -' (Num y) = Num (x - y)
Undefined *' num = Undefined
num *' Undefined = Undefined
(Num x) *' (Num y) = Num (x * y)
Undefined /' num = Undefined
num /' Undefined = Undefined
(Num x) /' (Num y) = if y == 0 then Undefined else Num (x/y)
Observe cómo la tienen todos la misma lógica en relación con Undefined valores de entrada. Solo la división hace un poco más. La solución es extraer la lógica haciéndola un combinador.
comb (~) Undefined num = Undefined
comb (~) num Undefined = Undefined
comb (~) (Num x) (Num y) = Num (x ~ y)
x +' y = comb (+) x y
x -' y = comb (-) x y
x *' y = comb (*) x y
x /' y = if y == Num 0 then Undefined else comb (/) x y
Esto se puede generalizar en la llamada Maybe mónada que los programadores hacen uso de en los lenguajes funcionales como Haskell, pero no voy a ir allí.
Poco, Y Combinator es una función de orden superior que se utiliza para implementar recursividad en las expresiones lambda (funciones anónimas). Compruebe el artículo How to Succeed at Recursion Without Really Recursing por Mike Vanier - es uno de los mejor explicación práctica de esta materia que he visto.
Además, explorar los archivos de SO:
un combinador es función con variables libres. Eso significa, entre otras cosas, que el combinador no tiene dependencias de cosas fuera de la función, solo en los parámetros de la función.
usuario de F # Esta es mi comprensión de combinadores:
let sum a b = a + b;; //sum function (lambda)
En el caso suma anterior es un combinador porque ambos a y b están unidos a los parámetros de la función.
let sum3 a b c = sum((sum a b) c);;
La función anterior no es un combinador, ya que utiliza sum, que no es una variable unida (es decir, que no procede de cualquiera de los parámetros).
podemos hacer sum3 un combinador simplemente pasando la función suma como uno de los parámetros:
let sum3 a b c sumFunc = sumFunc((sumFunc a b) c);;
De esta manera sumFunc es obligado y por lo tanto la función entera es un combinador.
Por lo tanto, este es mi comprensión de combinadores. Su significado, por otro lado, todavía se me escapa. Como otros señalaron, combinadores de punto fijo permiten que uno expresa una función recursiva sin explicit recursividad. Es decir. en lugar de llamarse a sí mismo la función recusiva llama a lambda que se pasa como uno de los argumentos.
He aquí una de las derivaciones de combinadores más comprensibles que he encontrado:
¿Qué pasa con '+' en la definición de 'suma'? No está atado. –
esto parece una buena: http://www.catonmat.net/blog/derivation-of-ycombinator/
que estaba esperando algo un poco más introductoria de los Dreamsongs uno. Tal vez con un poco más de motivación sobre cuál es el problema que abordan etc. – interstar