Aluminium95 a écrit 223 commentaires

Les types récursifs, en C on le fait avec des pointeurs

Je crois comprendre la difficulté alors. Le fait est que en C tu penses à la construction effective du type, alors que là c'est purement théorique. On peut même l'écrire « mathématiquement » de manière indépendante du langage sous-jacent : un type est un ensemble de valeurs, et un type paramétré est une fonction qui prend en argument des types pour en construire un autre.

Quand tu parles de pointeurs, tu rentres déjà dans le détail de la réalisation. C'est le constructeur ! Par exemple, quand on écrit :

data Tree a = Node [(a, Tree a)]

On dit au compilateur : quelque soit le type a que tu me donnes, je peux construire un nouveau type Tree a, et pour le construire j'utilise la fonction Node, à laquelle je donne une liste de couples de type (a, Tree a). La définition est récursive, car pour construire un élément de type Tree a, je peux avoir besoin d'en construire un de type Tree a … Mais en pratique, la construction se fait « à la main » de manière très simple : 

vide :: Tree a -- ici le type a est quelconque, vide est un élément « commun à tous les types d'arbres »
vide = Node [] -- C'est bien un arbre valide, selon la construction donnée 

simple :: Tree Int -- ici on spécifie le type 
simple = Node [(8, vide)] -- C'est bien un arbre, car vide est un arbre !

Au final, ce sont effectivement des pointeurs : la structure Node contient un pointeur vers une liste, qui est elle même simplement chaînée par des pointeurs. Les valeurs de la listes sont des pointeurs vers des couples de pointeurs … etc. Mais cette considération est « inutile » au niveau où on travaille.

« comment vérifie-tu que tu parcourt bien un arbre et pas un graphe ? »

Je ne le vérifie pas justement :-). Par construction c'est un arbre : il n'y a pas de « pointeurs » vers un étage plus haut, à chaque fois c'est un véritable nouveau nœud qui est crée, donc on ne peut que descendre. Par contre, on rencontre des nœuds qui contiennent la même information, ce qui est redondant pour l'exploration.

Aussi, comme précisé, comme je ne supprime pas les informations redondantes, il est infini (mais en haskell cela ne pose pas de problème).

Oh, ce n'est pas vraiment spécifique à Haskell ça. En fait, tu as un type récursif :

data Tree a = Node [(a,Tree a)]

Or traiter un type récursif c'est pas toujours facile. Du coup tu généralise, en regardant son homologue non récursif :

data Tree' a b = Node' [(a,b)]

On remarque que le deuxième est un type « normal », c'est à dire non récursif. Tu peux ensuite (formellement) écrire

Tree a <=> Tree' a (Tree a)

Car on remplace b par Tree a et on a des structures identiques (au nom du constructeur près).

Pour simplifier, on peut prendre le type liste :

data Liste a = Cons a (Liste a) | Vide

Sa contrepartie non-récursive est

data Paire a b = Cons' a b | Vide

Et on remarque bien que : Liste a <=> Paire a (Liste a).
Mieux tu peux définir le type récursif comme étant le type T a tel que Paire a (T a) = T a. Ce qui se comprend comme : une liste c'est un type tel que si je le met dans une paire, c'est encore une liste.

Quel intérêt ? Et bien, cela donne automatiquement une manière de « faire pousser » la structure. Pour nous c'était un arbre, pour la liste c'est pareil, il existe une fonction unfold qui permet de le faire.

Par exemple, on déduit la signature de unfold pour les listes :

Paire a b = Cons' a b | Vide
Liste a <=> Fixe (Paire a)

unfoldFinal :: b -> Liste a -- Ce que l'on veut 

f :: (b -> Paire a b) -- Ce que l'on sait faire 

unfold :: (b -> Paire a b) -> b -> Liste a

Mieux, tu as aussi l'inverse (ie : partir d'une liste et arriver à une valeur).

foldFinal :: Liste a -> b -- Ce que l'on veut 

f :: Paire a b -> b  -- Ce que l'on sait faire 

fold :: (Paire a b -> b) -> Liste a -> b

-- Exemple d'utilisation quand a = b = Nombre 
somme :: [Nombre] -> Nombre -- Ce que l'on veut 

add :: Paire Nombre Nombre -> Nombre -- Ce que l'on sait faire 
add Vide = 0
add (Cons' x y) = x + y

somme liste = fold add list

Il faudrait que je retrouve un article qui en parlait de manière plus générale. En tout cas la page wikipédia anglaise est assez bien faite.

Par boucle j'entends : comment vérifie tu que tu n'a pas de cycle dans ton arbre.

Je ne comprends pas … Un arbre ne peut pas contenir de cycle (enfin, sinon c'est plus un arbre) : Arbre_(graphe).

Donc, ce que je comprend quand tu dis « cycle », c'est retrouver une même configuration à deux niveaux différents dans l'arbre (qui auront donc les mêmes fils) :

A ---> B ---> ...
       C ---> ...
       D ---> A ---> Ici on aura encore le même arbre 

Et là je suis totalement d'accord avec toi sur la suite : il faut les retirer !

Donc j'avais bien compris : pour savoir s'il y a une solution, tu dois parcourir intégralement l'arbre (dans un sens ou dans l'autre), or retirant les doublons, il est fini, donc il est possible de savoir s'il existe une solution. Mais du coup c'est le même algorithme qui donne la solution et l'existence d'une solution.

On est donc à 4*10^9, il est donc possible de mémoriser les situations déjà visitées et donc déterminer si une situation est atteignable.

C'est peut-être évident … mais comment expliques-tu le « donc » dans ta phrase ?

J'avais proposé (pour la méthode en arrière) :

Sauf si à une étape on ne change pas l'ensemble des objectifs à atteindre : ce qui veut dire que l'on est dans une « boucle de dépendance » du jeu qui ne terminera jamais.

Ce qui serait l'équivalent de (pour la méthode en avant) de : « on ne trouve pas de nouvelles branches à visiter ». Dès lors, avec l'amélioration proposée (qui permet de ne pas revisiter des placements) il suffit de vérifier si à une étape la liste des branches à suivre est vide.

C'est bien ce à quoi tu pensais ?

C'est très clair merci, en gros tu fais des requêtes un peu comme avec une BDD, sur du code qui est écrit en ASP.

La question est donc la suivante : est-ce que l'apprentissage du langage est vraiment un plus ?

1. Il faut apprendre plusieurs langages et les faire cohabiter, ce qui fait plus de dépendances pour le programme à l'installation, et nécessite un apprentissage supplémentaire
2. Il y a une dépendance à un outil externe de résolution sur lequel il est difficile d'avoir du contrôle (en tout cas moins de contrôle que sur une bibliothèque). Si jamais on veut une nouvelle option, il faut soit :
   • La demander au développeur et attendre qu'elle soit intégrée
   • La coder soi-même, vraisemblablement dans un troisième langage, en reprenant le code du projet

Je vois tout de même certains avantages :

• Un langage unifié pour ce type d'algorithme
• Un langage spécifique qui facilite la description/résolution du problème
• Une décorrélation entre la résolution et le reste du programme

Pour l'instant, je ne pense pas que les avantages justifient les inconvénients pour mon utilisation.

En effet, c'était un prétexte pour parler de unfold pour les arbres et bind pour les listes.

Mais sa remarque est quand même pertinente, car un langage plus connu aurait peut-être rendu le contenu plus accessible …

Du coup toute la partie intéressante devient assez obscure. Dommage pour moi.

Aïe, c'est dommage, je ne voulais pas que ce soit un obstacle … J'avais pourtant essayé de ne pas trop faire de trucs abscons …

Le problème, c'est que la plus grande partie du code est basée sur les types, qui permettent de se guider pour coder les fonctions. D'ailleurs, cela permet de ne pas s'embrouiller, et de « matérialiser » les idées autrement que par le code : on ne désire pas coder une fonction, mais trouver une fonction qui a le type X, si possible en combinant des briques déjà présentes.

J'aurais pu le faire en python, mais il est plutôt laxiste sur les types (ce qui est parfois très utile), donc raisonner sur les types aurait été plutôt étrange.

Sinon, pour faire court, la fin (où on a retiré l'arbre intermédiaire) s'écrit très simplement en python par exemple (ici c'est naïf, aucune optimisation) :

pions = ["Rouge", "Bleu", "Vert"  , "Gris"]
direc = ["Haut" , "Bas" , "Droite", "Gauche"]

# branchesSuivies :: [ [(pion,direc)] ]
# liste des historiques des branches (sans le placement des pions)
def avance (branchesSuivies):
    t = []
    for historique in branchesSuivies:
        for p in pions:
            for d in direc:
                t.append ([(p,d)] + historique)
    return t

def estUneBonneConfig (pion,case,historique):
    ... # ici il faut avoir une grille et vraiment déplacer les pions
    return False / True

def trouveBonneConfig (pion,case,branchesSuivies):
    for b in branchesSuivies:
        if estUneBonneConfig (pion,case,b):
            return b
    return False

def resolution (pion,case):
    b = [ [] ] # Branches initiales : une vide !
    while True:
        b = avance (b)
        f = trouveBonneConfig (pion,case,b)
        if f != False:
            return f

Mais ici, on voit bien que j'ai « recodé » toutes les fonctions à la main, et sans trop m'intéresser aux types …

Sinon, est-ce que tu pourrais indiquer donner les passages qui posent problème, pour pouvoir les ré-écrire dans un style plus compréhensible ?

Bonne journée aussi !

il me semble important de savoir déterminer s'il existe une solution (si la case cible est au milieu et qu'il n'y a aucun mur alors il n'y a pas de solution par exemple)

Ce n'est pas un problème si facile : pour déterminer si une position est impossible à atteindre, soit on cherche une solution et on en trouve pas (ce qui ne veut pas dire grand chose vu que l'arbre est infini). Soit on part de la fin et on fait la méthode « en arrière » :

• Pour arriver à cette case, quels sont les directions possibles
• Pour chacune des directions, quelles sont les cases concernées où je dois amener le pion pour pouvoir faire ce mouvement
• Pour chaque case concernée, quelles sont les « cales » possibles ?
• Pour chaque couple (pion,cale) avec un pion différent du pion initial, on a un nouvel objectif
• appel récursif

Remarque : ici je ne prend pas en compte les murs, il faudrait ajouter, pour le premier mur rencontré dans chaque direction, un objectif.

On s'arrête quand on trouve :

1. Une solution triviale (le pion à déplacer est sur une des directions)
2. Un mouvement impossible : et là, comment le déterminer ? On revient au problème de départ, à priori, je n'ai pas de méthode simple pour déterminer un mouvement impossible … Sauf si à une étape on ne change pas l'ensemble des objectifs à atteindre : ce qui veut dire que l'on est dans une « boucle de dépendance » du jeu qui ne terminera jamais.

comment t'assure-tu de ne pas boucler ?

Dans le code naïf proposé, on repasse parfois par les mêmes placements de pions, mais c'est en largeur, du coup ce n'est pas vraiment une boucle, seulement, on est certain d'avoir branches à l'étape ce qui est très peu intéressant.

Étant donné qu'un placement est simplement un 4-uplet, on peut facilement faire un ensemble des positions déjà rencontrées, pour éviter de refaire les mêmes mouvements plusieurs fois. Je ne sais pas à quel est le gain réel de cette méthode, mais elle est facile à mettre en place.

Le coût d'une telle méthode est relativement moindre, puisqu'on va enregistrer des couples, et qu'à l'étape on aura au pire un nombre de configuration de l'ordre de grandeur de , ce qui ne change donc pas la complexité spatiale du programme.

j'aurais plutôt tendance à créer un arbre de configuration (chaque nœud de l'arbre est un ensemble de 4 coordonnées)

C'est intéressant, mais la réponse attendue n'est pas le placement final des pions, mais bien la suite de mouvements qui y mène … Donc si tu disposes seulement des placements, il te faut ensuite calculer les mouvements qui font la transition entre deux placements … Alors que l'autre sens est « trivial » (calculer le placement final à partir des mouvements).

il est possible de faire de la mémoïsation pour encore tronçonner le parcours de ton arbre

Donc, cela rejoint la mise en place d'un ensemble de positions déjà vues, pour ne pas créer des branches inutiles. À moins qu'il existe un autre moyen de mémoïser ?

Merci, c'est intéressant.
Je ne connaissait pas ASP, mais après une rapide recherche, c'est purement déclaratif, et donc c'est « l'interpréteur » qui s'occupe de faire la véritable exploration si j'ai bien compris, alors que mon objectif était de faire un parcours en largeur à gros coup de concat . map.

Après, c'est un avis personnel, mais c'est assez déconcertant de lire les « programmes » proposés sur la page wikipédia Answer set programming. C'est sûrement une question d'habitude toutefois.

Du coup, quel est l'avantage d'ASP par rapport à une bibliothèque de résolution en python par exemple ? Parce qu'il y a quand même des désavantages :

1. Pas d'interaction utilisateur possible en restant déclaratif
2. Le debug du programme se fait via les options fournies pas l'interpréteur
3. Quid de l'intégration dans un véritable programme (par exemple en tant qu'IA dans un jeu interactif) ?

