-- | Partially ordered data types. The standard 'Prelude.Ord' class is for
-- total orders and therefore not suitable for floating point.
-- However, we can still define meaningful 'max' and 'sort' functions for these types.
--
-- We define our own 'Ord' class which is intended as a replacement for
-- 'Prelude.Ord'. However, in order to take advantage of existing libraries
-- which use 'Prelude.Ord', we make every instance of 'Ord' an instance of
-- 'Prelude.Ord'. This is done using the OVERLAPS and UndecidableInstances
-- extensions -- it remains to be seen if problems occur as a result of this.
module Data.Poset
       ( Poset(..), Sortable(..), Ordering(..), Ord,
         module Data.Poset
       ) where

import qualified Prelude
import Prelude hiding (Ord(..), Ordering(..))
import qualified Data.List as List
import Data.Poset.Instances
import Data.Poset.Internal

import Data.Function
import Data.Monoid

instance Poset a => Poset (Maybe a) where
  Just a
x  <= :: Maybe a -> Maybe a -> Bool
<= Just a
y  = a
x a -> a -> Bool
forall a. Poset a => a -> a -> Bool
<= a
y
  Maybe a
Nothing <= Maybe a
_       = Bool
True
  Maybe a
_       <= Maybe a
_       = Bool
False

instance Poset a => Poset [a] where
  compare :: [a] -> [a] -> Ordering
compare = ([Ordering] -> Ordering
forall a. Monoid a => [a] -> a
mconcat ([Ordering] -> Ordering) -> ([a] -> [Ordering]) -> [a] -> Ordering
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) (([a] -> [Ordering]) -> [a] -> Ordering)
-> ([a] -> [a] -> [Ordering]) -> [a] -> [a] -> Ordering
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Ordering) -> [a] -> [a] -> [Ordering]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith a -> a -> Ordering
forall a. Poset a => a -> a -> Ordering
compare

-- | Sort a list using the default comparison function.
sort :: Sortable a => [a] -> [a]
sort :: [a] -> [a]
sort = (a -> a -> Ordering) -> [a] -> [a]
forall a. Sortable a => (a -> a -> Ordering) -> [a] -> [a]
sortBy a -> a -> Ordering
forall a. Poset a => a -> a -> Ordering
compare

-- | Sort a list using (isOrder, compare).
sortBy' :: ((a -> Bool), (a -> a -> Ordering)) -> [a] -> [a]
sortBy' :: (a -> Bool, a -> a -> Ordering) -> [a] -> [a]
sortBy' (a -> Bool
p, a -> a -> Ordering
f) = (a -> a -> Ordering) -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
List.sortBy ((Ordering -> Ordering
totalOrder(Ordering -> Ordering) -> (a -> Ordering) -> a -> Ordering
forall b c a. (b -> c) -> (a -> b) -> a -> c
.)((a -> Ordering) -> a -> Ordering)
-> (a -> a -> Ordering) -> a -> a -> Ordering
forall b c a. (b -> c) -> (a -> b) -> a -> c
.a -> a -> Ordering
f) ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter a -> Bool
p

-- | Apply a function to values before comparing.
comparing :: Poset b => (a -> b) -> a -> a -> Ordering
comparing :: (a -> b) -> a -> a -> Ordering
comparing = (b -> b -> Ordering) -> (a -> b) -> a -> a -> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
on b -> b -> Ordering
forall a. Poset a => a -> a -> Ordering
compare