Escovando

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Transformando uma função de tal forma que só leva um único argumento

Em matemática e ciência da computação, currying é a técnica de traduzir a avaliação de uma função que leva vários argumentos para avaliar uma sequência de funções, cada uma com um único argumento. Por exemplo, currying a function $f$ que leva três argumentos cria uma função unary aninhada $g$ , para que o código

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

dá $x$ o mesmo valor que o código

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

ou chamado em sequência,

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

Em uma linguagem mais matemática, uma função que leva dois argumentos, um de $X$ e um de $Y$ , e produz saídas em $Z,$ por currying é traduzido em uma função que leva um único argumento de $X$ e produz como saídas funções a partir de $Y$ para ${displaystyle Z.}$ Esta é uma correspondência natural entre estes dois tipos de funções, de modo que os conjuntos juntamente com funções entre eles formam uma categoria fechada cartesiana. O currying de uma função com mais de dois argumentos pode então ser definido por indução. Currying está relacionado com, mas não o mesmo que, aplicação parcial.

O curry é útil tanto em ambientes práticos quanto teóricos. Em linguagens de programação funcionais e em muitas outras, ele fornece uma maneira de gerenciar automaticamente como os argumentos são passados para funções e exceções. Na ciência da computação teórica, fornece uma maneira de estudar funções com vários argumentos em modelos teóricos mais simples que fornecem apenas um argumento. O cenário mais geral para a noção estrita de currying e uncurrying está nas categorias monoidais fechadas, que sustentam uma vasta generalização da correspondência Curry-Howard de provas e programas para uma correspondência com muitas outras estruturas, incluindo mecânica quântica, cobordismos e teoria das cordas. Foi introduzido por Gottlob Frege, desenvolvido por Moses Schönfinkel, e desenvolvido por Haskell Curry.

Sem cura é a transformação dupla para currying, e pode ser visto como uma forma de defuncionalização. É preciso uma função $f$ cujo valor de retorno é outra função $g$ , e produz uma nova função $f'$ que leva como parâmetros os argumentos para ambos $f$ e $g$ , e retorna, como resultado, a aplicação de $f$ e posteriormente, $g$ , para esses argumentos. O processo pode ser iterado.

Motivação

Currying fornece uma maneira de trabalhar com funções que recebem vários argumentos e usá-los em estruturas nas quais as funções podem receber apenas um argumento. Por exemplo, algumas técnicas analíticas só podem ser aplicadas a funções com um único argumento. Funções práticas freqüentemente levam mais argumentos do que isso. Frege mostrou que era suficiente fornecer soluções para o caso de argumento único, pois era possível transformar uma função com múltiplos argumentos em uma cadeia de funções de argumento único. Essa transformação é o processo agora conhecido como currying. Todos os "comuns" funções que normalmente podem ser encontradas na análise matemática ou na programação de computadores podem ser executadas. No entanto, existem categorias em que o currying não é possível; as categorias mais gerais que permitem currying são as categorias monoidais fechadas.

Algumas linguagens de programação quase sempre usam funções curried para obter vários argumentos; exemplos notáveis são ML e Haskell, onde em ambos os casos todas as funções têm exatamente um argumento. Esta propriedade é herdada do cálculo lambda, onde as funções multi-argumento são geralmente representadas na forma curried.

Currying está relacionado, mas não é o mesmo que aplicação parcial. Na prática, a técnica de programação de fechamentos pode ser utilizada para realizar aplicações parciais e uma espécie de currying, ocultando argumentos em um ambiente que trafega com a função curried.

Ilustração

Suponha que temos uma função ${displaystyle f:mathbb {R} times mathbb {R} to mathbb {R} }$ que leva dois números reais ( $mathbb {R}$ ) argumentos e saídas números reais, e é definido por ${displaystyle f(x,y)=x+y^{2}}$ . Currying traduz isso em uma função $h$ que leva um único argumento real e saídas funções de $mathbb {R}$ para $mathbb {R}$ . Em símbolos, ${displaystyle h:mathbb {R} to mathbb {R} ^{mathbb {R} }}$ , onde ${mathbb {R}}^{{mathbb {R}}}$ denota o conjunto de todas as funções que levam um único argumento real e produzem saídas reais. Para cada número real $x$ , definir a função ${displaystyle h_{x}:mathbb {R} to mathbb {R} }$ por ${displaystyle h_{x}(y)=x+y^{2}}$ , e então definir a função ${displaystyle h:mathbb {R} to mathbb {R} ^{mathbb {R} }}$ por ${displaystyle h(x)=h_{x}}$ . Por exemplo, ${displaystyle h(2)}$ é a função que envia seu argumento real $y$ para a saída ${displaystyle 2+y^{2}}$ ou ${displaystyle h(2)(y)=h_{2}(y)=2+y^{2}}$ . Vemos que em geral

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