Euh, s’il fallait porter plainte à chaque fois qu’un prof fait des remarques déplacées, ça serait fastidieux…

Oui, au début, et ensuite ça rentre dans les mentalités … Seulement, ne pas le faire c'est « cautionner » ce comportement : « Quoi ? Mes remarques sont déplacées ? Non ! Jamais personne ne s'est plaint ! »

D'ailleurs, faire remonter des comportements déplacés à la hiérarchie scolaire/porter plainte est tellement fastidieux qu'il vaut mieux construire des concours spécifiques pour les femmes ? Certes il y a des problèmes, mais refuser d'utiliser les moyens mis à disposition pour tenter de les régler « parce que c'est lourd » …

Histoire de rigoler, on remplace la remarque déplacée, par « voler le goûter des élèves » (même si ce n'est pas comparable) :

« Euh, s’il fallait porter plainte à chaque fois qu’un prof vole mon goûter, ça serait fastidieux… »

Pour rester dans le thème de départ (toujours en prenant un comportement qui n'est pas comparable) :

« Euh, s’il fallait porter plainte à chaque fois qu’un prof met une main aux fesses, ça serait fastidieux… »

La différence de réaction à la lecture « démontre » que les deux comportements (remarque/main) sont jugés différents, l'un étant « mineur » (puisque ne nécessitant pas d'action), et d'un autre côté on impose de ne plus faire la distinction « madame/mademoiselle » pour lutter contre le sexisme indirect que subissent les femmes à cause de ça … Alors que cela semble encore plus bas sur l'échelle des « comportements sexistes » (enfin, de mon point de vue qui peut être biaisé).

Le viol est un crime.

Je pense que nous sommes en accord sur ce point, pour me citer moi-même (l'exact commentaire auquel tu réponds en plus, en première phrase …)

Mais … ça c'est un crime

Sinon, tu as raison pour délit/crime : mais dans ma liste j'avais aussi d'autres choses que le viol (harcèlement pex) et je ne sais pas comment c'est considéré … Enfin bon, je m'excuse donc du choix de mots qui a pu diminuer la gravité de l'acte.

Tu penses que sans les quotas, les travailleurs handicapés seraient "égaux" sur le marché du travail face aux valides ?

C'est une phrase qui est pour ou contre les quotas ?

D'un côté, j'ai l'impression que tu es pour : cela permet d'avoir une « égalité des chances » mêmes pour les minorités dans un secteur de travail particulier, et donc favorise l'éducation de celles-ci et leur insertion dans ce milieu.

D'un autre côté, c'est totalement en opposition avec la libre concurrence (qui est quand même une des idées du système économique actuel) puisqu'à compétences égales on va forcer à sélectionner sur un critère arbitraire … (mais cette libre concurrence n'est pas forcément souhaitable en soi bien sûr).

En plus, l'analogie est intéressante, puisque (si j'ai bien compris) on compare « handicapés » et « femmes » ainsi que « valides » et « hommes » …

Du coup : pour ou contre ?

notre prof a trouvé judicieux et rigolo de prendre à partie la seule fille de la promo et de lui parler de ses photos en bikini, avec clins d'oeil, et dessins sur le tableau

Et comme tu es un fervent défenseur des droits des femmes tu as aussitôt réagit ? Non ? Dans le cas contraire, cela veut dire que tu acceptes socialement ce comportement, comme tes camarades, et que tu es par conséquent aussi sexiste que lui, voir même plus, puisqu'il peut s'agir d'une tentative très maladroite de faire de l'humour de sa part …

