Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] Simuler les vues avec des variantes polymorphes
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@c...>
Subject: [Caml-list] Simuler les vues avec des variantes polymorphes
    Bonjour,

Il y a eu plusieurs messages sur les vues dans la liste Caml
récemment, alors j'ai codé une implémentation des arbres de recherche
pondérés (Hinze 2001) simulant le mécanisme des vues à l'aide des
variantes polymorphes - c'est la seule structure de donnée que je
connaisse où cela apporte réellement une simplification du code -

En gros, un arbre de recherche pondéré est une structure hybride entre
les arbres de recherche binaires et les semi-tas

type 'a prioritySQ = 
  [ `Empty 
  | `Single of 'a * int 
  | `Pennant of `a * int * `a tree * `a ]

type 'a heapView =
  [ `Empty
  | `Single of 'a * int
  | `Link of 'a prioritySQ * 'a prioritySQ ]

Les fonctions utilisent l'une ou l'autre représentation selon leur
convenance en appelant si nécessaire les fonctions de transformations
entre vues avant le filtrage de motifs. 

let insert x p = function psq ->
  match heap_view psq with
    | `Empty -> ...
    | `Single _ -> ...
    | `Link _ -> ...

Seulement je ne peux par faire ceci

let insert x p = function
  | `Empty -> ...
  | `Single _ -> ...
  | `Link _ -> ...
  | other -> insert x p (to_heap_view other)

car le typeur n'accepte pas le mélange des types (je peux toujours
mettre tous les constructeurs dans un seul type il est vrai mais ce
n'est pas très propre) 

Est-il possible de concevoir des variantes polymorphes où le typeur
accepterait des unions de types ? (en ce sens qu'au lieu de typer une
fonction par les générateurs i.e. "tout type contenant Empty" ... il
la type par union de tous les types déclarés qui contiennent Empty)


        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners