Zurra

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Transformar una función de tal manera que sólo tome un solo argumento

En matemáticas y ciencias informáticas, currying es la técnica de traducir la evaluación de una función que toma múltiples argumentos para evaluar una secuencia de funciones, cada una con un solo argumento. Por ejemplo, currying a function $f$ que toma tres argumentos crea una función anidada $g$ , así que el código

{displaystyle {text{let }}x=f(a,b,c)}

da $x$ el mismo valor que el código

{displaystyle {begin{aligned}{text{let }}h=g(a)\{text{let }}i=h(b)\{text{let }}x=i(c),end{aligned}}}

o llamadas en secuencia,

{displaystyle {text{let }}x=g(a)(b)(c).}

En un lenguaje más matemático, una función que toma dos argumentos, uno de $X$ y uno de $Y$ , y produce salidas en $Z,$ por currying se traduce en una función que toma un solo argumento de $X$ y produce como productos funciones desde $Y$ a ${displaystyle Z.}$ Esta es una correspondencia natural de uno a uno entre estos dos tipos de funciones, de modo que los conjuntos con funciones entre ellos forman una categoría cerrada cartesiana. El currying de una función con más de dos argumentos se puede definir por inducción. Currying está relacionado con, pero no igual que, aplicación parcial.

Currying es útil tanto en entornos prácticos como teóricos. En los lenguajes de programación funcional y muchos otros, proporciona una forma de administrar automáticamente cómo se pasan los argumentos a las funciones y excepciones. En informática teórica, proporciona una forma de estudiar funciones con múltiples argumentos en modelos teóricos más simples que proporcionan un solo argumento. El escenario más general para la noción estricta de curry y uncurrying se encuentra en las categorías monoidales cerradas, lo que sustenta una amplia generalización de la correspondencia Curry-Howard de demostraciones y programas a una correspondencia con muchas otras estructuras, incluida la mecánica cuántica, los cobordismos y la teoría de cuerdas.. Fue presentado por Gottlob Frege, desarrollado por Moses Schönfinkel, y desarrollado por Haskell Curry.

Incurrencia es la doble transformación para curar, y se puede ver como una forma de desfuncionalización. Toma una función $f$ cuyo valor de retorno es otra función $g$ , y produce una nueva función $f'$ que toma como parámetros los argumentos para ambos $f$ y $g$ , y regresa, como resultado, la aplicación de $f$ y posteriormente, $g$ A esos argumentos. El proceso puede ser iterado.

Motivación

Currying proporciona una forma de trabajar con funciones que toman múltiples argumentos y usarlos en marcos donde las funciones pueden tomar solo un argumento. Por ejemplo, algunas técnicas analíticas solo se pueden aplicar a funciones con un solo argumento. Las funciones prácticas frecuentemente toman más argumentos que este. Frege demostró que era suficiente proporcionar soluciones para el caso de un solo argumento, ya que era posible transformar una función con múltiples argumentos en una cadena de funciones de un solo argumento. Esta transformación es el proceso que ahora se conoce como curry. Todo "ordinario" Se pueden currar funciones que normalmente se encuentran en el análisis matemático o en la programación de computadoras. Sin embargo, hay categorías en las que el curry no es posible; las categorías más generales que permiten curry son las categorías monoidales cerradas.

Algunos lenguajes de programación casi siempre usan funciones curry para lograr múltiples argumentos; ejemplos notables son ML y Haskell, donde en ambos casos todas las funciones tienen exactamente un argumento. Esta propiedad se hereda del cálculo lambda, donde las funciones de múltiples argumentos generalmente se representan en forma de curry.

Currying está relacionado, pero no es lo mismo que la aplicación parcial. En la práctica, la técnica de programación de los cierres se puede utilizar para realizar una aplicación parcial y una especie de curry, ocultando argumentos en un entorno que viaja con la función curry.

Ilustración