para que a função original $f$ e seu currying $h$ transmitir exatamente a mesma informação. Nesta situação, também escrevemos

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

Isso também funciona para funções com mais de dois argumentos. Se $f$ foram uma função de três argumentos $f(x,y,z)$ , seu currying $h$ teria a propriedade

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

História

O "Curry" em "Curry" é uma referência ao lógico Haskell Curry, que usou o conceito extensivamente, mas Moses Schönfinkel teve a ideia seis anos antes de Curry. O nome alternativo "Schönfinkelisation" Foi proposto. No contexto matemático, o princípio pode ser rastreado até o trabalho em 1893 por Frege.

O criador da palavra "currying" não está claro. David Turner diz que a palavra foi cunhada por Christopher Strachey em suas notas de aula de 1967, Conceitos Fundamentais em Linguagens de Programação, mas embora o conceito seja mencionado, a palavra "currying" não aparece nas notas. John C. Reynolds definiu "curry" em um artigo de 1972, mas não afirmou ter cunhado o termo.

Definição

Currying é mais facilmente entendido, começando com uma definição informal, que pode então ser moldado para caber muitos domínios diferentes. Primeiro, há alguma notação a ser estabelecida. A notação ${displaystyle Xto Y}$ denota todas as funções de $X$ para $Y$ . Se $f$ é tal função, escrevemos ${displaystyle fcolon Xto Y}$ . Vamos. $Xtimes Y$ denote os pares ordenados dos elementos de $X$ e $Y$ ou seja, o produto cartesiano de $X$ e $Y$ . Toma. $X$ e $Y$ podem ser conjuntos, ou podem ser tipos, ou podem ser outros tipos de objetos, como explorados abaixo.

Dada uma função

f colon (X times Y) to Z

currying constrói uma nova função

{displaystyle hcolon Xto (Yto Z)}

Isso é, $h$ leva um argumento de $X$ e retorna uma função que mapeia $Y$ para $Z$ . É definido por

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

para $x$ a partir de $X$ e $y$ a partir de $Y$ . Nós também escrevemos

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

Sem cura é a transformação reversa, e é mais facilmente entendido em termos de sua união direita, o função ${displaystyle operatorname {apply}.}$

Teoria dos conjuntos

Na teoria dos conjuntos, a notação $Y^X$ é usado para denotar o conjunto de funções do conjunto $X$ para o conjunto $Y$ . Currying é a bijeção natural entre o conjunto $A^{Btimes C}$ de funções de $Btimes C$ para $A$ , e o conjunto ${displaystyle (A^{C})^{B}}$ de funções de $B$ para o conjunto de funções de $C$ para $A$ . Em símbolos:

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

De fato, é esta bijeção natural que justifica a notação exponencial para o conjunto de funções. Como é o caso em todos os casos de cura, a fórmula acima descreve um par adjunto de funtores: para cada conjunto fixo $C$ O funtor ${displaystyle Bmapsto Btimes C}$ é deixado junto ao funtor ${displaystyle Amapsto A^{C}}$ .

Na categoria de conjuntos, o objeto $Y^X$ é chamado de objeto exponencial.

Espaços de função

Na teoria dos espaços de função, como na análise funcional ou na teoria da homotopia, é comumente interessado em funções contínuas entre espaços topológicos. Um escreve ${text{Hom}}(X,Y)$ (o funtor Hom) para o conjunto de Todos funções $X$ para $Y$ , e usa a notação $Y^X$ denotar o subconjunto de funções contínuas. Toma. ${displaystyle {text{curry}}}$ é a bijeção

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

enquanto não currying é o mapa inverso. Se o conjunto $Y^X$ de funções contínuas $X$ para $Y$ é dada a topologia compacta-aberto, e se o espaço $Y$ é localmente compacto Hausdorff, então

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

é um homeomorfismo. Este é também o caso quando $X$ , $Y$ e $Y^X$ são gerados compactamente, embora haja mais casos.

