From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id QAA14641; Mon, 21 May 2001 16:13:01 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA14635 for <caml-list@pauillac.inria.fr>; Mon, 21 May 2001 16:13:00 +0200 (MET DST)
Received: from miss.wu-wien.ac.at (miss.wu-wien.ac.at [137.208.107.17])
	by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f4LECxv13641
	for <caml-list@inria.fr>; Mon, 21 May 2001 16:12:59 +0200 (MET DST)
Received: (from mottl@localhost)
	by miss.wu-wien.ac.at (8.9.0/8.9.0) id QAA31673
	for caml-list@inria.fr; Mon, 21 May 2001 16:12:53 +0200 (MET DST)
Date: Mon, 21 May 2001 16:12:52 +0200
From: Markus Mottl <mottl@miss.wu-wien.ac.at>
To: OCAML <caml-list@inria.fr>
Subject: [Caml-list] Implementation of posets?
Message-ID: <20010521161252.A8457@miss.wu-wien.ac.at>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.2.5i
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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