English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
[Caml-list] Implementation of posets?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2001-05-21 (14:13)
From: Markus Mottl <mottl@m...>
Subject: [Caml-list] Implementation of posets?

could somebody, please, point me to references of efficiently implemented
partially ordered sets (or maps)? They need not necessarily be purely
functional, but this would be preferable. It will be important that all
operations require bounded stack space only (i.e. they are composed out
of tail-recursive functions only), though I'd surely be able to transform
any other solution into this form.

What I want to do in particular is maintain a datastructure that is
parameterized over a partial order, e.g.:

  module MakePOSet (PartOrd : PARTIAL_ORDER) = struct
    type poset = ...

and allows the following operations efficiently:

  val add : PartOrd.el -> poset -> handle * poset

"add" inserts an element into the partially ordered set. "handle" should
allow me to quickly remove the associated element as in e.g.:

  val remove : handle -> poset -> poset

  val fold_top : (PartOrd.el -> 'a -> 'a) -> poset -> 'a -> 'a
  val fold_bot : (PartOrd.el -> 'a -> 'a) -> poset -> 'a -> 'a

"fold_top" folds over all top elements of the ascending chains in the
poset, "fold_bot" does so for all the bottom elements.

  val sucs : handle -> HandleSet.t
  val prds : handle -> HandleSet.t

"sucs" should give me a set of all successors of an element in the poset,
"prds" the set of all predecessors.

Especially pointers on how to soundly and efficiently manipulate
Hasse-diagrams of partially ordered sets with the "add"-operation would
probably be a good start into the right direction. Any hints one where
to find those?

Thanks a lot for your help!

Best regards,
Markus Mottl

Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr