The Domain (Co)Monad

93 Views Asked by At

Many different kinds of data structures can be captured as Monads. Lists and trees are two good examples. A domain (dcpo) is like a tree, with extra axioms.

Definition. A directed subset of a partially ordered set is a nonempty subset which contains an upper bound for every pair of elements in it. A domain or dcpo (directed-complete partial order) is a partially ordered set such that every directed subset has a supremum.

Can Domains be encoded as a monad or comonad?

My intuition is telling me you can get both based on this paper.

From that paper, we see that trees can be comonads by labelling the nodes with the tree rooted at that node. That would be the comultiplication, creating a tree of trees. This should apply directly to domains, we just take each upper bound and label it with the set of points lower than the upper bound and likewise for the lower bounds.

This should be a monad on Set, so a triple $\{ Dom, \mu, \eta \}$, where

$$Dom :Set \rightarrow Set$$ $$\mu : Dom \cdot Dom \rightarrow Dom$$ $$\eta : 1_{Set} \rightarrow Dom$$