Supongamos que tenemos una función ${displaystyle f:mathbb {R} times mathbb {R} to mathbb {R} }$ que toma dos números reales ( $mathbb {R}$ ) argumentos y salidas números reales, y se define por ${displaystyle f(x,y)=x+y^{2}}$ . Currying traduce esto en una función $h$ que toma un solo argumento real y las funciones de salidas de $mathbb {R}$ a $mathbb {R}$ . En símbolos, ${displaystyle h:mathbb {R} to mathbb {R} ^{mathbb {R} }}$ , donde ${mathbb {R}}^{{mathbb {R}}}$ denota el conjunto de todas las funciones que toman un solo argumento real y producen productos reales. Por cada número real $x$ , definir la función ${displaystyle h_{x}:mathbb {R} to mathbb {R} }$ por ${displaystyle h_{x}(y)=x+y^{2}}$ , y luego definir la función ${displaystyle h:mathbb {R} to mathbb {R} ^{mathbb {R} }}$ por ${displaystyle h(x)=h_{x}}$ . Por ejemplo, ${displaystyle h(2)}$ es la función que envía su argumento real $y$ al producto ${displaystyle 2+y^{2}}$ , o ${displaystyle h(2)(y)=h_{2}(y)=2+y^{2}}$ . Lo vemos en general

{displaystyle h(x)(y)=x+y^{2}=f(x,y)}

para que la función original $f$ y su currying $h$ transmitir exactamente la misma información. En esta situación, también escribimos

{displaystyle {text{curry}}(f)=h.}

Esto también funciona para funciones con más de dos argumentos. Si $f$ eran una función de tres argumentos $f(x,y,z)$ , su currying $h$ Tendría la propiedad

{displaystyle f(x,y,z)=h(x)(y)(z).}

Historia

El "Curry" en "Currying" es una referencia al lógico Haskell Curry, quien usó el concepto ampliamente, pero Moses Schönfinkel tuvo la idea 6 años antes que Curry. El nombre alternativo "Schönfinkelisation" ha sido propuesto. En el contexto matemático, el principio se remonta al trabajo de Frege en 1893.

El creador de la palabra "currying" no está claro. David Turner dice que la palabra fue acuñada por Christopher Strachey en sus notas de conferencias de 1967 Conceptos fundamentales en lenguajes de programación, pero aunque se menciona el concepto, la palabra "currying" no aparece en las notas. John C. Reynolds definió "currying" en un artículo de 1972, pero no afirmó haber acuñado el término.

Definición

La curación se entiende más fácilmente comenzando con una definición informal, que puede ser moldeada para adaptarse a muchos dominios diferentes. En primer lugar, hay que establecer una cierta notación. La notación ${displaystyle Xto Y}$ denota todas las funciones de $X$ a $Y$ . Si $f$ es tal función, escribimos ${displaystyle fcolon Xto Y}$ . Vamos $Xtimes Y$ denota los pares ordenados de los elementos de $X$ y $Y$ respectivamente, es decir, el producto cartesiano de $X$ y $Y$ . Aquí, $X$ y $Y$ pueden ser conjuntos, o pueden ser tipos, o pueden ser otros tipos de objetos, como se explora a continuación.

Dada una función

f colon (X times Y) to Z

currying construye una nueva función

{displaystyle hcolon Xto (Yto Z)}

Eso es, $h$ toma un argumento $X$ y devuelve una función que mapea $Y$ a $Z$ . Se define por

{displaystyle h(x)(y)=f(x,y)}

para $x$ desde $X$ y $y$ desde $Y$ . Entonces también escribimos

{displaystyle {text{curry}}(f)=h.}

Incurrencia es la transformación inversa, y se entiende más fácilmente en términos de su unión derecha, el función ${displaystyle operatorname {apply}.}$

Teoría de conjuntos

