ordered (empty) → 0.1

raw patch · 6 files changed

+219/−0 lines, 6 filesdep +basesetup-changed

Dependencies added: base

Files

Data/Poset.hs +38/−0
Data/Poset/Instances.hs +40/−0
Data/Poset/Internal.hs +87/−0
LICENSE +23/−0
Setup.lhs +4/−0
ordered.cabal +27/−0

+ Data/Poset.hs view

@@ -0,0 +1,38 @@+{-+ - Copyright (C) 2009 Nick Bowler.+ -+ - License BSD2:  2-clause BSD license.  See LICENSE for full terms.+ - This is free software: you are free to change and redistribute it.+ - There is NO WARRANTY, to the extent permitted by law.+ -}++-- | 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 a 'PosetOrd' class which extends 'Prelude.Ord' by adding+-- a 'NComp' constructor representing that two elements are+-- incomparable.+module Data.Poset (+    Poset(..), +    PosetOrd(..),+    module Data.Poset+) where++import Data.Poset.Instances+import Data.Poset.Internal++import Data.Function+import Data.Monoid++instance Poset a => Poset (Maybe a) where+    Just x  `leq` Just y = x `leq` y+    Nothing `leq` _      = True+    _       `leq` _      = False++instance Poset a => Poset [a] where+    posetCmp = (mconcat .) . zipWith posetCmp++-- | Apply a function to values before comparing.+comparing :: Poset b => (a -> b) -> a -> a -> PosetOrd+comparing = on posetCmp

+ Data/Poset/Instances.hs view

@@ -0,0 +1,40 @@+{-+ - Copyright (C) 2009-2010 Nick Bowler.+ -+ - License BSD2:  2-clause BSD license.  See LICENSE for full terms.+ - This is free software: you are free to change and redistribute it.+ - There is NO WARRANTY, to the extent permitted by law.+ -}++-- | 'Poset' for instances of 'Prelude.Ord'+{-# LANGUAGE CPP #-}+module Data.Poset.Instances where++import qualified Data.Poset.Internal as Poset+import Data.Poset.Internal (Poset, partialOrder)++import Data.Ratio+import Data.List+import Data.Word+import Data.Int++#define POSET_ORD_INSTANCE(ctx, v) instance ctx Poset (v) where { \+    posetCmp = (partialOrder .) . compare; \+    (<==>)  = const $ const True; \+    (</=>)  = const $ const False }++POSET_ORD_INSTANCE(, Bool)+POSET_ORD_INSTANCE(, Char)+POSET_ORD_INSTANCE(, Int)+POSET_ORD_INSTANCE(, Int8)+POSET_ORD_INSTANCE(, Int16)+POSET_ORD_INSTANCE(, Int32)+POSET_ORD_INSTANCE(, Int64)+POSET_ORD_INSTANCE(, Word)+POSET_ORD_INSTANCE(, Word8)+POSET_ORD_INSTANCE(, Word16)+POSET_ORD_INSTANCE(, Word32)+POSET_ORD_INSTANCE(, Word64)+POSET_ORD_INSTANCE(, Integer)++POSET_ORD_INSTANCE(Integral a =>, Ratio a)

+ Data/Poset/Internal.hs view

@@ -0,0 +1,87 @@+{-+ - Copyright (C) 2009-2010 Nick Bowler.+ -+ - License BSD2:  2-clause BSD license.  See LICENSE for full terms.+ - This is free software: you are free to change and redistribute it.+ - There is NO WARRANTY, to the extent permitted by law.+ -}++module Data.Poset.Internal where++import Data.Monoid++-- | Are two elements of the underlying comparabale or not; if they+-- are, then Ordering tell the relation between them.+data PosetOrd = Comp Ordering | NComp+    deriving (Eq, Show, Read)++instance Bounded PosetOrd where+    minBound = Comp $ minBound +    maxBound = NComp++instance Enum PosetOrd where+    toEnum n | n >= 0 && n < 3 = Comp $ toEnum n+             | n == 3 = NComp+             | otherwise = error "Data.Poset.toEnum: bad argument"++    fromEnum (Comp c) = fromEnum c+    fromEnum NComp = 3++-- Lexicographic ordering.++instance Monoid PosetOrd where+    mempty = Comp EQ+    mappend (Comp EQ) x = x+    mappend NComp _ = NComp+    mappend (Comp LT) _ = Comp LT+    mappend (Comp GT) _ = Comp GT++-- | Internal-use function to convert the ordinary Ordering to ours.+partialOrder :: Ordering -> PosetOrd+partialOrder = Comp++-- | Class for partially ordered data types.  Instances should satisfy the+-- following laws for all values a, b and c:+--+-- * @a `leq` a@.+--+-- * @a `leq` b@ and @b `leq` a@ implies @a == b@.+--+-- * @a `leq` b@ and @b `leq` c@ implies @a `leq` c@.+--+-- But note that the floating point instances don't satisfy the first rule.+--+-- Minimal definition: posetCmp or leq.+class Eq a => Poset a where+    posetCmp :: a -> a -> PosetOrd+    -- | Is comparable to.+    (<==>)  :: a -> a -> Bool+    -- | Is not comparable to.+    (</=>)  :: a -> a -> Bool+    -- | Less than or equal.+    leq :: a -> a -> Bool+    -- | Greater than or equal.+    geq :: a -> a -> Bool+    -- | Strict less than.+    lt :: a -> a -> Bool+    -- | Strict greater than.+    gt :: a -> a -> Bool++    a `posetCmp` b+        | a == b = Comp EQ+        | a `leq` b = Comp LT+        | b `leq` a = Comp GT+        | otherwise = NComp++    a <==> b = a `posetCmp` b /= NComp+    a </=> b = a `posetCmp` b == NComp++    a `lt` b = a `posetCmp` b == Comp LT+    a `gt` b = a `posetCmp` b == Comp GT++    a `leq` b | a <==> b = a `posetCmp` b /= Comp GT+              | otherwise = False+    a `geq` b | a <==> b = a `posetCmp` b /= Comp LT+              | otherwise = False++infixl 4 <==>,</=>

+ LICENSE view

@@ -0,0 +1,23 @@+Copyright (c) 2009 Nick Bowler+All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++1. Redistributions of source code must retain the above copyright notice,+   this list of conditions and the following disclaimer.+2. Redistributions in binary form must reproduce the above copyright+   notice, this list of conditions and the following disclaimer in the+   documentation and/or other materials provided with the distribution.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE+ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE+LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR+CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF+SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS+INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN+CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)+ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE+POSSIBILITY OF SUCH DAMAGE.

+ Setup.lhs view

@@ -0,0 +1,4 @@+#!/usr/bin/env runhaskell++> import Distribution.Simple+> main = defaultMain

+ ordered.cabal view

@@ -0,0 +1,27 @@+Name:               ordered+Version:            0.1+License:            OtherLicense+License-File:       LICENSE+Cabal-Version:      >= 1.6+Author:             Nick Bowler, Miguel Pagano+Maintainer:         miguel.pagano@gmail.org+Stability:          experimental+Category:           Mathematics+Build-Type:         Simple+Synopsis:           A definition of Posets.+Description:+	A library defining the notion of Poset.+++Source-repository head+  type:     git+  location: http://github.com/miguelpagano/ordered++Library+    Build-Depends: base >= 4 && < 5+    Include-Dirs: .+    Exposed-Modules:+        Data.Poset+    Other-Modules:+        Data.Poset.Internal,+        Data.Poset.Instances