Curryfication
En informatique, plus précisément en programmation fonctionnelle, la curryfication est la transformation d'une fonction à plusieurs arguments en une fonction à un argument qui retourne une fonction sur le reste des arguments. L'opération inverse est possible et s'appelle la décurryfication.
Le terme vient du nom du mathématicien américain Haskell Curry, bien que cette opération ait été introduite pour la première fois par Moses Schönfinkel[1].
Définition
Considérons une fonction add
qui prend deux arguments (x et y) et en renvoie la somme. En la curryfiant, on obtient une fonction addcur
qui prend un argument et renvoie une fonction qui prend le deuxième argument. En pseudo-langage :
curry (add (x,y)) → addcur x → lambda (y → x + y)
La curryfication permet l'application partielle : si on appelle la fonction curryfiée avec l'argument 3, on récupère une fonction qui ajoute 3 à son argument.
Exemples dans les langages de programmation
Haskell
En Haskell, voici une fonction non-curryfiée :
uncurried_add (x, y) = x + y
et la même après curryfication :
curried_add x y = x + y
ou bien :
curried_add x = \y -> x + y
où la barre oblique \ introduit une λ-expression (lambda-expression) et sert à définir des fonctions anonymes. Et voici une application partielle :
main = do print (uncurried_add (3, 5)) -- 8 print ((curried_add 3) 5) -- 8 print (curried_add 3 5) -- 8 let add_three = curried_add 3 print (add_three 5) -- 8 print (add_three 12) -- 15
- Remarques
La curryfication peut se faire à la main ou bien par un programme. Pour les fonctions à deux arguments, voici ces programmes en Haskell :
main = do let uncurried = uncurry curried_add print (uncurried (3, 5)) -- 8 let curried = curry uncurried_add print ((curried 3) 5) -- 8 print (curried 3 5) -- 8 let add_three = curried 3 print (add_three 5) -- 8 print (add_three 12) -- 15
Python
Même fonction en Python :
def uncurried_add(x, y): return x + y def curried_add(x): return lambda y: x + y print(uncurried_add(3, 5)) # 8 print(curried_add(3)(5)) # 8 add_three = curried_add(3) print(add_three(5)) # 8 print(add_three(12)) # 15
Caml
Même fonction en Caml :
let uncurried_add(x, y) = x + y;; (* Type de la fonction : (entier * entier) -> entier *) let curried_add x y = x + y;; (* Type de la fonction : entier -> entier -> entier *) uncurried_add(3,4);; (* Retourne 7. Type de la valeur retournée : entier. *) curried_add 3;; (* Retourne la fonction qui ajoute 3. Type de la valeur retournée : entier -> entier. *) (curried_add 3) 4;; (* Crée la fonction qui ajoute 3 et l'applique à l'entier 4. Retourne 7. Type de la valeur retournée : entier. *) let add_three = curried_add 3;; (* Définit la fonction add_three comme la fonction qui ajoute 3 à son argument. *) add_three 5;; (* Applique add_three à 5. Retourne 8. *) add_three 12;; (* Applique add_three à 12. Retourne 15. *)
Ruby
def uncurried_add(x, y) return x + y end def curried_add(x) return lambda { |y| x + y } end puts uncurried_add(3, 5) # 8 puts curried_add(3).call(5) # 8 add_three = curried_add(3) puts add_three.call(5) # 8 puts add_three.call(12) # 15
Ruby fournit l'expression lambda avec la méthode curry. La méthode prend en argument un argument optionnel : l'arity, qui permet des processus plus fins, qui ne seront pas discutés ici.
uncurried_add = lambda { |x, y| x + y } puts uncurried_add.call(3, 5) # 8 puts uncurried_add.curry[3][5] # 8 add_three = uncurried_add.curry[3] puts add_three.call(5) # 8 puts add_three.call(12) # 15
Scheme
(define uncurried-add (lambda (x y) (+ x y))) (define curried-add (lambda (x) (lambda (y) (+ x y)))) (display (uncurried-add 3 5)) (newline) ; 8 (display ((curried-add 3) 5)) (newline) ; 8 (define add-three (curried-add 3)) (display (add-three 5)) (newline) ; 8 (display (add-three 12)) (newline) ; 15
Scala
def uncurried_add(x: Int, y: Int) = x + y // => Int // Après currying def curried_add0(x: Int)(y: Int) = x + y // => Int // Ce qui équivaut (si on décompose) à def curried_add1(x: Int) = (y: Int) => x + y // => (Int) => Int // Ou encore à: def curried_add2 = (x: Int) => (y: Int) => x + y // => (Int) => (Int) => Int // applications partielles def add_three0 = curried_add0(3) // retourne une fonction de type: (Int) => Int curried_add0(3)(5) // Retourne 8 add_three0(5) // Retourne 8 def add_three1 = curried_add1(3) // retourne une fonction de type: (Int) => Int curried_add1(3)(5) // Retourne 8 add_three1(5) // Retourne 8 def add_three2 = curried_add2(3) // retourne une fonction de type: (Int) => Int curried_add2(3)(5) // Retourne 8 add_three2(5) // Retourne 8
Tcl
proc uncurried_add {x y} { expr {$x + $y} } proc curried_add x { list apply [list y [format {expr {%d + $y}} $x]] } puts stdout [uncurried_add 3 5]; # 8 puts stdout [{*}[curried_add 3] 5]; # 8 set add_three [curried_add 3] puts stdout [{*}$add_three 5]; # 8 puts stdout [{*}$add_three 12]; # 15
Perl 6
Un JAPH qui est un exemple de curryfication en Perl 6 :
sub japh (Str $lang) { say "just another $lang hacker"; } my &perl6Japh := &japh.assuming("Perl6"); perl6Japh();
JavaScript
function uncurried_add(x, y) { return x + y; } function curried_add(x) { return function(y) { return x + y; }; } console.log(uncurried_add(3, 5)); // 8 console.log(curried_add(3)(5)); // 8 const add_three = curried_add(3); console.log(add_three(5)); // 8 console.log(add_three(12)); // 15
JavaScript ES2015
const uncurriedAdd = (x, y) => x + y; const curriedAdd = x => y => x + y; uncurriedAdd(2, 5); // 7 curriedAdd(2)(5); // 7
Clojure
(defn uncurried-add [x y] (+ x y)) (defn curried-add [x] (fn [y] (+ x y))) ;; curried-add renvoie une fonction anonyme (println (uncurried-add 3 5)) ;; 8 (println ((curried-add 3) 5)) ;; 8 (def add-three (curried-add 3)) (println (add-three 5)) ;; 8 (println (add-three 12)) ;; 15
Modern C++
Le C++11 a introduit les lambdas dans le langage, puis le C++14 a introduit la possibilité de définir un type de retour auto pour faciliter l'écriture de certaines fonctions.
Ces deux améliorations permettent d'implémenter la curryfication :
#include <iostream> int uncurried_add(int x, int y) { return x + y; } auto curried_add(int x) { return [x](int y) { return x + y; }; } int main() { std::cout << uncurried_add(3, 5) << std::endl; // 8 std::cout << curried_add(3)(5) << std::endl; // 8 auto add_three = curried_add(3); std::cout << add_three(5) << std::endl; // 8 std::cout << add_three(12) << std::endl; // 15 }
À noter que depuis le C++17, la mention du type int en argument de l'expression lambda peut également être remplacée par auto, généralisant l'implémentation (au prix de faire de la méthode curried_add un template implicite).
Notes et références
- ↑ (en) John C. Reynolds, « Definitional Interpreters for Higher-Order Programming Languages », Higher-Order and Symbolic Computation, vol. 11, no 4, , p. 374 (DOI 10.1023/A:1010027404223) :
« In the last line we have used a trick called Currying (after the logician H. Curry) to solve the problem of introducing a binary operation into a language where all functions must accept a single argument. (The referee comments that although "Currying" is tastier, "Schönfinkeling” might be more accurate.) »
Annexes
Sur les autres projets Wikimedia :
- curryfication, sur le Wiktionnaire
- opérateur de diffusion, sur le Wiktionnaire
Articles connexes
v · m | |
---|---|
Création |
|
Structure |
|
Comportement |
|
Fonctionnel |
|
Patron d'architecture |
|
Autres patrons |
Portail de l’informatique
Portail de la logique
Portail de la programmation informatique