comprendre la Curryfication [Résolu]

[Overcrash]

Bonsoir,

Je sais pas si je suis dans la bonne section j'ai hésité a poster

Je suis tombé sur une méthode de programmation donc cela ne concerne pas vraiment de langage en particulier, et c'est uniquement pour moi, pour ma culture.

Donc en clair qu'est ce que la Curryfication ?

J'ai bien sur cherché sur google je suis tombé notamment la dessus :
http://fr.wikipedia.org/wiki/Curryfication

J'ai pas très bien compris la définition mais encore moins quand/pourquoi l'utiliser

Si un d'entre pourrait reformuler/expliquer avec un exemple je lui en serais reconnaissant. Par exemple je sous entends un exemple d'utilisation pas de code

Merci.

[Médinoc]

Déjà, c'est de la programmation fonctionnelle, donc impossible à faire directement dans des langages comme C ou C++: il est question de générer des fonctions en run-time.

Si j'ai bien compris, la currification, c'est remplacer une fonction genre ajouter(x, y) par un truc du genre creer_fonction_ajouter_x(x) qui retourne une fonction.

Ainsi, imaginons que je veuille ajouter 3 + 5, au lieu de faire ceci:

Code non-currifié :

int resultat = ajouter(3, 5)

j'appellerais une telle fonction ainsi:

Code curryfié :

1
2
Fonction f = creer_fonction_ajouter_x(3)
int resultat = f(5)

[Overcrash]

plop,

Ha ok je comprend mieux mais alors ca sert a quoi ? Concrètement ?

[Médinoc]

Il me semble qu'en programmation fonctionnelle, pratiquement tout est basé sur ce genre de truc. Je ne peux pas t'en dire plus, là: C'est aussi alien pour moi que pour quiconque a grandi avec la programmation impérative.

[Twinside]

C'est principalement utilisé pour les fonctions d'ordre supérieur, tel que map, filter ou les fold_left/fold_right.

par exemple pour ajouter 5 à tous les nombres d'une liste de nombre, on va utiliser l'opérateur (+) qui est une fonction qui prend 2 entiers et en renvoit 1, et qui a pour type sous sa forme curryfié :

Code :

(+) :: Int -> Int -> Int

où la flèche représente l'application d'une fonction. L'opération d'ordre supérieure pour transformer les éléments d'une liste s'appelle map, ici décrit pour les listes d'entier uniquement :

Code :

map :: (Int -> Int) -> [Int] -> [Int]

Elle prend en premier paramètre une fonction qui pour entier donné retourne un autre entier, et une liste. Map retourne une liste d'entier. Au final nous obtenons :

Code :

1
2
3
map ((+) 5) [1, 2, 3, 4]
=> [6, 7, 8, 9]

Ici on utilise la curryfication pour grandement simplifier l'écriture. Dans la pratique, on appelle souvent des fonctions plus complexes, conçue pour tirer partie de la curryfication, typiquement placer les arguments de paramétrage au début des paramètres et l'argument "manipulé" à la fin.

En respectant cette forme d'écriture, on peut même arriver à créer des "pipeline" de fonction (un peu comme en shell), où l'on combine des fonctions curryfiée, en laissant juste le dernier argument manquant.

Par exemple en Haskell, on peut écrire :

Code :

1
2
3
4
5
normalizeList = map (/ 10) . filter (< 0) . filter (> 10)

normalizeList [0, -10, 15, 5, 2]
=> [0, 0.5, 0.20]

Qui est une fonction créé en combinant 3 fonctions currifyé, chaque fonction a besoin d'une liste en dernier paramètre et retourne un fonction, et le . sert à combiner les fonctions, créant ainsi un pipeline.

C'est très puissant et pratique d'utilisation, mais il faut juste s'habituer un peu au mécanisme, un peut "alien" au début, indispensable par la suite.

Déjà, c'est de la programmation fonctionnelle, donc impossible à faire directement dans des langages comme C ou C++: il est question de générer des fonctions en run-time.

Il n'y a pas de création de fonction au runtime, mais il y a allocation de donnée, pour reprendre l'éxemple de l'opérateur d'addition, voici comment on pourrait écrire l'équivalent en C++ :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Add
{
    int  n1;
    Add( int nn1 ) : n1( nn1 ) {}
    int   operator() ( n2 ) { return n1 + n2; }
};

struct Add3
{
    int  n1;
    Add3( int nn1 ) : n1( nn1 ) {}
    Add   operator() ( int n2 ) { return Add( n1 + n2 ); }
};

