Commentaires

Envoyé par SpiceGuid

J'ai envie d'une formulation un peu plus générale.

Par exemple:

• soit C un ensemble et soit P=℘(C).
• soit T un multi-ensemble d'éléments P.
• on veut trier P selon le nombre d’occurrences de ses éléments dans T, par ordre décroissant.

Après, pour paramétrer l'algorithme, on peut introduire des bornes, par exemple le nombre d'occurrences minimales.

Est-ce qu'en procédant ainsi on s'éloigne du problème concret ? Ou bien au contraire on a explicité la question cachée derrière la motivation matérielle ?
Avec le décodage évident :

• C pour catalogue
• P pour paniers
• T pour transactions

Merci pour ce commentaire judicieux qui m'oblige à éclaircir la notion!

• soit C un ensemble: le catalogue, pourquoi pas!
• soit P=℘(C): là nous divergeons; l'ensemble des parties de l'ensemble est nécessaire lors d'une approche "force brute" pour générer des candidats au titre d'association fréquente, mais il n'est pas nécessaire pour définir le problème.
• soit T un multi-ensemble de P: nous divergeons encore; les transactions dans la recherche d'associations fréquentes ne sont pas un multi-ensemble mais un ensemble simple et de plus un sous-ensemble de C.

Je comprends l'intérêt de proposer une définition plus générale mais on y perd en l'occurrence toutes les possibilités d'optimisation présentes dans les algorithmes a priori et fp-growth (ce dernier étant celui que je présente) dont l'heuristique permet d'éviter la génération de ℘(C).

La succession tri de ℘(C) - borne de fréquence minimale a une complexité assez terrible: 2^|C|+1 pour la génération de ℘(C), |C|log^|C| pour le tri et encore |C| pour la borne...

J'ai envie d'une formulation un peu plus générale.

Par exemple:

• soit C un ensemble et soit P=℘(C).
• soit T un multi-ensemble d'éléments de P.
• on veut trier P selon le nombre d’occurrences de ses éléments dans T, par ordre décroissant.

Après, pour paramétrer l'algorithme, on peut introduire des bornes, par exemple le nombre d'occurrences minimales.

Est-ce qu'en procédant ainsi on s'éloigne du problème concret ? Ou bien au contraire on a explicité la question cachée derrière la motivation matérielle ?
Avec le décodage évident :

• C pour catalogue
• P pour paniers
• T pour transactions

Envoyé par SpiceGuid

Pour le débat ouvert sur la programmation fonctionnelle, je dirais que ça n'est pas une question de lieu, de format ou de style de présentation, c'est une simple question de part de marché.

J'espère ne pas être tout à fait à côté de la plaque quand je dis qu'on programme aussi par plaisir? Et j'ai pour ma part trouvé beaucoup de plaisir à découvrir et utiliser la programmation fonctionnelle. J'espérais partager ça dans le blog avec d'autres... J'ai vu qu'il y avait quand même un certain nombre d'affichages pour chaque post, il y a eu très peu de commentaires mais les billets ont tout de même été lus.

Envoyé par SpiceGuid

Mais revenons à nos moutons.
Le C++ moderne c'est à partir de quand ? Quand je remplace struct par class ? Ou plutôt quand je privilégie les récents ajouts dans la norme ?

Les récents ajouts de la norme: on arrive presqu'à l'expressivité des langages de script avec toujours la rigueur et la performance C++

Envoyé par SpiceGuid

Les associations. C'est vague. Si c'était juste des listes on utiliserait un Trie. Si c'était juste des paires on utiliserait un 2D-tree. Si c'était des n-uplets on utiliserait un kD-tree. Si c'était des partitions on utiliserait un Union-Find. Mais comme ça n'est rien de tout ça on va crafter un algorithme original. Ça ressemble assez à des inventaires, un peu comme ce que j'avais fait il y a longtemps en OCaml avec les briques lego.
Au niveau des données la similitude est frappante, par contre comme la finalité n'est pas la même au niveau des traitements ça n'aura aucun rapport.

