diff options
Diffstat (limited to 'src/Data')
| -rw-r--r-- | src/Data/Dependent/EnumMap/Strict/Internal.hs | 168 |
1 files changed, 117 insertions, 51 deletions
diff --git a/src/Data/Dependent/EnumMap/Strict/Internal.hs b/src/Data/Dependent/EnumMap/Strict/Internal.hs index ed8283f..ddf9405 100644 --- a/src/Data/Dependent/EnumMap/Strict/Internal.hs +++ b/src/Data/Dependent/EnumMap/Strict/Internal.hs @@ -85,7 +85,7 @@ dSumToKV (k :=> v) = let (i, inf) = fromEnum1 k in (i, KV inf v) -- | Assumes that the input was obtained via 'fromEnum1'. kVToDSum :: Enum1 k => (Int, KV k v) -> DSum k v -kVToDSum (i, KV inf v) = case toEnum1 i inf of k -> k :=> v +kVToDSum (i, KV inf v) = toEnum1 i inf :=> v -- * Construction @@ -121,9 +121,9 @@ fromListWithKey :: forall k v. (Enum1 k, TestEquality k) fromListWithKey f l = DEnumMap (IM.fromListWithKey (\i (KV inf1 v1) (KV inf2 v2) -> - case toEnum1 @k i inf1 of - k1 -> case typeCheck1 k1 i inf2 of - Refl -> KV inf1 (f k1 v1 v2)) + let k1 = toEnum1 @k i inf1 + in case typeCheck1 k1 i inf2 of + Refl -> KV inf1 (f k1 v1 v2)) (dSumToKV <$> l)) -- ** From Ascending Lists @@ -147,9 +147,9 @@ fromAscListWithKey :: forall k v. (Enum1 k, TestEquality k) fromAscListWithKey f l = DEnumMap (IM.fromAscListWithKey (\i (KV inf1 v1) (KV inf2 v2) -> - case toEnum1 @k i inf1 of - k1 -> case typeCheck1 k1 i inf2 of - Refl -> KV inf1 (f k1 v1 v2)) + let k1 = toEnum1 @k i inf1 + in case typeCheck1 k1 i inf2 of + Refl -> KV inf1 (f k1 v1 v2)) (dSumToKV <$> l)) fromDistinctAscList :: Enum1 k => [DSum k v] -> DEnumMap k v @@ -321,9 +321,10 @@ unionWithKey :: forall k v. (Enum1 k, TestEquality k) unionWithKey f (DEnumMap m1 :: DEnumMap k v) (DEnumMap m2) = DEnumMap (IM.unionWithKey f' m1 m2) where f' :: Int -> KV k v -> KV k v -> KV k v - f' i (KV inf1 v1) (KV inf2 v2) = case toEnum1 @k i inf1 of - k1 -> case typeCheck1 k1 i inf2 of - Refl -> KV inf1 (f k1 v1 v2) + f' i (KV inf1 v1) (KV inf2 v2) = + let k1 = toEnum1 @k i inf1 + in case typeCheck1 k1 i inf2 of + Refl -> KV inf1 (f k1 v1 v2) unions :: (Foldable f, Enum1 k, TestEquality k) => f (DEnumMap k v) -> DEnumMap k v unions = Foldable.foldl' union empty @@ -354,9 +355,10 @@ differenceWithKey :: forall k v1 v2. (Enum1 k, TestEquality k) differenceWithKey f (DEnumMap m1) (DEnumMap m2) = DEnumMap (IM.differenceWithKey f' m1 m2) where f' :: Int -> KV k v1 -> KV k v2 -> Maybe (KV k v1) - f' i (KV inf1 v1) (KV inf2 v2) = case toEnum1 @k i inf1 of - k1 -> case typeCheck1 k1 i inf2 of - Refl -> KV inf1 <$> f k1 v1 v2 + f' i (KV inf1 v1) (KV inf2 v2) = + let k1 = toEnum1 @k i inf1 + in case typeCheck1 k1 i inf2 of + Refl -> KV inf1 <$> f k1 v1 v2 -- | Because the underlying maps are keyed on integers, it is possible to -- subtract a map from another even if the key types differ. This function @@ -373,8 +375,10 @@ differenceWithKey' :: forall k1 k2 v1 v2. (Enum1 k1, Enum1 k2) differenceWithKey' f (DEnumMap m1) (DEnumMap m2) = DEnumMap (IM.differenceWithKey f' m1 m2) where f' :: Int -> KV k1 v1 -> KV k2 v2 -> Maybe (KV k1 v1) - f' i (KV inf1 v1) (KV inf2 v2) = case (toEnum1 i inf1, toEnum1 i inf2) of - (k1, k2) -> KV inf1 <$> f k1 v1 k2 v2 + f' i (KV inf1 v1) (KV inf2 v2) = + let k1 = toEnum1 i inf1 + k2 = toEnum1 i inf2 + in KV inf1 <$> f k1 v1 k2 v2 -- ** Intersection @@ -395,9 +399,10 @@ intersectionWithKey :: forall k v1 v2 v3. (Enum1 k, TestEquality k) intersectionWithKey f (DEnumMap m1) (DEnumMap m2) = DEnumMap (IM.intersectionWithKey f' m1 m2) where f' :: Int -> KV k v1 -> KV k v2 -> KV k v3 - f' i (KV inf1 v1) (KV inf2 v2) = case toEnum1 @k i inf1 of - k1 -> case typeCheck1 k1 i inf2 of - Refl -> KV inf1 $ f k1 v1 v2 + f' i (KV inf1 v1) (KV inf2 v2) = + let k1 = toEnum1 @k i inf1 + in case typeCheck1 k1 i inf2 of + Refl -> KV inf1 $ f k1 v1 v2 -- | Generalises 'intersectionWithKey' in the same way as 'differenceWithKey'' -- generalises 'differenceWithKey'. @@ -407,8 +412,10 @@ intersectionWithKey' :: forall k1 k2 v1 v2 v3. (Enum1 k1, Enum1 k2) intersectionWithKey' f (DEnumMap m1) (DEnumMap m2) = DEnumMap (IM.intersectionWithKey f' m1 m2) where f' :: Int -> KV k1 v1 -> KV k2 v2 -> KV k1 v3 - f' i (KV inf1 v1) (KV inf2 v2) = case (toEnum1 i inf1, toEnum1 i inf2) of - (k1, k2) -> KV inf1 $ f k1 v1 k2 v2 + f' i (KV inf1 v1) (KV inf2 v2) = + let k1 = toEnum1 i inf1 + k2 = toEnum1 i inf2 + in KV inf1 $ f k1 v1 k2 v2 -- ** Disjoint @@ -432,9 +439,10 @@ mergeWithKey f g1 g2 (DEnumMap m1) (DEnumMap m2) = DEnumMap (IM.mergeWithKey f' (coerce g1) (coerce g2) m1 m2) where f' :: Int -> KV k v1 -> KV k v2 -> Maybe (KV k v3) - f' i (KV inf1 v1) (KV inf2 v2) = case toEnum1 @k i inf1 of - k1 -> case typeCheck1 k1 i inf2 of - Refl -> KV inf1 <$> f k1 v1 v2 + f' i (KV inf1 v1) (KV inf2 v2) = + let k1 = toEnum1 @k i inf1 + in case typeCheck1 k1 i inf2 of + Refl -> KV inf1 <$> f k1 v1 v2 -- * Traversal -- ** Map @@ -444,28 +452,43 @@ map f = mapWithKey (const f) mapWithKey :: Enum1 k => (forall a. k a -> v1 a -> v2 a) -> DEnumMap k v1 -> DEnumMap k v2 mapWithKey f (DEnumMap m) = - DEnumMap (IM.mapWithKey (\i (KV inf v) -> case toEnum1 i inf of k -> KV inf $ f k v) m) + DEnumMap (IM.mapWithKey (\i (KV inf v) -> + let k = toEnum1 i inf + in KV inf $ f k v) + m) traverseWithKey :: (Applicative f, Enum1 k) => (forall a. k a -> v1 a -> f (v2 a)) -> DEnumMap k v1 -> f (DEnumMap k v2) traverseWithKey f (DEnumMap m) = - DEnumMap <$> IM.traverseWithKey (\i (KV inf v) -> case toEnum1 i inf of k -> KV inf <$> f k v) m + DEnumMap <$> IM.traverseWithKey (\i (KV inf v) -> + let k = toEnum1 i inf + in KV inf <$> f k v) + m traverseMaybeWithKey :: (Applicative f, Enum1 k) => (forall a. k a -> v1 a -> f (Maybe (v2 a))) -> DEnumMap k v1 -> f (DEnumMap k v2) traverseMaybeWithKey f (DEnumMap m) = - DEnumMap <$> IM.traverseMaybeWithKey (\i (KV inf v) -> case toEnum1 i inf of k -> fmap (KV inf) <$> f k v) m + DEnumMap <$> IM.traverseMaybeWithKey (\i (KV inf v) -> + let k = toEnum1 i inf + in fmap (KV inf) <$> f k v) + m mapAccum :: Enum1 k => (forall a. acc -> v1 a -> (acc, v2 a)) -> acc -> DEnumMap k v1 -> (acc, DEnumMap k v2) mapAccum f = mapAccumWithKey (\x _ y -> f x y) mapAccumWithKey :: Enum1 k => (forall a. acc -> k a -> v1 a -> (acc, v2 a)) -> acc -> DEnumMap k v1 -> (acc, DEnumMap k v2) mapAccumWithKey f acc0 (DEnumMap m) = - second DEnumMap $ IM.mapAccumWithKey (\acc i (KV inf v) -> case toEnum1 i inf of k -> second (KV inf) $ f acc k v) acc0 m + second DEnumMap $ IM.mapAccumWithKey (\acc i (KV inf v) -> + let k = toEnum1 i inf + in second (KV inf) $ f acc k v) + acc0 m mapAccumRWithKey :: Enum1 k => (forall a. acc -> k a -> v1 a -> (acc, v2 a)) -> acc -> DEnumMap k v1 -> (acc, DEnumMap k v2) mapAccumRWithKey f acc0 (DEnumMap m) = - second DEnumMap $ IM.mapAccumRWithKey (\acc i (KV inf v) -> case toEnum1 i inf of k -> second (KV inf) $ f acc k v) acc0 m + second DEnumMap $ IM.mapAccumRWithKey (\acc i (KV inf v) -> + let k = toEnum1 i inf + in second (KV inf) $ f acc k v) + acc0 m -- TODO: These are hard. Probably we can't avoid using a fold, analogously as in IntMap. -- mapKeys @@ -482,15 +505,24 @@ foldl f acc0 (DEnumMap m) = IM.foldl (\acc (KV _ v) -> f acc v) acc0 m foldrWithKey :: Enum1 k => (forall a. k a -> v a -> acc -> acc) -> acc -> DEnumMap k v -> acc foldrWithKey f acc0 (DEnumMap m) = - IM.foldrWithKey (\i (KV inf v) acc -> case toEnum1 i inf of k -> f k v acc) acc0 m + IM.foldrWithKey (\i (KV inf v) acc -> + let k = toEnum1 i inf + in f k v acc) + acc0 m foldlWithKey :: Enum1 k => (forall a. acc -> k a -> v a -> acc) -> acc -> DEnumMap k v -> acc foldlWithKey f acc0 (DEnumMap m) = - IM.foldlWithKey (\acc i (KV inf v) -> case toEnum1 i inf of k -> f acc k v) acc0 m + IM.foldlWithKey (\acc i (KV inf v) -> + let k = toEnum1 i inf + in f acc k v) + acc0 m foldMapWithKey :: (Monoid m, Enum1 k) => (forall a. k a -> v a -> m) -> DEnumMap k v -> m foldMapWithKey f (DEnumMap m) = - IM.foldMapWithKey (\i (KV inf v) -> case toEnum1 i inf of k -> f k v) m + IM.foldMapWithKey (\i (KV inf v) -> + let k = toEnum1 i inf + in f k v) + m -- ** Strict folds @@ -502,11 +534,17 @@ foldl' f acc0 (DEnumMap m) = IM.foldl' (\acc (KV _ v) -> f acc v) acc0 m foldrWithKey' :: Enum1 k => (forall a. k a -> v a -> acc -> acc) -> acc -> DEnumMap k v -> acc foldrWithKey' f acc0 (DEnumMap m) = - IM.foldrWithKey' (\i (KV inf v) acc -> case toEnum1 i inf of k -> f k v acc) acc0 m + IM.foldrWithKey' (\i (KV inf v) acc -> + let k = toEnum1 i inf + in f k v acc) + acc0 m foldlWithKey' :: Enum1 k => (forall a. acc -> k a -> v a -> acc) -> acc -> DEnumMap k v -> acc foldlWithKey' f acc0 (DEnumMap m) = - IM.foldlWithKey' (\acc i (KV inf v) -> case toEnum1 i inf of k -> f acc k v) acc0 m + IM.foldlWithKey' (\acc i (KV inf v) -> + let k = toEnum1 i inf + in f acc k v) + acc0 m -- * Conversion @@ -542,7 +580,10 @@ filter f (DEnumMap m) = DEnumMap (IM.filter (\(KV _ v) -> f v) m) filterWithKey :: Enum1 k => (forall a. k a -> v a -> Bool) -> DEnumMap k v -> DEnumMap k v filterWithKey f (DEnumMap m) = - DEnumMap (IM.filterWithKey (\i (KV inf v) -> case toEnum1 i inf of k -> f k v) m) + DEnumMap (IM.filterWithKey (\i (KV inf v) -> + let k = toEnum1 i inf + in f k v) + m) -- TODO: Wait for DEnumSet. -- restrictKeys @@ -554,7 +595,10 @@ partition f (DEnumMap m) = partitionWithKey :: Enum1 k => (forall a. k a -> v a -> Bool) -> DEnumMap k v -> (DEnumMap k v, DEnumMap k v) partitionWithKey f (DEnumMap m) = - bimap DEnumMap DEnumMap (IM.partitionWithKey (\i (KV inf v) -> case toEnum1 i inf of k -> f k v) m) + bimap DEnumMap DEnumMap (IM.partitionWithKey (\i (KV inf v) -> + let k = toEnum1 i inf + in f k v) + m) -- | \(O(\min(n,W)^2)\). Because of the lack of a @takeWhileAntitoneWithValue@ -- operation on 'Data.IntMap.Strict.IntMap', this function performs additional lookups to @@ -562,17 +606,27 @@ partitionWithKey f (DEnumMap m) = -- worse complexity than 'IM.takeWhileAntitone'. takeWhileAntitone :: Enum1 k => (forall a. k a -> Bool) -> DEnumMap k v -> DEnumMap k v takeWhileAntitone f (DEnumMap m) = - DEnumMap (IM.takeWhileAntitone (\i -> case m IM.! i of KV inf _ -> case toEnum1 i inf of k -> f k) m) + DEnumMap (IM.takeWhileAntitone (\i -> case m IM.! i of + KV inf _ -> let k = toEnum1 i inf + in f k) + m) -- | \(O(\min(n,W)^2)\). See 'takeWhileAntitone'. dropWhileAntitone :: Enum1 k => (forall a. k a -> Bool) -> DEnumMap k v -> DEnumMap k v dropWhileAntitone f (DEnumMap m) = - DEnumMap (IM.dropWhileAntitone (\i -> case m IM.! i of KV inf _ -> case toEnum1 i inf of k -> f k) m) + DEnumMap (IM.dropWhileAntitone (\i -> case m IM.! i of + KV inf _ -> let k = toEnum1 i inf + in f k) + m) -- | \(O(\min(n,W)^2)\). See 'takeWhileAntitone'. spanAntitone :: Enum1 k => (forall a. k a -> Bool) -> DEnumMap k v -> (DEnumMap k v, DEnumMap k v) spanAntitone f (DEnumMap m) = - bimap DEnumMap DEnumMap (IM.spanAntitone (\i -> case m IM.! i of KV inf _ -> case toEnum1 i inf of k -> f k) m) + bimap DEnumMap DEnumMap + (IM.spanAntitone (\i -> case m IM.! i of + KV inf _ -> let k = toEnum1 i inf + in f k) + m) mapMaybe :: Enum1 k => (forall a. v1 a -> Maybe (v2 a)) -> DEnumMap k v1 -> DEnumMap k v2 mapMaybe f = mapMaybeWithKey (const f) @@ -580,7 +634,10 @@ mapMaybe f = mapMaybeWithKey (const f) mapMaybeWithKey :: Enum1 k => (forall a. k a -> v1 a -> Maybe (v2 a)) -> DEnumMap k v1 -> DEnumMap k v2 mapMaybeWithKey f (DEnumMap m) = - DEnumMap (IM.mapMaybeWithKey (\i (KV inf v) -> case toEnum1 i inf of k -> KV inf <$> f k v) m) + DEnumMap (IM.mapMaybeWithKey (\i (KV inf v) -> + let k = toEnum1 i inf + in KV inf <$> f k v) + m) mapEither :: Enum1 k => (forall a. v1 a -> Either (v2 a) (v3 a)) -> DEnumMap k v1 -> (DEnumMap k v2, DEnumMap k v3) @@ -589,7 +646,10 @@ mapEither f = mapEitherWithKey (const f) mapEitherWithKey :: Enum1 k => (forall a. k a -> v1 a -> Either (v2 a) (v3 a)) -> DEnumMap k v1 -> (DEnumMap k v2, DEnumMap k v3) mapEitherWithKey f (DEnumMap m) = - bimap DEnumMap DEnumMap (IM.mapEitherWithKey (\i (KV inf v) -> case toEnum1 i inf of k -> bimap (KV inf) (KV inf) $ f k v) m) + bimap DEnumMap DEnumMap (IM.mapEitherWithKey (\i (KV inf v) -> + let k = toEnum1 i inf + in bimap (KV inf) (KV inf) $ f k v) + m) split :: Enum1 k => k a -> DEnumMap k v -> (DEnumMap k v, DEnumMap k v) split k (DEnumMap m) = bimap DEnumMap DEnumMap (IM.split (fst $ fromEnum1 k) m) @@ -651,14 +711,20 @@ updateMin f = updateMinWithKey (const f) updateMinWithKey :: Enum1 k => (forall a. k a -> v a -> Maybe (v a)) -> DEnumMap k v -> DEnumMap k v updateMinWithKey f (DEnumMap m) = - DEnumMap (IM.updateMinWithKey (\i (KV inf v) -> case toEnum1 i inf of k -> KV inf <$> f k v) m) + DEnumMap (IM.updateMinWithKey (\i (KV inf v) -> + let k = toEnum1 i inf + in KV inf <$> f k v) + m) updateMax :: Enum1 k => (forall a. v a -> Maybe (v a)) -> DEnumMap k v -> DEnumMap k v updateMax f = updateMaxWithKey (const f) updateMaxWithKey :: Enum1 k => (forall a. k a -> v a -> Maybe (v a)) -> DEnumMap k v -> DEnumMap k v updateMaxWithKey f (DEnumMap m) = - DEnumMap (IM.updateMaxWithKey (\i (KV inf v) -> case toEnum1 i inf of k -> KV inf <$> f k v) m) + DEnumMap (IM.updateMaxWithKey (\i (KV inf v) -> + let k = toEnum1 i inf + in KV inf <$> f k v) + m) minView :: DEnumMap k v -> Maybe (v a, DEnumMap k v) minView (DEnumMap m) = bimap' (\(KV _ v) -> coe1 v) DEnumMap <$!> IM.minView m @@ -681,20 +747,20 @@ coe1 = unsafeCoerce typeCheck1 :: (Enum1 k, TestEquality k) => k a -> Int -> Enum1Info k b -> k a :~: k b typeCheck1 k1 i inf2 = - assert (case toEnum1 i inf2 of { k2 -> - case testEquality k1 k2 of - Just Refl -> True - Nothing -> False }) + assert (let k2 = toEnum1 i inf2 + in case testEquality k1 k2 of + Just Refl -> True + Nothing -> False) (unsafeCoerce Refl) typeCheck2 :: forall k proxy a b. (Enum1 k, TestEquality k) => proxy k -> Int -> Enum1Info k a -> Enum1Info k b -> k a :~: k b typeCheck2 _ i inf1 inf2 = - assert (case toEnum1 @k i inf1 of { k1 -> - case toEnum1 i inf2 of { k2 -> - case testEquality k1 k2 of - Just Refl -> True - Nothing -> False }}) + assert (let k1 = toEnum1 @k i inf1 + k2 = toEnum1 i inf2 + in case testEquality k1 k2 of + Just Refl -> True + Nothing -> False) (unsafeCoerce Refl) bimap' :: (a -> b) -> (c -> d) -> (a, c) -> (b, d) |