En la teoría del conjunto, la notación $Y^X$ se utiliza para denotar el conjunto de funciones del conjunto $X$ al conjunto $Y$ . Currying es la bijeción natural entre el conjunto $A^{Btimes C}$ of functions from $Btimes C$ a $A$ , y el conjunto ${displaystyle (A^{C})^{B}}$ of functions from $B$ al conjunto de funciones desde $C$ a $A$ . En símbolos:

{displaystyle A^{Btimes C}cong (A^{C})^{B}}

De hecho, es esta bijeción natural que justifica la notación exponencial para el conjunto de funciones. Como es el caso en todas las instancias de currying, la fórmula anterior describe un par de functores adjuntos: para cada conjunto fijo $C$ , el functor ${displaystyle Bmapsto Btimes C}$ se deja junto al functor ${displaystyle Amapsto A^{C}}$ .

En la categoría de conjuntos, el objeto $Y^X$ se llama el objeto exponencial.

Espacios de funciones

En la teoría de los espacios de función, como en el análisis funcional o en la teoría de la homotopia, uno está comúnmente interesado en funciones continuas entre los espacios topológicos. Uno escribe ${text{Hom}}(X,Y)$ (el functor Hom) para el conjunto de Todos funciones de $X$ a $Y$ , y utiliza la notación $Y^X$ para denotar el subconjunto de funciones continuas. Aquí, ${displaystyle {text{curry}}}$ es la bijeción

{displaystyle {text{curry}}:{text{Hom}}(Xtimes Y,Z)to {text{Hom}}(X,{text{Hom}}(Y,Z)),}

mientras que incurrir es el mapa inverso. Si el conjunto $Y^X$ de funciones continuas $X$ a $Y$ se da la topología compacta-abierto, y si el espacio $Y$ es localmente compacto Hausdorff, entonces

{displaystyle {text{curry}}:Z^{Xtimes Y}to (Z^{Y})^{X}}

es un homeomorfismo. Este también es el caso cuando $X$ , $Y$ y $Y^X$ se generan compactamente, aunque hay más casos.

Un corolario útil es que una función es continua si y solo si su forma cursada es continua. Otro resultado importante es que el mapa de aplicación, generalmente llamado "evaluación" en este contexto, es continua (tenga en cuenta que eval es un concepto estrictamente diferente en informática). Es decir,

${displaystyle {begin{aligned}&&{text{eval}}:Y^{X}times Xto Y\&&(f,x)mapsto f(x)end{aligned}}}$

es continuo cuando $Y^X$ es compacto y abierto $Y$ localmente compacto Hausdorff. Estos dos resultados son centrales para establecer la continuidad de la homotopy, es decir, cuando $X$ es el intervalo de unidad $I$ Así que ${displaystyle Z^{Itimes Y}cong (Z^{Y})^{I}}$ puede el pensamiento como una homotopia de dos funciones de $Y$ a $Z$ , o, equivalentemente, un único camino (continua) $Z^{Y}$ .

Topología algebraica

En topología algebraica, curry sirve como un ejemplo de la dualidad Eckmann-Hilton y, como tal, juega un papel importante en una variedad de entornos diferentes. Por ejemplo, el espacio de bucle es adjunto a suspensiones reducidas; esto se escribe comúnmente como

{displaystyle [Sigma X,Z]approxeq [X,Omega Z]}

Donde $[A,B]$ es el conjunto de clases de homotopy de mapas $Arightarrow B$ , y $Sigma A$ es la suspensión de A, y ${displaystyle Omega A}$ es el espacio del bucle A. En esencia, la suspensión $Sigma X$ se puede ver como el producto cartesiano de $X$ con el intervalo de unidad, modulo una relación de equivalencia para convertir el intervalo en un bucle. La forma curried entonces mapas el espacio $X$ al espacio de funciones desde los bucles en $Z$ , es decir, de $X$ en ${displaystyle Omega Z}$ . Entonces... ${displaystyle {text{curry}}}$ es el funerario adjunto que mapea las suspensiones a los espacios de bucle, y sin correr es el dual.