J'ai jeté un oeil à ton article qui est très intéressant. Le vaisseau logo est incroyable! En revanche sur la question des associations fréquentes je vais éditer mon article pour le rendre moins vague. Ce à quoi je pense est:
- soit E un ensemble d'éléments
- soit S un ensemble de séquences, ou transactions, qui sont des sous-ensembles de E
on veut trouver tous les sous-ensembles de E qui sont également des sous-ensembles d'un nombre déterminé de transactions présentes dans S

Pour le débat ouvert sur la programmation fonctionnelle, je dirais que ça n'est pas une question de lieu, de format ou de style de présentation, c'est une simple question de part de marché. Peu de parts de marché égale peu d'emplois, peu de logiciels. Et soyons honnête, une techno sans killer-app a du mal à justifier son existence sur un marché déjà saturé par l'offre. Et non, un assistant de preuve n'est pas une killer-app. La seule fois où j'ai réussi à arracher une réaction à un programmeur mainstream c'était à l'évocation de Raincat. J'ai eu droit à "je croyais que Haskell ça n'était que pour les abstractions mathématiques". Le comble de la gratification.
Ensuite je crois que Nikki and the robots n'a pas été un succès commercial et là ça a été le coup de grâce, plus aucun curieux ne s'est intéressé à Haskell.

Mais revenons à nos moutons.
Le C++ moderne c'est à partir de quand ? Quand je remplace struct par class ? Ou plutôt quand je privilégie les récents ajouts dans la norme ?

Les associations. C'est vague. Si c'était juste des listes on utiliserait un Trie. Si c'était juste des paires on utiliserait un 2D-tree. Si c'était des n-uplets on utiliserait un kD-tree. Si c'était des partitions on utiliserait un Union-Find. Mais comme ça n'est rien de tout ça on va crafter un algorithme original. Ça ressemble assez à des inventaires, un peu comme ce que j'avais fait il y a longtemps en OCaml avec les briques lego.
Au niveau des données la similitude est frappante, par contre comme la finalité n'est pas la même au niveau des traitements ça n'aura aucun rapport.

Envoyé par Hinault Romaric

,
Par contre, les titres sont horribles et bien trop abstraits . Je suis obligé de trouver de nouveaux titres pour les annoncer sur les rubriques de Developpez.com, pour les offrir plus de visibilité. De plus, de tels titres sont de véritables cailloux dans le référencement de tes billets.

Je vais garder ça en tête!

Salut,

Félicitation pour tes billets qui sont très bien rédigés. Par contre, les titres sont horribles et bien trop abstraits . Je suis obligé de trouver de nouveaux titres pour les annoncer sur les rubriques de Developpez.com, pour les offrir plus de visibilité. De plus, de tels titres sont de véritables cailloux dans le référencement de tes billets.

Un effort en ce sens me ferait du bien.

Merci pour vos retours pour info j'ai une bac Math et ma question été plustôt d'ordre générale

je me suis amusé y'a pas longtemps à écrire des séries Mathématiques en php (c'est une classe )

https://github.com/ghaliano/AwesomeP...rogression.php

apparament je vais essayer de les écrire en Haskell pour voir ce que ça donne

Bien à vous

Envoyé par phpiste

Bonjour,
je suis entrein de voir un peu de quoi il s'agit en suivant tes billets,
enfaite j'arrive pas à commencer
Est ce qu'il faux être un mathématitien pour comprendre et bénéficier de ce language
Sérieusement, y'a t'il un point de départ (un truc genre hello world basic )
Merci

- Il n'est pas nécessaire d'être mathématicien pour se lancer dans la programmation fonctionnelle! Cela peut aider mais on peut s'en tirer sans.
- Il y aurait bien un hello world, d'ailleurs pas bien compliqué:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

putStrLn "Hello World!"

mais il n'apprend pas grand chose...
- je ne sais pas à quel moment du blog tu as commencé à lire: les premiers billets étaient les plus simples possibles et j'ai fait attention à ce qu'aucune documentation externe ne soit nécessaire. Si tu as pris en cours de route, il y a un certain nombre de notions à acquérir
- en tout cas je te remercie pour ton intérêt et je te conseille de ne pas t'arrêter là! la programmation fonctionnelle a deux intérêts majeurs, je pense:
1) c'est une façon de programmer de plus en plus importante parce que: a) elle facilite la programmation parallèle, b) elle permet de programmer de façon plus concise et plus sûre, c) elle constitue un pont entre recherche et production et d) elle est à la mode (dans l'évolution de Java, C++, Python, etc. c'est impressionnant de voir le nombre de caractéristiques empruntées à LISP ou Haskell)
2) c'est une façon de penser qui rapproche la programmation et les mathématiques: cela donne un cadre rigoureux et permet de programmer le plus généralement possible. Je suppose que déjà, sans y penser forcément, tu utilises dans tes programmes des objets qui ont des propriétés répertoriées en mathématiques et que tu en tires les conséquences. Pour prendre un exemple, tu distingues des objets dont l'addition est commutative (1+2 = 2+1) ou non ("ab"+"ba" != "ba"+"ab") et peux modifier tes algorithmes en conséquence. Pour prendre un autre exemple simple qui porte un nom compliqué, tu utilises sans le savoir des "monoïdes", qui sont simplement des ensembles pourvus d'une opération associative ( (a+b)+c = a+(b+c) ) et d'un élément neutre associé (0 pour l'addition, par exemple). On peut faire des structures de données très puissantes dédiées aux monoïdes, comme des arbres indexés, qui fonctionnent pour tous les monoïdes.

Non, il n'y a pas de hello world qui te donnerait la clé de tout le reste.

Ou plutôt si, il y a quelque chose qui te donne la clé de tout le reste mais ça n'est pas un hello world. Il s'agit de la démonstration par récurrence (dans ℕ). Si tu ne maîtrises pas cette notion élémentaire alors tu ne sauras pas la généraliser à d'autres types algébriques.

Des choses fondamentales vont forcément t'échapper ou bien te paraître ésotériques. Par exemple le passage du monoïde (ℕ,+) au monoïde (list,append). La correspondance entre les deux n'est visible que si tu maîtrises la démonstration par récurrence.

Bonjour,
je suis entrein de voir un peu de quoi il s'agit en suivant tes billets,
enfaite j'arrive pas à commencer
Est ce qu'il faux être un mathématitien pour comprendre et bénéficier de ce language
Sérieusement, y'a t'il un point de départ (un truc genre hello world basic )
Merci

Ah! Quelqu'un suit!
Alors en avant vers les catégories et au-delà!

Déjà 15 billets

S'il le faut voici de la matière pour quelques prochains billets :

1. Monoïde.
2. Groupe (c'est très pratique car c'est un monoïde avec un "undo").
3. Foncteur & Foncteur applicatif.
4. Comonade.

Pour faire vite et bien (ou le moins pire possible).
Parce que prêcher pour des convertis c'est pas trop mon truc.

Avec l'encodage de Church on ne peut pas être Turing-complet. De plus il faut évaluer en ordre normal, ce qui n'est pas très efficace. En échange de quoi on a une garantie de terminaison. Pour ceux qui veulent plus de détails je vous renvoie à l'excellent papier de Gabriel Scherer.

Si l'encodage de Church ressemble à un pli (fold) généralisé alors l'encodage de Scott ressemblerait à un case. Dans ce cas on ne peut plus garantir la terminaison. Ce qui est une mauvaise nouvelle. Car on veut toujours qu'une tâche se termine. Le contre-exemple du driver d'imprimante est trompeur. Car on veut toujours qu'une impression se termine. Peut-être que l'on souhaite que le driver reste en mémoire après impression. C'est cependant une question orthogonale. Que le driver reste en mémoire ou soit rechargé pour une nouvelle impression, dans les deux cas on veut que l'impression se termine.
Comme on n'a pas de récurseur (autre mot pour fold généralisé) on va devoir coder explicitement la récursion. Ce codage ne sera bien typé que dans System F. L'autre alternative c'est de faire de la récursion une primitive du langage.
La bonne nouvelle c'est qu'on peut utiliser une stratégie d'évaluation stricte ou paresseuse, qui est plus rapide que la stratégie d'évaluation en ordre normal. Ainsi, on ne terminera pas forcément mais si on termine alors on terminera plus vite qu'avec l'encodage de Church.

Voilà, j'ai survolé le sujet, ceux qui voudront approfondir sauront bien trouver tout seuls la documentation la plus adaptée à leurs interrogations.

Merci!!

Tout à fait d'accord avec toi sur l'argument de l'équivalence Turing, qui passe complètement à côté de la réalité de la programmation, qui est avant tout une activité humaine...

Envoyé par SpiceGuid

Le lambda-calcul est un modèle bien plus plus pragmatique. On peut programmer avec. En choisissant l'encodage de Church. Ou bien en choisissant l'encodage de Scott. C'est déjà un premier choix.
Rapidement avec, l'encodage de Church, on va se heurter à de sévères limitations qui vont pousser à enrichir le système de typage.
De même, avec l'encodage de Scott, on a tellement de liberté qu'il va falloir organiser tout avec ça davantage de polymorphisme.
.

Là dessus je me dis que tu devrais te lancer et écrire un billet pour développer un peu...

C'est tellement vrai.
Et dit avec tellement d'éloquence.

J'ai ma petit idée personnelle quant à la racine idéologique de l'apologie du formatage de la pensée par le formatage du code.
C'est l'argument selon lequel toutes les machines de Turing sont équivalentes en terme de calculabilité. Le hic dans cet argumentation c'est que personne ne sait programmer avec une machine de Turing.
Le lambda-calcul est un modèle bien plus plus pragmatique. On peut programmer avec. En choisissant l'encodage de Church. Ou bien en choisissant l'encodage de Scott. C'est déjà un premier choix.
Rapidement avec, l'encodage de Church, on va se heurter à de sévères limitations qui vont pousser à enrichir le système de typage.
De même, avec l'encodage de Scott, on a tellement de liberté qu'il va falloir organiser tout avec ça davantage de polymorphisme.

Bref, avec le lambda-calcul, c'est tout un monde d'options qui s'ouvre au programmeur. Avec le lambda-calcul c'est la fin de la sempiternelle sarabande de l'orgue de barbarie dont l'insipide uniformité nivelle la créativité par le bas.

Merci pour ce très aimable commentaire!

Je ne sais pas trop ce que tu entends par "quel cas concret"? Un livre très bien fait pour avoir des exemples Haskell proches du "monde réel" est le livre Real world Haskell (http://book.realworldhaskell.org/read/) disponible gratuitement mais en anglais.

Pour ma part, dans des billets de blog, je suis un peu limité par la place, mais j'espère donner des exemples plus développés à l'avenir, quand les techniques de base seront couvertes. Pour l'instant, c'est à dose homéopathique...

Enfin un tuto différent ! La on apprends. Si vous pourriez compléter par des exemples qui nous montrerait le resultat et dans quel cas concret on utilise telle ou telle function, personnellement je serais comblé.
Merci d'user de votre temps pour nous les novices. Il n'y a que comme ca qu'on peut rendre Haskell plus populaire.

Bonjour Kolodz,

Tout d'abord, merci pour ce premier commentaire du blog, qui soulève des points importants que je suis content de pouvoir préciser.

J'ai édité le post pour insérer un lien vers le billet de François comme vous aviez raison de le demander, puisque je lui réponds.

Je suis d'accord pour dire que les généralités sur la programmation fonctionnelle -ou aussi bien la programmation objet- sont rarement justifiées et je ne veux pas affirmer d' équations comme: programmation fonctionnelle = bottom-up ou programmation objet = up-bottom.
Je suis encore plus d'accord pour dire que le choix d'un langage ne définit pas le choix d'une approche (au contraire, même, et j'essaierai dans ce blog de montrer les aspects fonctionnels de C++ 11 / 14 ou de Python).

Néanmoins, l'un des apports les plus intéressants de la programmation fonctionnelle est un certain type de modularité: la possibilité de composer des fonctions avec d'autres fonctions, qui pousse à une approche de type bottom-up. Inversement, dans la programmation objet, la modularité est orientée vers la réutilisation d'objets (que ce soit par héritage ou par composition); cela n'exclut pas des éléments bottom-up dans l'approche mais pousse tout de même à réfléchir d'abord à l'interface et ensuite à l'algorithme. Je ne dis pas pour autant qu'un programmeur objet expérimenté tombera dans les travers dénoncés par François.

Sur les questions de l'optimisation et des tests, que vous soulevez très justement:
- sur les tests, je n'affirme bien sûr pas que la programmation bottom-up est la seule qui permette des tests. Je dis simplement qu'il y a une plus forte incitation à tester des fonctions que l'on réutilise fréquemment, et une plus forte probabilité qu'elles aient déjà été écrites, testées et optimisées lorsqu'elles sont plus générales.
- sur l'optimisation, pour tout vous dire, j'en suis presque un adversaire. Je considère que la généralité et la compréhension du code sont en général plus importantes (mais je ne programme pas le logiciel d'avions de chasse ou de moteurs de fusée). Les optimisations figent trop souvent le code. Cela étant, le code de ce billet pourrait être facilement amélioré, mais je voulais en faire l'objet d'un prochain billet, dans un langage plus fonctionnel que LISP...

Est-il possible d'avoir un lien sur le billet " Misères de l’analyse objet, un cas pratique" de ce "François" ?

J'avoue ne pas trop comprendre la problématique traité dans le billet.

Le Bottom-Up n'est pas spécifique à la programmation fonctionnelle et la programmation fonctionnelle n'est pas limité au Bottom-Up.

Il est certains certains que la programmation objet pourrai commencer l'écriture d'un code équivalent en Up-Bottom de cette façon :

Code Java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
public class Hand{
 
    public static void main(String[] args) {
        Hand hand = new Hand();
        System.out.println(hand.getScore());
    }
}

Mais il est totalement possible de faire du Bottom-Up :

Code Java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
public class Hand{
    private Color color;
    private Rank rank;
 
    public boolean hasColor();
    public boolean hasSuccRank();
}

De même qu'il est possible de débuter votre raisonnement en commençant par la fonction synthetic-score.
Cela ne distingue aucunement le type langage, mais l'approche utilisé sur le problème.

De même, votre exemple présent une découpe fine en sous-fonction, qui n'est encore une fois spécifique au Bottom-Up (ou à la programmation fonctionnelle). D'ailleurs, c'est un approche qui a vite tendance à s'inverser quand on se rend compte qu'on ne maitrise pas les cas métier.

En suite, il y a la problématique que l'optimisation et du test.

Pour ce qui est du test :
Beaucoup vous diront qu'il est impératif de savoir le retour attendu d'une fonction avant de la coder. Certains vous diront même qu'il est nécessaire d'écrire les cas de test de cette fonction avant de la coder. Cette approche n'a donc pas d’influence sur le fait qu'une sera testé ou non.

Pour ce qui est de l'optimisation :
Il faut bien comprendre que l'approche Bottom-Up est basiquement inadapté pour réaliser une bonne optimisation. Même si l'ensemble des fonctions sont optimisés. Il est n'est pas rare de voir des optimisations ou des simplifications dans un traitement dû à un contexte plus général. D'ailleurs, il est déconseillé de réaliser des optimisations autres qu'algorithmique pendant une phase de développement. Celles-ci doivent se faire avec une fonction/application stable, afin de pouvoir mesurer l'impacte globale de cette "optimisation".

En somme, votre billet présent un belle exemple de programmation LISP, utilisant de nombreuse bonne pratique de programmation (Sous fonction, commentaire, etc...). Mais le propos de fond de l'article me laisse perplexe.

Cordialement,
Patrick Kolodziejczyk.