Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
Pari tenu. J'ai tapé "convex hull haskell" et 2 secondes plus tard google me donnait un lien vers une fonction toute faite dans le dépôt de libs ainsi qu'une implémentation sur rosetta code. Et pas d'opérateur >>= en vue.Envoyé par floyer
https://hackage.haskell.org/package/...Conqueror.html
https://rosettacode.org/wiki/Convex_hull#Haskell
Je rejoins la réponse de floyer : c'est du fonctionnel dans le sens où il n'y a pas de mutation et où tu passes une fonction en paramètre d'une autre fonction. Par contre count_if semble être une méthode de maListe et ça c'est plutôt de l'objet.
Effectivement, la proposition de code Haskell utilise la récursion et des constructions de listes pour éviter les mutations.
Rien de probant pour Dancing Link Haskell. Là, ce serait plus compliqué. Dans un domaine comparable (Dancing Link est fait pour résoudre différents types de problème : Sudoku, Pentamino…), pour des algorithmes de Sudoku, des exemples Haskell utilisent des monades, ce qui permet des sortes de "mutations" (ainsi, sur https://wiki.haskell.org/Sudoku, runStateT qui permet d'utiliser "put" pour modifier un état).
Je ne connais pas le Dancing Link mais je veux bien croire que c'est plus compliqué que l'enveloppe convexe.
Pour en revenir aux monades, ce n'est pas qu'un moyen de faire des mutations. C'est un concept plus général, qui permet de séquencer des actions, par exemple des mutations, mais aussi des entrées-sorties, de l'analyse syntaxique, des requêtes à un serveur, etc.
Mais souvent la monade n'est qu'une façon plus élégante d'écrire un code et n'est pas du tout indispensable. Par exemple pour la state monad dont tu parles, on peut très bien s'en passer : il suffit que chaque fonction prenne un state en paramètre et retourne le nouveau state en valeur de retour. C'est juste un peu plus verbeux à écrire.
Ah bah en fait si, il y a une version dancing links dans ton lien (https://wiki.haskell.org/Sudoku#Danc...Implementation). Mais effectivement, ça n'a pas l'air très simple...
Pour compléter ce que dit SimonDecoline, en Haskell, on peut se passer des monades, sauf :
- quand on utilise la monade IO, qui est le type officiel pour gérer les interactions avec l'extérieur du programme,
- quand on veut écrire du code générique qui doit marcher avec toutes les monades et
- quand on veut définir une nouvelle monade pour réutiliser du code existant qui marche avec toutes les monades.
Un intérêt typique d'écrire du code générique qui doit marcher avec toutes les monades est de rendre testable du code qui interagit avec l'extérieur du programme en production. En effet, à partir d'un code qui doit marcher avec toutes les monades :
- en production, on utilise la monade IO ou une autre monade qui encapsule IO et
- pendant les tests unitaires, on utilise une autre monade qui n'encapsule pas IO.
Un exemple simpliste se trouve dans l'article Unit testing effectful Haskell with monad-mock de Alexis King qui fait de la pub pour son package monad-mock (que je n'ai pas testé).
Merci pour vos réponses.
Ce qui me gêne est que passer une fonction en paramètre est possible dès le début de C avec les pointeurs de fonctions.
Dès le début du C++ aussi avec les foncteurs, et DP statégies.
Si cela est de la programmation fonctionnelle, alors on voit bel et bien la programmation fonctionnelle en IUT/Ingé.
Après, de dire que les langages deviennent de plus en plus fonctionnel avec map, filter, et autres, cela était possible dès la première version de C++ (C++98).
Pour les effets de bords, on est déjà bien obligé d'en avoir quelques uns, ne serait-ce que pour afficher du texte à l'écran.
Après, très très tôt il a été de bonne pratique de limiter les effets de bords que ce soit en C ou en C++.
Pour le :
Je ne considère pas cela comme un effet de bord.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4count = 0; for (auto elem : maListe) { if(elem == 2) count++; } return cout;
Pour faire de la programmation fonctionnelle on a aussi besoin de closure (fermeture).
Ainsi, pouvoir écrire : maListe.stream().filter( elem -> elem.x == monCritere) est très utile. Ici, on a plus qu’une fonction : on a une variable monCritere qui est passé implicitement avec la fonction.
Ces fermetures sont récentes en C++ et Java. Mais il est vrai que l’on peut instancier un objet MonFiltre qui a pour champ monCritere, et pour méthode Eval(elem)...
En Java (1.0 ou peu après), on pouvait écrire :
Là, le paramètre chaine est passé implicitement avec monActionListener afin de permettre l’exécution d’actionPerformed.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8String chaine = "bouton cliqué"; ActionListener monActionListener = new ActionListener() { public void actionPerformed(ActionEvent e) { System.out.println(chaine); } }; monButton.addActionListener(monActionListener);
Et d’un point de vu syntaxique, des lambda fonctions sont pratiques (placer une petite fonction directement là où on en a besoin plutôt que la déclarer plus haut et la référencer). Pouvoir écrire :
serait plutôt pratique en comparaison.
Code : Sélectionner tout - Visualiser dans une fenêtre à part monButton.addActionListener(e -> System.out.println(chaine));
En un sens, ça y ressemble. Mais pour C on ne peut pas vraiment dire que c'est de la programmation fonctionnelle car on ne peut que passer des fonctions déjà existantes. Pour que ce soit de la programmation fonctionnelle utilisable, il faut aussi pouvoir créer dynamiquement les fonctions que tu vas passer en paramètre, et surtout pouvoir définir leur environnement (qu'on appelle la "fermeture").
En C++, c'est effectivement possible depuis longtemps grâce aux "function-object", c'est à dire des objets qui ont "operator()". Mais c'est très lourd à écrire :
En c++11, les lambda et le type function simplifient énormément le code :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9
10
11
12
13
14
15struct Additionneur { int increment; int operator()(int valeur) { return valeur + increment; } }; int i = 2; Additionneur a {i}; // crée un additionneur à partir de i (c'est à dire 2) int res = a(8); // applique l'additionneur a sur la valeur 8 (donc retourne 10)
Du coup, les lambda sont pratiques à utiliser avec map, reduce, filter. Et on peut aussi faire de l'évaluation partielle (std::bind) et autres...
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8int v = 2; std::function<int(int)> a = [i](int valeur) { return valeur + i; }; // crée une fonction à partir de i (i est dans la fermeture de a) int res = a(8); // applique a sur la valeur 8
Oups, on répond en même temps...
Ah aussi, en fonctionnel, une fonction peut retourner une fonction. Par exemple en c++11
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9std::function<int(int)> creerAdditionneur(int i) { return [i](int v){ return v + i; }; } auto a = creerAdditionneur(2); int res = a(8); auto b = creerAdditionneur(100); ...
Je comprends mieux, mais dans ce cas est-ce vraiment une influence du fonctionnel sur le C++ qui a conduit aux lambda (comme la vidéo le suggère) ou tout simplement une volonté de simplifier l'écriture verbeuse des foncteurs ?
Est-ce que les évolutions sont donc liées au fait que le fonctionnel deviennent à la mode, ou tout simplement qu'un langage évolue et s'améliore au cours du temps ?
Et que l'effet observée est plus une "convergence évolutive" ?
La programmation fonctionnelle utilise certains patterns, et il est pratique que les langages utilisés pour programmer avec ce paradigme supportent ces patterns avec une écriture adaptée.
De même que l’on peut faire de la programmation objet en C, mais en codant « à la main » les tables de méthodes virtuelles (comme l’interface fichier des système d’exploitation où l’on a bien l’encapsulation - l’application n’interfère pas directement avec les variables du système d’exploitation - le polymorphisme - un fichier standard et un fichier device sont manipulés de la même manière, et le système d’exploitation utilise des tables de fonctions pour savoir comment lire ou écrire le fichier en fonction de la nature du fichier, du périphérique, du système de fichier, etc. Moins évident pour l’héritage)
Pas sûr que ce soit uniquement un effet de mode. Java 8 avec ses lamba functions, mais aussi les streams qui les utilisent propose une approche pratique... c’est une évolution à prendre ou à laisser. Influence ou volonté de pouvoir simplifier l’écriture ne s’exclut pas... c’est l’un est l’autre. (La simplification est l’objectif, l’influence est le moyen). Ce qui est intéressant à noter est que Java à introduit la programmation générique en même temps qu’un support de classes génériques (Collection). Avec Java 8, c’est en même temps que les streams qui les mettent à profit... c’est une approche assez pragmatique : on n’ajoute pas la programmation fonctionnelle juste pour cocher la case.
En C++, on a aussi quelques fonctions qui s’utilisent bien avec des lambda functions : copy_if, count_if, find_if.
Pour C++98, comme l'a dit SimonDecoline, écrire à la main une classe qui implémente operator() est lourd. On a la même lourdeur avec le patron de conception Stratégie.
Pour le langage C, on peut simuler une callback qui peut avoir un état mais, au niveau de la lourdeur, c'est encore pire. Par exemple, si on veut simuler une callback avec état qui prend en paramètre un const char* et qui returne un bool, il faut passer deux paramètres : un pointeur de fonction de type bool (*)(const char*, void*) et un paramètre de type void*. Ici, le paramètre de type void* pointe vers l'état de la callback, dont le vrai type dépend de la callback.
Or, le sucre syntaxique, c'est important. Si d'autres personnes vont récupérer ton code et si, chaque fois que tu veux mettre en place une abstraction, tu es obligé d'écrire un code lourd et illisible, alors les personnes qui vont récupérer le code vont reprocher au code d'être trop compliqué et vont invoquer le principe KISS. Sans ces abstractions, les briques du code seront alors moins réutilisables, mais plus lisibles pour ce langage.
Donc, quand on veut utiliser une fonctionnalité dans un langage, il est important qu'il n'y ait pas besoin de se battre contre le langage pour l'utiliser.
Si tu parles de std::transform et des autres algos de la bibliothèques standard du C++98 qui ont un itérateur de sortie, ces trucs ne font pas d'évaluation paresseuse, ce qui dissuade souvent de les utiliser sur de grosses collections, et ont en plus une syntaxe d'utilisation très lourde.
Remarque : en C++20, les équivalents de filter et map seront std::views::filter et std::views::transform.
La raison pour laquelle for (auto elem : maListe) { if(elem == 2) count++; } s'écarte du paradigme fonctionnel est que l'on utilise explicitement une variable muable. Cela dit, personnellement, quand une variable muable est bien isolée dans une petite fonction, je ne vois pas ça comme un problème. Les variables muables qui m'embêtent sont plutôt celles qui sont accessibles un peu partout dans le code.
Merci... je note que même si Haskell est un langage purement fonctionnel, les monades permettent une écriture procédurale (non fonctionnelle), que l’on observe avec la construction «*do*» abondamment utilisée (normal, l’algorithme de Knuth est très procédural; une écriture fonctionnelle ne serait pas l’algorithme de Knuth). Il y a néanmoins une différence majeure avec un langage classique, c’est que les effets de bord autorisés (setAttr qui appelle writeSTRef) sont limités aux données encapsulées par le type retourné. Comme ces fonctions sont encapsulées dans un runST, les seuls effets de bord sont ceux portant sur les états de runST (fonction solve). C’est comparable à une sandbox.
À titre d’exemple plus simple, une somme calculée de façon procédurale en Haskell :
Le runST crée un contexte d’exécution limité où les seuls effets de bord sont les modifySTRef / writeSTRef sur des références crées par newSTRef. Un «*putStrLn "Hello World"*» aurait un type IO qui serait rejeté par le compilateur. (On peut essayer de tricher avec un « ignore <- putStrLn "Hello World" » pour contourner ce problème de type, mais l’évaluation paresseuse de Haskell ferait qu’ignore n’enregistre qu’une intention jamais exécutée).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9
10
11
12
13
14import Control.Monad.ST import Data.STRef import Control.Monad sumST :: Num a => [a] -> a sumST xs = runST $ do -- runST takes out stateful code and makes it pure again. n <- newSTRef 0 -- Create an STRef (place in memory to store values) forM_ xs $ \x -> do -- For each element of xs .. modifySTRef n (+x) -- add it to what we have in n. readSTRef n -- read the value of n, and return it.
NB : DancingLink est un algorithme à connaître, mais d’autres implémentations sont probablement plus lisibles.
Pour pinailler, en fait, si tu insères ignore <- putStrLn "Hello World" dans ton bloc do, tu auras une erreur de compilation, car le compilateur le traduira en putStrLn "Hello World" >>= (\ignore -> le reste du bloc) et putStrLn "Hello World", de type IO (), ne sera pas compatible avec le deuxième opérande de >>=.
Par contre, si tu insères let ignore = putStrLn "Hello World" sans utiliser ignore, alors le code compilera et l'évaluation paresseuse, effectivement, n'exécutera pas ce code.
Oui, effectivement, j’avais commencé à penser let ... ignore... puis me suis fourvoyé. Un « résultat <- monade » ne prend que des monades du bon type, ici, ceux permis par runST. Et toutes ces monades sont exécutées dans l’ordre (dans un autre contexte, une lecture de fichier dont le résultat est ignoré fera bien avancer la position courante dans le fichier).
En fait si, on peut faire ignore <- putStrLn "Hello World" mais ça ne doit pas être la dernière ligne du bloc (car la dernière "opération" doit être une expression et non une déclaration). Pour que ça compile, il faut ajouter return ignore, ce qui est ici équivalent à return () et en fait à putStrLn "Hello World" tout simplement.
Pour le let ignore = putStrLn "Hello World", je ne pense pas que ce soit un problème d'évaluation paresseuse mais juste de déclaration sans utilisation. On aurait la même chose dans un langage classique si on déclare une variable et qu'on ne l'utilise jamais.
Et effectivement, pouvoir définir différents contextes d'exécution avec des fonctionnalités particulières, grâce aux monades, est très pratique.
Dans un langage classique, un ignore = putStrLn "Hello world" serait exécuté dès l’exécution de la ligne. En Haskell, ignore pointerait sur la séquence à exécuter plus tard lorsque l’on a besoin de ignore, ou jamais si on ignore la variable. C’est ce qui rend impossible d’utiliser des IO dans un contexte qui ne le permet pas.
Pour le return ignore, cela permet effectivement de sortir le putStrLn, mais cela ne fait que déplacer le problème : il faudrait que le programme appelant place ce résultat en sortie de fonction main directement ou non (dans un contexte de nomade IO plus généralement). Avec le sudoku :: [[Int]] -> [[[Int]]] qui appelle les fonctions de résolution, on sais d’avance que le runST qui récupérerait le ignore ne pourrait pas en faire grand chose... et si ce résultat est ignoré, l’évaluation paresseuse rendrait non exécuté le putStrLn.
EDIT, il y a la backdoor unsafePerfomeIO qui consommerait le résultat de putStrLn... mais sans cette fonction (ou autre issue de System.IO.Unsafe) le putStrLn ne pourrait pas être exécuté hors contexte ad’hoc.
Je me suis mal exprimé dans mon message précédent en parlant de variable. Si on fait ignore = putStrLn "Hello world", le type de ignore est IO () c'est-à-dire une action dans la monade IO et qui retourne une valeur de type "Unit". L'equivalent dans un langage classique est de déclarer une fonction (pour laquelle on n'autoriserait que les entrées-sorties). Et si on n'appelle pas cette fonction, il ne se passe rien non plus, indépendamment de l'évaluation stricte ou paresseuse.
Sur un exemple de code complet, en haskell on aurait :
et en C :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
Là où l'évaluation paresseuse apporte des difficultés, c'est plutôt pour analyser le comportement des fonctions pures car l'ordre d'évaluation des expressions n'est pas forcément l'ordre dans lequel elles sont écrites.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9void ignore() { printf("Hello world\n"); } int main() { ignore(); return 0; }
En fait à vous lire, on comprend pourquoi la programmation fonctionnelle n'est pas la norme
C'est objectivement simple, en aucun cas quelque chose d'obligatoire pour produire du code, mais quand on se met à couper les cheveux en 4...
Émotion
Infantilisation
Culpabilisation
Christophe Alévèque - 18 Mars 2021
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager