Subsumption in partially ordered sets
GK at ninebynine.org
Tue Nov 18 11:00:53 EST 2003
At 21:18 17/11/03 +0100, rvollmert-lists at gmx.net wrote:
> > 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.
This looks much nicer. On inspection I think it's at least as efficient as
mine, and I think it also preserves ordering.
>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
If I fold this together with Tom's suggestions, I think the result is much
closer to what I felt I should be getting.
More information about the Haskell-Cafe