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

  1. ↑ (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 :

Articles connexes

v · m
Création
Structure
Comportement
Fonctionnel
Patron d'architecture
Autres patrons