La dualidad entre el cono de mapeo y la fibra de mapeo (cofibración y fibración) puede entenderse como una forma de curry, que a su vez conduce a la dualidad de las secuencias Puppe exactas y coexactas largas.

En álgebra homológica, la relación entre curry y uncurrying se conoce como adjunción tensor-hom. Aquí surge un giro interesante: el funtor Hom y el funtor producto tensorial podrían no elevarse a una secuencia exacta; esto lleva a la definición del funtor Ext y el funtor Tor.

Teoría del dominio

En la teoría del orden, es decir, la teoría de las vestiduras de conjuntos parcialmente ordenados, ${displaystyle {text{curry}}}$ es una función continua cuando la celosía se da la topología de Scott. Las funciones continuas de Scott fueron investigadas por primera vez en el intento de proporcionar una semántica para el cálculo de lambda (como la teoría de conjunto ordinario es inadecuada para hacer esto). Más generalmente, las funciones contínuas de Scott ahora se estudian en la teoría del dominio, que abarca el estudio de semántica denotacional de algoritmos informáticos. Tenga en cuenta que la topología de Scott es bastante diferente de muchas topologías comunes que se pueden encontrar en la categoría de espacios topológicos; la topología de Scott es típicamente más fina, y no es sobria.

La noción de continuidad hace su aparición en la teoría de tipos de homotopía, donde, en términos generales, dos programas de computadora pueden considerarse homotópicos, es decir, calculan los mismos resultados, si pueden ser "continuamente" refactorizado de uno a otro.

Cálculos lambda

En la informática teórica, el currying proporciona una manera de estudiar funciones con múltiples argumentos en modelos teóricos muy simples, como el cálculo de la lambda, en el que las funciones sólo toman un solo argumento. Considerar una función $f(x,y)$ tomando dos argumentos, y teniendo el tipo ${displaystyle (Xtimes Y)to Z}$ , que debe entenderse significa que x debe tener el tipo $X$ , Sí. debe tener el tipo $Y$ , y la función misma devuelve el tipo $Z$ . La forma currada de f se define como

{displaystyle {text{curry}}(f)=lambda x.(lambda y.(f(x,y)))}

Donde $lambda$ es el abstractor del cálculo de lambda. Dado que el curry toma, como entrada, funciones con el tipo ${displaystyle (Xtimes Y)to Z}$ , se concluye que el tipo de curry en sí es

{displaystyle {text{curry}}:((Xtimes Y)to Z)to (Xto (Yto Z))}

El operador → se considera a menudo asociativo derecho, por lo que el tipo de función curried $X to (Y to Z)$ a menudo escrito como $X to Y to Z$ . Por el contrario, la aplicación de la función se considera asociada a la izquierda, de modo que $f(x,y)$ equivale a

{displaystyle (({text{curry}}(f);x);y)={text{curry}}(f);x;y}

Es decir, los paréntesis no son necesarios para desambiguar el orden de la aplicación.

Las funciones seleccionadas se pueden usar en cualquier lenguaje de programación que admita cierres; sin embargo, las funciones no cursadas generalmente se prefieren por razones de eficiencia, ya que la sobrecarga de la aplicación parcial y la creación de cierres se pueden evitar para la mayoría de las llamadas a funciones.

Teoría de tipos

En la teoría del tipo, la idea general de un sistema de tipo en la ciencia informática se formaliza en un álgebra específica de tipos. Por ejemplo, cuando escribe ${displaystyle fcolon Xto Y}$ , la intención es que $X$ y $Y$ son tipos, mientras que la flecha $to$ es un constructor tipo, específicamente, el tipo de función o tipo de flecha. Del mismo modo, el producto cartesiano $Xtimes Y$ de tipos es construido por el constructor tipo de producto $times$ .

El enfoque teórico de tipos se expresa en lenguajes de programación como ML y los lenguajes derivados e inspirados por él: CaML, Haskell y F#.