Um corolário útil é que uma função é contínua se e somente se sua forma atual for contínua. Outro resultado importante é que o mapa de aplicação, normalmente chamado de "avaliação" neste contexto, é contínuo (observe que eval é um conceito estritamente diferente na ciência da computação). Ou seja,

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

é contínuo quando $Y^X$ é compacto-aberto e $Y$ localmente compacto Hausdorff. Estes dois resultados são centrais para estabelecer a continuidade da homotopia, ou seja, quando $X$ é o intervalo da unidade $I$ , para que ${displaystyle Z^{Itimes Y}cong (Z^{Y})^{I}}$ pode o pensamento de como uma homotopia de duas funções $Y$ para $Z$ , ou, equivalentemente, um caminho único (contínuo) $Z^{Y}$ .

Topologia algébrica

Na topologia algébrica, currying serve como um exemplo da dualidade Eckmann-Hilton e, como tal, desempenha um papel importante em uma variedade de configurações diferentes. Por exemplo, o espaço do loop é adjacente às suspensões reduzidas; isso é comumente escrito como

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

Onde? $[A,B]$ é o conjunto de classes de homotopia de mapas $Arightarrow B$ e $Sigma A$ é a suspensão de Ae ${displaystyle Omega A}$ é o espaço de loop de A. Em essência, a suspensão $Sigma X$ pode ser visto como o produto cartesiano de $X$ com o intervalo de unidade, modulo uma relação de equivalência para transformar o intervalo em um loop. A forma curada então mapeia o espaço $X$ para o espaço de funções de loops em $Z$ , isto é, de $X$ para dentro ${displaystyle Omega Z}$ . Então... ${displaystyle {text{curry}}}$ é o funtor adjunto que mapeia suspensões para loop espaços, e uncurrying é o dual.

A dualidade entre o cone de mapeamento e a fibra de mapeamento (cofibração e fibração) pode ser entendida como uma forma de currying, que por sua vez leva à dualidade das sequências de Puppe exatas e coexatas longas.

Na álgebra homológica, a relação entre currying e uncurrying é conhecida como adjunção tensor-hom. Aqui, surge uma reviravolta interessante: o functor Hom e o functor produto tensorial podem não elevar-se a uma sequência exata; isso leva à definição do functor Ext e do functor Tor.

Teoria do domínio

Em teoria da ordem, isto é, a teoria dos trenós de conjuntos parcialmente ordenados, ${displaystyle {text{curry}}}$ é uma função contínua quando a treliça é dada a topologia Scott. As funções contínuas de Scott foram investigadas pela primeira vez na tentativa de fornecer uma semântica para cálculo de lambda (como a teoria dos conjuntos comuns é inadequada para fazer isso). Mais geralmente, funções contínuas por Scott são agora estudadas na teoria do domínio, que engloba o estudo da semântica denotacional de algoritmos de computador. Note que a topologia Scott é bastante diferente de muitas topologias comuns que se pode encontrar na categoria de espaços topológicos; a topologia Scott é tipicamente mais fina, e não é sóbria.

A noção de continuidade aparece na teoria do tipo de homotopia, onde, grosso modo, dois programas de computador podem ser considerados homotópicos, ou seja, calcular os mesmos resultados, se eles puderem ser "continuamente" refatorado de um para o outro.

Cálculo lambda

Na ciência da computação teórica, currying fornece uma maneira de estudar funções com vários argumentos em modelos teóricos muito simples, como o cálculo lambda, em que as funções só levam um único argumento. Considere uma função $f(x,y)$ tomando dois argumentos, e tendo o tipo ${displaystyle (Xtimes Y)to Z}$ , que deve ser entendido como significar que x deve ter o tipo $X$ , Sim. deve ter o tipo $Y$ , e a própria função retorna o tipo $Z$ . A forma curada de f é definido como

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

Onde? $lambda$ é o abstrator do cálculo lambda. Uma vez que o curry leva, como entrada, funciona com o tipo ${displaystyle (Xtimes Y)to Z}$ , conclui-se que o tipo de caril em si é

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

O operador → é muitas vezes considerado direito-associativo, então o tipo de função curried $X to (Y to Z)$ é frequentemente escrito como $X to Y to Z$ . Por outro lado, a aplicação da função é considerada de esquerda-associativa, de modo que $f(x,y)$ é equivalente a

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

Ou seja, os parênteses não são necessários para eliminar a ambiguidade da ordem do aplicativo.

