Saturday, August 11, 2012

The lattice of multisets

The join operation in the multiset lattice is provided by taking the maximum value of each key present in any of the multisets and the meet operation is provided by taking the corresponding minimum value.
(defn join-multisets-by
  ([] {})
  ([a] a)
  ([a b]
    (apply merge
        (fn [key]
            (if (contains? a key) (get a key) 0)
            (if (contains? b key) (get b key) 0)))
        (clojure.set/union (keys a) (keys b))))
  ([a b & more] (reduce func (func a b) more))))
(def join-multisets (join-multisets-by max))
(def meet-multisets (join-multisets-by min))
Sets can be defined as a particular type of multisets whose values are all equal to one, as such the set lattice is a sublattice of the multiset lattice dealing with just sets. On the other hand, multisets can be represented as sets by replacing the value for each key with an interval set from the minimal value to that number. All distributive lattices can be represented in terms of the multiset lattice.

No comments:

Post a Comment