De plus, cet exemple est assez mal choisi … On peut en trouver des centaines en remplaçant femme par une catégorie en minorité dans une classe donnée : un élève particulièrement petit, gros, grand, chauve, … Quelque soit la raison de ce « traitement de faveur » qui expose publiquement la personne, c'est un comportement qu'il faut combattre : pas uniquement parce que c'est une femme !

10% contre 90%. Avec une telle disparité tu oses parler de privilèges ? Tu oses réclamer des efforts dans l'autre sens ? Sérieusement: de quel ordre ?

Euh, on reprend le même avec les éboueurs et tu arrives à la même conclusion : un point essentiel manque ici, c'est la « qualité » du poste. Sinon, comme il l'a indiqué, malgré la faible représentation, elles occupent statistiquement des postes plus élevés que les hommes (ce que je ne critique pas).

De grâce, ne nous joue pas le couplet larmoyant du mec aigri face à la fille subventionnée.

Je n'ai pas voulu être aigri, seulement constater que :

1. Les solutions proposées à base d'argent sont au mieux étranges, au pire totalement absurdes
2. Les raisons évoquées pour obtenir des aides ne sont souvent pas « bonnes ». Si était évoqué les problèmes de comportements de camarades, le fait de se retrouver « isolée » (même si c'est faux) … c'est acceptable. Maintenant dire : je suis réprimée / repoussée de cette filière / c'est plus dur pour une femme que pour un homme, c'est un mensonge

Epargne-nous le couplet pathétique sur la féministe qui se réclamerait supérieure aux hommes.

Hein ? Je n'ai jamais parlé de féministe … encore moins supérieure aux hommes …

La Convention sur l'élimination de toutes les formes de discriminations à l'égard des femmes s'exempte de toute considération de supériorité ou de privilège. Supprimer toute supériorité d'un sexe par rapport à un autre est précisément l'objectif de ce genre de texte.

Oui, le but est de supprimer les inégalités (donc supériorité d'un sexe sur l'autre), mais en faisant des activités séparées de manière « naturelle » on tend à distinguer les deux sexes encore plus, alors qu'à priori, pour un grand nombre de gens … franchement, c'est de l'informatique, on ne sait même pas à qui on parle vraiment avant de voir la personne en photo/physiquement … et on s'en fout !

Très dur de faire sa place alors que le credo est DIY

Mais c'est pareil pour les hommes là non ? (Je n'en sais rien, c'est une vraie question)

En attendant, y'a pas eu beaucoup d'hommes qui se sont fait violés ou agressé sexuellement dans le milieu libriste/hacker

Mais … ça c'est un crime, et c'est la police qu'il faut aller voir, pas faire des campagnes « girl can code » ! Si dès qu'il y a un problème, on fait un truc dans son coin … on s'en sort jamais !

« Je me fais cambrioler, mais du coup, plutôt que de faire respecter une loi qui est déjà en vigueur, je déménage dans un quartier exclusivement pour les gens comme moi … »

D'un autre côté, il est vrai que changer un milieu n'est pas facile. D'ailleurs, en reprenant le même exemple, on peut défendre le point de vue : « je me met dans un quartier avec des gens de même revenu, pour éviter d'avoir des emmerdements ». Ce qui est tout à fait légitime. Seulement, à mon sens, il y a deux choses à distinguer :

1. Les emmerdements : voisins pas sympa, remarques chiantes etc …
2. Les délits : vol, viol, harcèlement …

Dans le second cas : c'est pas un problème social. La société a été dans le sens de lois interdisant ce type de comportement, il « suffit » de demander leur application. Bien sûr, reste ensuite les emmerdements, mais d'un autre côté … on en a partout (à plus ou moins grande échelle) …

"il n'y a pas de femmes scientifiques célèbres parce-que cela ne les intéresse pas"

C'est assez intéressant comme « citation », parce que … personnellement, je ne connais pas de scientifique célèbre qui ait eu une reconnaissance « véritable » après 1990 (manque cruel de culture générale, je sais). En revanche, les « grands esprits » qui ont développés les concepts et posés les bases de la physique, des mathématiques ou de la logique sont plutôt connus : Pascal, Newton, Descartes, Pythagore, Maxwell, Boltzmann, Planck, Einstein, Legendre, Lagrange, Lavoisier etc …. Mais ce sont des VIEUX. À l'époque où ces personnes ont fait leurs travaux :

1. La situation sociale était très différente : pour certains la science était un passe temps (car ils étaient rentiers / nobles)
2. Les femmes n'avaient alors pas vraiment les mêmes acquis sociaux

Du coup, le « manque d'exemple féminins » s'explique assez facilement. Et je suis presque certain que de nombreuses femmes se sont illustrées en sciences quand on leur a laissé la possibilité de le faire (il me semble bien que la dernière médaille fields était pour une femme qui faisait de la géométrie hyperbolique nan ?) :

1. Il y a un effet « bombe à retardement » (il faut laisser le temps de construire des figures féminines)
2. On a de moins en moins de gens considérés comme de « grand génies » (ou alors ils seront considérés comme tels dans un certain temps)

Remarque 1 : l'effet retardement se voit aussi en politique par exemple, où la moyenne d'âge très élevée, fait que toute modification sociale se fait sentir avec approximativement 40 ans d'écart !

Remarque 2 : le constat fait sur les sciences peut s'appliquer aussi en littérature (avec quelques nuances)

Mais on constate en effet tous que les femmes ne font pas beaucoup d'informatique !

Ça dépend ce que tu appelles informatique aussi. C'est quand même assez vaste comme sujet d'étude. Après, il faut aussi distinguer les gens dont c'est le métier, et les gens dont c'est la passion. Ensuite, il faut regarder la corrélation entre les deux …

Personnellement, toutes les personnes qui ont eu un premier contact avec l'informatique (côté programmation/algorithmique) dans le système scolaire sont totalement hermétiques à cette discipline.

Pour comparer à autre chose : la danse classique. On va dire que très peu d'hommes font de la danse classique, principalement pour des raisons sociales (là pour le coup c'est plutôt avéré). On cherche maintenant à faire pleins de campagnes pour favoriser les hommes faisant de la danse et tout.

1. Cela ne change pas le problème social sous-jacent : si c'est socialement réprimé, une campagne ne change rien … Au contraire quand on voit les réactions à ces campagnes qui attisent les oppositions …
2. Cela fait d'une petite portion des femmes une raison de faire une campagne : je m'explique, très peu de femmes sont passionnées de danse classique en moyenne (enfin, je pense). Tout comme très peu d'hommes sont passionnés d'Informatique, de moteurs à réactions etc … On s'obstine à tout équilibrer alors qu'en réalité le problème est « ailleurs » (je ne dis pas qu'il ne faut pas le régler !!!)

Et quand ce sont les filles/femmes qui réclament ou mettent en place ce genre d'initiative, ce sont aussi des "débiles profondes" ?

[ironie]
Et, moi aussi je veux un concours rien que pour moi ! Tu penses qu'on va me l'accorder ? Non. Mais … du coup … si quand elles réclament des privilèges elles les obtiennent … elles sont pas défavorisées en fait …. ?
[/ironie]

Plus sérieusement, sa réaction est tout à fait compréhensible, étant donné qu'on fait tout un plat pour favoriser les femmes dans des domaines « pour les hommes » mais qu'il n'y a que très peu d'efforts faits dans l'autre sens, ce qui pousse presque à croire que certains seraient « plus compétents que d'autres » (vu qu'on estime qu'ils n'ont pas besoin d'une aide particulière pour réussir).

J'ai connu une fille qui a passé ses deux années de classes préparatoires avec une bourse d'étude parce que « c'est dur d'être une femme en prépa ». Bah, je suis désolé, mais homme ou femme, c'est exactement pareil : la sélection ne se fait pas sur le sexe, les notes non plus, le concours non plus … C'est même l'inverse : les écoles cherchent à avoir plus de femmes (ce qui peut légèrement influencer leur notation en faveur de celles-ci). Ce qui veut dire une chose : une femme est donc (déduction logique) moins compétente et pour l'aider il lui faut … de l'argent ?!

Maintenant imaginons un homme en littéraire : demande de bourse ? Mais on se moque de qui là, franchement, c'est le rêve, une classe remplie de jeunes demoiselles ! Et puis quel rapport avec de l'argent ici ?

Je suis donc en accord avec l'opinion exprimée plus haut : si on veut gommer les inégalités, il faut pas en créer artificiellement de nouvelles en forçant la main à la société. Au contraire, il suffit de supprimer les à-priori, et faire des campagnes : « Informatique pour tous » (ce qui viserait non seulement les jeunes femmes, mais plus généralement toute la population).

mais qu'est-ce que le () à la fin ?

Euh, c'est moi qui ai oublié de le remplacer par (\s -> length s > 0 && (s !! 0) /= '#'), du coup c'est normal que cela n'ai pas de sens …

fmap je suppose que ça veut dire function map

En fait, c'est « un peu plus » que cela. Imaginons que tu te donnes un type A quelconque, et que tu puisse manipuler des types [A] (ici c'est liste, mais en fait, ça peut être « programme », IO …). Tu te dis :

