Journal Données vs Code

Posté par Aluminium95 le 28 mars 2016 à 23:00. Licence CC By‑SA.

Étiquettes : aucune

mar.

2016

Bonjour nal,

C'est avec humilité que je viens de présenter une « révélation récente », qui si elle est déjà connue, s'accompagne bien mieux d'un exemple : l'avantage certain à construire des données par rapport à celui de construire des instructions.

Ce sujet est assez vieux, ne serait-ce que grâce à Lisp qui permet de considérer (à un niveau assez bas) données et programmes comme interchangeables via son Homoiconicité. Néanmoins, pour chaque problème à résoudre il faut se poser la question : quelle partie est représentée physiquement en tant que donnée, et quelle partie est procédurale/impérative/mécanique ?

Très souvent, il est préférable (dans un premier temps en tout cas) de construire une structure de données qui correspond à une représentation du problème, puis de la détruire en calculant une solution. Une manière simple de le faire est via un Hylomorphism (computer science), qui se détermine en donnant deux ingrédients

Une fonction simple qui construit un morceau de structure
Une fonction simple qui détruit un morceau de structure

L'exemple classique de la factorielle devient alors

fact n = product [1..n]

-- Si on regarde comment sont codées les fonctions range et product

-- a) construction de la fonction range (inclusive)
range a b = unfold (\x -> if x <= b then Just (x,x+1) else Nothing) a

-- b) construction de la fonction product 
product = foldr (*) 1

Tant que l'on reste dans des choses « simples », on est dans un monde parfait où tout est facile, lisible, modifiable à souhaits. Pour prendre un autre exemple académique, demandons-nous ce qu'il faut pour coder un tri fusion :

Une fonction qui crée un arbre binaire équilibré dont les feuilles sont des singletons
Une fonction qui fusionne deux listes triées pour en construire une nouvelle triée

Classiquement, c'est la pile d'appels récursifs qui va en réalité représenter l'arbre binaire (qui sera alors implicite) en écrivant les noeuds dans l'ordre d'un parcours en profondeur. À quoi ressemble donc le code avec un arbre explicite ?

mergeSort = detruireArbre . construireArbre 

data TreeF a b = Feuille [a] | Noeud b b
data Tree a = Fix (TreeF a)

-- Construction
construireArbre :: [a] -> Tree a
construireArbre = unfoldTree construireNoeud -- ici on suppose que unfoldTree existe bien

construireNoeud :: [a] -> TreeF a [a]
construireNoeud []  = Feuille []
construireNoeud [a] = Feuille [a]
construireNoeud l   = Noeud gauche droite
    where
        gauche,droite = halfSplit l


-- Destruction 

detruireArbre :: (Ord a) => Tree a -> [a]
detruireArbre = foldTree detruireNoeud

detruireNoeud :: (Ord a) => TreeF a [a] -> [a]
detruireNoeud (Feuille a) = a
detruireNoeud (Noeud a b) = mergeListes a b

Certaines fonctions ne sont pas codées (mergeListes et halfSplit) simplement parce que cela ne change rien à la structure du code.

Quels sont donc les différences avec un code récursif normal ?

La construction explicite de l'arbre coûte plus de mémoire
La modification et la lecture du code devient évidente

Bien entendu, comme c'est encore un cas évident, il n'y a pas de réel bénéfices : à priori, quand on code un tri fusion, on veut un tri fusion, et le code n'évoluera pas beaucoup. Malgré tout, on peut très facilement mélanger des tris avec cette construction, pour faire par exemple un tri par insertion quand il y a moins de N éléments, simplement en ajoutant un constructeur à l'arbre, et modifiant les mini-fonctions de construction/destruction en conséquence : l'allure générale du code ne varie pas. Mieux, ce sont seulement les petites fonctions (non récursives, pures, simples) qui auront plus de cas.

Un exemple plus concret s'est trouvé être la session de qualification au Google Hash Code 2016, le problème est le suivant :

Étant donné une carte avec des entrepôts (possédant des stocks de produits), une liste de commandes et une flottille de drones, comment optimiser un score qui est calculé en fonction du temps mis pour répondre aux commandes (les commandes remplies le plus tôt rapportent plus de points, indépendamment de leur poids/nombre de produits).

L'algorithme devait être un algorithme de type glouton, le problème étant à priori difficile.
La première solution qui vient à l'esprit, est une solution de type opérationnelle et qui décrit le comportement des drones. Par exemple :

Tant qu'il reste des commandes, pour chaque drone, trouver l'entrepôt le plus proche, trouver la commande avec un meilleur score relatif à cet entrepôt, faire le trajet, et déposer.

Quel est le problème ? Dans un premier temps, on remarque que cette méthode impose l'utilisation d'effets de bords dans l'intégralité des fonctions (ou alors d'utiliser des fonctions qui se passent l'état courant). Dans un deuxième temps, le débug d'un tel programme est très pénible : la solution la plus économe et efficace est de lancer le programme sur des petits fichiers, et faire une animation, afin de voir globalement ce qu'il se passe. Dans un dernier temps, il est assez fastidieux de faire des choix plus « en avant », par exemple en sélectionnant les k prochaines commandes …

L'alternative étant bien entendu de construire une structure de donnée intermédiaire pour représenter les choix du programme glouton. Naturellement on en vient a construire un arbre, et la solution est une branche de cet arbre (une suite de choix). Quels avantages ?

Seule la fonction qui trouve le chemin dans l'arbre a besoin d'un état, et encore. Toutes les autres fonctions seront pures et donc facilement testables de manière indépendantes.
Il est possible en utilisant des outils comme QuickCheck de vérifier certaines propriétés facilement sur du code pur
On peut effectivement afficher des (petits) arbres générés aléatoirement pour comprendre quels choix sont localement optimaux sur des petits exemples, en comparant l'algorithme glouton avec une recherche exhaustive.
On peut facilement modifier des parties indépendantes du code
1. La génération de l'arbre va décider
  - Des données accessibles dans les nœuds
  - De la manière dont sont organisés les fils (triés dans un certain ordre)
2. La destruction/Le parcours de l'arbre va décider
  - De la façon dont les données sont utilisées (prise ou non en compte)
  - De la manière dont les choix de branches sont optimisés (sur un,deux niveaux ? combien de fils sont effectivement explorés ? etc.)
