caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
From: Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr>
To: caml-list@inria.fr
Subject: [Caml-list] Simuler les vues avec des variantes polymorphes
Date: Wed, 14 Aug 2002 10:37:25 +0200 (DST)	[thread overview]
Message-ID: <Pine.A32.3.95.1020814103006.46622E-100000@ibm1.cicrp.jussieu.fr> (raw)

    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


             reply	other threads:[~2002-08-14  8:40 UTC|newest]

Thread overview: 3+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2002-08-14  8:37 Diego Olivier Fernandez Pons [this message]
2002-08-16  5:16 ` Jacques Garrigue
2002-08-21  8:37   ` Diego Olivier Fernandez Pons

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=Pine.A32.3.95.1020814103006.46622E-100000@ibm1.cicrp.jussieu.fr \
    --to=diego-olivier.fernandez-pons@cicrp.jussieu.fr \
    --cc=caml-list@inria.fr \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).