POMAP  Partially Ordered Maps for OCaml
What is Pomap
?
The Pomaplibrary maintains purely functional maps of partially ordered elements. Partially ordered maps are similar to partially ordered sets, but map values for which a partial order relation is defined to some arbitrary other values. Here is an example for a partially ordered set to visualize the idea:
Whereas total orders allow you to say whether some element is smaller than, equal to, or greater than another one, partial orders also allow for a "don't know" or "undefined"case.
Mathematically speaking, the axioms that hold for a partial order relation are the following:
x <= x (reflexivity)
x <= y /\ y <= x > x = y (antisymmetry)
x <= y /\ y <= z > x <= z (transitivity)
Total orders, as usually used for "normal" maps that programmers are acquainted with, would additionally require the following axiom:
x <= y \/ y <= x (totality)
Whereas a total order allows you to align elements in a linear way to exhibit
this order relation (e.g. [1; 3; 7; 42]
), partial orders are usually
represented by graphs (socalled Hassediagrams). Here is another example:
(89,73) (93,21)

(91,38) (57,42)
 / 
 / 
(44,26) (25,42)
\ /
(22,23)
The elements of this example partial order structure are pairs of integers. We say that an element (a pair) is larger than another one if both of its integers are larger then the respective integers in the other pair. If both integers are smaller, then the pair is smaller, and if the two pairs contain equal elements, they are equal. If none of the above holds e.g. if the first element of the first pair is smaller than the corresponding one of the second pair and the second element of the first pair is greater than its corresponding element of the second pair, then we cannot say that either of the pairs is greater or smaller, i.e. the order is "unknown" (e.g. pairs (44,26) and (25,42)).
Lines connecting elements indicate the order of the elements: the greater element is above the smaller element. Hassediagrams do not display the order if it is implied by transitivity. E.g. there is no separate line for the elements (89,73) and (25,42). If elements cannot be reached on lines without reversing direction, then they cannot be compared. E.g. the pair (93,21) is incomparable to all others whereas (44,26) cannot be compared to this latter pair and to (25,42) only.
This library internally represents relations between known elements similar to Hassediagram. This allows you to easily reason about or quickly manipulate such structures.
Sounds too mathematical so far? There are many uses for such a library!
Application areas
Datamining
Concept lattices obey rules similar to partial orders and can also be handled using this library. E.g., you might have a big ecommerce site with lots of products. For marketing purposes it would be extremely useful to know product baskets that people frequently buy. This is equivalent to asking where in a Hassediagram such baskets might be placed.
Or imagine you develop a medical system that automatically associates different mixes of medication with illnesses they effectively treat to support doctors in deciding on a therapy. This can all be addressed with concept lattices.
Software engineering
Refactoring software to reduce complexity is an important task for large software projects. If you have many different components that implement many different features, you might want to know whether there are groups of components that make use of specific features in other components. You could then find out whether the current form of abstraction exactly meets these dependencies, possibly learning that you should factor out a set of features in a separate module to reduce overall complexity.
Databases
Partial order structures represented by Hassediagrams can be used to optimize database queries on multivalued attributes by providing better ways of indexing.
General problemsolving
For general problemsolving we often need at least to know whether some solution is better, equal to, worse or incomparable to another. Given a large number of known solutions, the partial order structure containing the elements can be used to draw conclusions about e.g. whether their particular form (syntax) implies anything about their position in the partial order (semantic aspect).
What advantages does this particular library offer?
Referential transparency
The currently implemented functions all handle the data structure in a purely functional way. This allows you to hold several versions of a data structure in memory while benefiting from structure sharing. This makes backing out changes to the data structure efficient and straightforward and also allows you to use the library safely in a multithreaded environment.
Incremental updates
Some algorithms only perform batch generation of Hassediagrams: once the diagram has been computed, one cannot use such algorithms to add further elements to it incrementally. This library can handle incremental updates (adding and removing of elements) fairly efficiently as required for onlineproblems.
Efficiency
Both time and memory consumption seem suitable for practical problems, even not so small ones. Building up the Hassediagram for 1000 elements of a moderately complex partial order should usually take less than a second with native code on modern machines.
Usage
APIdocumentation
Please refer to the APIdocumentation as programming reference, which
is built during installation with make doc
. It can also be found
online.
Specification of the partial order relation
All you need to provide is the function that computes the partial order
relation between two elements. Take a look at the signature PARTIAL_ORDER
in file lib/pomap_intf.ml
:
module type PARTIAL_ORDER = sig
type el
type ord = Unknown  Lower  Equal  Greater
val compare : el > el > ord
end
You only have to specify the type of elements of the partially ordered
structure and a comparison function that returns Unknown
if the elements
are not comparable, Lower
if the first element is lower than the second,
Equal
when they are equal and Greater
if the first element is greater
than the second one. You can find example implementations of such modules
in directory examples/hasse/po_examples.ml
.
Creating and using partially ordered maps
Given the specification, e.g. MyPO
, of a partial order relation, we can
now create a map of partially ordered elements like this:
module MyPOMap = Pomap_impl.Make(MyPO)
The interface specification POMAP
in file lib/pomap_intf.ml
documents in
detail all the functions that can be applied to partially ordered maps and
objects they maintain. The important aspect is that information is stored in
nodes: you can access the key on which the partial order relation is defined,
the associated data element, the set of indices of successors and the set
of indices of predecessors. Fresh indices are generated automatically for
new nodes.
Together with accessors to the indices of the bottommost and topmost nodes in the partially ordered map, this allows for easy navigation in the associated Hassediagram.
Rendering Hassediagrams using the dotutility
The Pomaplibrary also contains modules that allow you to easily render
Hassediagrams given some partially ordered map and prettyprinting
functions for elements. This requires installation of the
Graphviz package, which supplies the needed
dot
utility. The use of these modules is demonstrated in the distributed
hasse
example, which comes with its own README.
Contact Information and Contributing
In the case of bugs, feature requests, contributions and similar, you can contact me here: markus.mottl@gmail.com
Uptodate information should be available at: http://mmottl.github.io/pomap
Enjoy!
Markus Mottl on July 10, 2012