Discussion :

[SpiceGuid]

Je suis allé faire un tour du côté de OCaml batteries included, j'ai cliqué sur le premier lien de l'API à savoir data structures, et je dois dire que j'ai été un peu déçu.
En gros y sont repris les modules standards auxquels ont été ajoutés quelques timides fonctions supplémentaires.
J'attendais quelque chose de plus ambitieux.
Il est fait mention d'une possible intégration d'OCaml-Reins ce qui est déjà plus intéressant.

En attendant je vous propose de commenter mes partis-pris en matières de structures de données.
D'abord je ne veux pas avoir à choisir entre style fonctionnel et impératif.
Selon moi, la meilleure conception (pour OCaml) c'est un TAD impératif avec la possibilité de l'utiliser de façon persistante.

Pour un type conteneur associatif ça donnerait ceci :

Code OCaml :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  module type Map =
  sig
    type 'a t
    type key
    (* imperative *)
    val empty:   unit -> 'a t
    val put:     key -> 'a -> 'a t -> unit
    val find:    key -> 'a t -> 'a  
    val remove:  key -> 'a t -> unit
    val copy:    'a t -> 'a t
    (* functional *)
    val singleton: key -> 'a -> 'a t
    val count:   'a t -> int 
    val has:     key -> 'a t -> bool
    val add:     key -> 'a -> 'a t -> 'a t
    val lookup:  key -> 'a t -> 'a option
    val delete:  key -> 'a t -> 'a t
    (* iterators *)
    val fold:    (key -> 'a -> 'b -> 'b) -> 'b -> 'a t -> 'b
    val map:     (key -> 'a -> 'b) -> 'a t -> 'b t
    val iter:    (key -> 'a -> unit) -> 'a t -> unit
    val filter:  (key -> 'a -> bool) -> (key -> 'a -> 'b -> 'b) -> 'b -> 'a t -> 'b
  end

Où add/lookup/delete font en style fonctionnel ce que put/find/remove font en style impératif.
Evidemment ça n'est pas idéal (si on veut du fonctionnellement pur) mais ça me paraît un bon compromis.

Ensuite, en plus de ces fonctions élémentaires, il y a les fonctions binaires faisant intervenir deux structures de données.
Il y a deux façons de coder les fonctions binaires :

1. directement dans l'implémentation (comme c'est fait dans Set.Make), l'avantage c'est qu'on peut utiliser la représentation pour réaliser une implantation efficace
2. de façon externe à l'aide des itérateurs, l'avantage c'est la généralité, on peut coder l'opération indépendamment de toute représentation

Malheureusement OCaml batteries included ne fournit pas ces opérations binaires pour d'autres TAD que Set.Make.
À mon avis une bonne bibliothèque devrait toujours fournir ces opérations binaires, à la fois de façon externe et de façon interne (quand c'est plus efficace).
Comme la façon interne est dépendante de l'implantation je vais m'attacher à expliquer comment coder ces fonctions de façon externe afin que tout le monde voit de quoi je parle.

Le problème avec les fonctions binaires comme l'intersection c'est qu'on peut vouloir des choses différentes :

• on peut vouloir l'intersection sous la forme d'un nouvel ensemble
• on peut vouloir l'intersection sous la forme d'une liste
• on peut vouloir itérer (map/filter/exists) sur cette intersection
• on peut vouloir un traitement spécial de l'intersection (voir billet blog)

La bonne solution pour faire toutes ces choses de façon flexible c'est le pliage.
Il ne faut pas renvoyer la partie souhaitée, le risque serait trop grand que le TAD renvoyé soit un gaspillage de mémoire (ou bien qu'il ne soit que traversé ou bien qu'il nécessite une conversion vers un autre TAD).
Ce qu'il faut renvoyer c'est un pliage sur la partie souhaitée.

Par exemple, dans le type de module Map, pour tout prédicat p, filter p renvoie un pliage sur la partie du conteneur qui vérifie ce prédicat. De cette façon on ne préjuge pas de l'usage qui sera fait de cette partie.

Le 'foncteur' ci-dessous généralise cette idée à toute paire de conteneurs associatifs (même d'implantation différente) :

• intersection itère sur A ⋂ B
• union itère sur A ⋃ B
• product itère sur A × B
• filter itère sur la partie de A × B qui vérifie prop
• cons1 et cons2 sont les valeurs pour le paramètre f dans le cas où l'on veut le résultat sous forme de liste
• put1 et put2 sont les valeurs pour le paramètre f dans le cas où l'on veut le résultat sous forme d'un conteneur associatif

Code OCaml :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
  module Mixed (A: Map) (B: Map with type key = A.key) =
  struct
    let cons1 key a l =
      (key,a)::l
    let cons2 key a b l =
      (key,a,b)::l
    let put1 =
      A.put
    let put2 key a b =
      A.put key a
    let intersection f init ta tb =
      if A.count ta < B.count tb then
        A.fold
        ( fun key a b -> match B.lookup key tb with
        | None   -> b
        | Some x -> f key a x b )
        init ta
      else
        B.fold
        ( fun key a b -> match A.lookup key ta with
        | None   -> b
        | Some x -> f key a x b )
        init tb
    let union f init ta tb =
      B.fold
      f
      ( A.fold
        (fun key a b -> if B.has key tb then b else f key a b)
        init ta )
      tb
    let product f init ta tb =
      A.fold
      (fun key a b -> B.fold (fun k -> f k a) b tb)
      init ta
    let filter prop f init ta tb =
      A.fold
      (fun key a b -> B.filter (fun k -> prop k a) f b tb)
      init ta
  end

le code est non testé et donné uniquement à titre d'illustration

[gasche]

Je suis allé faire un tour du côté de OCaml batteries included, j'ai cliqué sur le premier lien de l'API à savoir data structures, et je dois dire que j'ai été un peu déçu.
En gros y sont repris les modules standards auxquels ont été ajoutés quelques timides fonctions supplémentaires.
J'attendais quelque chose de plus ambitieux.
Il est fait mention d'une possible intégration d'OCaml-Reins ce qui est déjà plus intéressant.

Si tu remplaces "modules standard" par "modules Extlib", c'est plutôt vrai. Il y a quand même quelques ajouts notables par rapport à la simple stdlib INRIA, par exemple les map polymorphes (non fonctorisées) et les tableaux dynamiques.

Les ajouts sont plutôt timides pour l'instant, mais personnellement je trouve ça plutôt normal : on essaie d'intégrer des codes de sources différentes (lib INRIA, Extlib, autres propositions de stdlib (eg. Core), fonctions maison...), tout en gardant une cohérence. Rien choisir des noms adaptés pour les fonctions, ça met du temps, c'est délicat, et cependant c'est important (parce que ça a beaucoup d'impact sur la facilité à utiliser l'ensemble). On ne peut pas ajouter Reins tout d'un coup, à côté des autres modules, et sans faire d'effort d'intégration (parce que ça entraîne de la redondance, de l'hétérogénéité, et de la difficulté de maintenance) : Batteries ne survirait certainement pas sur le long terme.

Selon moi, la meilleure conception (pour OCaml) c'est un TAD impératif avec la possibilité de l'utiliser de façon persistante.

Il me paraît très difficile de proposer une implémentation efficace des deux interfaces dans une même structure. Dans la plupart des cas ça me semble impossible (Array par exemple, ou l'interface fonctionnelle de Hashtbl), et je ne vois pas l'intérêt par rapport à deux modules bien séparés, quitte à avoir des fonctions de conversion entre les deux. En clair, ça me semble être une mauvaise idée.

Ensuite, en plus de ces fonctions élémentaires, il y a les fonctions binaires faisant intervenir deux structures de données.
[..]
La bonne solution pour faire toutes ces choses de façon flexible c'est le pliage. [..] Par exemple, dans le type de module Map, pour tout prédicat p, filter p renvoie un pliage sur la partie du conteneur qui vérifie ce prédicat. De cette façon on ne préjuge pas de l'usage qui sera fait de cette partie.

Note aux lecteurs : "pliage" est une traduction de "fold". Moi je n'ai rien compris avant de voir les exemples.

On en a déjà discuté : il n'y a pas une seule opération fold par structure, et l'interface choisie pour le fold favorise certaines "intentions d'utilisation" par rapport aux autres.

Par exemple, pour un arbre binaire, il y a des fold qui présentent la structure de l'arbre (fold : ('a option * 'node * 'a option) -> 'a -> 'node tree -> 'a)), et d'autres qui exposent juste un parcours linéaire des valeurs (ce que tu appelles itérateur) : (fold : ('a -> 'node -> 'a) -> 'a -> 'node tree -> 'a).

Il est donc faux de penser qu'on "ne préjuge pas de l'usage qui sera fait de cette partie" : si après une intersection je te donne le premier fold, c'est sans doute que j'ai déjà construit l'arbre, et tu es contraint de formuler ton usage comme un catamorphisme; si je te donne le deuxième, tu n'as plus de structure à disposition et tu es obligé de la reconstituer toi-même si tu en as besoin (ce qui peut être couteux si tu reconstruis un arbre, ce qui nous fait des passes inutiles (arbre -> "liste" -> arbre), alors que peut-être la construction (arbre -> arbre) était simple grâce à des spécificités de l'implémentation).
Il n'y a pas de "bonne solution" qui soit claire et évidente.


Je pense que tu as tort de faire une différence entre les structures de données et les "machins qui contiennent implicitement des structures" (itérateur ou fold) : on peut aussi les voir comme la même chose, les itérateurs étant des structures paresseuses. Par exemple, les Enum sont exactement des itérateurs linéaires, et tu peux t'en servir pour faire ce que tu proposes : au lieu de faire un "filter" sur ta structure, tu la convertis en enum, tu filtres dessus, et tu te retrouves avec un itérateur filtré.

Si tu n'aimes pas l'idée d'écrire les conversions par Enum à la main à chaque fois, c'est facile à faire par exemple avec un peu de sucre syntaxique :

Code :

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

[? DynArray : a | a <- Tree : arbre; is_good a ?]

À mon avis, il n'est pas pertinent d'essayer de proposer toutes les manipulations possibles sur toutes les structures de données. Typiquement les opérations que tu décris (union, intersection) n'ont aucun sens sur la plupart des structures "non linéaires" (qu'on ne manipule pas comme une liste d'éléments vérifiant une certaine propriété), et il y a plusieurs possibilités pour les structures associatives par exemple.

Je pense qu'au lieu de vouloir tout supporter sur toutes les structures, on a intérêt à :
- proposer des représentants canoniques des cas d'utilisation classique, avec des conversions faciles (et si possible efficaces) de n'importe quelle structure intéressée vers ces représentants (par exemple Enum pour les structures linéaires)
- éviter d'exposer dans une interface des fonctions inefficaces par nature (par exemple une intersection des listes non triées); la méthode des représentants permet de rendre le coût de l'opération explicite (ah, il faut convertir vers un PSet, intersecter, puis revenir)
- standardiser des sous-groupes de structures supportant une partie des opérations, de manière pertinente et efficace. C'est ce que j'essaie de faire avec des interfaces de modules (à la manière de la bibliothèque Core de Jane Street), mais ce n'est pas facile et on se sent vite limité par la rigidité du langage des interfaces (impossible par exemple de réunir les opérations String.enum et Array.enum sous une même interface). Le risque, c'est l'explosion des interfaces différentes, qui rendent la chose pénible pour l'utilisateur (tu as regardé Reins ?)

[SpiceGuid]

Bien choisir des noms adaptés pour les fonctions, ça met du temps, c'est délicat, et cependant c'est important (parce que ça a beaucoup d'impact sur la facilité à utiliser l'ensemble). On ne peut pas ajouter Reins tout d'un coup, à côté des autres modules, et sans faire d'effort d'intégration

Je suis bien d'accord avec cette approche prudente.
Ce que je voulais dire c'est que l'état actuel des choses n'est pas excitant pour moi, ne correspond pas à l'idée que je me fais d'une bibliothèque riche et moderne et est inutilisable sur une bonne partie de mon code.

Il me paraît très difficile de proposer une implémentation efficace des deux interfaces dans une même structure. Dans la plupart des cas ça me semble impossible (Array par exemple, ou l'interface fonctionnelle de Hashtbl), et je ne vois pas l'intérêt par rapport à deux modules bien séparés, quitte à avoir des fonctions de conversion entre les deux.

Ok, ça n'est pas possible dans le cas général.
Mais c'est possible dans le cas de toutes les structures arborescentes.
Et comme les files/queues sont souvent implémentées à l'aide d'arbres (tas de Fibonacci, tas binomiaux) ça mérite considération. Après est-ce qu'il faut privilégier l'uniformité sur l'ensemble de la bibliothèque ou bien considérer les TAD arborescents comme un domaine à part entière c'est matière à débat.
La conversion est de toute façon inévitable, c'est la fonction copy dans mon interface.

Moi je n'ai rien compris avant de voir les exemples.

D'accord, je me suis mal expliqué. J'y reviendrai.

Remarque: mes fold ne sont pas des vrais fold ce sont juste des sérialiseurs qui sont censés remplacer les Enum de Extlib. Donc ils n'exposent pas la structure interne du TAD, pour exploiter au mieux la structure interne du TAD je fais confiance aux opérations du TAD lui-même. Là ce que je veux faire c'est coder un certain nombre d'opérations sur n'importe quel couple de TAD.

Remarque: mes types n'étaient pas assez explicites. Avec mes nouvelles notations il est beaucoup plus visible que mes fonction renvoient des fold, ce sont des combinateurs de fold.

au lieu de faire un "filter" sur ta structure, tu la convertis en enum, tu filtres dessus, et tu te retrouves avec un itérateur filtré.

Au lieu de renvoyer un enum je renvoie un pliage, donc pas de structure intermédiaire, par contre en temps c'est probablement aussi inefficace.

ce qui peut être couteux si tu reconstruis un arbre, ce qui nous fait des passes inutiles (arbre -> "liste" -> arbre

Tu permets que je note fold à la place de "liste" mais c'est certain qu'il s'agit bien d'une linéarisation.
Si je veux l'intersection de deux AVL je vais évidemment utiliser l'opération AVLTree -> AVLTree -> AVLTree telle qu'elle m'est fournie par l'implémentation du TAD, c'est ce que j'ai appelé la méthode "interne".
C'est d'ailleurs le principal reproche que je fais à Map.Make de la stdlib : ne pas fournir ces opérations en interne.
Maintenant si je veux placer l'intersection d'un arbre de Braun et d'un arbre AVL dans un arbre binaire de recherche

Code :

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

BraunTree -> AVLTree -> fold -> ABRTree

J'ai besoin d'une autre méthode qui ne sait rien de l'implémentation, c'est ce que j'ai appelé la méthode "externe".


La suite de ce message corrige et améliore la source du premier message.

Le type de Mixed.filter dans le premier message est incorrect car le pliage renvoyé n'utilise pas les éléments de A.t.
Le type de Mixed.product n'est pas complètement satisfaisant parce qu'il ne fait apparaître qu'une seule clé pour deux éléments ayant chacun leur clé distincte.
Pour plus de rigueur j'ai recommencé avec de nouvelles notations et une signature complète du 'foncteur' Mixed.

Le type de module Map n'a pas changé, il est seulement un peu enrichi en notations :

Code OCaml :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
  module type Map =
  sig
    type 'a t
    type key
    type ('a,'b) fold = (key -> 'a -> 'b -> 'b) -> 'b -> 'a t -> 'b
    type 'a cond = key -> 'a -> bool
    (* imperative *)
    val empty:   unit -> 'a t
    val put:     key -> 'a -> 'a t -> unit
    val find:    key -> 'a t -> 'a  
    val remove:  key -> 'a t -> unit
    val copy:    'a t -> 'a t
    (* functional *)
    val singleton: key -> 'a -> 'a t
    val count:   'a t -> int 
    val has:     key -> 'a t -> bool
    val add:     key -> 'a -> 'a t -> 'a t
    val lookup:  key -> 'a t -> 'a option
    val delete:  key -> 'a t -> 'a t
    (* folds *)
    val fold:    ('a,'b) fold
    val filter:  'a cond -> ('a,'b) fold
    (* iterators *)
    val map:     (key -> 'a -> 'b) -> 'a t -> 'b t
    val iter:    (key -> 'a -> unit) -> 'a t -> unit
    val for_all: 'a cond -> 'a t -> bool
  end

Ce que j'appelle fold ici ce sont des itérateurs/sérialiseurs sur une partie d'un TAD.
Pour Map.fold cette partie est la totalité.
Pour Map.filter cette partie est celle qui vérifie un certain prédicat.
(étant donné une condition filter renvoie un fold sur la partie qui vérifie cette condition)

Remarque: le Map.Make de OCaml batteries utilise des clés comparables mais ne permet pas la sélection d'un intervalle de clés, peut être parce qu'on a pas su comment le représenter. Selon moi il faudrait ajouter trois pliages supplémentaires.

Code :

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

1
2
3
4
 
val less:  key -> ('a,'b) fold 
val more:  key -> ('a,'b) fold 
val interval:  key -> key -> ('a,'b) fold

Quand les clés sont comparables ces trois pliages sont nettement plus performants que le Map.fold ou le Map.filter qui pourraient les simuler.

On a vu 5 pliages sur 5 parties d'un ensemble.
Reste maintenant à combiner ces pliages pour en produire de nouveaux.
Car même dans le cas on l'on utilise partout le même TAD, le fait qu'on ne soit intéressé que par une partie de l'ensemble rend caduque l'utilisation de la méthode interne (voir mon billet blog pour un cas d'utilisation où l'on ne s'intéresse manifestement qu'à l'intersection).

Avec mon 'foncteur' Mixed précédent il n'était pas possible d'exploiter la performance des pliages less/more/interval (sur une implantation à base de clés comparables) au niveau des fonctions intersection/union/product.

Pour vraiment exploiter la performance des pliages qui utilisent les propriétés du TAD il ne faut plus écrire les fonctions intersection/union/product pour les TAD mais pour les pliages eux-mêmes. C'est de cette façon qu'on pourra combiner les pliages les plus appropriés. On retrouvera les opérations classiques simplement en paramétrant les combinateurs de fold avec les pliages A.fold et B.fold.

Code OCaml :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
  module Mixed (A: Map) (B: Map with type key = A.key) 
  :
  sig
    (* folds *)
    type ('a,'b) intersection =
      (A.key -> 'a -> 'a -> 'b -> 'b) -> 'b -> 'a A.t -> 'a B.t -> 'b
    type ('a,'b) union =
      (B.key -> 'a -> 'b -> 'b) -> 'b -> 'a A.t -> 'a B.t -> 'b
    type ('a,'b,'c) product =
      (A.key -> B.key -> 'a -> 'b -> 'c -> 'c) -> 'c -> 'a A.t -> 'b B.t -> 'c
    (* predicates *)
    type ('a,'b) intersection_cond =
      A.key -> 'a -> 'a -> bool
    type ('a,'b) product_cond =
      A.key -> B.key -> 'a -> 'b -> bool
    (* operations *)
    val union:          ('a,'b) union
    val intersection:   ('a,'b) intersection
    val product:        ('a,'b,'c) product
    val filter_union:   ('a) A.cond -> ('a,'b) union
    val filter_product: ('a,'b) product_cond -> ('a,'b,'c) product
    val filter_intersection: ('a,'b) intersection_cond -> ('a,'b) intersection
    val make_union:          ('a,'b) A.fold -> ('a,'b) B.fold -> ('a,'b) union
    val make_intersection:   ('a,'b) A.fold -> ('a,'b) B.fold -> ('a,'b) intersection
    val make_product:
          ((A.key -> 'a -> 'b -> 'b) -> 'c -> 'd A.t -> 'c) ->
          ((B.key -> 'd -> 'c -> 'c) -> 'b -> 'a B.t -> 'b) ->
          (A.key -> B.key -> 'a -> 'd -> 'c -> 'c) -> 'c -> 'd A.t -> 'a B.t -> 'c
          (* ('a,'b) A.fold -> ('c,'d) B.fold -> ('e,'f,'g) product *)
  end
  =
  struct
    (* folds *)
    type ('a,'b) intersection =
      (A.key -> 'a -> 'a -> 'b -> 'b) -> 'b -> 'a A.t -> 'a B.t -> 'b
    type ('a,'b) union =
      (B.key -> 'a -> 'b -> 'b) -> 'b -> 'a A.t -> 'a B.t -> 'b
    type ('a,'b,'c) product =
      (A.key -> B.key -> 'a -> 'b -> 'c -> 'c) -> 'c -> 'a A.t -> 'b B.t -> 'c
    (* predicates *)
    type ('a,'b) intersection_cond =
      A.key -> 'a -> 'a -> bool
    type ('a,'b) product_cond =
      A.key -> B.key -> 'a -> 'b -> bool
    (* operations *)
    let make_intersection fa fb f init ta tb =
      if A.count ta < B.count tb then
        fa
        ( fun key a b -> match B.lookup key tb with
        | None   -> b
        | Some x -> f key a x b )
        init ta
      else
        fb
        ( fun key a b -> match A.lookup key ta with
        | None   -> b
        | Some x -> f key a x b )
        init tb
    let make_union fa fb f init ta tb =
      fb
      f
      ( fa
        (fun key a b -> if B.has key tb then b else f key a b)
        init ta )
      tb
    let make_product fa fb f init ta tb =
      fa
      (fun key a b -> fb (fun k -> f key k a) b tb)
      init ta      
    let filter_intersection cond f init ta tb =
      if A.count ta < B.count tb then
        A.fold
        ( fun key a b -> match B.lookup key tb with
        | None   -> b
        | Some x -> if cond key a x then f key a x b else b)
        init ta
      else
        B.fold
        ( fun key a b -> match A.lookup key ta with
        | None   -> b
        | Some x -> if cond key a x then f key a x b else b)
        init tb
    let filter_union cond f init ta tb =
      B.filter
      cond
      f
      ( A.filter
        cond
        (fun key a b -> if B.has key tb then b else f key a b)
        init ta )
      tb
    let filter_product cond f init ta tb =
      A.fold
      (fun key a b -> B.filter (fun k -> cond key k a) (fun k -> f key k a) b tb)
      init ta
    let union f =
      make_union A.fold B.fold f
    let product f =
      make_product A.fold B.fold f
    let intersection f =
      make_intersection A.fold B.fold f
  end

Remarque: j'ai prédéfini les types des pliages pour simplifier les notations, ça marche assez bien sauf pour make_product que je n'arrive pas à simplifier et qui reste particulièrement opaque pour moi.

À mon avis, il n'est pas pertinent d'essayer de proposer toutes les manipulations possibles sur toutes les structures de données
....
Je pense qu'au lieu de vouloir tout supporter sur toutes les structures, on a intérêt à :
...

Intéressant et certainement plein de bon sens.
Je le relirai plus attentivement quand j'aurai moins la tête dans ma source.

Ma réponse rapide: si ça ne coûte qu'un seul module pour supporter une large gamme d'opérations croisées entre une multitude de TAD différents, pourquoi devrais-je m'en priver ?
De plus mon approche du pliage n'exclue pas les approches ou stratégies concurrentes. Elle n'est surtout pas destinée à se substituer à des implantations spécifiques et efficaces. C'est seulement une flexibilité additionnelle et gratuite, quoique un peu pénible à appréhender j'en conviens.

(tu as regardé Reins ?)

Non, pas en détail. J'ai été assommé par l'inflation du nombre de 'foncteurs'. Ma conception n'est pas dans ce style même si je le trouve intéressant. Bien sûr je suis conscient que ce qui est la simplicité (factorisation) pour les uns peut apparaître comme de la surenchère pour les autres.

[gasche]

Ce que je voulais dire c'est que l'état actuel des choses n'est pas excitant pour moi, ne correspond pas à l'idée que je me fais d'une bibliothèque riche et moderne et est inutilisable sur une bonne partie de mon code.

Si tu as des suggestions/propositions raisonnables (ie. pas trop farfelues, si possible déjà utilisées par des gens, et dont on a le sentiment qu'on n'aura pas peut-être besoin de tout changer en cassant la compatibilité un jour), il faut t'exprimer. Les bouts de code sont même bienvenus, et Git est fait pour faciliter la collaboration.

Mais c'est possible dans le cas de toutes les structures arborescentes.

Je ne comprends pas très bien ce point là. Dans ma tête, si on utilise ton interface fonctionnelle pure, et qu'après on utilise l'interface impérative sur une ancienne version de la structure, les nouvelles versions pures seront modifiées par effet de bord, ce qui détruit une grande partie de l'intérêt de la pureté. Est-ce que :
- je n'ai pas compris comment tu voulais faire
- c'est à l'utilisateur de garantir l'absence d'effets de bord lui-même en utilisant judicieusement copy
- tu penses à une implémentation plus sophistiquée que je ne connais pas ?

Je suis un peu perplexe à ce sujet. J'ai une idée (séparation en deux modules de même représentation physique, avec une projection qui impose la copie) qui pourrait peut-être nous satisfaire tous les deux, mais je n'ai pas le temps de la développer maintenant (ou de répondre au reste du post qui est intéressant).

[SpiceGuid]

Je veux faire simple: il y a une interface pour le style fonctionnel mais sinon c'est strictement impératif, il n'y a aucune pureté là dedans. Il n'y a pas non plus d'astuce pour simuler de la pureté parce que ce genre d'astuce (à supposer que ce soit possible) va forcément à l'encontre de la simplicité. Et moins de simplicité c'est potentiellement moins de performance. Je ne veux rien ajouter qui empêcherait de se concentrer seulement sur le côté algorithmique du TAD.

L'utilisateur doit :

• ou bien faire attention et utiliser judicieusement copy quand c'est nécessaire pour préserver l'illusion de la persistance si c'est ce qu'on souhaite
• ou bien écrire une autre interface identique dans laquelle on aura omis put/find/remove, un module qui implémente la première implémente aussi la deuxième, non ?
• deux interfaces suffisent, je ne vois aucune raison de fournir une interface où il n'y aurait que le style impératif sans le style fonctionnel

Tu dois bien voir le problème que j'ai rencontré avec les tables de transposition :

• elles se comportent comme des ensembles
• d'un autre côté elles se comportent comme des conteneurs qui associent un plateau à une liste de coups
• pour terminer une recherche bidirectionnelle tu dois intersecter deux tables de transposition et effectuer un append sur les deux listes de coups
• tu ne peux pas le faire avec Set.Make (pas de capacité associative) et tu ne peux pas le faire avec Map.Make (pas d'intersection)
• du coup je suis obligé de développer un TAD maison incomplet avec des algos naifs et pas testés

En résumé :

• je suis pour des interfaces simples et efficaces à l'intérieur
• je suis pour y inclure quelques fonctions non triviales ou inhabituelles lorsque le besoin et la performance l'exigent, il suffit qu'elles soient bien documentées et bien répertoriées (comme non fondamentales)
• pour aller plus loin je propose d'ajouter une interface complexe et riche à l'extérieur dans des modules annexes, qui apporte de la flexibilité sans compliquer ni l'interface ni l'implantation du TAD de base
• je suis pour une approche algorithmique, c'est-à-dire que l'objectif doit être de s'attaquer aux problèmes les plus difficiles
• l'approche opposée serait au contraire de faciliter à tout prix les cas les plus simples et/ou les plus fréquents, où des modules écris par les experts ne serviraient ni aux experts (pas réutilisables) ni aux débutants (ça resterait des higher-order modules)
• mon argument c'est qu'un bon TAD comme Set.Make est très difficile à réaliser, il faut donc tout faire pour qu'il soit réutilisable sinon cet effort est perdu. on ne doit pas avoir peur des sémantiques difficiles, on n'est pas obligé de comprendre toute l'interface du premier coup. un débutant OCaml ne commence pas par les foncteurs, on peut donc y mettre des sémantiques riches. si on veut du simpliste les versions défonctorisées sont faites pour ça.
• étant d'abord concerné par l'algorithmique je ne suis pas obsédé par la recherche d'uniformité des interfaces. la compatibilité est une préoccupation importante, mais pas autant que la performance et l'utilisabilité. une interface complète vaut mieux qu'une interface compatible. une interface incomplète n'est pas utilisable. une interface incompatible n'est pas enfichable, c'est beaucoup moins grave.

[gasche]

Je veux faire simple: il y a une interface pour le style fonctionnel mais sinon c'est strictement impératif, il n'y a aucune pureté là dedans.

Donc tu proposes de pouvoir écrire dans un "style fonctionnel", sans pour autant protéger le programmeur des effets de bord. Je trouve cela dangereux parce que, de mon point de vue, le mélange de ces fonctions dans l'interface revient à dire à l'utilisateur "vas-y, fais ce que tu veux, mélange les deux", et ça détruit directement l'avantage du fonctionnel : plus de transparence référentielle, il faut à nouveau regarder partout pour éviter les bugs liés aux effets de bord.

Je préfèrerais de loin un design dans ce genre là :

Code ocaml :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
module rec MutableTree : sig
  include InnerTree
  val put : key -> 'a -> 'a t -> unit
  (* ... *)
  val to_pure : 'a t -> 'a PureTree.t
  val to_pure_unsafe : 'a t -> 'a PureTree.t
end
and PureTree : sig
  include InnerTree
  val add : key -> 'a -> 'a t -> 'a t
  (* ... *)
  val to_mutable : 'a t -> 'a MutableTree.t
  val to_mutable_unsafe : 'a t -> 'a MutableTree.t
end

On aurait to_pure et to_mutable faisant des copies (avec potentiellement du copy_on_write pour to_mutable), et les versions _unsafe sans copie, permettant de propager les effets de bords (soit pour des raisons de performance, parce que le développeur est sûr que l'utilisation qui est faite ne fera aucun effet de bord dont la propagation serait indésirable, soit parce que l'utilisation d'un effet de bord simplifie quelque chose). Les deux versions sont typées différemment donc le compilateur empêche d'utiliser les opérations de l'une sur l'autre, et tout cela est bien séparé.

deux interfaces suffisent, je ne vois aucune raison de fournir une interface où il n'y aurait que le style impératif sans le style fonctionnel

Je ne vois aucune raison d'utiliser un "style fonctionnel" sur un objet impératif. Si c'est parce que c'est plus simple pour certains itérateurs (je pense au fold qui s'accomoderait peut-être mieux d'une primitive d'ajout fonctionnelle, et encore, j'en doute), c'est un problème de bibliothèque qui doit être corrigé.

mes fold ne sont pas des vrais fold ce sont juste des sérialiseurs qui sont censés remplacer les Enum de Extlib. Donc ils n'exposent pas la structure interne du TAD, pour exploiter au mieux la structure interne du TAD je fais confiance aux opérations du TAD lui-même. Là ce que je veux faire c'est coder un certain nombre d'opérations sur n'importe quel couple de TAD.

Je pense que tu fais trop compliqué ici. Au lieu de proposer des folds pour "tout couple de structures", tu pourrais proposer une seule structure de donnée qui propose toutes les opérations qui t'intéressent (la méthode du "représentant canonique" que j'ai évoquée plus tôt), et qui soit flexible comme Enum (paresse, et abstraction des accesseurs qui permet d'appeler en interne des fonctions d'accès plutôt que de travailler sur une représentation concrète précalculée). Ensuite, il ne te reste plus qu'à écrire une fonction de traduction de tes structures vers cette "structure représentant" unique, et tu peux faire ce que tu veux en traduisant chacun des deux membre vers cette "structure représentant", avant de faire les opérations qui t'intéressent.

C'est exactement l'idée derrière Enum. Ce serait un "Enum adapté aux structures set-like".

Pour la flexibilité, ça n'a que des avantages. Ça permet comme tu le fais d'utiliser les méthodes internes des structures de départ, mais aussi éventuellement de ne pas le faire : certaines structures pourraient ne pas avoir par exemple une opération (mem : 'a -> 'a t -> bool) efficace, et il est alors plus intéressant de la précalculer que d'utiliser la méthode de la structure; cette décision peut être prise dans la fonction de conversion vers la "structure représentant", qui se trouve dans le code de la structure, donc la logique n'est pas éparpillée.

Il y a un léger surcoût au runtime lié à l'utilisation de fonctions d'accès abstraites, mais je m'attends à ce qu'il soit du même ordre que celui de tes "sérialiseurs" (c'est le même genre de 'mise en fonction' après tout, même si celle-ci est plus profonde dont le surcoût serait sans doute supérieur).

En résumé :
* je suis pour des interfaces simples et efficaces à l'intérieur
* je suis pour y inclure quelques fonctions non triviales ou inhabituelles lorsque le besoin et la performance l'exigent, il suffit qu'elles soient bien documentées et bien répertoriées (comme non fondamentales)
* pour aller plus loin je propose d'ajouter une interface complexe et riche à l'extérieur dans des modules annexes, qui apporte de la flexibilité sans compliquer ni l'interface ni l'implantation du TAD de base
* je suis pour une approche algorithmique, c'est-à-dire que l'objectif doit être de s'attaquer aux problèmes les plus difficiles
* l'approche opposée serait au contraire de faciliter à tout prix les cas les plus simples et/ou les plus fréquents, où des modules écris par les experts ne serviraient ni aux experts (pas réutilisables) ni aux débutants (ça resterait des higher-order modules)
* mon argument c'est qu'un bon TAD comme Set.Make est très difficile à réaliser, il faut donc tout faire pour qu'il soit réutilisable sinon cet effort est perdu. on ne doit pas avoir peur des sémantiques difficiles, on n'est pas obligé de comprendre toute l'interface du premier coup. un débutant OCaml ne commence pas par les foncteurs, on peut donc y mettre des sémantiques riches. si on veut du simpliste les versions défonctorisées sont faites pour ça.
* étant d'abord concerné par l'algorithmique je ne suis pas obsédé par la recherche d'uniformité des interfaces. la compatibilité est une préoccupation importante, mais pas autant que la performance et l'utilisabilité. une interface complète vaut mieux qu'une interface compatible. une interface incomplète n'est pas utilisable. une interface incompatible n'est pas enfichable, c'est beaucoup moins grave.

Je crois que tu ne fais pas la différence entre deux types de besoins que peuvent satisfaire des bibliothèques logicielles :
- le besoin de proposer des interfaces de références, qui apporte à l'utilisateur un certain nombre d'opérations bien délimitées, tout en lui masquant les détails de l'implémentation (pour pouvoir assurer la compatibilité en changeant l'implémentation, par exemple)
- le besoin de proposer des implémentations de référence, qui apporte à l'utilisateur un certaine quantité de "connaissance d'implémentation", en essayant de lui permettre d'adapter le plus possible le module à ses besoins, en retardant le plus possible le moment (inévitable) où le plus flexible pour lui sera de copier-coller le code du module en le modifiant


Ces deux besoins, à l'intérieur d'une même interface, sont contradictoire : le premier demande un traitement très abstrait qui laisse ressortir le moins de détail d'implémentation possible (et donc limite la réutilisation "algorithmique"), le deuxième demande d'exposer le plus de manipulations possible, laissant transparaître la structure sous-jacente spécifique, le cas extrême (du point de vue de la programmation modulaire) étant la publication dans l'interface du type algébrique sous-jacent, permettant à l'utilisateur de faire virtuellement n'importe quoi avec tout en continuant à utiliser les fonctions du module, et empêchant toute modification de l'implémentation de la structure par la suite.

* je suis pour y inclure quelques fonctions non triviales ou inhabituelles lorsque le besoin et la performance l'exigent, il suffit qu'elles soient bien documentées et bien répertoriées (comme non fondamentales)
[...]
* mon argument c'est qu'un bon TAD comme Set.Make est très difficile à réaliser, il faut donc tout faire pour qu'il soit réutilisable sinon cet effort est perdu. [...]
* étant d'abord concerné par l'algorithmique je ne suis pas obsédé par la recherche d'uniformité des interfaces. la compatibilité est une préoccupation importante, mais pas autant que la performance et l'utilisabilité

Ces points (et d'autres) classent ta demande dans la "deuxième catégorie" : accès aux connaissances d'implémentation, au mépris de l'abstraction présente dans l'interface.

Tu comprends bien qu'une bibliothèque logicielle ne puisse se contenter de satisfaire seulement ce type de besoin (parce qu'ils vont à l'encontre des bonnes pratiques d'ingénérie logicielle, qui sont plus intéressés par une séparation propre des modules et la minimisation des dépendances que par une facilité de réutilisation de l'algorithme en changeant l'interface du module), et qu'elles mettent en priorité en avant la "deuxième catégorie" d'interfaces. C'est ce que font les modules Set et Make et c'est pour cela que tu es mécontent.

Les besoins de "deuxième catégorie" seront toujours minoritaires (la plupart des gens s'en tapent, et contrairement à ce que tu sembles penser il est plus productif pour tout le monde de rendre simple le cas simple, car les gens ayant besoin du cas compliqué auront toujours des demandes compliquées et souvent contradictoires de toute façon), et ils sont ajoutés dans un "deuxième temps". Mais, comme tu le dis, on peut les ajouter quand même :

# pour aller plus loin je propose d'ajouter une interface complexe et riche à l'extérieur dans des modules annexes, qui apporte de la flexibilité sans compliquer ni l'interface ni l'implantation du TAD de base

C'est un choix qui est présent dans la bibliothèque standard Caml light : tu as "set" et "map" qui proposent une interface comme celle d'Objective Caml, et un module baltree qui expose l'implémentation sous-jacente.

On sort ici du cadre "TAD" parce ce n'a plus rien d'"abstrait". Cela peut-être pertinent dans une bibliothèque standard, mais certainement pas pour "tous les modules" : priorité aux interfaces qui proposent une vraie abstraction, et que tu trouves insatisfaisante.

L'idée d'ajouter à Batteries une collection de modules à des fins algorithmiques n'est pas mauvaise, mais on se heurete aux problèmes de compatibilité : contrairement aux interfaces vraiment abstraites, ces modules sont très sensibles aux modifications, et il devient difficile d'assurer à l'utilisateur que son code restera compatible avec les versions futures, sans bloquer les possibilités d'amélioration des structures proposées.

[Cacophrene]

Salut !

- le besoin de proposer des interfaces de références, qui apporte à l'utilisateur un certain nombre d'opérations bien délimitées, tout en lui masquant les détails de l'implémentation (pour pouvoir assurer la compatibilité en changeant l'implémentation, par exemple)
- le besoin de proposer des implémentations de référence, qui apporte à l'utilisateur un certaine quantité de "connaissance d'implémentation", en essayant de lui permettre d'adapter le plus possible le module à ses besoins, en retardant le plus possible le moment (inévitable) où le plus flexible pour lui sera de copier-coller le code du module en le modifiant.

Éternel dilemme entre les modules opaques et les modules transparents. Pourquoi pas (c'est une suggestion comme ça en passant, je n'y ai pas réfléchi beaucoup) deux interfaces distinctes ? Disons quelque chose comme ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

(* Implémentation masquée pour l'usage courant. *)
module Abstract_Something :
  sig
    type 'a t

    val create : 'a -> 'a t
    val compare : 'a t -> 'a t -> int
    val iter : ('a -> unit) -> 'a t -> unit
    val map : ('a -> 'b) -> 'a t -> 'b t
    ...
  end

(* Implémentation visible pour les utilisations plus siouxes. *)
module Concrete_Something :
  sig
    type 'a t = Nothing | Something of 'a * 'a t

    val create : 'a -> 'a t (* Quelque peu inutile maintenant. *)
    val compare : 'a t -> 'a t -> int
    val iter : ('a -> unit) -> 'a t -> unit
    val map : ('a -> 'b) -> 'a t -> 'b t
  end

(* Deux noms pour une seule chose. *)
val abstract_to_concrete : 'a Abstract_Something.t -> 'a Concrete_Something.t
val concrete_to_abstract : 'a Concrete_Something.t -> 'a Abstract_Something.t

Bon, je répète que je n'ai pas beaucoup réfléchi à cette idée, à son esthétique ou son caractère pertinent ou rocambolesque, etc. Cela ne pourrait-il pas (presque) fournir à chacun les outils qu'il cherche ?

Cordialement,
Cacophrène

[gasche]

C'est exactement ce que propose "baltree" de Caml Light (cf. lien dans mon précédent message).

La seule fonction qui pose problème dans ton exemple est abstract_to_concrete : elle "casse" l'abstraction de l'interface, et donc nous ramène à tous les problèmes précédents, par exemple on ne peut pas maintenir la compatibilité en changeant de version dès qu'on change l'implémentation. concrete_to_abstract ne pose bien sûr aucun problème puisque c'est un simple témoin que l'implémentation correspond bien à l'interface exposée.

On pourrait éventuellement garder abstract_to_concrete en disant à l'utilisateur "attention, casse l'abstraction, use it at your own risks". Ça pourrait cependant créer des problèmes de solidité de l'interface, et je pense qu'il est plus raisonnable de ne pas l'inclure, quitte à laisser l'utilisateur faire de la magie noire (Obj.magic ici) s'il en a vraiment besoin, ce qui n'est pas le cas normalement, et une mauvaise idée de toute façon.

[Cacophrene]

Salut !

C'est sûr que dès qu'on expose la représentation interne d'un type, on s'interdit tout changement d'implémentation ultérieur (ou alors on se moque vraiment des utilisateurs ).

D'un autre côté, on ne pense pas toujours à tout du premier coup... et les utilisateurs pensent toujours à des choses auxquelles on ne pense pas. Heureusement, il ne faut pas céder sur tout, car sinon les interfaces de modules deviendraient énormes pour des fonctions pas forcément très utilisées. Genre moi je veux ci, moi je veux ça et on se retrouve avec des modules si gros que plus personne ne veut les utiliser / les maintenir.

Il y a quand même la solution offerte par le mot-clef private qui semble assez bonne : d'un côté on voit ce qui se passe en interne, ce qui permet une utilisation souple du type (filtrage notamment), mais on ne peut pas créer de valeur « à la main » en faisant n'importe quoi. Hélas, là encore, on perd en généralité et tout changement d'implémentation sera fatal...

La quadrature du chameau en somme

Cordialement,
Cacophrène

[SpiceGuid]

Les types conteneurs associatifs:

Code :

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

1
2
3
4
5
6
7
module type PureMap =
sig
  type 'a t
  type key
  val empty: unit -> 'a t
  val add:   key -> 'a -> 'a t -> 'a t
end

La version mutable :

Code :

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

1
2
3
4
5
module type MutableMap =
sig
  include PureMap 
  val put: key -> 'a -> 'a t -> unit
end

L'implémentation des tableaux creux mutables :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
module MutableBraun : MutableMap with type key = int
=
struct
  type 'a vector =
    | Leaf
    | Node of 'a node
  and 'a node =
    {mutable left: 'a vector; mutable item: 'a option; mutable right: 'a vector}
  type 'a t =
    {mutable plus: 'a vector; mutable minus: 'a vector}
  type key =
    int
  let empty () =
    {plus = Leaf; minus = Leaf}
  let rec grow i x =
    Node
    (
    if i = 1 then {left = Leaf; item = Some x; right = Leaf}
    else if i land 1 = 0 then {left = grow (i asr 1) x; item = None; right = Leaf}
    else {left = Leaf; item = None; right = grow (i asr 1) x}
    )
  let put i x v =
    let rec tree i node =
      match node with
      | Leaf ->
          grow i x
      | Node n ->
          if i = 1 then n.item <- Some x
          else if i land 1 = 0 then n.left <- tree (i asr 1) n.left
          else n.right <- tree (i asr 1) n.right;
          node       
    in 
    if i >= 0 then v.plus <- tree (succ i) v.plus
    else v.minus <- tree (-i) v.minus
  let add i x v =
    let rec tree i node =
      match node with
      | Leaf ->
          grow i x
      | Node n ->
          Node
          (
          if i = 1 then {n with item = Some x}
          else if i land 1 = 0 then {n with left = tree (i asr 1) n.left}
          else {n with right = tree (i asr 1) n.right}
          )    
    in
    if i >= 0 then {v with plus = tree (succ i) v.plus}
    else {minus = tree (-i) v.minus; plus = v.plus}
end

La signature produite par cette implantation :

Code :

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

1
2
3
4
5
6
7
8
module MutableBraun :
  sig
    type 'a t
    type key = int
    val empty : unit -> 'a t
    val add : key -> 'a -> 'a t -> 'a t
    val put : key -> 'a -> 'a t -> unit
  end

Les mêmes tableaux creux en style purement fonctionnel :

Code :

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

module PureBraun : PureMap with type key = int = MutableBraun

La signature produite pour le style fonctionnel :

Code :

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

1
2
3
4
5
6
7
module PureBraun :
  sig
    type 'a t
    type key = int
    val empty : unit -> 'a t
    val add : key -> 'a -> 'a t -> 'a t
  end

Je préfèrerais de loin un design dans ce genre là :

Code ocaml :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
module rec MutableTree : sig
  include InnerTree
  val put : key -> 'a -> 'a t -> unit
  (* ... *)
  val to_pure : 'a t -> 'a PureTree.t
  val to_pure_unsafe : 'a t -> 'a PureTree.t
end
and PureTree : sig
  include InnerTree
  val add : key -> 'a -> 'a t -> 'a t
  (* ... *)
  val to_mutable : 'a t -> 'a MutableTree.t
  val to_mutable_unsafe : 'a t -> 'a MutableTree.t
end

Avec cette conception il est sans doute plus difficile de pouvoir partager l'implantation. Cependant je reconnais qu'elle est élégante et a certains mérites, notamment celui de permettre de passer d'une version purement fonctionnelle à une version impérative, ce que ma conception ne permet pas.

Sinon le reste de ton message assume complètement le fait que les TAD de OCaml batteries n'ont que peu d'intérêt algorithmique. Du coup je ne vois pas bien pourquoi j'y participerais si on pose comme condition que ma contribution soit sans audace et sans intérêt. Selon toi voir plus loin qu'une interface au rabais à la push/pop/top c'est vouloir violer l'encapsulation.
Selon moi, tant qu'on a pas exposé la réprésentation interne tout est envisageable pourvu que ça soit suffisamment générique, utile et efficace.

les utilisateurs pensent toujours à des choses auxquelles on ne pense pas. Heureusement, il ne faut pas céder sur tout, car sinon les interfaces de modules deviendraient énormes pour des fonctions pas forcément très utilisées.

Il ne faut pas céder sur une demande particulière, par contre il faut répondre au besoin algorithmique dès qu'on a réussi à trouver l'interface pour le satisfaire de la façon la plus générale possible (toujours sans rien exposer de la représentation bien sûr). Après évidemment on peut prétendre que fournir des routines sur des intervalles de clés c'est révéler une implantation à l'aide de clés totalement ordonnées. Mais ne pas le faire c'est :

• prendre l'utilisateur pour un imbécile, il doit implanter OrderedType mais il ne doit surtout pas savoir que les clés sont ordonnées
• hypocrite, l'utilisateur peut très bien comparer les clès à l'aide du module OrderedType qu'il a fourni, s'il le veut il pourra parcourir tout le conteneur et appliquer un certain traitement seulement sur un certain intervalle de clés. mais il ne le fera pas parce que c'est horriblement inefficace.
• l'obliger à développer un nouveau module ad-hoc alors qu'un module efficace et bien testé existe déjà

Il ne faut pas oublier qu'on peut produire plusieurs interfaces pour une même implantation simplement à l'aide de implantation : interface. L'argument des interfaces volumineuses n'est qu'une excuse pour le manque d'ambition.

[gasche]

Avec cette conception il est sans doute plus difficile de pouvoir partager l'implantation.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
(* les InnerFoo ne sont pas exposés à l'extérieur *)
module type InnerMap = sig
  type 'a t
  type key
  val empty : unit -> 'a t
  (* mais aussi map, fold, iter, etc. *)
end
 
module InnerBraun = struct
  type 'a vector =
    | Leaf
    | Node of 'a node
  and 'a node =
      {mutable left: 'a vector; mutable item: 'a option; mutable right: 'a vector}
  type 'a t =
      {mutable plus: 'a vector; mutable minus: 'a vector}
 
  type key = int
 
  let empty () = {plus = Leaf; minus = Leaf}
 
  let rec grow i x = Node (
    if i = 1 then {left = Leaf; item = Some x; right = Leaf}
    else if i land 1 = 0 then {left = grow (i asr 1) x; item = None; right = Leaf}
    else {left = Leaf; item = None; right = grow (i asr 1) x}
  )
 
  let map f tree =
    let rec map = function
    | Leaf -> Leaf
    | Node n ->
        let item = match n.item with
        | None -> None
        | Some x -> Some (f x) in
        Node {item = item; left = map n.left; right = map n.right} in
    {plus = map tree.plus; minus = map tree.minus}
 
  let id x = x
  let copy tree = map id tree
end
 
module rec PureBraun : sig
  include InnerMap
  val add : key -> 'a -> 'a t -> 'a t
  val to_mutable : 'a t -> 'a MutableBraun.t
  val to_mutable_unsafe : 'a t -> 'a MutableBraun.t
end = struct
  include InnerBraun
 
  let add i x v =
    let rec tree i node =
      match node with
      | Leaf -> grow i x
      | Node n -> Node (
          if i = 1 then {n with item = Some x}
          else if i land 1 = 0 then {n with left = tree (i asr 1) n.left}
          else {n with right = tree (i asr 1) n.right}
        ) in
    if i >= 0 then {v with plus = tree (succ i) v.plus}
    else {minus = tree (-i) v.minus; plus = v.plus}  
 
  let to_mutable = copy
  let to_mutable_unsafe = id
end
 
and MutableBraun : sig
  include InnerMap
  val put : key -> 'a -> 'a t -> unit
  val to_pure : 'a t -> 'a PureBraun.t
  val to_pure_unsafe : 'a t -> 'a PureBraun.t
end = struct
  include InnerBraun
 
  let put i x v =
    let rec tree i node =
      match node with
      | Leaf -> grow i x
      | Node n ->
          if i = 1 then n.item <- Some x
          else if i land 1 = 0 then n.left <- tree (i asr 1) n.left
          else n.right <- tree (i asr 1) n.right;
          node in 
    if i >= 0 then v.plus <- tree (succ i) v.plus
    else v.minus <- tree (-i) v.minus
 
  let to_pure = copy
  let to_pure_unsafe = id
end

Sinon le reste de ton message assume complètement le fait que les TAD de OCaml batteries n'ont que peu d'intérêt algorithmique. Du coup je ne vois pas bien pourquoi j'y participerais si on pose comme condition que ma contribution soit sans audace et sans intérêt. Selon toi voir plus loin qu'une interface au rabais à la push/pop/top c'est vouloir violer l'encapsulation.

... T'es au taquet :p

Si tu as des améliorations à proposer, vas-y, envoie un message sur la mailing-list, et propose un patch. D'une part je n'ai absolument rien contre le faire d'enrichir certaines interfaces (tant que ça n'expose pas trop l'implémentation pour un module dont on peut justement vouloir changer l'implémentation dans le futur), d'autre part je ne suis pas le seul participant (plus ou moins actif) à Batteries et ce n'est pas moi qui m'occupe des libs en général, donc tu n'as pas à te soucier de mon avis pour proposer ce que tu trouves bien.

Batteries c'est un effort commun des gens qui acceptent de bosser dessus, c'est ouvert à tous les membres de la communauté OCaml, et si t'es pas satisfait de ce qui se fait, tu peux toujours venir discuter, exposer ton point de vue et participer. Là, tu es en train d'expliquer que tu n'as pas envie de participer parce que ce qui est fait jusqu'ici ne te plaît pas... contradictoire ?

Après évidemment on peut prétendre que fournir des routines sur des intervalles de clés c'est révéler une implantation à l'aide de clés totalement ordonnées. Mais ne pas le faire c'est :

Sauf que tu sais très bien que nombreuses structures ont besoin d'un ordre sur les clés, sans pour autant permettre facilement d'itérer sur un intervalle de clés donné; par exemple les leftist heaps.



Je trouve que tu prends cette discussion d'un ton un peu crispé. J'ai donné un avis général, mais ça ne veut pas dire que je suis fondamentalement opposé à tous les interfaces "pas au rabais" ! Il faut discuter au cas par cas.

[Cacophrene]

Salut !

L'argument des interfaces volumineuses n'est qu'une excuse pour le manque d'ambition.

Ce n'est pas mon avis. Il y a deux attitudes extrêmes qui mécontentent la plupart des utilisateurs :

• D'un côté, les modules minimalistes qui fournissent des fonctions vraiment très générales (et dont la présence au sein d'un module est donc largement fondée) et ne prennent pas la peine d'implémenter des fonctions un peu spécialisées mais qui font gagner un temps considérable. C'est le syndrome de la « pureté » extrême. Symptômes classiques : les utilisateurs passent leur temps à écrire une sorte de module étendu à partir de la bibliothèque qui leur est fournie.
• De l'autre, les modules-mondes qui contiennent des fonctions sur à peu près tout ce qu'on peut espérer faire (j'exagère à peine), et dont on ne fait pas le tour en six mois. C'est le syndrome du couteau suisse. Symptômes classiques : les utilisateurs avertis découvrent encore de nouvelles fonctions et/ou n'ont pas encore tout utilisé/rencontré/lu au moins une fois.

Écrire une bibliothèque qui ne se laisserait prendre à aucun de ces deux pièges, voilà quelque chose d'ambitieux. Je me permets d'emprunter à Antoine de Saint-Exupéry une phrase qui illustre très bien l'idée que je me fais d'une bibliothèque réussie : la perfection ce n'est pas quand il n'y a plus rien à ajouter, mais quand il n'y a plus rien à enlever.

Cordialement,
Cacophrène

PS : Il ne fait donc aucun doute que je trouve quelques défauts à la bibliothèque standard d'OCaml et que j'attends beaucoup (trop ?) de projets tels que Batteries.

[SpiceGuid]

@bluestorm

J'ai parlé trop vité en effet. Ta conception est la meilleure. À bien y réfléchir tu as raison, mélanger deux interfaces qui ne sont pas du même monde ça dégrade inutilement la qualité de la spécification/documentation.

Il y a deux attitudes extrêmes qui mécontentent la plupart des utilisateurs

C'est bien vrai mais la grande majorité de ce retour d'expérience provient des frameworks de POO qui sont écrits dans des langages qui ne sont pas conçus pour l'abstraction. Du coup l'utilisateur perd son temps à lire des docs alambiquées et bâclées (car pas le "coeur de métier") avant de se rendre compte que rien n'est utilisable dans son cas car le système de typage n'est de toute manière pas assez expressif pour couvrir des besoins génériques avancés.
L'ambition ce serait justement d'oser faire ce que la POO échoue à faire. Si on se concente d'opérations simples et mollement génériques, par exemple sous prétexte de simplifier l'interface, alors on ne fera pas mieux que la POO. Par exemple il ne faut pas hésiter à demander une fonction en paramètre quand c'est le moyen approprié pour booster la généricité d'une opération.

[Cacophrene]

Salut !

L'ambition ce serait justement d'oser faire ce que la POO échoue à faire. Si on se concente d'opérations simples et mollement génériques, par exemple sous prétexte de simplifier l'interface, alors on ne fera pas mieux que la POO. Par exemple il ne faut pas hésiter à demander une fonction en paramètre quand c'est le moyen approprié pour booster la généricité d'une opération.

Tout à fait d'accord. De plus l'écriture de fonctions d'ordre supérieur ne devrait pas dérouter ceux qui pratiquent un langage fonctionnel... et qui utilisent donc ladite bibliothèque.

@+
Cacophrène

[InOCamlWeTrust]

PS : Il ne fait donc aucun doute que je trouve quelques défauts à la bibliothèque standard d'OCaml et que j'attends beaucoup (trop ?) de projets tels que Batteries.

La bibliothèque contient des défauts, oui, mais elle a une grande qualité : elle est très bien écrite et pensée, sauf peut-être pour Format, qu'il faudrait refondre complètement.

A part ça, ce que je lui reproche, c'est de ne pas fournir plus de modules et fonctionnalités se rapportant aux objets (Format pourrait être repensé en POO, ça serait très sain). Sinon, l'essentiel est déjà là.

Je ne vois pas trop ce que vous lui reprochez en fait, ce que vous voudriez y incorporer (de plus), mis à part des monades qui ne servent qu'à faire joli (en OCaml).

[Cacophrene]

Salut !

La bibliothèque contient des défauts, oui, mais elle a une grande qualité : elle est très bien écrite et pensée

Oui, est c'est au quotidien une chose très agréable. Ceci dit :

Je ne vois pas trop ce que vous lui reprochez en fait, ce que vous voudriez y incorporer (de plus), mis à part des monades qui ne servent qu'à faire joli (en OCaml).

Les quelques ajouts qui me viennent à l'esprit relèvent du détail, mais j'ai souvent trouvé dommage de ne pas les voir dans la bibliothèque standard. Je pense à des choses vraiment simples comme List.iteri, Array.rev, String.map, String.find (sans utiliser Str : un algo comme Knuth-Morris-Pratt ou Boyer-Moore par exemple) et quelques fonctions de base pour le type 'a option. Rien de bien méchant ou insurmontable, mais pas toujours amusant à recoder dix fois. Et puis l'opérateur de composition (comme en Haskell, il me semble) pour utiliser un peu moins de parenthèses.

A part ça, ce que je lui reproche, c'est de ne pas fournir plus de modules et fonctionnalités se rapportant aux objets (Format pourrait être repensé en POO, ça serait très sain). Sinon, l'essentiel est déjà là.

C'est clair que ça donne vraiment l'impression que les objets sont quelque chose de vraiment à part puisqu'on n'en trouve aucune trace. Mais l'essentiel est là, c'est un fait, d'autant plus qu'il s'agit avant tout d'un projet d'origine académique (et il y a des choses plus intéressantes à faire qu'ajouter des broutilles comme ça, j'en conviens tout à fait).

Cordialement,
Cacophrène

[SpiceGuid]

Je pense à des choses vraiment simples comme List.iteri, Array.rev, String.map, String.find

et List.rev_iter, ...


D'après ce que je peux constater du côté de SML on a plutôt une approche dans le genre baltree où les implémentations sont carrément exposées pour pouvoir être réutilisées par des modules de plus haut niveau.

Par exemple le module SplayMap de SML/NJ utilise le module SplayTree) pour implanter un dictionnaire.

[SpiceGuid]

Le fichier joint contient mes implémentations de TADs, arbre binaire de recherche, dictionnaire bidirectionnel (implanté à l'aide d'un KD-tree), dictionnaire AVL, ensemble AVL, et Leftist Heap, chacun en version mutable et immutable (interconvertibles).

Merci à bluestorm à qui j'ai emprunté plusieurs bonnes idées.

• pour chaque TAD il y a 3 modules, un module Base à l'implémentation transparente et réutilisable, un module opaque Mutable pour le mutable, et un module opaque Pure pour l'immutable
• les interfaces sont moins monolithiques que celles de OCaml-Reins, elles sont fabriquées par inclusion de plusieurs petites interfaces réunies dans Interfaces.ml, par conséquent chaque aspect de l'interface d'un module est compréhensible (et implémentable) indépendamment des autres
• tous les modules fournis implémentent au moins autant d'opérations au moins aussi efficaces que leurs équivalents dans OCaml-Reins
• le module BinaryTreeMap peut servir à implanter d'autres arbres binaires de recherche (Splay-tree ou Scapegoat-tree)

Les petits plus :

• pas de routines naives comme dans la ExtLib
• tous les modules en version mutable et en version transparente et réutilisable
• la recherche avec exception (find) ou exceptionless (lookup)
• plus d'opérations rapides que OCaml-Reins: filter et subset
• plus d'opérations sur les ensembles ordonnées: rev_fold, less_fold, more_fold, interval_fold
• les opérations ensemblistes disponibles à la fois en version mutable et immutable
• possibilité d'insertion à la racine pour les arbres binaires

Les gros moins :

• largement pas testé
• moins de TAD qu'OCaml-Reins
• pas de compare pour les TADs
• pas de zippers ni d'enum

Prochains TADs : table de hachage, skew binary list, tas binomial.

[gasche]

Deux remarques après un parcours rapide (désolé de ne pas y dédier plus de temps ce soir, mais il se fait tard) :
- pas possible de compiler tes modules, on dirait que tu les utilises que dans le toplevel ? Il y a un conflit de nom entre Map et la stdlib
- tes opérations d'insertion impures sont en fait l'opération pure, suivie d'une mutation de la référence de l'arbre. On pourrait implémenter une opération d'insertion "100% impure", qui insère en place, sans passer par la phase "retour du chemin modifié"
- les "some" utilisent tous un type option, qui est caché pour mettre une exception à la place; pourquoi ne pas exposer aussi le type option ? certains préfère cela, et ici ça n'a pas de coût de performance puisque c'est naturel

[SpiceGuid]

Désolé, j'ai développé dans le top-level et je n'ai même pas essayé de compiler.
Et ça ne passe qu'avec OCaml 3.11, les version antérieures ayant de sérieux problèmes avec les modules récursifs.

Code :

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

1
2
3
4
5
6
 
#use "Property.ml";;
#use "Map.ml";;
#use "AvlTreeMap.ml";;
#use "BinaryTreeMap.ml";;
#use "BraunTreeMap.ml";;

C'est vrai aussi que c'est fait à la rache et que mon code mutable est un copier-collé du code immutable.

edit:

• some est maintenant de type option
• signature Heap et module LeftistHeap (d'après une source de Brian Hurt)