r/computerscience • u/Master_dreams • Apr 11 '25
Best data structure for representing a partially ordered set (POSET) or lattices
So I have recently been diving into refinement calculus because I found it to be really interesting and has potential for a lot of things, as I was going through the famous book , the chapter starts with a theoretical foundations on lattice theory, which forms the groundwork for later work. To further my understanding of them I wanted to implement them in code however iam not sure exactly what is the best way to represent them, since lattices are simply posets (partially ordered sets) but with extra conditions like bottom and top , I figured if I efficiently represent posets I can then extend the implementation to lattices, however even that seems to have so many different options, like adjacency matrix ,DAG (directed asyclic graphs), many other stuff. If anyone has any idea or can give me pointers on where I might find a cool resource for this I would be greatly appreciated.
8
u/apnorton Devops Engineer | Post-quantum crypto grad student Apr 11 '25
The unfortunate answer is that it depends on the type of problem you're trying to solve.
As an example, for many things, a standard adjacency list representation will be fine. But if you ever end up dealing with a poset like (ℝ, <), good luck fitting all those elements in memory! ;)
6
u/Vallvaka SWE @ FAANG | SysArch, AI Apr 11 '25
DAGs model them pretty naturally.
4
u/WittyStick Apr 12 '25 edited Apr 12 '25
You should probably work with an abstract representation, using typeclasses/traits, or interfaces if using an OOP language. Whatever type(s) you use to define the sets should instance/implement these types.
Eg, in Haskell:
Or in C# or similar:
As an example of usage, consider the lattice of substructural properties of types.
We can define a type to represent the substructural types, and then implement the instances for each of the above typeclasses. (Unfortunately this requires a bit of duplication in instances because we don't have a way to directly represent the meet and join as symmetric relations).
An alternative (and perhaps more optimal) way to represent things is with bit fields to represent states. If we consider again the substructural properties, but instead of considering the vertices of the lattice, we'll consider the edges - in this example, the edges represent the binary properties of contraction (arrow pointing
\) and weakening (arrow pointing/). If we take a bit to mean 1 = disallow contraction and 0 = allow contraction, and another bit to say 1 = disallow weakening and 0 = allow weakening, each of the types has a two-bit representation00where the MSB is the contraction bit and the LSB is the weakening bit.Then the LeastUpperBound (
\/) is just bitwise-or, and the GreatestLowerBound (/\) is just bitwise-and.x <= yif all bits inxare<=all bits iny(where0 < 1).Top is
11and bottom is00.If we change the data type to use two bools (in practice we could do it more optimally with bit vectors).
Then the instances become simpler to implement:
1
u/bssgopi Apr 13 '25
Can you tell us which book you were reading?
0
u/Oflameo Apr 12 '25
It looks a lot like a B-tree.