Data/Poset.hs

   1 {-
   2  - Copyright (C) 2009 Nick Bowler.
   3  -
   4  - License BSD2:  2-clause BSD license.  See LICENSE for full terms.
   5  - This is free software: you are free to change and redistribute it.
   6  - There is NO WARRANTY, to the extent permitted by law.
   7  -}
   8
   9 -- | Partially ordered data types.  The standard 'Prelude.Ord' class is for
  10 -- total orders and therefore not suitable for floating point.  However, we can
  11 -- still define meaningful 'max' and 'sort' functions for these types.
  12 --
  13 -- We define our own 'Ord' class which is intended as a replacement for
  14 -- 'Prelude.Ord'.  However, in order to take advantage of existing libraries
  15 -- which use 'Prelude.Ord', we make every instance of 'Ord' an instance of
  16 -- 'Prelude.Ord'.  This is done using the OverlappingInstances and
  17 -- UndecidableInstances extensions -- it remains to be seen if problems occur
  18 -- as a result of this.
  19 module Data.Poset (
  20     Poset(..), Sortable(..), Ordering(..), Ord,
  21     module Data.Poset
  22 ) where
  23
  24 import qualified Prelude
  25 import Prelude hiding (Ord(..), Ordering(..))
  26 import Data.Poset.Instances
  27 import Data.Poset.Internal
  28
  29 import Data.Function
  30 import Data.Monoid
  31
  32 instance Poset a => Poset (Maybe a) where
  33     Just x  <= Just y = x <= y
  34     Nothing <= _      = True
  35     _       <= _      = False
  36
  37 instance Poset a => Poset [a] where
  38     compare = (mconcat .) . zipWith compare
  39
  40 -- | Sort a list using the default comparison function.
  41 sort :: Sortable a => [a] -> [a]
  42 sort = sortBy compare
  43
  44 -- | Apply a function to values before comparing.
  45 comparing :: Poset b => (a -> b) -> a -> a -> Ordering
  46 comparing = on compare