At 21:18 17/11/03 +0100, rvollmert-lists@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