El enfoque teórico de tipos proporciona un complemento natural al lenguaje de la teoría de categorías, como se analiza a continuación. Esto se debe a que las categorías, y específicamente las categorías monoidales, tienen un lenguaje interno, siendo el cálculo lambda de tipo simple el ejemplo más destacado de dicho lenguaje. Es importante en este contexto, porque se puede construir a partir de un único constructor de tipo, el tipo de flecha. Currying entonces dota al idioma con un tipo de producto natural. La correspondencia entre objetos en categorías y tipos permite que los lenguajes de programación se reinterpreten como lógicos (a través de la correspondencia de Curry-Howard) y como otros tipos de sistemas matemáticos, como se explora más adelante.

Lógica

Bajo la correspondencia Curry-Howard, la existencia de curry e incurrir es equivalente a la teorema lógica ${displaystyle (Aland B)to CLeftrightarrow Ato (Bto C)}$ , como tuples (tipo de producto) corresponde a la conjunción en lógica, y el tipo de función corresponde a la implicación.

El objeto exponencial ${displaystyle Q^{P}}$ en la categoría de álgebras Heyting se escribe normalmente como implicación material $Pto Q$ . Distributive Heyting álgebras son álgebras booleanas, y el objeto exponencial tiene la forma explícita ${displaystyle neg Plor Q}$ , dejando así claro que el objeto exponencial realmente es implicación material.

Teoría de categorías

Las nociones anteriores de currying e incurrir en encontrar su declaración más general y abstracta en la teoría de la categoría. Currying es una propiedad universal de un objeto exponencial, y da lugar a una adjunción en categorías cerradas cartesianas. Es decir, hay un isomorfismo natural entre los morfismos de un producto binario $f colon (X times Y) to Z$ y los morfismos a un objeto exponencial $g colon X to Z^Y$ .

Esto se generaliza en un resultado más amplio en categorías monoidales cerradas: Currying es la afirmación de que el producto tensor y el Hom interno son functores adjuntos; es decir, para cada objeto $B$ hay un isomorfismo natural:

{displaystyle mathrm {Hom} (Aotimes B,C)cong mathrm {Hom} (A,BRightarrow C).}

Aquí, Hom denota el (externo) Hom-functor de todos los morfismos de la categoría, mientras ${displaystyle BRightarrow C}$ denota el functor interno hom en la categoría monoidal cerrada. Para la categoría de conjuntos, los dos son los mismos. Cuando el producto es el producto cartesiano, entonces el homo interno ${displaystyle BRightarrow C}$ se convierte en el objeto exponencial ${displaystyle C^{B}}$ .

El curry puede descomponerse de dos maneras. Una es si una categoría no está cerrada y, por lo tanto, carece de un funtor hom interno (posiblemente porque hay más de una opción para dicho funtor). Otra forma es si no es monoide y, por lo tanto, carece de producto (es decir, carece de una forma de escribir pares de objetos). Las categorías que tienen productos y homs internos son exactamente las categorías monoidales cerradas.

La configuración de categorías cerradas cartesianas es suficiente para la discusión de la lógica clásica; la configuración más general de categorías monoidales cerradas es adecuada para el cálculo cuántico.

La diferencia entre estos dos es que el producto de las categorías cartesianas (como la categoría de conjuntos, órdenes parciales completas o álgebras de Heyting) es simplemente el producto cartesiano; se interpreta como un par ordenado de elementos (o una lista). El cálculo lambda simplemente tipeado es el lenguaje interno de las categorías cerradas cartesianas; y es por esta razón que los pares y las listas son los tipos principales en la teoría de tipos de LISP, Scheme y muchos lenguajes de programación funcional.

