diff options
| -rw-r--r-- | dependent-enummap.cabal | 1 | ||||
| -rw-r--r-- | src/Data/Dependent/EnumMap/Strict.hs | 375 | ||||
| -rw-r--r-- | src/Data/Dependent/EnumMap/Strict/Internal.hs | 284 |
3 files changed, 425 insertions, 235 deletions
diff --git a/dependent-enummap.cabal b/dependent-enummap.cabal index 8b3839b..8005de5 100644 --- a/dependent-enummap.cabal +++ b/dependent-enummap.cabal @@ -8,6 +8,7 @@ build-type: Simple library exposed-modules: Data.Dependent.EnumMap.Strict + Data.Dependent.EnumMap.Strict.Internal build-depends: base >=4.15, containers, diff --git a/src/Data/Dependent/EnumMap/Strict.hs b/src/Data/Dependent/EnumMap/Strict.hs index 6e1e9d6..31f7e52 100644 --- a/src/Data/Dependent/EnumMap/Strict.hs +++ b/src/Data/Dependent/EnumMap/Strict.hs @@ -1,284 +1,189 @@ -{-# LANGUAGE ExistentialQuantification #-} -{-# LANGUAGE RankNTypes #-} -{-# LANGUAGE ScopedTypeVariables #-} -{-# LANGUAGE TypeFamilies #-} -module Data.Dependent.EnumMap.Strict where +module Data.Dependent.EnumMap.Strict ( + DEnumMap, + Enum1(..), -import Data.Bifunctor (bimap) -import Data.Dependent.Sum -import qualified Data.IntMap.Strict as IM -import Data.Some -import Unsafe.Coerce (unsafeCoerce) + -- * Construction + empty, + singleton, + -- fromSet -data KV k v = forall a. KV !(Enum1Info k) !(v a) + -- ** From Unordered Lists -newtype DEnumMap k v = DEnumMap (IM.IntMap (KV k v)) + fromList, + -- fromListWith + -- fromListWithKey -class Enum1 f where - type Enum1Info f - fromEnum1 :: f a -> (Int, Enum1Info f) - toEnum1 :: Int -> Enum1Info f -> Some f + -- ** From Ascending Lists --- * Construction + -- fromAscList + -- fromAscListWith + -- fromAscListWithKey + fromDistinctAscList, -empty :: DEnumMap k v -empty = DEnumMap IM.empty + -- * Insertion -singleton :: Enum1 k => k a -> v a -> DEnumMap k v -singleton k v = - let (i, inf) = fromEnum1 k - in DEnumMap (IM.singleton i (KV inf v)) + insert, + -- insertWith + insertWithKey, + -- insertLookupWithKey --- fromSet + -- * Deletion\/Update --- ** From Unordered Lists + delete, + adjust, + -- adjustWithKey + -- update + -- updateWithKey + -- updateLookupWithKey + alter, + -- alterF -fromList :: Enum1 k => [DSum k v] -> DEnumMap k v -fromList l = - DEnumMap (IM.fromList (map (\(k :=> v) -> let (i, inf) = fromEnum1 k in (i, KV inf v)) l)) + -- * Query + -- ** Lookup --- fromListWith --- fromListWithKey + lookup, + -- (!?) + -- (!) + findWithDefault, + member, + -- notMember + -- lookupLT + -- lookupGT + -- lookupLE + -- lookupGE --- ** From Ascending Lists + -- ** Size --- fromAscList --- fromAscListWith --- fromAscListWithKey + null, + -- size -fromDistinctAscList :: Enum1 k => [DSum k v] -> DEnumMap k v -fromDistinctAscList l = - DEnumMap (IM.fromDistinctAscList (map (\(k :=> v) -> let (i, inf) = fromEnum1 k in (i, KV inf v)) l)) + -- * Combine + -- ** Union --- * Insertion + union, + unionWith, + -- unionWithKey + -- unions + -- unionsWith -insert :: Enum1 k => k a -> v a -> DEnumMap k v -> DEnumMap k v -insert k v (DEnumMap m) = - let (i, inf) = fromEnum1 k - in DEnumMap (IM.insert i (KV inf v) m) + -- ** Difference --- insertWith + difference, + -- (\\) + -- differenceWith + -- differenceWithKey -insertWithKey :: Enum1 k - => (k a -> v a -> v a -> v a) - -> k a -> v a -> DEnumMap k v -> DEnumMap k v -insertWithKey f k v (DEnumMap m) = - let (i, inf) = fromEnum1 k - in DEnumMap (IM.insertWithKey - (\_ (KV _ v1) (KV _ v2) -> KV inf (f k (coe1 v1) (coe1 v2))) - i (KV inf v) m) + -- ** Intersection --- insertLookupWithKey + -- intersection + -- intersectionWith + -- intersectionWithKey --- * Deletion\/Update + -- ** Disjoint -delete :: Enum1 k => k a -> DEnumMap k v -> DEnumMap k v -delete k (DEnumMap m) = DEnumMap (IM.delete (fst (fromEnum1 k)) m) + -- disjoint -adjust :: Enum1 k => (v a -> v a) -> k a -> DEnumMap k v -> DEnumMap k v -adjust f k (DEnumMap m) = DEnumMap (IM.adjust (\(KV k' v) -> KV k' (f (coe1 v))) (fst (fromEnum1 k)) m) + -- ** Compose --- adjustWithKey --- update --- updateWithKey --- updateLookupWithKey + -- compose -alter :: forall k v a. Enum1 k => (Maybe (v a) -> Maybe (v a)) -> k a -> DEnumMap k v -> DEnumMap k v -alter f k (DEnumMap m) = DEnumMap (IM.alter f' i m) - where - (i, inf) = fromEnum1 k + -- ** Universal combining function - f' :: Maybe (KV k v) -> Maybe (KV k v) - f' Nothing = KV inf <$> f Nothing - f' (Just (KV _ v)) = KV inf <$> f (Just (coe1 v)) + -- mergeWithKey --- alterF + -- * Traversal + -- ** Map --- * Query --- ** Lookup + -- map + -- mapWithKey + -- traverseWithKey + -- traverseMaybeWithKey + -- mapAccum + -- mapAccumWithKey + -- mapAccumRWithKey + -- mapKeys + -- mapKeysWith + -- mapKeysMonotonic -lookup :: Enum1 k => k a -> DEnumMap k v -> Maybe (v a) -lookup k (DEnumMap m) = (\(KV _ v) -> coe1 v) <$> IM.lookup (fst (fromEnum1 k)) m + -- * Folds --- (!?) --- (!) + -- foldr + -- foldl + -- foldrWithKey + -- foldlWithKey + -- foldMapWithKey -findWithDefault :: Enum1 k => v a -> k a -> DEnumMap k v -> v a -findWithDefault def k (DEnumMap m) = - case IM.findWithDefault (KV undefined def) (fst (fromEnum1 k)) m of - KV _ v -> coe1 v + -- ** Strict folds -member :: Enum1 k => k a -> DEnumMap k v -> Bool -member k (DEnumMap m) = IM.member (fst (fromEnum1 k)) m + -- foldr' + -- foldl' + -- foldrWithKey' + -- foldlWithKey' --- notMember --- lookupLT --- lookupGT --- lookupLE --- lookupGE + -- * Conversion --- ** Size + elems, + keys, -null :: DEnumMap k v -> Bool -null (DEnumMap m) = IM.null m + -- assocs + -- keysSet --- size + -- ** Lists --- * Combine + -- toList --- ** Union + -- ** Ordered lists -union :: DEnumMap k v -> DEnumMap k v -> DEnumMap k v -union (DEnumMap m1) (DEnumMap m2) = DEnumMap (IM.union m1 m2) + -- toAscList + toDescList, -unionWith :: forall k v. (forall a. v a -> v a -> v a) - -> DEnumMap k v -> DEnumMap k v -> DEnumMap k v -unionWith f (DEnumMap m1) (DEnumMap m2) = DEnumMap (IM.unionWith f' m1 m2) - where - f' :: KV k v -> KV k v -> KV k v - f' (KV inf v1) (KV _ v2) = KV inf (f v1 (coe1 v2)) + -- * Filter --- unionWithKey --- unions --- unionsWith + -- filter + -- filterWithKey + -- restrictKeys + -- withoutKeys + partition, + -- partitionWithKey --- ** Difference + -- takeWhileAntitone + -- dropWhileAntitone + -- spanAntitone -difference :: DEnumMap k v -> DEnumMap k v -> DEnumMap k v -difference (DEnumMap m1) (DEnumMap m2) = DEnumMap (IM.difference m1 m2) + -- mapMaybe + -- mapMaybeWithKey + -- mapEither + -- mapEitherWithKey --- (\\) --- differenceWith --- differenceWithKey + -- split + -- splitLookup + -- splitRoot --- ** Intersection + -- * Submap --- intersection --- intersectionWith --- intersectionWithKey + -- isSubmapOf, isSubmapOfBy + -- isProperSubmapOf, isProperSubmapOfBy --- ** Disjoint + -- * Min\/Max --- disjoint + -- lookupMin + -- lookupMax + -- findMin + -- findMax + -- deleteMin + -- deleteMax + -- deleteFindMin + -- deleteFindMax + -- updateMin + -- updateMax + -- updateMinWithKey + -- updateMaxWithKey + -- minView + -- maxView + -- minViewWithKey + maxViewWithKey, +) where --- ** Compose - --- compose - --- ** Universal combining function - --- mergeWithKey - --- * Traversal --- ** Map - --- map --- mapWithKey --- traverseWithKey --- traverseMaybeWithKey --- mapAccum --- mapAccumWithKey --- mapAccumRWithKey --- mapKeys --- mapKeysWith --- mapKeysMonotonic - --- * Folds - --- foldr --- foldl --- foldrWithKey --- foldlWithKey --- foldMapWithKey - --- ** Strict folds - --- foldr' --- foldl' --- foldrWithKey' --- foldlWithKey' - --- * Conversion - -elems :: DEnumMap k v -> [Some v] -elems (DEnumMap m) = map (\(KV _ v) -> Some v) (IM.elems m) - -keys :: Enum1 k => DEnumMap k v -> [Some k] -keys (DEnumMap m) = map (\(k, KV inf _) -> toEnum1 k inf) (IM.assocs m) - --- assocs --- keysSet - --- ** Lists - --- toList - --- ** Ordered lists - --- toAscList - -toDescList :: Enum1 k => DEnumMap k v -> [DSum k v] -toDescList (DEnumMap m) = - map (\(i, KV inf v) -> case toEnum1 i inf of Some k -> k :=> coe1 v) - (IM.toDescList m) - --- * Filter - --- filter --- filterWithKey --- restrictKeys --- withoutKeys - -partition :: (forall a. v a -> Bool) -> DEnumMap k v -> (DEnumMap k v, DEnumMap k v) -partition f (DEnumMap m) = - bimap DEnumMap DEnumMap (IM.partition (\(KV _ v) -> f v) m) - --- partitionWithKey - --- takeWhileAntitone --- dropWhileAntitone --- spanAntitone - --- mapMaybe --- mapMaybeWithKey --- mapEither --- mapEitherWithKey - --- split --- splitLookup --- splitRoot - --- * Submap - --- isSubmapOf, isSubmapOfBy --- isProperSubmapOf, isProperSubmapOfBy - --- * Min\/Max - --- lookupMin --- lookupMax --- findMin --- findMax --- deleteMin --- deleteMax --- deleteFindMin --- deleteFindMax --- updateMin --- updateMax --- updateMinWithKey --- updateMaxWithKey --- minView --- maxView --- minViewWithKey - -maxViewWithKey :: Enum1 k => DEnumMap k v -> Maybe (DSum k v, DEnumMap k v) -maxViewWithKey (DEnumMap m) = - bimap (\(i, KV inf v) -> case toEnum1 i inf of Some k -> k :=> coe1 v) DEnumMap - <$> IM.maxViewWithKey m - - --- * Unsafe helpers - -coe1 :: v a -> v b -coe1 = unsafeCoerce +import Prelude () +import Data.Dependent.EnumMap.Strict.Internal diff --git a/src/Data/Dependent/EnumMap/Strict/Internal.hs b/src/Data/Dependent/EnumMap/Strict/Internal.hs new file mode 100644 index 0000000..7c94f89 --- /dev/null +++ b/src/Data/Dependent/EnumMap/Strict/Internal.hs @@ -0,0 +1,284 @@ +{-# LANGUAGE ExistentialQuantification #-} +{-# LANGUAGE RankNTypes #-} +{-# LANGUAGE ScopedTypeVariables #-} +{-# LANGUAGE TypeFamilies #-} +module Data.Dependent.EnumMap.Strict.Internal where + +import Data.Bifunctor (bimap) +import Data.Dependent.Sum +import qualified Data.IntMap.Strict as IM +import Data.Some +import Unsafe.Coerce (unsafeCoerce) + + +data KV k v = forall a. KV !(Enum1Info k) !(v a) + +newtype DEnumMap k v = DEnumMap (IM.IntMap (KV k v)) + +class Enum1 f where + type Enum1Info f + fromEnum1 :: f a -> (Int, Enum1Info f) + toEnum1 :: Int -> Enum1Info f -> Some f + +-- * Construction + +empty :: DEnumMap k v +empty = DEnumMap IM.empty + +singleton :: Enum1 k => k a -> v a -> DEnumMap k v +singleton k v = + let (i, inf) = fromEnum1 k + in DEnumMap (IM.singleton i (KV inf v)) + +-- fromSet + +-- ** From Unordered Lists + +fromList :: Enum1 k => [DSum k v] -> DEnumMap k v +fromList l = + DEnumMap (IM.fromList (map (\(k :=> v) -> let (i, inf) = fromEnum1 k in (i, KV inf v)) l)) + +-- fromListWith +-- fromListWithKey + +-- ** From Ascending Lists + +-- fromAscList +-- fromAscListWith +-- fromAscListWithKey + +fromDistinctAscList :: Enum1 k => [DSum k v] -> DEnumMap k v +fromDistinctAscList l = + DEnumMap (IM.fromDistinctAscList (map (\(k :=> v) -> let (i, inf) = fromEnum1 k in (i, KV inf v)) l)) + +-- * Insertion + +insert :: Enum1 k => k a -> v a -> DEnumMap k v -> DEnumMap k v +insert k v (DEnumMap m) = + let (i, inf) = fromEnum1 k + in DEnumMap (IM.insert i (KV inf v) m) + +-- insertWith + +insertWithKey :: Enum1 k + => (k a -> v a -> v a -> v a) + -> k a -> v a -> DEnumMap k v -> DEnumMap k v +insertWithKey f k v (DEnumMap m) = + let (i, inf) = fromEnum1 k + in DEnumMap (IM.insertWithKey + (\_ (KV _ v1) (KV _ v2) -> KV inf (f k (coe1 v1) (coe1 v2))) + i (KV inf v) m) + +-- insertLookupWithKey + +-- * Deletion\/Update + +delete :: Enum1 k => k a -> DEnumMap k v -> DEnumMap k v +delete k (DEnumMap m) = DEnumMap (IM.delete (fst (fromEnum1 k)) m) + +adjust :: Enum1 k => (v a -> v a) -> k a -> DEnumMap k v -> DEnumMap k v +adjust f k (DEnumMap m) = DEnumMap (IM.adjust (\(KV k' v) -> KV k' (f (coe1 v))) (fst (fromEnum1 k)) m) + +-- adjustWithKey +-- update +-- updateWithKey +-- updateLookupWithKey + +alter :: forall k v a. Enum1 k => (Maybe (v a) -> Maybe (v a)) -> k a -> DEnumMap k v -> DEnumMap k v +alter f k (DEnumMap m) = DEnumMap (IM.alter f' i m) + where + (i, inf) = fromEnum1 k + + f' :: Maybe (KV k v) -> Maybe (KV k v) + f' Nothing = KV inf <$> f Nothing + f' (Just (KV _ v)) = KV inf <$> f (Just (coe1 v)) + +-- alterF + +-- * Query +-- ** Lookup + +lookup :: Enum1 k => k a -> DEnumMap k v -> Maybe (v a) +lookup k (DEnumMap m) = (\(KV _ v) -> coe1 v) <$> IM.lookup (fst (fromEnum1 k)) m + +-- (!?) +-- (!) + +findWithDefault :: Enum1 k => v a -> k a -> DEnumMap k v -> v a +findWithDefault def k (DEnumMap m) = + case IM.findWithDefault (KV undefined def) (fst (fromEnum1 k)) m of + KV _ v -> coe1 v + +member :: Enum1 k => k a -> DEnumMap k v -> Bool +member k (DEnumMap m) = IM.member (fst (fromEnum1 k)) m + +-- notMember +-- lookupLT +-- lookupGT +-- lookupLE +-- lookupGE + +-- ** Size + +null :: DEnumMap k v -> Bool +null (DEnumMap m) = IM.null m + +-- size + +-- * Combine + +-- ** Union + +union :: DEnumMap k v -> DEnumMap k v -> DEnumMap k v +union (DEnumMap m1) (DEnumMap m2) = DEnumMap (IM.union m1 m2) + +unionWith :: forall k v. (forall a. v a -> v a -> v a) + -> DEnumMap k v -> DEnumMap k v -> DEnumMap k v +unionWith f (DEnumMap m1) (DEnumMap m2) = DEnumMap (IM.unionWith f' m1 m2) + where + f' :: KV k v -> KV k v -> KV k v + f' (KV inf v1) (KV _ v2) = KV inf (f v1 (coe1 v2)) + +-- unionWithKey +-- unions +-- unionsWith + +-- ** Difference + +difference :: DEnumMap k v -> DEnumMap k v -> DEnumMap k v +difference (DEnumMap m1) (DEnumMap m2) = DEnumMap (IM.difference m1 m2) + +-- (\\) +-- differenceWith +-- differenceWithKey + +-- ** Intersection + +-- intersection +-- intersectionWith +-- intersectionWithKey + +-- ** Disjoint + +-- disjoint + +-- ** Compose + +-- compose + +-- ** Universal combining function + +-- mergeWithKey + +-- * Traversal +-- ** Map + +-- map +-- mapWithKey +-- traverseWithKey +-- traverseMaybeWithKey +-- mapAccum +-- mapAccumWithKey +-- mapAccumRWithKey +-- mapKeys +-- mapKeysWith +-- mapKeysMonotonic + +-- * Folds + +-- foldr +-- foldl +-- foldrWithKey +-- foldlWithKey +-- foldMapWithKey + +-- ** Strict folds + +-- foldr' +-- foldl' +-- foldrWithKey' +-- foldlWithKey' + +-- * Conversion + +elems :: DEnumMap k v -> [Some v] +elems (DEnumMap m) = map (\(KV _ v) -> Some v) (IM.elems m) + +keys :: Enum1 k => DEnumMap k v -> [Some k] +keys (DEnumMap m) = map (\(k, KV inf _) -> toEnum1 k inf) (IM.assocs m) + +-- assocs +-- keysSet + +-- ** Lists + +-- toList + +-- ** Ordered lists + +-- toAscList + +toDescList :: Enum1 k => DEnumMap k v -> [DSum k v] +toDescList (DEnumMap m) = + map (\(i, KV inf v) -> case toEnum1 i inf of Some k -> k :=> coe1 v) + (IM.toDescList m) + +-- * Filter + +-- filter +-- filterWithKey +-- restrictKeys +-- withoutKeys + +partition :: (forall a. v a -> Bool) -> DEnumMap k v -> (DEnumMap k v, DEnumMap k v) +partition f (DEnumMap m) = + bimap DEnumMap DEnumMap (IM.partition (\(KV _ v) -> f v) m) + +-- partitionWithKey + +-- takeWhileAntitone +-- dropWhileAntitone +-- spanAntitone + +-- mapMaybe +-- mapMaybeWithKey +-- mapEither +-- mapEitherWithKey + +-- split +-- splitLookup +-- splitRoot + +-- * Submap + +-- isSubmapOf, isSubmapOfBy +-- isProperSubmapOf, isProperSubmapOfBy + +-- * Min\/Max + +-- lookupMin +-- lookupMax +-- findMin +-- findMax +-- deleteMin +-- deleteMax +-- deleteFindMin +-- deleteFindMax +-- updateMin +-- updateMax +-- updateMinWithKey +-- updateMaxWithKey +-- minView +-- maxView +-- minViewWithKey + +maxViewWithKey :: Enum1 k => DEnumMap k v -> Maybe (DSum k v, DEnumMap k v) +maxViewWithKey (DEnumMap m) = + bimap (\(i, KV inf v) -> case toEnum1 i inf of Some k -> k :=> coe1 v) DEnumMap + <$> IM.maxViewWithKey m + + +-- * Unsafe helpers + +coe1 :: v a -> v b +coe1 = unsafeCoerce |