packages feed

ordered-containers 0.1.1 → 0.2

raw patch · 5 files changed

+253/−18 lines, 5 filesdep ~base

Dependency ranges changed: base

Files

ChangeLog.md view
@@ -1,5 +1,17 @@ # Revision history for ordered-containers +## 0.2 -- 2019-03-24++* Support many more operations:+	* Semigroup,Monoid,Data,Typeable for OSet+	* Semigroup,Monoid,Functor,Traversable,Data,Typeable for OMap+	* union and intersection primitives for both+* Document asymptotics (when they vary from Set and Map)++## 0.1.1 -- 2018-10-31++* Metadata changes only+ ## 0.1.0 -- 2016-12-26  * Documentation fix
Data/Map/Ordered.hs view
@@ -1,5 +1,11 @@--- | An 'OMap' behaves much like a 'Map', with all the same asymptotics, but--- also remembers the order that keys were inserted.+{-# LANGUAGE CPP #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE DeriveFunctor #-}+{-# LANGUAGE FlexibleInstances #-}++-- | An 'OMap' behaves much like a 'Map', with mostly the same asymptotics, but+-- also remembers the order that keys were inserted. All operations whose+-- asymptotics are worse than 'Map' have documentation saying so. module Data.Map.Ordered 	( OMap 	-- * Trivial maps@@ -15,8 +21,11 @@ 	-- 	-- * If both sides contain the same key, the tuple's value wins 	, (<|), (|<), (>|), (|>)+	, (<>|), (|<>), unionWithL, unionWithR+	, Bias(Bias, unbiased), L, R 	-- * Deletion 	, delete, filter, (\\)+	, (|/\), (/\|), intersectionWith 	-- * Query 	, null, size, member, notMember, lookup 	-- * Indexing@@ -27,14 +36,20 @@  import Control.Applicative ((<|>)) import Control.Monad (guard)+import Data.Data import Data.Foldable (Foldable, foldl', foldMap) import Data.Function (on) import Data.Map (Map)-import Data.Map.Util (Index, Tag, maxTag, minTag, nextHigherTag, nextLowerTag, readsPrecList, showsPrecList)+import Data.Map.Util+import Data.Monoid+#if MIN_VERSION_base(4,9,0)+import Data.Semigroup+#endif import Prelude hiding (filter, lookup, null) import qualified Data.Map as M  data OMap k v = OMap !(Map k (Tag, v)) !(Map Tag (k, v))+	deriving (Functor, Typeable)  -- | Values are produced in insertion order, not key order. instance Foldable (OMap k) where foldMap f (OMap _ kvs) = foldMap (f . snd) kvs@@ -43,12 +58,71 @@ instance (       Show k, Show v) => Show (OMap k v) where showsPrec = showsPrecList assocs instance (Ord k, Read k, Read v) => Read (OMap k v) where readsPrec = readsPrecList fromList +-- This instance preserves data abstraction at the cost of inefficiency.+-- We provide limited reflection services for the sake of data abstraction.+instance (Data k, Data a, Ord k) => Data (OMap k a) where+	gfoldl f z m   = z fromList `f` assocs m+	toConstr _     = fromListConstr+	gunfold k z c  = case constrIndex c of+		1 -> k (z fromList)+		_ -> error "gunfold"+	dataTypeOf _   = oMapDataType+	dataCast2      = gcast2++fromListConstr :: Constr+fromListConstr = mkConstr oMapDataType "fromList" [] Prefix++oMapDataType :: DataType+oMapDataType = mkDataType "Data.Map.Ordered.Map" [fromListConstr]++#if MIN_VERSION_base(4,9,0)+instance (Ord k, Semigroup v) => Semigroup (Bias L (OMap k v)) where+	Bias o <> Bias o' = Bias (unionWithL (const (<>)) o o')+instance (Ord k, Semigroup v) => Semigroup (Bias R (OMap k v)) where+	Bias o <> Bias o' = Bias (unionWithR (const (<>)) o o')+#endif++-- | Empty maps and map union. When combining two sets that share elements, the+-- indices of the left argument are preferred, and the values are combined with+-- 'mappend'.+--+-- See the asymptotics of 'unionWithL'.+instance (Ord k, Monoid v) => Monoid (Bias L (OMap k v)) where+	mempty = Bias empty+	mappend (Bias o) (Bias o') = Bias (unionWithL (const mappend) o o')++-- | Empty maps and map union. When combining two sets that share elements, the+-- indices of the right argument are preferred, and the values are combined+-- with 'mappend'.+--+-- See the asymptotics of 'unionWithR'.+instance (Ord k, Monoid v) => Monoid (Bias R (OMap k v)) where+	mempty = Bias empty+	mappend (Bias o) (Bias o') = Bias (unionWithR (const mappend) o o')++-- | Values are traversed in insertion order, not key order.+--+-- /O(n*log(n))/ where /n/ is the size of the map.+instance Ord k => Traversable (OMap k) where+	traverse f (OMap tvs kvs) = fromKV <$> traverse (\(k,v) -> (,) k <$> f v) kvs+ infixr 5 <|, |< -- copy : infixl 5 >|, |>+infixr 6 <>|, |<> -- copy <>  (<|) , (|<) :: Ord k => (,)  k v -> OMap k v -> OMap k v (>|) , (|>) :: Ord k => OMap k v -> (,)  k v -> OMap k v +-- | When a key occurs in both maps, prefer the value from the first map.+--+-- See asymptotics of 'unionWithR'.+(<>|) :: Ord k => OMap k v -> OMap k v -> OMap k v++-- | When a key occurs in both maps, prefer the value from the first map.+--+-- See asymptotics of 'unionWithL'.+(|<>) :: Ord k => OMap k v -> OMap k v -> OMap k v+ (k, v) <| OMap tvs kvs = OMap (M.insert k (t, v) tvs) (M.insert t (k, v) kvs) where 	t = maybe (nextLowerTag kvs) fst (M.lookup k tvs) @@ -63,7 +137,41 @@ OMap tvs kvs |> (k, v) = OMap (M.insert k (t, v) tvs) (M.insert t (k, v) kvs) where 	t = maybe (nextHigherTag kvs) fst (M.lookup k tvs) +(<>|) = unionWithR (const const)+(|<>) = unionWithL (const const)++-- | Take the union. The first 'OMap' \'s argument's indices are lower than the+-- second. If a key appears in both maps, the first argument's index takes+-- precedence, and the supplied function is used to combine the values.+--+-- /O(r*log(r))/ where /r/ is the size of the result+unionWithL :: Ord k => (k -> v -> v -> v) -> OMap k v -> OMap k v -> OMap k v+unionWithL = unionWithInternal (\t t' -> t )++-- | Take the union. The first 'OMap' \'s argument's indices are lower than the+-- second. If a key appears in both maps, the second argument's index takes+-- precedence, and the supplied function is used to combine the values.+--+-- /O(r*log(r))/ where /r/ is the size of the result+unionWithR :: Ord k => (k -> v -> v -> v) -> OMap k v -> OMap k v -> OMap k v+unionWithR = unionWithInternal (\t t' -> t')++unionWithInternal :: Ord k => (Tag -> Tag -> Tag) -> (k -> v -> v -> v) -> OMap k v -> OMap k v -> OMap k v+unionWithInternal fT fKV (OMap tvs kvs) (OMap tvs' kvs') = fromTV tvs'' where+	bump  = case maxTag kvs  of+		Nothing -> 0+		Just k  -> -k-1+	bump' = case minTag kvs' of+		Nothing -> 0+		Just k  -> -k+	tvs'' = M.unionWithKey (\k (t,v) (t',v') -> (fT t t', fKV k v v'))+		(fmap (\(t,v) -> (bump +t,v)) tvs )+		(fmap (\(t,v) -> (bump'+t,v)) tvs')+ -- | @m \\\\ n@ deletes all the keys that exist in @n@ from @m@+--+-- /O(m*log(n))/ where /m/ is the size of the smaller map and /n/ is the size+-- of the larger map. (\\) :: Ord k => OMap k v -> OMap k v' -> OMap k v o@(OMap tvs kvs) \\ o'@(OMap tvs' kvs') = if size o < size o' 	then filter (const . (`notMember` o')) o@@ -106,6 +214,40 @@ delete k o@(OMap tvs kvs) = case M.lookup k tvs of 	Nothing     -> o 	Just (t, _) -> OMap (M.delete k tvs) (M.delete t kvs)++-- | Intersection. (The @/\\@ is intended to look a bit like the standard+-- mathematical notation for set intersection.)+--+-- See asymptotics of 'intersectionWith'.+(/\|) :: Ord k => OMap k v -> OMap k v' -> OMap k v+o /\| o' = intersectionWith (\k v' v -> v) o' o++-- | Intersection. (The @/\\@ is intended to look a bit like the standard+-- mathematical notation for set intersection.)+--+-- See asymptotics of 'intersectionWith'.+(|/\) :: Ord k => OMap k v -> OMap k v' -> OMap k v+o |/\ o' = intersectionWith (\k v v' -> v) o o'++-- | Take the intersection. The first 'OMap' \'s argument's indices are used for+-- the result.+--+-- /O(m*log(n\/(m+1)) + r*log(r))/ where /m/ is the size of the smaller map, /n/+-- is the size of the larger map, and /r/ is the size of the result.+intersectionWith ::+	Ord k =>+	(k -> v -> v' -> v'') ->+	OMap k v -> OMap k v' -> OMap k v''+intersectionWith f (OMap tvs kvs) (OMap tvs' kvs') = fromTV+	$ M.intersectionWithKey (\k (t,v) (t',v') -> (t, f k v v')) tvs tvs'++fromTV :: Ord k => Map k (Tag, v) -> OMap k v+fromTV tvs = OMap tvs kvs where+	kvs = M.fromList [(t,(k,v)) | (k,(t,v)) <- M.toList tvs]++fromKV :: Ord k => Map Tag (k, v) -> OMap k v+fromKV kvs = OMap tvs kvs where+	tvs = M.fromList [(k,(t,v)) | (t,(k,v)) <- M.toList kvs]  findIndex :: Ord k => k -> OMap k v -> Maybe Index findIndex k o@(OMap tvs kvs) = do
Data/Map/Util.hs view
@@ -1,6 +1,10 @@+{-# LANGUAGE DataKinds #-}+{-# LANGUAGE KindSignatures #-}+ module Data.Map.Util where  import Data.Map (Map)+import Data.Monoid -- so that the docs for Monoid link to the right place import qualified Data.Map as M  -- | An internal index used to track ordering only -- its magnitude doesn't@@ -29,3 +33,11 @@ 	("fromList", s) <- lex r 	(xs, t) <- reads s 	return (fromList xs, t)++-- | A newtype to hand a 'Monoid' instance on. The phantom first parameter+-- tells whether 'mappend' will prefer the indices of its first or second+-- argument if there are shared elements in both.+newtype Bias (dir :: IndexPreference) a = Bias { unbiased :: a }+data IndexPreference = L | R+type L = 'L+type R = 'R
Data/Set/Ordered.hs view
@@ -1,11 +1,16 @@--- | An 'OSet' behaves much like a 'Set', with all the same asymptotics, but--- also remembers the order that values were inserted.+{-# LANGUAGE CPP #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE FlexibleInstances #-}++-- | An 'OSet' behaves much like a 'Set', with mostly the same asymptotics, but+-- also remembers the order that values were inserted. All operations whose+-- asymptotics are worse than 'Set' have documentation saying so. module Data.Set.Ordered 	( OSet 	-- * Trivial sets 	, empty, singleton 	-- * Insertion-	-- | Conventionts:+	-- | Conventions: 	-- 	-- * The open side of an angle bracket points to an 'OSet' 	--@@ -14,10 +19,11 @@ 	-- * The left argument's indices are lower than the right argument's indices 	, (<|), (|<), (>|), (|>) 	, (<>|), (|<>)+	, Bias(Bias, unbiased), L, R 	-- * Query 	, null, size, member, notMember 	-- * Deletion-	, delete, filter, (\\)+	, delete, filter, (\\), (|/\), (/\|) 	-- * Indexing 	, Index, findIndex, elemAt 	-- * List conversions@@ -25,15 +31,21 @@ 	) where  import Control.Monad (guard)+import Data.Data import Data.Foldable (Foldable, foldl', foldMap, foldr, toList) import Data.Function (on) import Data.Map (Map)-import Data.Map.Util (Index, Tag, maxTag, minTag, nextHigherTag, nextLowerTag, readsPrecList, showsPrecList)+import Data.Map.Util+import Data.Monoid+#if MIN_VERSION_base(4,9,0)+import Data.Semigroup+#endif import Data.Set (Set) -- so the haddocks link to the right place import Prelude hiding (filter, foldr, lookup, null) import qualified Data.Map as M  data OSet a = OSet !(Map a Tag) !(Map Tag a)+	deriving Typeable  -- | Values appear in insertion order, not ascending order. instance Foldable OSet where foldMap f (OSet _ vs) = foldMap f vs@@ -42,14 +54,59 @@ instance         Show a  => Show (OSet a) where showsPrec = showsPrecList toList instance (Ord a, Read a) => Read (OSet a) where readsPrec = readsPrecList fromList +-- This instance preserves data abstraction at the cost of inefficiency.+-- We provide limited reflection services for the sake of data abstraction.+instance (Data a, Ord a) => Data (OSet a) where+	gfoldl f z set = z fromList `f` toList set+	toConstr _     = fromListConstr+	gunfold k z c  = case constrIndex c of+		1 -> k (z fromList)+		_ -> error "gunfold"+	dataTypeOf _   = oSetDataType+	dataCast1      = gcast1++fromListConstr :: Constr+fromListConstr = mkConstr oSetDataType "fromList" [] Prefix++oSetDataType :: DataType+oSetDataType = mkDataType "Data.Set.Ordered.Set" [fromListConstr]++#if MIN_VERSION_base(4,9,0)+instance Ord a => Semigroup (Bias L (OSet a)) where Bias o <> Bias o' = Bias (o |<> o')+instance Ord a => Semigroup (Bias R (OSet a)) where Bias o <> Bias o' = Bias (o <>| o')+#endif++-- | Empty sets and set union. When combining two sets that share elements, the+-- indices of the left argument are preferred.+--+-- See the asymptotics of ('|<>').+instance Ord a => Monoid (Bias L (OSet a)) where+	mempty = Bias empty+	mappend (Bias o) (Bias o') = Bias (o |<> o')++-- | Empty sets and set union. When combining two sets that share elements, the+-- indices of the right argument are preferred.+--+-- See the asymptotics of ('<>|').+instance Ord a => Monoid (Bias R (OSet a)) where+	mempty = Bias empty+	mappend (Bias o) (Bias o') = Bias (o <>| o')+ infixr 5 <|, |<   -- copy : infixl 5 >|, |> infixr 6 <>|, |<> -- copy <>  (<|) , (|<)  :: Ord a =>      a -> OSet a -> OSet a (>|) , (|>)  :: Ord a => OSet a ->      a -> OSet a-(<>|), (|<>) :: Ord a => OSet a -> OSet a -> OSet a +-- | /O(m*log(n)+n)/, where /m/ is the size of the smaller set and /n/ is the+-- size of the larger set.+(<>|) :: Ord a => OSet a -> OSet a -> OSet a++-- | /O(m*log(n)+n)/, where /m/ is the size of the smaller set and /n/ is the+-- size of the larger set.+(|<>) :: Ord a => OSet a -> OSet a -> OSet a+ v <| o@(OSet ts vs) 	| v `member` o = o 	| otherwise    = OSet (M.insert v t ts) (M.insert t v vs) where@@ -89,10 +146,29 @@  -- | Set difference: @r \\\\ s@ deletes all the values in @s@ from @r@. The -- order of @r@ is unchanged.+--+-- /O(m*log(n))/ where /m/ is the size of the smaller set and /n/ is the size+-- of the larger set. (\\) :: Ord a => OSet a -> OSet a -> OSet a o@(OSet ts vs) \\ o'@(OSet ts' vs') = if size o < size o' 	then filter (`notMember` o') o 	else foldr delete o vs'++-- | Intersection. (@/\\@ is meant to look a bit like the standard mathematical+-- notation for intersection.)+--+-- /O(m*log(n\/(m+1)) + r*log(r))/, where /m/ is the size of the smaller set,+-- /n/ the size of the larger set, and /r/ the size of the result.+(|/\) :: Ord a => OSet a -> OSet a -> OSet a+OSet ts vs |/\ OSet ts' vs' = OSet ts'' vs'' where+	ts'' = M.intersection ts ts'+	vs'' = M.fromList [(t, v) | (v, t) <- M.toList ts]++-- | @flip ('|/\')@+--+-- See asymptotics of '|/\'.+(/\|) :: Ord a => OSet a -> OSet a -> OSet a+(/\|) = flip (/\|)  empty :: OSet a empty = OSet M.empty M.empty
ordered-containers.cabal view
@@ -1,15 +1,10 @@--- Initial ordered-containers.cabal generated by cabal init.  For further --- documentation, see http://haskell.org/cabal/users-guide/- name:                ordered-containers-version:             0.1.1+version:             0.2 synopsis:            Set- and Map-like types that remember the order elements were inserted--- description:          license:             BSD3 license-file:        LICENSE author:              Daniel Wagner maintainer:          me@dmwit.com--- copyright:            category:            Data build-type:          Simple extra-source-files:  ChangeLog.md@@ -22,8 +17,6 @@ library   exposed-modules:     Data.Map.Ordered, Data.Set.Ordered   other-modules:       Data.Map.Util-  -- other-extensions:    -  build-depends:       base >=4 && <5, containers >=0.1 && <0.7-  -- hs-source-dirs:      +  build-depends:       base >=4.7 && <5, containers >=0.1 && <0.7   default-language:    Haskell98   ghc-options:         -fno-warn-tabs