...
Add3( 4 )( 9 )( 2 )
...

Add représente vraiment l'opérateur +, l'appel au constructeur représente le premier argument, le deuxième est donné lors de l'appel de l'opérateur surchargé. On peut imaginer le cas où on veut additionner 3 chiffres, comme pour Add3. Dans la réalité, lorsqu'on appelle une fonction curryfiée, ça donne lieu à une fermeture, on alloue de l'espace pour garder traces des arguments successifs (du moins dans l'idée, dans la pratique cela peut être optimisé).

[Médinoc]

^C'est ce que je voulais dire par "pas directement": Pour faire ça en C++, tu dois reproduire toutes les fonctions et le moteur pour les évaluer.

[Twinside]

Envoyé par Médinoc

^C'est ce que je voulais dire par "pas directement": Pour faire ça en C++, tu dois reproduire toutes les fonctions et le moteur pour les évaluer.

C'est plutôt la partie sur la génération de fonctions lors de l'exécution qui est erronée. De plus avec le C++1x0x (bon je sais plus comment il s'appelle au final), rien n'empêche de faire la curryfication avec les lambdas du langage.

Code :

1
2
3
4
5
auto addFun =
    []( int x ) -> std::function<int (int)> { 
        return [x]( int y ) -> int { return x + y; };
    };

Vu la tronche du code, j'éviterais personnellement d'abuser de ce style en C++.

[TropMDR]

Ah, la curryfication, en voilà un sujet sympa ! (note aux modos: un petit lien depuis le sous forum "langage fonctionnel" attirerait sans doute plus de gens qui comprennent bien)

Je vais essayer de me concentrer sur la curryfication et non sur les types par exemple, même si le liens est souvent fort.

Pour mes exemples, j'utiliserai du caml (je n'ai pas testé le code, donc il ne faut pas s'étonner si ça ne compile pas et s'il y a des erreurs de syntaxe. Mais l'idée sera là)

Commençons par voir comment on défini une fonction en caml:

Code :

let plus1 x = x + 1

Le mot clé let dit que l'on défini quelque chose. Là, c'est une fonction (plus1) qui attends un argument x, et retourne x + 1.

Pour appeler cette fonction, rien de plus simple. plus1 41 vaut 42. On remarquera qu'on n'utilise pas de parenthèse.

Supposons maintenant qu'on veuille définir une fonction à 2 arguments.

Il est possible de faire quelque chose comme

Code :

let plus (x, y) = y + x

comme dans la majorité des langages. Néanmoins, il est d'usage de faire

Code :

let plus x y = y + x

Et pour appeler cette fonction : plus 20 22 retournera 42.

Là non plus, pas de parenthèse. C'est ce qu'on appelle une fonction "curryfiée". Pourquoi ?
A première vu, ça semble être un simple changement de syntaxe, f(x, y) contre f x y. Mais la différence de syntaxe semble impliquer quelque chose de bien intéressant. On devrait pouvoir s'arrêter après le x, en écrivant juste f x (ce qui ne semble pas possible dans l'autre cas. Ecrire f(x, n'a pas trop de sens !).

Qu'est ce que ça peut bien vouloir dire ? Supposons qu'on récupère cette application partielle

Code :

let foo = plus 12

Il "manque un bout" pour avoir l'application complète. Et bien ça tombe bien, on peut finir de l'appliquer. foo 30 === plus 12 30 === 42.

On a ici le plus grand intérêt de la curryfication, si ce n'est le seul, à savoir l'application partielle, qui permet de créer une "nouvelle" fonction, qui est comme l'ancienne, mais avec quelques arguments déjà fournis.

Est ce que c'est une sorte de magie ad-hoc qui fait qu'on peut appliquer partiellement les fonctions ? Bien sur que non ! En fait, d'un point de vue sémantique (c'est à dire le sens que l'on donne à un programme), toutes les fonctions n'ont qu'un seul argument. Mais une fonction peut très bien retourner une autre fonction comme résultat ! Donc quand on définie

Code :

let mult x y = y * x

ce que l'on défini réellement, c'est une fonction mult qui attend un argument x et qui retourne une fonction (anonyme) qui attend un argument y et qui retourne y * x. (J'arrête tout de suite ceux qui vont pousser des haut cris "mais c'est super inefficace !", ce n'est pas comme ça que c'est implémenté en caml ! Quand une fonction est totalement appliqué, c'est un appel de fonction à plusieurs arguments qui est implémenté via une "décurryfication". Aucune différence d'efficacité.)
Plus précisément, on pourrait écrire mult de la façon suivante :

Code :

let mult = fun x -> (fun y -> y * x)

où fun x -> blah est la fonction qui attend un argument x et retourne blah. Et donc quand on écris ensuite mult 21 2, c'est en fait (mult 21) 2 === (fun y -> y * 21) 2 === 2 * 21 === 42.

Donc aucune "magie" derrière la curryfication, juste une sémantique liée au fait qu'on peut retourner une fonction.

Maintenant quels sont les exemples d'utilisation ? Comme le disait Twinside, c'est souvent lié aux "fonctions d'ordre supérieur". Par exemple la fonction List.map en caml prend en argument une fonction et une liste, applique la fonction a chaque élément de la liste, et retourne la liste des résultat. Par exemple List.map plus1 [1;2;3] va retourner la liste [2;3;4]. Imaginons maintenant que je ne veuille pas ajouter 1, mais multiplier par 2. Je pourrais d'abord définir une fonction mult2, puis appeler List.map mult2 [1;2;3]. Mais il y a plus simple ! J'ai déjà une fonction mult, qui multiplie deux nombres. Donc il suffit d'écrire List.map (mult 2) [1;2;3] pour obtenir [2;4;6] !

Maintenant, est ce tout ? Oh que non Ca permet de faire des choses encore plus puissante.

Supposons que l'on veulent écrire une fonction append_line qui prend un nom de fichier et une chaine de caractères, ouvre le fichier, et écrit la ligne dedans. Ca donnerait sans doute quelque chose comme

Code :

1
2
3
let append_line file_name line =
  let chan = open_out file_name in
  ouput_string chan line

(on constate ici que je ne ferme pas le descripteur de fichier, ce qui est clairement mal ! On pourrait éventuellement supposer que le GC s'occupera de le fermer (bon, c'est pas vraiment le cas, mais disons que si :p). Rappelons nous que c'est ici pour l'exemple).
On a notre fonction, et on commence à l'utiliser à pas mal d'endroit dans le code. Dont une fois, ou on a une liste de chaine à écrire, et on a List.map (append_line "monFichier.txt" lst. Et là on constate qu'à chaque élément de la liste, on va appliquer la fonction, qui va créer une nouveau descripteur de fichier pour "monFichier.txt", ajouter une chaine, et jeter le descripteur ! Peut on faire mieux ? Hé oui, comme suit :

Code :

1
2
3
let append_line file_name =
  let chan = open_out file_name in
  fun line -> ouput_string chan line

Qu'est ce qu'il se passe maintenant quand j'écris List.map (append_line "monFichier.txt") lst ? On se rappelle qu'une fonction à deux arguments est une fonction qui attends un argument et retourne une fonction qui... Mais avant de retourner la deuxième fonction, elle peut faire quelque chose. C'est exactement ce qui se passe ici ! append_line "monFichier.txt" n'est pas directement une fonction. Elle commence par ouvrir le fichier, puis seulement retourne la fonction fun line -> ouput_string chan line ! Donc maintenant le code List.map (append_line "monFichier.txt") lst n'ouvre plus le fichier qu'une seul fois ! Et toutes les autres utilisation "normales" sous forme append_line "unAutreFichier" "une ligne super\n" continuent à marcher comme avant.

Bref, la curryfication permet en plus d'effectuer un calcul entre l'application de deux arguments, ce qui peut être tout particulièrement puissant.

Si tu as besoin d'autres précisions, n'hésite pas à demander

[SpiceGuid]

C'est une question archi-débattue sur dvp, ici par exemple.

[TropMDR]

Envoyé par SpiceGuid

C'est une question archi-débattue sur dvp, ici par exemple.

Euh, sérieusement, tu penses que

Envoyé par SpiceGuid

selon moi la notion de curryfication c'est la présence d'une transformation naturelle (un morphisme de foncteur vers foncteur) de type (A × B → C) → (A → B → C)

ça répond à la question

Envoyé par Overcrash3181

J'ai bien sur cherché sur google je suis tombé notamment la dessus :
http://fr.wikipedia.org/wiki/Curryfication

J'ai pas très bien compris la définition mais encore moins quand/pourquoi l'utiliser

??

[Overcrash]

Bonsoir,

Tout d'abords je vous remercie pour le temps consacré a la question et aux différents posteur qui m'ont aidé a comprendre cette notions super flou a la base

En revanche il est vrai que mon post a plus sa place sur cette section : http://www.developpez.net/forums/f51...-fonctionnels/

Mais je savais pas que le langage fonctionnelle était un "type" je le saurai la prochaine fois

Merci encore