2 - Copyright (C) 2009-2010 Nick Bowler.
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.
9 {-# LANGUAGE FlexibleInstances, OverlappingInstances, UndecidableInstances #-}
10 module Data
.Poset
.Internal
where
12 import qualified Data
.List
as List
13 import qualified Prelude
14 import Prelude
hiding (Ordering(..), Ord
(..))
18 data Ordering = LT | EQ | GT | NC
19 deriving (Eq
, Show, Read, Bounded
, Enum
)
21 -- Lexicographic ordering.
22 instance Monoid
Ordering where
29 -- | Internal-use function to convert our Ordering to the ordinary one.
30 totalOrder
:: Ordering -> Prelude
.Ordering
31 totalOrder LT
= Prelude
.LT
32 totalOrder EQ
= Prelude
.EQ
33 totalOrder GT
= Prelude
.GT
34 totalOrder NC
= error "Uncomparable elements in total order."
36 -- | Internal-use function to convert the ordinary Ordering to ours.
37 partialOrder
:: Prelude
.Ordering -> Ordering
38 partialOrder Prelude
.LT
= LT
39 partialOrder Prelude
.EQ
= EQ
40 partialOrder Prelude
.GT
= GT
42 -- | Class for partially ordered data types. Instances should satisfy the
43 -- following laws for all values a, b and c:
47 -- * @a <= b@ and @b <= a@ implies @a == b@.
49 -- * @a <= b@ and @b <= c@ implies @a <= c@.
51 -- But note that the floating point instances don't satisfy the first rule.
53 -- Minimal complete definition: 'compare' or '<='.
54 class Eq a
=> Poset a
where
55 compare :: a
-> a
-> Ordering
56 -- | Is comparable to.
57 (<==>) :: a
-> a
-> Bool
58 -- | Is not comparable to.
59 (</=>) :: a
-> a
-> Bool
61 (<=) :: a
-> a
-> Bool
62 (>=) :: a
-> a
-> Bool
71 a
< b
= a `
compare` b
== LT
72 a
> b
= a `
compare` b
== GT
73 a
<==> b
= a `
compare` b
/= NC
74 a
</=> b
= a `
compare` b
== NC
75 a
<= b
= a
< b || a `
compare` b
== EQ
76 a
>= b
= a
> b || a `
compare` b
== EQ
78 -- | Class for partially ordered data types where sorting makes sense.
79 -- This includes all totally ordered sets and floating point types. Instances
80 -- should satisfy the following laws:
82 -- * The set of elements for which 'isOrdered' returns true is totally ordered.
84 -- * The max (or min) of an insignificant element and a significant element
85 -- is the significant one.
87 -- * The result of sorting a list should contain only significant elements.
89 -- * @max a b@ = @max b a@
91 -- * @min a b@ = @min b a@
93 -- The idea comes from floating point types, where non-comparable elements
94 -- (NaNs) are the exception rather than the rule. For these types, we can
95 -- define 'max', 'min' and 'sortBy' to ignore insignificant elements. Thus, a
96 -- sort of floating point values will discard all NaNs and order the remaining
99 -- Minimal complete definition: 'isOrdered'
100 class Poset a
=> Sortable a
where
101 sortBy :: (a
-> a
-> Ordering) -> [a
] -> [a
]
102 isOrdered
:: a
-> Bool
106 sortBy f
= List
.sortBy ((totalOrder
.) . f
) . filter isOrdered
107 max a b
= case a `
compare` b
of
111 NC
-> if isOrdered a
then a
else if isOrdered b
then b
else a
112 min a b
= case a `
compare` b
of
116 NC
-> if isOrdered a
then a
else if isOrdered b
then b
else a
118 -- | Class for totally ordered data types. Instances should satisfy
119 -- @isOrdered a = True@ for all @a@.
120 class Sortable a
=> Ord a
122 -- This hack allows us to leverage existing data structures defined in terms
124 instance Data
.Poset
.Internal
.Ord a
=> Prelude
.Ord a
where
125 compare = (totalOrder
.) . compare