[Caml-list] Simuler les vues avec des variantes polymorphes

[Caml-list] Simuler les vues avec des variantes polymorphes

[Diego Olivier Fernandez Pons]

    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

Re: [Caml-list] Simuler les vues avec des variantes polymorphes

[Jacques Garrigue]

From: Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr>
> type 'a heapView =
>   [ `Empty
>   | `Single of 'a * int
>   | `Link of 'a prioritySQ * 'a prioritySQ ]
[...]
> 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) 

Je ne suis pas sur de tout comprendre, mais si le type de
to_heap_view est : 'a otherView -> 'a heapView
et si otherView est aussi un type de variant polymorphe, alors on peut
deja ecrire

    | #otherView as other -> insert x p (to_heap_view other)

Est-ce le comportement desire'?
Attention, si ton let ci-dessus est en fait un let rec, il faut
peut-etre ecrire:
    (to_heap_view other : ['a heapView] :> [> 'a heapView])
pour eviter d'unifier le resultat de to_heap_view a` l'entree de
insert.

> 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)

Et quid des types pas encore declares?
L'idee des variants polymorphes est de se debarasser des declarations
prealables.
Mais on peut toujours ecrire des declarations a` posteriori:

   type 'a anyView = ['a heapView | 'a otherView]

---------------------------------------------------------------------------
Jacques Garrigue      Kyoto University     garrigue at kurims.kyoto-u.ac.jp
		<A HREF=http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/>JG</A>

-------------------
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

Re: [Caml-list] Simuler les vues avec des variantes polymorphes

[Diego Olivier Fernandez Pons]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1819 bytes --]

Jacques Garrigue a écrit :

> Je ne suis pas sur de tout comprendre, mais si le type de

Désolé, j'envoie du code désormais

> Et quid des types pas encore declares?
> L'idee des variants polymorphes est de se debarasser des declarations
> prealables.
> Mais on peut toujours ecrire des declarations a` posteriori:
> 
>    type 'a anyView = ['a heapView | 'a otherView]
> 

En réalité, comme je ne restreins pas le type de mes fonctions dans le
code source (mais seulement dans le mli), l'interpréteur ne prend pas
en compte mes déclarations (que je ne fais que pour convenance
personnelle afin de pouvoir éventuellement vérifier la conformité des
types inférés avec ce que j'attends) 

Au demeurant, je pensais que l'idée des variantes polymorphes, plus
que débarasser le programmeur des déclarations préalables était de
permettre l'écriture incrémentielle de code (par exemple plusieurs
programmeurs qui piochent dans un flot de données les valeurs qu'ils
peuvent traiter et laissent les autres)

Enfin, la documentation sur les variantes polymorphes est assez
succinte, par exemple elle n'aborde pas le cas où un constructeur est
à la fois marqué d'un < et d'un > (alors que c'est le type de la
première fonction dans mon code, j'ai dû me reporter au livre
"développement d'applications en Objective Caml") 

Je suis vraiment loin d'avoir complètement compris le fonctionnement
des variantes polymorphes : à la vue du premier exemple de la section
"Avanced use"

# let f = function `A -> `C | x -> x ;;
val f : ([> `A | `C] as 'a) -> 'a

# f `E;;
- : _ [> `A | `C | `E] = `E

je m'imaginais donc que

# let f = function `A -> 1 | _ -> 0 ;;
# let x = `E in (f x, x) ;;

me répondrait - : int * _[> `A | `E] = (0, `E)
or il répond int * _[>`E]

        Diego Olivier

[-- Attachment #2: code --]
[-- Type: APPLICATION/octet-stream, Size: 1850 bytes --]