pomap
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 neededdot
utility. The use of these modules is demonstrated in the distributedhasse
example, which comes with its own README.
Contact Information and Contributing
Please submit bugs reports, feature requests, contributions and similar to
the GitHub issue tracker.
Uptodate information is available at: https://mmottl.github.io/pomap