Une utilisation un peu plus avancée est la suivante : si on travaille sur un set de données précis (ce qui est le cas dans le Hash Code), on peut calculer l'arbre et l'enregistrer dans un fichier, et faire du traitement itératif dessus, en supprimant des branches au fur et à mesure par exemple, ou détruisant des patterns répétitifs. Même si on ne fait pas ce type de traitement, cela permet de gagner du temps sur les tests du code de destruction, puisque l'arbre n'a pas à être recalculé (à nuancer, en haskell l'arbre n'est a priori pas calculé totalement avec l'évaluation paresseuse, et donc lire l'intégralité de l'arbre peut devenir moins performant…)

Ce qui est amusant c'est qu'au final, la quantité de code est assez similaire : il faut toujours mettre à jours les états, toujours gérer les drones, toujours parser l'entrée standard. Pourtant, il y a une grosse différence : dans le code impératif, on se concentre sur une solution pas à pas, et la généraliser pour faire des « grands pas » devient vite pénible. En rendant explicite la donnée, et en permettant de la traiter de manière arbitraire, on s'autorise beaucoup plus de choses, les algorithmes viennent plus naturellement, et sont plus facilement compréhensibles par d'autres êtres humains.

PS: certains dirons « où est donc le code ? », la réponse est la suivante : la version proposée était en python, avec pleins de variables globales, codée de manière horrible et donnait des solutions inefficaces. Je n'ai pas eu le courage de convertir complètement l'algorithme en haskell avec un arbre de décision effectif (ce qui rend ce journal un peu hypocrite).

PS': je n'ai pas eu le temps de pousser l'analogie très loin, mais la différence entre les deux approches semble être la différence entre une sémantique opérationnelle (à petits pas) et une sémantique dénotationnelle (cf Sémantique des langages de programmation)

# ouai

Posté par Guillaume Knispel le 29 mars 2016 à 01:05. Évalué à 8.

J'abonde totalement en ce qui concerne la testabilité infiniment supérieure des fonctions pures, qui apportent des bénéfices même si au final elles sont employées dans un programme impur.

Concernant le problème des drones, ne pourrait-on pas aussi le réduire, peut-être certes partiellement, à un énoncé classique d'optimisation sous contraintes ?
- [^] # Re: ouai
  
  Posté par barmic le 29 mars 2016 à 09:10. Évalué à 3.
  
  même si au final elles sont employées dans un programme impur
  
  Heureusement que le programme est impur ! Il faut bien que son résultat apparaisse quelque part :)
  
  J'abonde totalement en ce qui concerne la testabilité infiniment supérieure des fonctions pures[…]
  
  Je me fais de la pub pour un vieux journal (4 ans déjà), qui parle précisément de cette problématique (l'article de John Carmack n'est plus disponible, mais la traduction de developpez si) : Adopter un style de programmation fonctionnel.
  
  Depuis j'ai moi aussi fais mon bout de chemin et maintenant ce que j'aimerais c'est pouvoir faire plus de choses avec les types, mais les langages généralistes que je côtoient n'ont pas ce qu'il faut pour gérer ça.
  
  Concernant le problème des drones, ne pourrait-on pas aussi le réduire, peut-être certes partiellement, à un énoncé classique d'optimisation sous contraintes ?
  
  Tu parle de programmation linéaire ? Très certainement, mais c'est peu probable que ce soit le plus efficace (il trouve la solution la plus efficace, mais sa recherche ne l'est pas)
  
  Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
  - [^] # Re: ouai
    
    Posté par ckyl le 29 mars 2016 à 09:18. Évalué à 3.
    
    L'article n'est plus sur son blog mais est toujours dispo sur gamasutra: http://gamasutra.com/view/news/169296/Indepth_Functional_programming_in_C.php
    
    Si ma mémoire ne me trahie pas c'est bien le même.
  - [^] # Re: ouai
    
    Posté par Nicolas Boulay (site web personnel) le 29 mars 2016 à 09:58. Évalué à 3.
    
    Depuis j'ai moi aussi fais mon bout de chemin et maintenant ce que j'aimerais c'est pouvoir faire plus de choses avec les types, mais les langages généralistes que je côtoient n'ont pas ce qu'il faut pour gérer ça.
    
    Qu'est-ce que tu entends par là ? J'ai un peu réfléchit à un système de type plus complet, mais c'est en standby pour l'instant.
    
    "La première sécurité est la liberté"
    - [^] # Re: ouai
      
      Posté par barmic le 29 mars 2016 à 10:21. Évalué à 3.
      Comme je ne le pratique pas (encore) c'est balbutiant, mais pouvoir à minima faire des alias de types et éviter les casts entre le type racine et l'alias.
      
      L'exemple qui me vient à l'esprit : on te fourni une chaîne de caractère qui pourrait être un mot de passe, mais pour que ça en soit un, il faut passer par la fonction validPasswd() qui prend une chaîne de caractère et sort un password (qui est un type alias de chaînes caractères).
      
      Tu as 3 façons de faire ça :
      
      en orienté objet tu fait de l'encapsulation, ça peut être joli mais c'est assez lourd (si tu veux étendre cet usage un peu partout ça t'oblige à créer beaucoup de classe)
      
      en impératif à la Ada : tu peux faire des alias et tu peux en plus leur donner des contraintes (tu peux coder l'invariant sur tes mots de passe directement dans le type)
      
      en fonctionnel : c'est là que j'ai le plus de lacune, mais si je ne m'abuse tu va faire exactement ce que je décris plus haut. Tu crée un type et une fonction qui te sort le type en question
      
      Ça paraît pas forcément génial comme ça mais en poussant vraiment plus loin le truc, tu peux faire en sorte que tout ton algo consiste en une résolution du type. Par exemple tu as un tableau d'entier (ton type initial) et tu va créer un type tableau d'entier trié (ton type de sortie) et seul tes méthodes de tris sortent ce type précis.
      
      Pour pouvoir aller loin dans tout ça, tu as pleins d'outils très utiles :
      
      l'inférence de type
      
      les unions de type
      
      etc
      
      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
      - [^] # Re: ouai
        
        Posté par Moonz le 29 mars 2016 à 10:26. Évalué à 3.
        
        Par exemple tu as un tableau d'entier (ton type initial) et tu va créer un type tableau d'entier trié (ton type de sortie) et seul tes méthodes de tris sortent ce type précis.
        
        Pour ton exemple de tableau d’entier, tu peux ajouter une autre contrainte (orthogonale au tri), par exemple que les éléments doivent être uniques. Ou pairs. Ou compris entre 1 et 12 (mois). Comment tu composes ces contraintes (trié + pairs par exemple) si chaque contrainte donne naissance à un seul type ?
        
        [^] # Re: ouai
        
        Posté par Nicolas Boulay (site web personnel) le 29 mars 2016 à 10:35. Évalué à 3.
        
        J'ai la même question. Si tu as un type "trié + validé" issue d'une string, souvent tu va avoir besoin de fonction de base de string, parfois que pour "trié" ou que pour "validé", comment gères-tu ces cas ?
        
        "La première sécurité est la liberté"
        
        [^] # Re: ouai
        
        Posté par chimrod (site web personnel) le 30 mars 2016 à 21:42. Évalué à 3. Dernière modification le 30 mars 2016 à 21:44.
        
        J'imagine plutôt que le type trié + validé comme un type fantôme, c'est à dire que ta fonction de tri peut avoir la signature suivante :
        
        type 'a sorted val sort: string -> string sorted
        
        Le type indique juste que le texte est trié est validé, mais il est tout à fait possible d'en extraire la chaîne donnée :
        
        val extract: 'a sorted -> 'a
        
        par contre les fonctions qui nécessitent d'avoir en entrée un type trié + validé nécessitent juste de prendre un type « 'a sorted » en paramètre.
        
        C'est ce qui est utilisé dans la librairie js_of_ocaml : tous les types utilisé dans le code javascript sont de type Js.t, ce qui permet de séparer le type des données qui sont utilisées dans le code ocaml, et celles qui sont issues/destinée au code javascript.
        
        Edit: Bon, c'est ça d'arriver après la tempête, cela a expliqué plus bas…
        
        [^] # Re: ouai
        
        Posté par Nicolas Boulay (site web personnel) le 31 mars 2016 à 09:52. Évalué à 2.
        
        Je comprends les types fantômes, mais si tu extrais la string, pour l'utiliser avec des fonctions standard tu perds le tag qui t’empêches de faire des bêtises avec.
        
        "La première sécurité est la liberté"
        
        [^] # Re: ouai
        
        Posté par chimrod (site web personnel) le 31 mars 2016 à 09:59. Évalué à 2.
        
        Exact.
        
        Mais pour suivre le raisonnement jusqu'au bout, une fois que tu a utilisé les fonctions standards qui te renvoie une chaîne différente, tu n'as plus la garantie que la nouvelle chaîne est toujours valide.
        
        Autant que cette contrainte soit rendue explicite.
        
        [^] # Re: ouai
        
        Posté par kantien le 29 mars 2016 à 10:43. Évalué à 3.
        
        Comment tu composes ces contraintes (trié + pairs par exemple) si chaque contrainte donne naissance à un seul type ?
        
        En utilisant des variants polymoprhes pour faire de l'héritage multiple ?
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: ouai
        
        Posté par Nicolas Boulay (site web personnel) le 29 mars 2016 à 10:54. Évalué à 2.
        
        Tu veux faire un filtrage dans chaque fonction qui prendrait un de ces types en argument ?
        
        Mais comment faire pour utiliser une fonction standard ? Tu filtres avant ?
        
        "La première sécurité est la liberté"
        
        [^] # Re: ouai
        
        Posté par kantien le 29 mars 2016 à 10:57. Évalué à 1.
        
        Tu devrais lire l'article de Jacques Garrigue que j'ai donnée en lien, tu devrais y trouver les réponses à tes questions.
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: ouai
        
        Posté par Nicolas Boulay (site web personnel) le 29 mars 2016 à 11:14. Évalué à 3.
        
        Je connaissais un peu les variants polymorphes, et surtout le fait que Ocaml n'est pas capable de trouver tous les problèmes possibles à la compilation.
        
        Mais je n'ai pas compris grand chose aux papiers pour l'instant. Je ne vois pas comment tu évites de filtrer tout le temps.
        
        "La première sécurité est la liberté"
        
        [^] # Re: ouai
        
        Posté par barmic le 29 mars 2016 à 10:55. Évalué à 3.
        
        J'en ai pas la moindre idée (oui oui c'est balbutiant dans ma tête, je n'ai pas encore pratiqué ce genre de choses). Là comme ça je te dirais que c'est pas un besoin primordiale : l'objectif n'est pas d'avoir une bibliothèque de ce genre de sous-type que l'on utilise, mais plutôt de construire toi-même le type dont tu as besoin.
        
        C'est donc utile uniquement si tu as toi-même besoin de cette composition. Tu as besoin de tableau de paire, de tableau trié et de tableau de paire trié. Ça réduit l'usage de ce genre de composition à mon avis.
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
      - [^] # Re: ouai
        
        Posté par Michaël (site web personnel) le 29 mars 2016 à 10:43. Évalué à 4.
        
        Comme je ne le pratique pas (encore) c'est balbutiant, mais pouvoir à minima faire des alias de types et éviter les casts entre le type racine et l'alias.
        
        Avec cette approche, il y a deux candidats “naturels” dans le monde fonctionnel. Le premier est l'utilisation de monades pour représenter le mot de passe validé, un peu comme si en JavaScript la fonction de validation retournait une valeur de la forme: {result:"MY-PASSWORD"} ou bien {error:"MESSAGE"}. Avec OCaml, j'utiliserais par exemple la monade Maybe. Le second candidat est l'utilisation de types fantômes, auxquels on peut penser comme à une annotation pour le compilateur qui permet d'exposer certains attributs ou se souvenir des traitements subis par une valeur.
        
        Dans le cas particulier des mots de passe, je préférerais utiliser un type abstrait de donnée, qui permet de limiter les traitements sur les mots de passe, interdisant par exemple à ceux-ci d'être imprimés dans la sortie du programme (pas de conversion en type string) et sont effacés de la mémoire aussitôt que possible.
        
        [^] # Re: ouai
        
        Posté par barmic le 29 mars 2016 à 11:02. Évalué à 3.
        
        Le premier est l'utilisation de monades pour représenter le mot de passe validé, un peu comme si en JavaScript la fonction de validation retournait une valeur de la forme: {result:"MY-PASSWORD"} ou bien {error:"MESSAGE"}. Avec OCaml, j'utiliserais par exemple la monade Maybe.
        
        Hum… Il me semble que c'est équivalent au Option/Optional que l'on trouve un peu partout. Ça sert à représenter des erreurs potentiels (et ça se manipule avec du patern matching pour contraindre à gérer le cas d'erreur). Mais une fois le cas d'erreur passé, c'est une string toute simple non ?
        
        Le second candidat est l'utilisation de types fantômes, auxquels on peut penser comme à une annotation pour le compilateur qui permet d'exposer certains attributs ou se souvenir des traitements subis par une valeur.
        
        Je suis loin de comprendre, mais c'est une représentation de l'état courant en suivant tout le chemin de la donnée ça me semble un peu violent.
        
        Dans le cas particulier des mots de passe, je préférerais utiliser un type abstrait de donnée, qui permet de limiter les traitements sur les mots de passe, interdisant par exemple à ceux-ci d'être imprimés dans la sortie du programme (pas de conversion en type string) et sont effacés de la mémoire aussitôt que possible.
        
        Ça me semble représenter au mieux ce que je pense. En quoi est-ce que c'est un type abstrait ?
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
        
        [^] # Re: ouai
        
        Posté par Michaël (site web personnel) le 29 mars 2016 à 11:28. Évalué à 4.
        
        Hum… Il me semble que c'est équivalent au Option/Optional que l'on trouve un peu partout.
        
        Oui exactement, la monade ajoute des traitements et des opérateurs pour travailler facilement avec.
        
        Je suis loin de comprendre, mais c'est une représentation de l'état courant en suivant tout le chemin de la donnée ça me semble un peu violent.
        
        Voici un petit exemple en OCaml
        
        type validation_pending type validation_done type 'a password = string val password_input : unit -> validation_pending password (** Lit un mot de passe sur stdin. *) val password_validate : 'a password -> validation_done password (** Valide un mot de passe. Lève l'exception [Failure] si le mot de passe est rejeté. *) val password_store : validation_done password -> unit (** Sauvegarde le (hash du) mot de passe. *)
        
        Avec cette API, le mot de passe est une simple chaîne de caractères mais les types fantômes (qui n'ont pas de définition) validation_pending et validation_done permettent à la fonction password_validate de marquer sa sortie et à la fonction password_store de n'accepter que les valeurs passées par l'étape de validation.
        
        C'est différent d'un bit d'attribut car le type est un attribut du programme connu du compilateur, qui garantit que si un programme compile, alors la fonction password_store ne peut être appelée que sur un valeur de sortie de password_validate.
        
        Ça me semble représenter au mieux ce que je pense. En quoi est-ce que c'est un type abstrait ?
        
        Le type password est un type abstrait si on ne montre pas la définition du type password dans l'API. Cela permet de garantir que seules les fonctions de l'API permettent de manipuler la valeur. Ainsi, on peut s'assurer que le programme ne va jamais afficher de password en n'offrant aucune fonction qui permet de transformer le password en string ou un autre type affichable.
        
        [^] # Re: ouai
        
        Posté par barmic le 29 mars 2016 à 11:56. Évalué à 3.
        
        Oula il y a des subtilités que je suis loin de comprendre :)
        
        Je ne vois pas bien la différence entre un type fantôme et un type (mais te fatigue pas je pense qu'il faudrait que je manipule tout ça pour commencer à comprendre ^_^).
        
        Ok je comprends pour les types abstraits, c'est juste tellement la base en OO qu'on ne l'explicite pas.
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
        
        [^] # Re: ouai
        
        Posté par benja le 29 mars 2016 à 14:33. Évalué à 3. Dernière modification le 29 mars 2016 à 14:36.
        
        C'est ça ! C'est exactement la même "opacification" du type que l'on retrouve en POO classique avec ses "classes".
        
        Maintenant OCaml a aussi un système d'objet qui a un typage autrement plus complexe. Il vaut a lui seul le détour ;-) Par exemple, il n'y a pas de classe au sens POO du terme (=type) mais bien une correspondance par typage réel des méthodes avec évidemment une possibilité d'opacifier la représentation concrète si on veut.
        
        Donc bref une troisième solution serait d'utiliser les objets immédiats, qui nous affranchi du "problème" de pattern-matching de la solutions avec les types variants. Par exemple, avec des objets immédiats là on peut avoir un objet "validé" qui peut être utilisé à la plasse de l'objet non-validé sans devoir modifier le code utilisateur.
        
        let make_obj i = object val _v = i method get = i end;; (* val make_obj : 'a -> < get : 'a > = <fun> *) let make_validator f i = object(self) val _v = i#get method validate = if f _v then _v else failwith "invalid" method get = self#validate end;; (* val make_validator : ('a -> bool) -> < get : 'a; .. > -> < get : 'a; validate : 'a > = <fun> *) let use_string o = (o#get : string);; (* val use_string : < get : bytes; .. > -> bytes = <fun> *) let use_validable_string o = (o#validate:string);; (* val use_validable_string : < validate : bytes; .. > -> bytes = <fun> *) (* un validated_string peut être utilisé pour un string *) use_string (make_validator (fun _ -> true) (make_obj "password"));; (* - : bytes = "password" *)
        
        Note que j'utilise la méthode "validate" pour discriminer un objet validable, donc si j'oublie d'appeller validate je ne me rendrai pas compte que j'utilise le mauvais type… Note aussi que la solution reste polymorphique donc que tu peux construire n'importe quel type d'objet avec make_validator.
        
        Une autre solution c'est d'utilise les classes ocaml, qui ne sont pas encore tout à fait des classes au sens POO du terme mais qui permette de discriminer avec une contrainte de type (de nouveau, si on oublie cette annotation, ben ça ne sert à rien… le compilo ne peut pas se mettre à deviner ce que tu veux faire non plus :p). Je crois que c'est ce qui se rapproche le plus que ce que tu a demandé.
        
        class ['a] base i = object method get = (i:'a) end;; class ['a] validated f i = let _ = if not (f i) then failwith "invalid" in object inherit ['a] base i end;; let make_valid f o = new validated f o#get;; let use_valid_string (o : string #validated) = o#get;; let use_any_string o = print_endline o#get;; use_any_string (make_valid (fun _ -> false) (new base "god"));; (* Exception: Failure "invalid" *)
        
        Note que cela reste tout à fait polymorphique comme solution :)
        
        (Il y peut-être encore une solution possible avec les gadt pour émuler les types classes d'haskell mais cela dépasse mon niveau de compétence là…)
        
        [^] # Re: ouai
        
        Posté par benja le 29 mars 2016 à 14:44. Évalué à 1. Dernière modification le 29 mars 2016 à 14:48.
        
        s/plasse/place/ (désolé pour les yeux)
        s/que ce que tu a/de ce que tu as/;s/complexe/complèxe/;s/types classes/typeclass ou classes de type ?/;s/permette/permettent/;il y p/il y a p/
        
        [^] # Re: ouai
        
        Posté par benja le 29 mars 2016 à 14:53. Évalué à 2.
        
        Note que ces deux codes ont une sémantique différente, à savoir que le deuxième force la validation avant l'usage et le premier non. C'est juste pour l'illustration; tu peux évidemment implémenter le même comportement avec ces deux techniques…
        
        [^] # Re: ouai
        
        Posté par benja le 29 mars 2016 à 16:41. Évalué à 3. Dernière modification le 29 mars 2016 à 16:42.
        
        Mon exemple ne marche pas et ça tombe bien car cella montre bien que les classe ocaml ne sont pas comme des classes de poo. T'es bien obligé de changer la signature de validated (comme avec les objets immédiats) pour ne pas qu'il soit considéré comme un sous-type de base.
        
        (* c'est accepté par le compilo car le type validated est un sous type de base *) use_valid_string (new base "invalid") (*- : bytes = "invalid" *) (* on peut faire *) class ['a] validated f i = let _ = if not (f i) then failwith "invalid" in object inherit ['a] base i method valid = true end;; let use_valid_string (o : _ validated) = print_endline o#get;; use_valid_string (new base "invalid");; (*Error: This expression has type bytes base but an expression was expected of type bytes validated The first object type has no method valid *) (* ouf... *)
        
        On peut aussi combiner avec un phantom type pour un maximum de safety. Attention, si on retire la méthode repr, ça ne marche à nouveau plus.
        
        class ['a,'b] any repr i = object(self) (* on est obligé de rendre la representation publique ! *) method repr : 'b = repr i method get : 'a = i end;; type 'a valid (* notre type fantome *) class ['a, 'b] validated repr i = (* ici on force la validation, commenté car i'm lazy *) (* let _ = repr i in *) object constraint 'b = 'a valid inherit ['a, 'b] any repr i end (* on passe au constructeur une fonction qui "valide" en construisant le type fantome *) (* le but de cette fonction c'est d'avoir une version spécialisée du constructeur, via l'annotation de type sur repr. on peut s'en passser...*) let make_validated (repr : 'a -> 'a valid) obj = new validated repr obj#get let use_validated (o : _ validated) = o#get let use_any o = o#get let id x = x use_validated (new any id "invalid");; (* Error: This expression has type (bytes, bytes) any but an expression was expected of type (bytes, bytes valid) validated Types for method repr are incompatible *) use_validated (make_validated (fun _ -> failwith "i am lazy") (new any id "plain"));; (* - : bytes = "plain" *) (* et on peut toujours utiliser un string validated pour un string any *) use_any (make_validated (fun _ -> failwith "i am lazy") (new any id "plain"));; (* - : bytes = "plain" *)
        
        S'il y en a par ici qui ont une solution pour cacher repr ?
        
        [^] # Re: ouai
        
        Posté par benja le 29 mars 2016 à 17:14. Évalué à 2. Dernière modification le 29 mars 2016 à 17:16.
        
        Notons bien aussi le type de use_any.
        - : < get : 'a; .. > -> 'a = <fun>
        
        Cela ressemble à une fonction polymorphique, mais contrairement au polymorphisme classique, le mode objet d'ocaml ne "fixe" pas le type polymorphique une foit qu'elle est utilisée. Comparons
        
        let use_length length = let _ = length [1] in let _ = length ["a"] in ();; Error: This expression has type bytes but an expression was expected of type int
        
        avec
        
        class ['a] mylist l = object method length = List.length l end let use_length' length = let a = length (new mylist [1]) in let b = length (new mylist ["a"]) in a+b;; (* val use_length' : ('a mylist -> int) -> int = <fun> *)
        
        [^] # Re: ouai
        
        Posté par benja le 29 mars 2016 à 17:32. Évalué à 2. Dernière modification le 29 mars 2016 à 17:35.
        
        Par "fixer le type polymorphique", j'entends bien le type de l'objet (polymorphique), soit le 'a dans <get : 'a; ...>. La deuxième partie de la fonction -> 'a sera bel et bien fixé à un moment donné (et dans ce cas-ci le (sur)type de l'objet aussi par l'égalité 'a = 'a… mais bon, cf. l'exemple avec mylist, c'est possible).
        
        use_length' (fun o -> o#length);; - : int = 2
        
        [^] # Re: ouai
        
        Posté par Michaël (site web personnel) le 29 mars 2016 à 17:59. Évalué à 4.
        
        (Il y peut-être encore une solution possible avec les gadt pour émuler les types classes d'haskell mais cela dépasse mon niveau de compétence là…)
        
        En fait il suffit d'attendre bien sagement la sortie de OCaml 4.04 – ou bien utiliser la branche expérimentale du compilateur. Voir à ce sujet la dépêche sur 4.0.3 (encore dans les tuyaux).
        
        [^] # Re: ouai
        
        Posté par Michaël (site web personnel) le 29 mars 2016 à 17:55. Évalué à 6.
        
        Je ne vois pas bien la différence entre un type fantôme et un type (mais te fatigue pas je pense qu'il faudrait que je manipule tout ça pour commencer à comprendre ^{_^).}
        
        En réalité il y a un type fantôme avec lequel tu es déjà familier, c'est le void en C. On ne peut pas créer de valeurs de de type void par contre on peut créer des types dérivés, comme pointer to void – que je n'écris pas avec une petit étoile à cause du markdown.
        
        Un type fantôme est juste un type qui est déclaré mais pas défini, comme dans
        
        type my_first_fantom_type
        
        On ne peut pas créer de valeurs de type my_first_fantom_type par contre on peut s'en servir pour paramétrer d'autres types. L'équivalent en C++ serait d'utiliser des templates et leurs spécialisation. J'essaie de traduire mon example OCaml en déclarations C++, mais mon C++ n'est plus tout frais:
        
        struct validation_pending {}; struct validation_done {}; template<struct T> struct password { typedef string type; }; password<validation_pending>::type password_input(); password<validation_done>::type password_validate(const password<validation_pending>::type&); void password_store(const password<validation_done>::type&);
        
        Le paramètre de template, qui correspond au paramètre de type dans le cas de OCaml, sert uniquement à “documenter” l'API aux yeux du compilateur – mais je ne connais malheureusement aucune astuce en C++ pour rendre les types password<validation_pending>::type
        et password<validation_done>::type incompatibles entre eux, donc la correspondance est imparfaite.
        
        [^] # Re: ouai
        
        Posté par barmic le 30 mars 2016 à 09:38. Évalué à 3.
        
        On ne peut pas créer de valeurs de type my_first_fantom_type par contre on peut s'en servir pour paramétrer d'autres types.
        
        Est-ce qu'il peut exister tout de même des instances ?
        
        Ça correspond à une classe dont tous les constructeurs seraient privés. Mais tu peux tout de même avoir du contenu.
        
        Là ce que tu représente en C++, c'est un type qui ne sert qu'à annoter. Je comprends mieux. Merci :)
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
        
        [^] # Re: ouai
        
        Posté par Michaël (site web personnel) le 30 mars 2016 à 10:34. Évalué à 4.
        
        Est-ce qu'il peut exister tout de même des instances ?
        Ça correspond à une classe dont tous les constructeurs seraient privés. Mais tu peux tout de même avoir du contenu.
        
        Lorsqu'un type n'a pas de définition on est en pratique face à l'un des deux cas suivants:
        
        le cas des types abstrait de donnée: il existe une définition du type mais elle est cachée, on ne peut pas créer de valeurs du type à partir d'une valeur “immédiate” ou explicite, mais on peut créer des valeurs en utilisant les fonctions de l'API. Cela correspond, il me semble, à une classe C++ dont le constructeur synthétique (celui fourni par le compilateur) serait privé mais dont des fonctions membre statiques permettent autorisent la création de valeurs.
        
        le cas des types fantômes: il n'existe nulle-part de définition du type, dans ce cas il est absolument impossible de créer des valeurs!
        
        [^] # Re: ouai
        
        Posté par GTof le 31 mars 2016 à 09:19. Évalué à 2.
        
        Excellent article!! :)
        
        En réalité il y a un type fantôme avec lequel tu es déjà familier, c'est le void en C. On ne peut pas créer de valeurs de de type void par contre on peut créer des types dérivés, comme pointer to void
        
        Non. Ce que tu décris ici est un type qui n'est pas habité. Un type phantome c'est tout autre chose. Un type phantome est un paramètre qui est présent dans le type mais n'intervient pas dans sa définition. Par exemple:
        type 'a t = T of intLe paramètre 'a est ici un type phantome. Ce qui veut dire que les deux valeurs suivantes sont de type différents.
        let x : string T = T 5 let y : bool T = T 5En revanche une expression
        type TReprésente soit un type non habité (pas de valeur de ce type) si elle intervient dans une définition. Soit un type abtrait quand elle intervient dans une signature.
        
        [^] # Re: ouai
        
        Posté par Nicolas Boulay (site web personnel) le 31 mars 2016 à 09:55. Évalué à 2.
        
        Tu voulais dire :
        
        let x : string t = T 5
        
        let y : bool t = T 5
        
        non ? (petit 't' de 'type 'a t = T of int')
        
        "La première sécurité est la liberté"
        
        [^] # Re: ouai
        
        Posté par Michaël (site web personnel) le 31 mars 2016 à 10:29. Évalué à 2.
        
        Non. Ce que tu décris ici est un type qui n'est pas habité. Un type phantome c'est tout autre chose. Un type phantome est un paramètre qui est présent dans le type mais n'intervient pas dans sa définition. Par exemple:
        
        Ah oui, je me suis un peu emmêlé les pinceaux en confondant le paramètre avec les valeurs qu'il prend – qui sont en pratique des types qui n'ont pas de définition.
        
        [^] # Re: ouai
        
        Posté par Ontologia (site web personnel) le 30 mars 2016 à 11:27. Évalué à 5.
        
        Je ne vois pas bien la différence entre un type fantôme et un type (mais te fatigue pas je pense qu'il faudrait que je manipule tout ça pour commencer à comprendre ^{_^).}
        
        Je te propose un exemple simple (celui avec lequel j'avais compris le concept).
        
        Imagine que tu ais deux tables :
        
        create table T1(idt1 text, lbl1 text); create table T2(idt2 text, lbl2 text);
        
        Tu veux faire un mapping sur ces deux tables, avec chacune une structure
        
        type t1 = { idt1 : string; lbl1 : string; } type t2 = { idt2 : string; lbl2 : string; }
        
        Le genre de problème qui m'est arrivé, c'est quand tu vas chercher une ligne de ta table, avec un select, tes données pour hydrater ta structure : tu est fatigué, tu fais pas attention et tu intervertis idt1 et lbl1.
        Erreur d'étourderie classique qui arrive à tout le monde.
        Comme c'est deux chaînes, tu te retrouves avec un bug 4 kilomètres plus loin, et tu cherches longtemps avant de trouver.
        <troll>Et là, tu te retrouves au moyen-âge, comme quand tu faisais du java</troll>
        
        La solution, c'est d'utiliser un phantom type :
        
        Si tout était simple, on pourrait faire ça, car c'est l'idée
        
        type id type lbl type 'a champBase = string
        
        Mais le compilateur reconnait que les id champBase et lbl champBase, c'est la même chose
        Donc, on le force :
        
        module T : sig (*on défini nos types spécialisés*) type id type lbl (*on devra passer par ces fonctions pour créer les chaines typées. *) val makeid : string -> id val makelbl : string -> lbl val fromid : id -> string val fromlbl : lbl -> string end = struct (*Nous sommes dans l'implémentation du module, on défini que nos types particuliers sont des chaînes*) type id = string type lbl = string (*la définition de type dans la signature nous garantie que l'on renvoi bien un type T, alors que l'implémentation est une bête fonction identité*) let makeid s = s let makelbl s = s let fromid s = s let fromlbl s = s end;;
        
        Du coup tu définis tes deux types avec
        
        type t1 = { idt1 : T.id ; lbl1 : T.lbl; } type t2 = { idt2 : T.id ; lbl2 : T.lbl; }
        
        Tu peux définir ta structure en utilisant les phantom-type
        
        { idt1 = T.makeid "456s" ; lbl1 = T.makelbl "456" };;
        
        Et voilà, tu es forcé par le compilateur de ne pas te tromper.
        C'est un peu chiant et lourd, mais ça évite plain de problèmes, car chaque chaîne est à sa place
        
        « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
        
        [^] # Re: ouai
        
        Posté par kantien le 29 mars 2016 à 11:28. Évalué à 3.
        
        En quoi est-ce que c'est un type abstrait ?
        
        Un type abstrait est un type encapsulé dans un module dont on cache la représentation concrète à l'utilisateur. Ainsi, il ne peut manipuler les données de ce types que via les fonctions exportées par le module, ce qui permet de garantir des invariants sur la structure de données (à condition que les fonctions la manipulant soient bien codées, cela va de soi ;-)
        
        En OCaml ça peut donner cela, avec un fichier d'interface password.mli
        
        type t val create_pwd : string -> t
        
        et dans le fichier qui implémente l'interface password.ml tu as
        
        type t = string (* le type t est un alias du type string mais l'utilisateur ne le sait pas *) let create_pwd s = (* mon über code générant des mots de passe *)
        
        et l'utilisateur ne pourra jamais manipuler les mots de passe comme des string.
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: ouai
        
        Posté par ckyl le 29 mars 2016 à 20:48. Évalué à 3.
        
        Il me semble que c'est équivalent au Option/Optional que l'on trouve un peu partout.
        
        Non. Option/Optional peut aussi être vu comme une monade mais son but est de représenter la présence ou l'absence de quelque chose. Pas quelque chose ou une erreur. Dans ce cas ça serait plutôt Either.
        
        Si tu veux une très bonne introduction aux principes sans la tartine de pedantrie fonctionnelle (quoi tu sais même pas ce qu'est un groupe abélien ?!?) tu as "Introduction to railway oriented programming". Tu n'as besoin d'aucune connaissance fonctionnelle et c'est très pratique et applicable dans plein de langages (même si les langages fonctionnels sont très adaptés à ça). Tu as une version article et une version conférence.
        
        http://fsharpforfunandprofit.com/rop/
        http://fsharpforfunandprofit.com/posts/recipe-part2/
        
        Après si tu veux aller plus loin tu peux regarder Either en Scala ou Haskell et creuser les concepts.
        
        Et tu peux regarder aussi quelque chose comme https://github.com/kittinunf/Result qui implémente le truc dans un langage OO (Kotlin)
        
        [^] # Re: ouai
        
        Posté par barmic le 30 mars 2016 à 09:13. Évalué à 2.
        
        Merci je vais potasser tout ça :)
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
        
        [^] # Re: ouai
        
        Posté par Guillaume Denry (site web personnel) le 30 mars 2016 à 12:01. Évalué à 2.
        
        Et comme j'ai cru comprendre que tu t'étais mis à Elm, tu as le type Result qui devrait aussi répondre à cette problématique.
        
        [^] # Re: ouai
        
        Posté par kantien le 30 mars 2016 à 12:24. Évalué à 1. Dernière modification le 30 mars 2016 à 12:25.
        
        De ce que j'ai compris du type Either en Haskell, il est identique au type Result en Elm.
        
        En Haskell la définition est :
        
        date Either a b = Left a | Right b
        
        en Elm, selon ton lien c'est :
        
        type Result error value = Ok value | Err error
        
        et en OCaml, son équivalent est :
        
        type ('a,'b) result = Ok of 'a | Error of 'b
        
        Et à l'usage, on les emploie pareil : soit le calcul s'est bien passé est on renvoie du Ok (ou Right en Haskell), soit il y a eu une erreur et on la propage via Err, Error ou Left.
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: ouai
        
        Posté par barmic le 30 mars 2016 à 14:25. Évalué à 2.
        
        C'est flatteur, mais je ne suis pas Bruno Michel ;)
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
        
        [^] # Re: ouai
        
        Posté par Guillaume Denry (site web personnel) le 30 mars 2016 à 14:29. Évalué à 2.
        
        J'étais sûr que je ferai cette erreur un jour.
        Toutes mes excuses :)
        
        [^] # Re: ouai
        
        Posté par barmic le 30 mars 2016 à 15:12. Évalué à 2.
        
        Moi ça ne me dérange pas (tu n'es pas le premier à faire l'erreur).
        
        Je me renomme pour l'occasion :)
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
# Niklas Wirth: Data Structures + Algorithms = Programs

Posté par Michaël (site web personnel) le 29 mars 2016 à 10:25. Évalué à 3.

C'est amusant, j'ai écrit sur le même sujet en présentant Lemonade Sqlite. Bien-sûr l'angle est différent puisque je me concentre sur la présentation de Lemonade Sqlite, mais ce paragraphe devrait te plaire:

Almost every programmer has already seen the equation popularised by Niklas Wirth, but is has an aspect whose subtlety that is less well-known: the frontier between data structures and algorithms is very fluid, when it comes to decide how should the different aspects of our program be represented.

Soit en français

Presque tout programmeur a déjà vu l'équation popularisée par Niklas Wirth mais elle a un aspect dont la subtilité est moins bien connue: la frontière entre les structures de données et les algorithmes est très fluide lorsqu'il s'agit de décider comment représenter les divers aspects de nos programmes.

J'ai demandé sur Programmers SE si NIklas Wirth voulait lui-même transmettre cette idée dans son livre (KEJNÉPALU™), il semblerait que ce soit le cas.
# Map-Reduce

Posté par barmic le 29 mars 2016 à 14:33. Évalué à 2.

Finalement ce que tu présente est une généralisation du Map-Reduce, non ?

Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
- [^] # Re: Map-Reduce
  
  Posté par Axioplase ıɥs∀ (site web personnel) le 29 mars 2016 à 17:18. Évalué à 3.
  
  Non. Le map reduce applique une fonction F à tous les éléments d'une collection de données via map, et ensuite consolide les résultats ("reduce").
  Le principe ici est de générer ta collection de données à la volée, pour pouvoir la consolider immédiatement. Donc tu n'as jamais toute la collection en mémoire.
  
  Omettant le fait qu'on puisse écrire ''wc -c monFichier'', c'est la différence entre
  LIGNES=`cat file`; echo $LIGNES | wc -c
  qui lit le fichier en entier avant de compter les caractères, et
  cat file | wc -c
  qui ne garde qu'une ligne en mémoire à la fois.
  - [^] # Re: Map-Reduce
    
    Posté par Michaël (site web personnel) le 29 mars 2016 à 17:38. Évalué à 0.
    C'est la différence entre
```
LIGNES=$(cat file)
printf '%s' "${LIGNES}" | wc - c
```
    et
```
wc -c < file
```
    (Si je peux me permettre.)
    - [^] # Re: Map-Reduce
      
      Posté par Axioplase ıɥs∀ (site web personnel) le 29 mars 2016 à 18:16. Évalué à 4.
      
      Le but n'est pas de faire du shell correct, mais une analogie dans un langage qu'il connait.
      L'utilisation de ''cat'' dans le deuxième exemple est volontaire, car c'est la fonction qui génère les données (l'anamorphisme, aka unfold)… Sinon, l'analogie de composition d'un producteur et d'un consommateur est perdue.
  - [^] # Re: Map-Reduce
    
    Posté par barmic le 30 mars 2016 à 09:13. Évalué à 2.
    Je ne comprends pas¹. Le map va charger en mémoire tes données puis les rendre accessible à la réduction. Il les transforme d'une source (SQL, HFS, cassandra,…) à une chose sur la quelle on peut itérer. Oui c'est limité à quelque chose que l'on peut itérer et non un graphe ou un arbre et c'est pour ça que je parle d'un cas particulier.
    en fait je ne vois même pas ce que tu veux présenter entre les 2 cas. C'est le fait que le chargement soit paresseux ? Parce que tu as précisément la même structure de données d'un coté et de l'autre. Si les étapes 1 et 2 présentées plus haut ne sont pas séquentiels ce n'est plus la même chose ? Si c'est le cas c'est dommage. Le concept perds beaucoup de son intérêt. Je ne connais pas la volumétrie des données proposées par Google, mais sur des problème où tu as un peu de données et où la combinatoire explose rapidement (c'est facile à trouver comme problème) ça ne marche pas. ↩
    Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
    - [^] # Re: Map-Reduce
      
      Posté par Aluminium95 le 30 mars 2016 à 10:08. Évalué à 3.
      En fait, il y a deux choses à distinguer
      
      Le fait de construire une structure intermédiaire (qui serait sinon implicite dans le code)
      
      Le fait de construire/détruire cette structure « à la même vitesse » (ce qui n'est possible que dans certains cas) et qui permet de ne jamais à avoir l’intégralité de la structure en mémoire
      
      Ce qui est illustré avec cat est le deuxième point (selon moi).
      
      Le map va charger en mémoire tes données puis les rendre accessible à la réduction
      
      C'est bien la différence : ce qui est illustré est le fait de construire une donnée qui n'était pas explicitement construite avant. Dans les premiers exemples du journal, cela consiste simplement à construire l'arbre d'appel réellement, puis de le parcourir, le dernier consiste à construire l'arbre de décisions que l'algorithme allait parcourir de manière physique, plutôt que de continuer à raisonner sur des décisions locales.
      
      De plus, dans ta définition, le map est « inutile » : on peut quasi-systématiquement écrire map en fonction de reduce
      
      map (f,coll) = reduce (lambda x,y: insertColl(x,f(y)), emptyColl, coll)
      
      Mieux encore, en utilisant quelques équations algébriques sur les compositions de reduce, le map-reduce peut se ré-écrire sans map :
      
      reduce (action, init, map (fonction, collection)) = reduce (lambda x,y: action (x, fonction(y)), init, collection)
      
      à une chose sur la quelle on peut itérer
      
      C'est déjà assez puissant : une grande partie des données sont définies de manière inductive dans les langages fonctionnels, et donc un reduce vient automatiquement. Par exemple, il existe une manière de représenter les graphes de manière inductive (ce qui vient avec un certain cout toutefois).
      - [^] # Re: Map-Reduce
        
        Posté par barmic le 30 mars 2016 à 10:31. Évalué à 3.
        
        J'ai relus pas mal de fois pour comprendre.
        
        Et je pense avoir compris les 2 seule différences :
        
        le map n'agit que localement (c'est tout son intérêt dans le concept du map-reduce), il ne peut faire de calcul sur l'ensemble des données et en principe ne devrait pas faire de calcul sur un sous-ensemble
        
        la structure de sortie est uniquement itérable on ne peux la parcourir qu'une fois sans jamais revenir en arrière
        
        Je vois ça comme 2 limitations plus que des approches différentes, c'est pour ça que j'en parle comme d'un cas particulier, mais je présume que l'on s'est compris.
        
        De plus, dans ta définition, le map est « inutile »
        
        Alors quand je parle du map-reduce. Je parle du papier de google pas des fonctions que tu retrouve dans les concepts fonctionnels. C'est proche, mais non dans le cas du papier de google tu ne peux pas te passer du map. Cette opération est faite pour être distribuée et exécutés sur localement à tes données, alors que le reduce est là pour agréger tes données.
        
        Par exemple, il existe une manière de représenter les graphes de manière inductive (ce qui vient avec un certain cout toutefois).
        
        Je vois pas comment c'est possible :
        
        soit tu pré-calcule le parcourt dont tu as besoin, mais ce n'est plus un graphe. C'est une projection de ton graphe.
        
        soit tu encode toutes les possibilités, tu te retrouve à faire un nombre de parcourt hallucinant (tu ne peux pas sauter là où tu veux, il ne s'agit pas d'un vecteur) et ça n'a aucun intérêt pratique
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
        
        [^] # Re: Map-Reduce
        
        Posté par kantien le 30 mars 2016 à 11:10. Évalué à 2.
        
        Je vois pas comment c'est possible :
        
        Signature minimale d'un graphe et exemples d'implémentation en OCaml
        
        type graph type vertex val iter_vertex : (vertex -> unit) -> graph -> unit (** Parcourt les sommets du graphe en appliquant la fonction passée en argument à chacun d'eux *) val iter_succ : (vertex -> unit) -> graph -> succ -> unit (** Comme l'autre mais se limite aux successeurs d'un sommet donné *)
        
        Quelques algorithme classiques sur les graphes : comme le parcours en largeur, le parcours en profondeur, le plus court chemin…
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: Map-Reduce
        
        Posté par barmic le 30 mars 2016 à 11:18. Évalué à 2.
        
        Caml, Haskell, Lisp,… sont bein trop abscons pour moi… :)
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
        
        [^] # Re: Map-Reduce
        
        Posté par Aluminium95 le 31 mars 2016 à 16:44. Évalué à 3.
        
        Je vois pas comment c'est possible :
        
        Voici une explication possible.
        Petit résumé rapide, un graphe c'est soit :
        
        Un graphe vide
        
        Un nœud v et les arêtes de v vers un graphe
        
        Cette définition est bien inductive et représentable avec des types récursifs. Elle possède certains avantages : on peut faire des inductions structurelles dessus. Par exemple, faire un parcours en largeur/profondeur ne nécessite plus de marquer des nœuds. Extraire des sous-graphes est naturel, on peut insérer des nœuds en O(1). Après, il est vrai que le parcours sans destruction est assez peu efficace … Avec un peu d'effort on peut la rendre moins inefficace qu'elle n'en a l'air.
        
        [^] # Re: Map-Reduce
        
        Posté par barmic le 31 mars 2016 à 17:48. Évalué à 3.
        
        Petit résumé rapide, un graphe c'est soit :
        
        Un graphe vide
        
        Un nœud v et les arêtes de v vers un graphe
        
        C'est inductif, mais ça n'est pas linéaire. Tu construit le graphe comme on construit un arbre. Cette définition n'est pas suffisante pour manipuler un graphe avec un itérateur, c'est-à-dire, quelque chose sur le quel tu n'a que la méthode :
        
        next() : foo : qui te renvoie l'instance de foo suivante ou vide/null/nil/either sinon
        
        Tu peux construire ton graphe comme une suite de nœuds (qui contiennent alors l'information des arrêtes) ou comme une suite d'arêtes, mais ça n'est intéressant que pour des cas assez particulier (par exemple pour serialiser ton graphe sur disque).
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
        
        [^] # Re: Map-Reduce
        
        Posté par chimrod (site web personnel) le 31 mars 2016 à 18:59. Évalué à 4.
        
        Reprenons ce que fait l'itérateur d'un point de vue fonctionnel.
        
        Tu seras d'accord pour dire qu'il s'agit d'accéder élément par élément à une structure pour y appliquer un traitement. On peut le reformuler en disant qu'il s'agit d'appliquer un traitement sur l'ensemble des éléments de manière successive.
        
        Dans ce cas, il n'est pas nécessaire d'avoir une fonction next qui serait typée ainsi :
        
        val next: 'a t -> unit -> 'a (* Récupère l'élément suivant, on suppose que la structure garde en mémoire ce qui a déjà été parcouru *)
        
        mais plutôt:
        
        val iter: ('a -> unit) -> 'a -> unit (* [iter f tree] applique f a chaque élément du graphe (on suppose que l'on s'intéresse aux effets de bord)*) val fold: ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a (* unifie le graphe sur une valeur unique de type 'a *)
        
        Cela ne limite pas du tout le traitement de la structure, c'est même au contraire une manière commune de traiter les données.
        
        [^] # Re: Map-Reduce
        
        Posté par Aluminium95 le 31 mars 2016 à 19:57. Évalué à 2.
        
        En lisant un peu la page que tu cites sur les itérateurs on trouve :
        
        An external iterator may be thought of as a type of pointer that has two primary operations: referencing one particular element in the object collection (called element access), and modifying itself so it points to the next element (called element traversal).
        
        Ici, vu la structure, ce qu'il faut c'est « tout simplement », pouvoir ré-ordonner les nœuds dans la construction qui est faite. C'est d'ailleurs l'une des premières choses qui sont abordées dans l'article. Un algorithme naïf permet de le faire facilement. On veut le noeud v en haut du graphe (pour avoir accès à son sommet, et ses arêtes) :
        
        Si le graphe est vide, on plante
        
        Si le nœud visible est v alors c'est fini
        
        Sinon, on a un sous graphe et un nœud w. On met le nœud v en haut du sous-graphe avec un appel récursif. Ensuite, on construit le graphe Graphe (v, arv, Graphe (w, arw, sous-sous-graphe)) en faisant attention à ce que les arv et arw respectent les contraintes de la structure (ie: ce sont les arêtes entre le nœud et le sous graphe, qui ne peuvent pas faire référence à des nœuds qui sont définis plus haut).
        
        C'est inductif, mais ça n'est pas linéaire.
        
        Je pense que pour un type algébrique, une définition récursive donne toujours un moyen de parcours linéaire (sur une structure finie). En tout cas le cas du graphe tel que proposé marche bien :
        
        Si c'est un graphe vide c'est fini
        
        Si c'est un graphe non vide alors c'est un tuple (sommet, aretes_du_sommet, sous-graphe). Il suffit donc d'afficher le sommet, puis de continuer sur le sous graphe (qui n'a plus ce sommet).
        
        La bonne propriété c'est que chaque nœud et chaque arête est vue une seule et unique fois.
        
        Tu construit le graphe comme on construit un arbre.
        
        En fait, c'est l'objectif du papier cité : avoir toute l'expressivité des graphes, avec la simplicité du traitement des arbres, sans trop perdre en performances.
        
        [^] # Re: Map-Reduce
        
        Posté par kantien le 31 mars 2016 à 21:17. Évalué à 3. Dernière modification le 31 mars 2016 à 21:21.
        
        Si j'ai bien compris l'idée, elle est assez proche de celle que j'avais présentée pour implémenter des tableaux persistants (avec explication ici pour le principe de fonctionnement de la structure). Dans le cas des tableaux persistants (qui est un graphe de commit sur la structure) la fonction reroot est l'équivalent de sa fonction match pour effectuer ce qu'il appelle active patterns. Avec la différence qu'il implémente tout cela avec du fonctionnel pur, là où l'autre structure utilise des effets de bords. C'est bien cela ? Tout graphe peut être représenté de multiple façons dans la structure, mais on définit une relation d'équivalence (deux structures sont équivalentes si elles représentent le même graphe) et dans chaque classe d'équivalence on prend une structure qui a le nœud désiré comme dernier ajout (une sorte de forme canonique relativement au nœud sur lequel on souhaite travailler) ?
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: Map-Reduce
        
        Posté par Aluminium95 le 01 avril 2016 à 09:50. Évalué à 2.
        
        En effet, je n'avais pas vu ton commentaire sur cette structure, c'est intéressant. En regardant en diagonale, j'ai l'impression que ce qui est fait est :
        
        Un tableau est un triplet (modification avant, tableau, modifications après), où modification avant est une liste, et modifications après est une liste (de modifications).
        
        Pour récupérer la version i du tableau, il faut effectuer les modifications sur le vrai tableau, et le faire bouger dans la liste en mettant à la place la modification nécessaire pour revenir (vers la gauche ou la droite). En gros, on se demande si la version est à gauche où à droite (en fonction de i), et si elle est à droite, on pop le premier élément de droite, on l'applique au tableau du milieu, et on push l'inverse de la transformation appliquée à gauche (jusqu'à ce que l'on soit sur le tableau désiré).
        
        On se rend compte après coup que cette liste est inutile, et on gère tout avec des pointeurs et des références (qui seront bien gérées par le GC d'ocaml).
        
        Vu sous cet angle c'est assez proche du graphe oui.
        Plus précisément, pour le graphe, l'idée vient très certainement de la notion de Zipper, et avec un peu de travail, je pense qu'on peut relier le tableau persistant que tu as présenté à un zipper sur un type bien choisi.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.