Por el contrario, el producto de las categorías monoidales (como el espacio de Hilbert y los espacios vectoriales del análisis funcional) es el producto tensorial. El lenguaje interno de tales categorías es la lógica lineal, una forma de lógica cuántica; el sistema de tipo correspondiente es el sistema de tipo lineal. Tales categorías son adecuadas para describir estados cuánticos entrelazados y, de manera más general, permiten una amplia generalización de la correspondencia de Curry-Howard con la mecánica cuántica, los cobordismos en la topología algebraica y la teoría de cuerdas. El sistema de tipo lineal y la lógica lineal son útiles para describir las primitivas de sincronización, como los bloqueos de exclusión mutua y el funcionamiento de las máquinas expendedoras.

Contraste con aplicación de función parcial

La aplicación de funciones parciales y de curry a menudo se combinan. Una de las diferencias significativas entre los dos es que una llamada a una función aplicada parcialmente devuelve el resultado de inmediato, no otra función en la cadena de curry; esta distinción se puede ilustrar claramente para funciones cuya aridad es mayor que dos.

Dado una función de tipo $f colon (X times Y times Z) to N$ , la curación produce $text{curry}(f) colon X to (Y to (Z to N))$ . Es decir, mientras que una evaluación de la primera función podría estar representada como $f(1, 2, 3)$ , la evaluación de la función curada estaría representada como $f_text{curried}(1)(2)(3)$ , aplicando cada argumento a su vez a una función de un solo compromiso devuelta por la invocación anterior. Note que después de llamar $f_text{curried}(1)$ , nos quedamos con una función que toma un solo argumento y devuelve otra función, no una función que toma dos argumentos.

En cambio, aplicación de función parcial se refiere al proceso de fijar una serie de argumentos a una función, produciendo otra función de menor aridad. Dada la definición $f$ arriba, podemos fijar (o 'bind') el primer argumento, produciendo una función de tipo $text{partial}(f) colon (Y times Z) to N$ . La evaluación de esta función podría estar representada como $f_text{partial}(2, 3)$ . Tenga en cuenta que el resultado de la aplicación de función parcial en este caso es una función que toma dos argumentos.

Intuitivamente, la aplicación de función parcial dice "si corrige el primer argumento de la función, obtiene una función de los argumentos restantes". Por ejemplo, si la función div representa la operación de división x/y, entonces div con el parámetro x fijada en 1 (es decir, div 1) es otra función: la misma que la función inv que devuelve el inverso multiplicativo de su argumento, definido por venta(y) = 1/y.

La motivación práctica para la aplicación parcial es que muy a menudo las funciones obtenidas al proporcionar algunos pero no todos los argumentos de una función son útiles; por ejemplo, muchos idiomas tienen una función u operador similar a plus_one. La aplicación parcial facilita la definición de estas funciones, por ejemplo, mediante la creación de una función que represente el operador de suma con 1 límite como primer argumento.

La aplicación parcial puede considerarse como evaluación de una función curada en un punto fijo, por ejemplo, dada $f colon (X times Y times Z) to N$ y $ain X$ entonces ${displaystyle {text{curry}}({text{partial}}(f)_{a})(y)(z)={text{curry}}(f)(a)(y)(z)}$ o simplemente ${displaystyle {text{partial}}(f)_{a}={text{curry}}_{1}(f)(a)}$ Donde ${displaystyle {text{curry}}_{1}}$ curries f's first parameter.

Así, la aplicación parcial se reduce a una función curada en un punto fijo. Además, una función curada en un punto fijo es (trivialmente), una aplicación parcial. Para más pruebas, note que, dada cualquier función $f(x,y)$ , una función ${displaystyle g(y,x)}$ puede definirse como tal ${displaystyle g(y,x)=f(x,y)}$ . Así, cualquier aplicación parcial puede reducirse a una sola operación de curry. Como tal, el curry es más adecuado como una operación que, en muchos casos teóricos, se aplica recursivamente, pero que es teóricamente indistinguible (cuando se considera una operación) de una aplicación parcial.

Entonces, una aplicación parcial se puede definir como el resultado objetivo de una sola aplicación del operador curry en algún orden de las entradas de alguna función.

Contenido relacionado

Más resultados...