bimap 0.3.2 → 0.5.0
raw patch · 3 files changed
Files
- Data/Bimap.hs +48/−7
- Data/BimapExt.hs +16/−0
- bimap.cabal +22/−6
Data/Bimap.hs view
@@ -1,3 +1,9 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE DeriveGeneric #-}+#if __GLASGOW_HASKELL__ >= 708+{-# LANGUAGE TypeFamilies #-}+#endif+ {-| An implementation of bidirectional maps between values of two key types. A 'Bimap' is essentially a bijection between subsets of@@ -30,6 +36,8 @@ lookupR, (!), (!>),+ (!?),+ (!?>), -- * Construction empty, singleton,@@ -87,13 +95,20 @@ twisted, ) where +import Control.DeepSeq (NFData) import Control.Monad.Catch +import Data.Function (on) import Data.List (foldl', sort) import qualified Data.Map as M import Data.Maybe (fromMaybe) import Data.Typeable +#if __GLASGOW_HASKELL__ >= 708+import qualified Data.BimapExt as GHCExts+#endif+import GHC.Generics (Generic)+ import Prelude hiding (filter, lookup, null, pred) import qualified Prelude as P @@ -105,14 +120,26 @@ {-| A bidirectional map between values of types @a@ and @b@. -}-data Bimap a b = MkBimap !(M.Map a b) !(M.Map b a)+data Bimap a b = MkBimap !(M.Map a b) !(M.Map b a) deriving (Generic) instance (Show a, Show b) => Show (Bimap a b) where show x = "fromList " ++ (show . toList $ x) instance (Eq a, Eq b) => Eq (Bimap a b) where- (==) bx by = toAscList bx == toAscList by+ (==) = (==) `on` toAscList +instance (Ord a, Ord b) => Ord (Bimap a b) where+ compare = compare `on` toAscList++instance (NFData a, NFData b) => NFData (Bimap a b)++#if __GLASGOW_HASKELL__ >= 708+instance (Ord a, Ord b) => GHCExts.IsList (Bimap a b) where+ type Item (Bimap a b) = (a, b)+ fromList = fromList+ toList = toList+#endif+ {-| A 'Bimap' action failed. -}@@ -321,6 +348,9 @@ This function will @return@ the result in the monad, or @fail@ if the value isn't in the bimap. +Note that the signature differs slightly from Data.Map's @lookup@. This one is more general -+it functions the same way as the "original" if @m@ is cast (or inferred) to Maybe.+ /Version: 0.2/-} lookup :: (Ord a, Ord b, MonadThrow m) => a -> Bimap a b -> m b@@ -332,6 +362,8 @@ {-| /O(log n)/. A version of 'lookup' that is specialized to the right key, and returns the corresponding left key.++ /Version: 0.2/-} lookupR :: (Ord a, Ord b, MonadThrow m) => b -> Bimap a b -> m a@@ -354,6 +386,16 @@ (!>) :: (Ord a, Ord b) => Bimap a b -> b -> a (!>) bi y = fromMaybe (error "Data.Bimap.(!>): Right key not found") $ lookupR y bi +{-| /O(log n)/.+See 'lookup'. -}+(!?) :: (Ord a, Ord b, MonadThrow m) => Bimap a b -> a -> m b+(!?) = flip lookup++{-| /O(log n)/.+See 'lookupR'. -}+(!?>) :: (Ord a, Ord b, MonadThrow m) => Bimap a b -> b -> m a+(!?>) = flip lookupR+ {-| /O(n*log n)/. Build a map from a list of pairs. If there are any overlapping pairs in the list, the later ones will override the earlier ones.@@ -600,7 +642,7 @@ /Version: 0.2.2/-} deleteMax :: (Ord b) => Bimap a b -> Bimap a b deleteMax = snd . deleteFindMax- + {-| /O(log n)/. Delete the element with maximal right key. Calls @'error'@ if the bimap is empty.@@ -616,7 +658,7 @@ findMax = M.findMax . toMap {-| /O(log n)/.-Find the element with maximal right key. The +Find the element with maximal right key. The right-hand key is the first entry in the pair. Calls @'error'@ if the bimap is empty. /Version: 0.2.2/-}@@ -646,7 +688,7 @@ /Version: 0.2.2/-} deleteMin :: (Ord b) => Bimap a b -> Bimap a b deleteMin = snd . deleteFindMin- + {-| /O(log n)/. Delete the element with minimal right key. Calls @'error'@ if the bimap is empty.@@ -662,10 +704,9 @@ findMin = M.findMin . toMap {-| /O(log n)/.-Find the element with minimal right key. The +Find the element with minimal right key. The right-hand key is the first entry in the pair. Calls @'error'@ if the bimap is empty. /Version: 0.2.2/-} findMinR :: Bimap a b -> (b, a) findMinR = M.findMin . toMapR-
+ Data/BimapExt.hs view
@@ -0,0 +1,16 @@+{-# LANGUAGE Trustworthy #-}+{-|+An auxiliary module that exports the 'IsList' class from "GHC.Exts". We use+this intermediate module to isolate a safe feature from an otherwise non-safe+module, and prevent all of "Data.Bimap" from being marked as not safe just+because we are importing "GHC.Exts".++The module only exports a class, and the class does not define any methods in+an unsafe way. We therefore consider it safe and mark this module as+trustworthy.+-}+module Data.BimapExt (+ IsList(..)+) where++import GHC.Exts (IsList(..))
bimap.cabal view
@@ -1,6 +1,6 @@-cabal-version: >= 1.8+cabal-version: >= 1.10 name: bimap-version: 0.3.2+version: 0.5.0 synopsis: Bidirectional mapping between two key types description: A data structure representing a bidirectional mapping between two@@ -14,17 +14,29 @@ maintainer: Joel Williamson <joel@joelwilliamson.ca> homepage: https://github.com/joelwilliamson/bimap build-type: Simple-tested-with: GHC <= 7.10.2 && >= 7.0+tested-with: GHC <= 8.6.4 && >= 7.0 extra-source-files: HISTORY Library- build-depends: base >= 4 && <5, containers, exceptions- extensions: DeriveDataTypeable+ build-depends: base >= 4 && <5, containers, deepseq, exceptions+ if impl(ghc < 7.6.1)+ build-depends: ghc-prim+ default-extensions: CPP+ DeriveGeneric+ TypeFamilies+ else+ default-extensions: CPP+ TypeFamilies+ default-language: Haskell98 ghc-options: -Wall exposed-modules: Data.Bimap + if impl(ghc >= 7.8)+ other-modules:+ Data.BimapExt+ test-suite tests type: exitcode-stdio-1.0 main-is: Test/RunTests.hs@@ -32,10 +44,14 @@ Test.Util build-depends: base >= 4 && < 5, containers,+ deepseq, exceptions, QuickCheck >= 2 && < 3, template-haskell >= 2 && < 3- extensions: DeriveDataTypeable+ if impl(ghc < 7.6.1)+ build-depends: ghc-prim+ default-extensions: TemplateHaskell+ default-language: Haskell98 source-repository head type: git