{- |
Module      :  $Header$
Description :  support for partial orders
Copyright   :  (c) Keith Wansbrough 200 and Uni Bremen 2005
License     :  GPLv2 or higher, see LICENSE.txt

Maintainer  :  Christian.Maeder@dfki.de
Stability   :  provisional
Portability :  portable

Support for partial orders

-}

module Common.Partial where

-- | the partial order relation type
type POrder a = a -> a -> Maybe Ordering

-- Ord a implies a total order
totalOrder :: Ord a => POrder a
totalOrder x = Just . compare x

-- | split a list of elements into equivalence classes
equivBy :: POrder a -> [a] -> [[a]]
equivBy 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
-}
