Subsumption in partially ordered sets

rvollmert-lists at rvollmert-lists at
Mon Nov 17 21:18:04 EST 2003

> I have a need for an algorithm to perform "subsumption" on partially
> ordered sets of values. That is, given a selection of values from a
> partially ordered set, remove all values from the collection that
> are less than some other member of the collection.

That is, you want the maxima, right?

The following seems to work, though I don't know how efficient it is.

maxima :: (Eq a) => [[Maybe a]] -> [[Maybe a]]
maxima es = maxima' [] es
    where maxima' ms []     = ms
          maxima' ms (e:es) = maxima' (add ms e) es
          add []     e = [e]
          add (m:ms) e = case pcompare m e of PNR -> m:(add ms e)
                                              PGT -> m:ms
                                              PLT -> add ms e
                                              PEQ -> m:ms


More information about the Haskell-Cafe mailing list