function lambda combinators y-combinator

function - Buena explicación de "Combinators"(Para no matemáticos)



lambda y-combinator (8)

¿Alguien tiene una buena explicación de "combinators" (Y-combinators etc. y NO de la compañía )?

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 estas cosas )

A menos que esté profundamente metido en la teoría, puede considerar al combinador en Y como un buen truco con funciones, como las mónadas.

Las mónadas le permiten encadenar acciones, el combinador Y le permite definir funciones recursivas.

Python tiene soporte integrado para funciones auto recursivas, por lo que puedes definirlas sin Y:

> def fun(): > print "bla" > fun() > fun() bla bla bla ...

fun es accesible dentro de la fun misma, así que podemos llamarla fácilmente.

Pero, ¿y si Python fuera diferente y la fun no fuera accesible dentro de la fun ?

> def fun(): > print "bla" > # what to do here? (cannot call fun!)

La solución es pasar la fun como un argumento a la fun :

> def fun(arg): # fun receives itself as argument > print "bla" > arg(arg) # to recur, fun calls itself, and passes itself along

Y Y lo hace posible:

> def Y(f): > f(f) > Y(fun) bla bla bla ...

Todo lo hace llamar a una función consigo misma como argumento.

(No sé si esta definición de Y es 100% correcta, pero creo que es la idea general).

Cita Wikipedia:

Un combinador es una función de orden superior que utiliza solo la aplicación de funciones y los combinados definidos anteriormente para definir un resultado a partir de sus argumentos.

Ahora, que 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 esas funciones y para qué se utilizan? Aquí hay unos ejemplos:

(fog)(x) = f(g(x))

Aquí o es un combinador que toma 2 funciones, f y g , y devuelve una función como resultado, la composición de f con g , es decir, fog .

Los combadores se pueden usar para ocultar la lógica. Digamos 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 para los de Number excepto si Undefined es una entrada, la salida también debe estar Undefined y cuando se divide por el número 0 la salida también está Undefined .

Uno podría escribir el código tedioso de la siguiente manera:

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 todos tienen la misma lógica con respecto a los valores de entrada no definidos. 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 Mónada Maybe que los programadores usan en lenguajes funcionales como Haskell, pero no iré allí.

Este es un buen article . Los ejemplos de código están en esquema, pero no deberían ser difíciles de seguir.

Estoy bastante corto en teoría, pero puedo darte un ejemplo que despierta mi imaginación, lo que puede ser útil para ti. El combinador más simple e interesante es probablemente "prueba".

Espero que conozcas a 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''

la prueba evalúa el segundo argumento si el primer argumento es verdadero, 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 Types and Programming Languages ​​por Benjamin C. Pierce)

Reginald Braithwaite (alias Raganwald) ha estado escribiendo una gran serie de combinadores en Ruby en su nuevo blog, homoiconic .

Si bien, por lo que yo sé, no mira al Y-combinator, sí observa otros combinadores, por ejemplo:

y algunas publicaciones sobre cómo puedes use .

Un combinador es una función sin 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.

Usando F # esta es mi comprensión de los combinadores:

let sum a b = a + b;; //sum function (lambda)

En el caso anterior, sum es un combinador porque tanto a como b están vinculados 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 usa sum , que no es una variable vinculada (es decir, no proviene de ninguno de los parámetros).

Podemos hacer que sum3 sea 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 forma, sumFunc está vinculado y, por lo tanto, toda la función es un combinador.

Entonces, esta es mi comprensión de los combinadores. Su significado, por otro lado, todavía se me escapa. Como otros señalaron, los combinadores de puntos fijos le permiten a uno expresar una función recursiva sin recursión explicit . Es decir, en lugar de llamarse a sí mismo, la función recusiva llama a lambda que se pasa como uno de los argumentos.

Esta es una de las derivaciones combinadas más comprensibles que encontré:

http://mvanier.livejournal.com/2897.html