Subsumption in partially ordered sets

[Graham Klyne]

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?

Er, yes!

>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.

Thanks!

#g


------------
Graham Klyne
For email:
http://www.ninebynine.org/#Contact