• J'ai tout un tas de fonctions super cool sur le type A
• J'ai tout un tas de fonctions super cool sur le type [] (indépendantes de A, par exemple head, tail etc …)
• J'aimerais avoir un moyen de transformer une fonction de A -> B en une fonction de [A] -> [B] : c'est fmap qui le fait

Alors, pour les listes, fmap = map. Mais en fait c'est beaucoup plus général : du moment que tu as un type paramétré, tu peux espérer trouver une fonction fmap, et qui a le bon goût de vérifier quelques axiomes (fmap id = id ou fmap f . fmap g = fmap (f . g) etc …)

Donc en fait fmap, c'est « functor map », et c'est un moyen de transformer une fonction « normale » sur une fonction d'un type paramétré.

Dans le cas présent, c'est IO a qui est un type paramétré, et qui représente un calcul effectué dans un état global.

>>= Ça doit être un truc avec l'approche monadique

Exactement, et cela vient très naturellement. Bon, c'est cool de pouvoir appliquer les fonctions normales sur ton type, mais tu as construit un type, c'est pas pour rien : il faut pouvoir faire plus de choses. En plus, tu as souvent des fonctions comme : a -> F b (j'ai remplacé [] par F) et le problème … c'est qu'elles ne se composent pas ! C'est tout ce que >>= fait : donner un moyen de composer ce nouveau type de fonctions.

• f : a -> F b : prend un type normal, retourne un type complexe
• g : b -> F c : idem
• f >=> g : a -> F c : prend un type normal, retourne un type complexe (en effectuant f puis g)

En fait, pour des raisons pratiques, on utilise plus souvent >>= que >=>, avec a >>= g === (\_ -> a) >>= g.

Exemple pratique, tu récupères la liste des arguments de la ligne de commande, c'est une action, de type Action [String], tu veux afficher cette liste, c'est une action, mais elle attend la chose à afficher en argument :

getArg :: Action [String]
print  :: String -> Action ()

printArgs :: Action ()
printArgs = getArg >>= (print . concat)

Donc en réalité, tout le code qui est écrit en exemple est soit

1. De la composition de fonction
2. De la transformation de fonction (en fonction sur les IO)

En espérant que mes explications sont claires :-)

Un intérêt est d'avoir des IO rapides à la jonction des processus puisque la communication est directement prise en charge par l'OS au lieu de tout remonter dans le langage, couper ligne à ligne, écrire immédiatement.

Un intérêt pour quel partie ? Faire le calcul entièrement en python ? Faire une librairie pour gérer la composition de fonctions ?

C'est la deuxième problématique que je trouvais discutable, et je n'ai pas vu/compris comment l'outil proposé améliorait l'IO en python … mis à part l'utilisation de générateurs (qui peut se faire de manière indépendante).

On est pas vendredi, mais remplacer du shell par du caml … mis à part des améliorations purement techniques de performances, je ne comprend pas l'intérêt syntaxique (voir l'exemple qui est donné …)

Après, pour la monade, oui, c'est une solution élégante, mais en OCaml, on ne peut pas garantir la pureté des fonctions, du coup, des méthodes de type « retry » et autres pourraient avoir des comportements étranges … (si on ne fait pas attention)