Funções Curried podem ser usadas em qualquer linguagem de programação que suporte fechamentos; no entanto, as funções não programadas são geralmente preferidas por motivos de eficiência, uma vez que a sobrecarga de aplicação parcial e criação de fechamento pode ser evitada para a maioria das chamadas de função.

Teoria do tipo

Na teoria do tipo, a ideia geral de um sistema de tipo na ciência da computação é formalizada em uma álgebra específica de tipos. Por exemplo, ao escrever ${displaystyle fcolon Xto Y}$ , a intenção é que $X$ e $Y$ são tipos, enquanto a seta $to$ é um construtor de tipo, especificamente, o tipo de função ou tipo de seta. Da mesma forma, o produto cartesiano $Xtimes Y$ de tipos é construído pelo construtor do tipo de produto $times$ .

A abordagem da teoria dos tipos é expressa em linguagens de programação como ML e nas linguagens derivadas e inspiradas por ela: CaML, Haskell e F#.

A abordagem da teoria dos tipos fornece um complemento natural para a linguagem da teoria das categorias, conforme discutido abaixo. Isso ocorre porque as categorias e, especificamente, as categorias monoidais têm uma linguagem interna, sendo o cálculo lambda simplesmente digitado o exemplo mais proeminente de tal linguagem. É importante nesse contexto, pois pode ser construído a partir de um único construtor de tipo, o tipo seta. Currying então confere à língua um tipo de produto natural. A correspondência entre objetos em categorias e tipos permite que as linguagens de programação sejam reinterpretadas como lógicas (via correspondência de Curry-Howard) e como outros tipos de sistemas matemáticos, conforme explorado mais adiante.

Lógica

Sob a correspondência Curry-Howard, a existência de currying e uncurrying é equivalente ao teorema lógico ${displaystyle (Aland B)to CLeftrightarrow Ato (Bto C)}$ , como tuplas (tipo de produto) corresponde à conjunção na lógica, e o tipo de função corresponde à implicação.

O objeto exponencial ${displaystyle Q^{P}}$ na categoria de álgebras de Heyting é normalmente escrito como implicação material $Pto Q$ . Álgebras de Heyting distributivas são álgebras booleanas, e o objeto exponencial tem a forma explícita ${displaystyle neg Plor Q}$ , tornando-se assim claro que o objeto exponencial realmente é implicação material.

Teoria da categoria

As noções acima de currying e uncurrying encontrar sua declaração mais geral, abstrata na teoria da categoria. Currying é uma propriedade universal de um objeto exponencial, e dá origem a uma adjunção em categorias fechadas cartesianas. Ou seja, há um isomorfismo natural entre os morfismos de um produto binário. $f colon (X times Y) to Z$ e os morfismos a um objeto exponencial $g colon X to Z^Y$ .

Isso se generaliza a um resultado mais amplo em categorias monoidal fechadas: Currying é a afirmação de que o produto tensor e o Hom interno são funtores adjacentes; isto é, para cada objeto $B$ há um isomorfismo natural:

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

Toma. Hom denota o (externo) Hom-funtor de todos os morfismos na categoria, enquanto ${displaystyle BRightarrow C}$ denota o funtor hom interno na categoria monoidal fechada. Para a categoria de conjuntos, os dois são os mesmos. Quando o produto é o produto cartesiano, então o hom interno ${displaystyle BRightarrow C}$ torna-se o objeto exponencial ${displaystyle C^{B}}$ .

O curry pode ser quebrado de duas maneiras. Uma delas é se uma categoria não é fechada e, portanto, carece de um functor interno (possivelmente porque há mais de uma escolha para tal functor). Outra maneira é se não for monoidal e, portanto, carece de um produto (ou seja, carece de uma maneira de escrever pares de objetos). As categorias que possuem produtos e homs internos são exatamente as categorias monoidais fechadas.

A definição de categorias cartesianas fechadas é suficiente para a discussão da lógica clássica; a configuração mais geral de categorias monoidais fechadas é adequada para computação quântica.

A diferença entre esses dois é que o produto para categorias cartesianas (como a categoria de conjuntos, ordens parciais completas ou álgebras de Heyting) é apenas o produto cartesiano; é interpretado como um par ordenado de itens (ou uma lista). O cálculo lambda simplesmente digitado é a linguagem interna das categorias cartesianas fechadas; e é por esta razão que pares e listas são os tipos primários na teoria de tipos de LISP, Scheme e muitas linguagens de programação funcional.

