0N/A{- |

553N/AModule : $Header$

0N/ADescription : support for partial orders

0N/ACopyright : (c) Keith Wansbrough 200 and Uni Bremen 2005

0N/ALicense : GPLv2 or higher

0N/A

0N/AMaintainer : Christian.Maeder@dfki.de

0N/AStability : provisional

0N/APortability : portable

0N/A

0N/ASupport for partial orders

0N/A

0N/A-}

0N/A

0N/Amodule Common.Partial where

0N/A

0N/A-- | the partial order relation type

0N/Atype POrder a = a -> a -> Maybe Ordering

553N/A

553N/A-- Ord a implies a total order

553N/AtotalOrder :: Ord a => POrder a

0N/AtotalOrder x = Just . compare x

0N/A

0N/A-- | split a list of elements into equivalence classes

0N/AequivBy :: POrder a -> [a] -> [[a]]

0N/AequivBy order l = equiv0 [] l where

equiv0 = foldl add

add cs x = case cs of

[] -> [[x]]

[] : _ -> error "Partial.equivBy"

c@(y : _) : r -> case order x y of

Just EQ -> (x : c) : r

_ -> c : add r x

-- | split a set into the minimal elements and the remaining elements

minimalBy :: POrder a -> [a] -> ([a], [a])

minimalBy order es = go es [] [] where

go l ms rs = case l of

[] -> (reverse ms, reverse rs)

x : xs ->

if any (\ e -> order x e == Just GT) es

then go xs ms (x : rs)

else go xs (x : ms) rs

-- | split a set into ranks of elements, minimal first

rankBy :: POrder a -> [a] -> [[a]]

rankBy order l = case l of

[] -> []

_ -> let (xs, ys) = minimalBy order l in

xs : rankBy order ys

-- | A partial-ordering class.

class Partial a where

pCmp :: POrder a

pCmp a b =

if a <=? b

then if b <=? a then Just EQ else Just LT

else if b <=? a then Just GT else Nothing

(<=?) :: a -> a -> Bool

a <=? b = case pCmp a b of

Just o -> o <= EQ

_ -> False

equiv :: Partial a => [a] -> [[a]]

equiv = equivBy pCmp

minimal :: Partial a => [a] -> ([a], [a])

minimal = minimalBy pCmp

rank :: Partial a => [a] -> [[a]]

rank = rankBy pCmp

{- undecidable

instance Ord a => Partial a where

pCmp = totalOrder

-}