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 modifier
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 modifier
Haskell modifier
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 modifier
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 modifier
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 modifier
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 modifier
(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 modifier
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 modifier
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 modifier
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 modifier
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 modifier
const uncurriedAdd = (x, y) => x + y;
const curriedAdd = x => y => x + y;
uncurriedAdd(2, 5); // 7
curriedAdd(2)(5); // 7
Clojure modifier
(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++ modifier
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 modifier
- (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.) »