Quitte à essayer de construire une bibliothèque qui le fait bien, autant coder directement en Haskell, qui possède tout ce qu'il faut pour combiner des fonctions, et qui permet (via l'évaluation paresseuse) de remplacer les générateurs de python par de simples listes … et ce sans avoir une syntaxe immonde

cat :: String -> IO [String]
cat f = lines <$> readFile f

-- En traduisant « mot à mot » l'exemple du journal 
main :: IO ()
main = cat "fichier" >>= return . filter (\s -> length s > 0 && (s !! 0) /= '#') 
                     >>= return . map toFloat
                     >>= return . sort
                     >>= return . take 10
                     >>= output

-- En ré-écrivant pour utiliser >>= uniquement 
-- quand nécessaire (préférant (<$>) qui correspond à 
-- fmap en notation infixe)
main :: IO ()
main = (take 10 <$> 
        sort <$> 
        map toFloat <$> 
        filter (\s -> length s > 0 && (s !! 0) /= '#') <$> 
        cat "fichier") >>= output 

-- Enfin, en utilisant fmap f . fmap g = fmap (f . g)
main :: IO ()
main = (fmap traitement (cat "fichier")) >>= output
    where 
        traitement = take 10 . sort . map toFloat . filter ()

Pour résumer, oui l'approche monadique (ici avec IO) a beaucoup d'avantages :

1. Tu peux automatiquement promouvoir n'importe quelle fonction « normale » en une fonction qui agit sur un résultat de « programme » avec fmap ou <$>, ce qui permet d'utiliser toute fonction déjà écrite dans le langage que tu utilises
2. Tu peux raisonner sur des axiomes simples pour simplifier le code
3. Le résultat est encore lisible, plus facile à « comprendre » et surtout à modifier (on voit la structure du programme de manière apparente, et pas seulement au travers de commentaires à chaque étape …)

Le seul problème est l'intégration du code monadique dans le langage, et en python c'est pas toujours « esthétique », le problème en caml se pose moins puisqu'il est possible de définir des opérateurs infixes.

Remarque : c'est le genre de syntaxe que j'ai proposé d'utiliser en mettant en place une classe python dans un autre commentaire.

coté hack me fait préférer une notation explicite.

Le côté « hack » c'est juste utiliser un symbole, comme un autre commentaire l'a montré, on peut utiliser un nom de fonction … par exemple chain,
ce qui donne (mais qui est « moins joli »)

cat ().chain (sed ()). chain ( etc ...) . chain ( ... )

Après, il y a d'autres avantages à encapsuler dans un objet le calcul: tu peux contrôler les actions ! Ainsi, tu peux permettre des trucs utiles dans le genre:

• lancer en mode debug
• définir des « variables environnement » pour le programme
• construire d'autres manière de combiner les actions :
  • pour chaque ligne de résultat lancer une nouvelle chaine de commande et fusionner le tout (en parallèle ou non). Cette fonction serait en gros un « concatMap » sur des générateurs
  • exécuter une partie de code si et seulement si la première a échoué
  • etc …

Quand on y regarde de plus près, on se rend compte qu'une action (cat, sed etc …) c'est simplement une fonction de type action A : () -> [A].
On peut donc construire tout un tas de combinateurs :

• chain : action A -> ([A] -> action B) -> action B qui correspond à ta version
• chainEach : action A -> (A -> action B) -> action B qui lance un appel sur chaque ligne et concatène le résultat
• alter : action A -> action A -> action A qui essaie la première, et si elle échoue, lance la deuxième (alternative)
• fmap : (A -> B) -> action A -> action B, applique une fonction « normale » au résultat d'une action
• apply : action (A -> B) -> action A -> action B (l'utilisation de celle-ci est plus anecdotique, mais on peut en trouver).

Ensuite, on peut écrire du code comme celui-ci:

# 1) sélectionne un fichier qui contient une liste de fichiers
alter (cat ("fichier1"), cat ("fichier2"), erreur ("pas de fichiers"))
. chainEach (readFile) # lis les fichiers un par un et concatène 
. chain ( sed (" ... ") ) # applique un filtre (sur la totalité)
. fmap ( int ) # transforme chaque ligne du résultat en entier 
. run () # lance le véritable calcul