[Caml-list] Implementation of posets?

[Caml-list] Implementation of posets?

[Markus Mottl]

Hello,

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 = ...
    ...
  end

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