Por outro lado, o produto para categorias monoidais (como o espaço de Hilbert e os espaços vetoriais da análise funcional) é o produto tensorial. A linguagem interna dessas categorias é a lógica linear, uma forma de lógica quântica; o sistema de tipo correspondente é o sistema de tipo linear. Tais categorias são adequadas para descrever estados quânticos emaranhados e, de forma mais geral, permitem uma vasta generalização da correspondência de Curry-Howard para a mecânica quântica, para cobordismos na topologia algébrica e para a teoria das cordas. O sistema de tipo linear e a lógica linear são úteis para descrever primitivas de sincronização, como bloqueios de exclusão mútua e a operação de máquinas de venda automática.

Compare com aplicação de função parcial

Currying e aplicação de função parcial são frequentemente confundidos. Uma das diferenças significativas entre os dois é que uma chamada para uma função parcialmente aplicada retorna o resultado imediatamente, não outra função na cadeia de currying; esta distinção pode ser ilustrada claramente para funções cuja aridade é maior que dois.

Dada uma função do tipo $f colon (X times Y times Z) to N$ , currying produz $text{curry}(f) colon X to (Y to (Z to N))$ . Ou seja, enquanto uma avaliação da primeira função pode ser representada como $f(1, 2, 3)$ , a avaliação da função curada seria representada como $f_text{curried}(1)(2)(3)$ , aplicando cada argumento por sua vez a uma função de um único argumento retornada pela invocação anterior. Note que depois de chamar $f_text{curried}(1)$ , somos deixados com uma função que leva um único argumento e retorna outra função, não uma função que leva dois argumentos.

Em contraste, aplicação parcial da função refere-se ao processo de fixação de um número de argumentos a uma função, produzindo outra função de aridade menor. Dada a definição de $f$ acima, podemos corrigir (ou 'bind') o primeiro argumento, produzindo uma função do tipo $text{partial}(f) colon (Y times Z) to N$ . Avaliação desta função pode ser representada como $f_text{partial}(2, 3)$ . Note que o resultado da aplicação de função parcial neste caso é uma função que leva dois argumentos.

Intuitivamente, o aplicativo de função parcial diz "se você corrigir o primeiro argumento da função, obterá uma função dos argumentos restantes". Por exemplo, se a função div representa a operação de divisão x/y, então div com o parâmetro x fixado em 1 (ou seja, div 1) é outra função: a mesma que a função inv que retorna o inverso multiplicativo de seu argumento, definido por inv(y) = 1/y.

A motivação prática para a aplicação parcial é que muitas vezes as funções obtidas fornecendo alguns, mas não todos os argumentos para uma função são úteis; por exemplo, muitos idiomas têm uma função ou operador semelhante a plus_one. A aplicação parcial facilita a definição dessas funções, por exemplo, criando uma função que representa o operador de adição com 1 vinculado como seu primeiro argumento.

Aplicação parcial pode ser visto como avaliar uma função curried em um ponto fixo, por exemplo, dado $f colon (X times Y times Z) to N$ e $ain X$ então ${displaystyle {text{curry}}({text{partial}}(f)_{a})(y)(z)={text{curry}}(f)(a)(y)(z)}$ ou simplesmente ${displaystyle {text{partial}}(f)_{a}={text{curry}}_{1}(f)(a)}$ Onde? ${displaystyle {text{curry}}_{1}}$ curries f's primeiro parâmetro.

Assim, a aplicação parcial é reduzida a uma função curried em um ponto fixo. Além disso, uma função curried em um ponto fixo é (trivialmente), uma aplicação parcial. Para mais provas, note que, dada qualquer função $f(x,y)$ , uma função ${displaystyle g(y,x)}$ pode ser definido como ${displaystyle g(y,x)=f(x,y)}$ . Assim, qualquer aplicação parcial pode ser reduzida a uma única operação de caril. Como tal, o curry é mais adequadamente definido como uma operação que, em muitos casos teóricos, é frequentemente aplicada recursivamente, mas que é teoricamente indistinguível (quando considerado como uma operação) de uma aplicação parcial.

Assim, uma aplicação parcial pode ser definida como o resultado objetivo de uma única aplicação do operador curry em alguma ordenação das entradas de alguma função.

Contenido relacionado

Más resultados...