witherable 0.3.4 → 0.3.5
raw patch · 3 files changed
+86/−222 lines, 3 filesdep +voiddep +witherable-class
Dependencies added: void, witherable-class
Files
- CHANGELOG.md +13/−0
- src/Data/Witherable.hs +64/−218
- witherable.cabal +9/−4
CHANGELOG.md view
@@ -1,3 +1,16 @@+0.3.5+-------++* Make `wither` and `witherM` methods of `Witherable []` instance+ good consumers for list fusion.+* Added instances for `Reverse`, `Backwards`, `ZipList`, and types from `GHC.Generics`+* Added `Wither`, `WitherLike`, `Wither'` and `WitherLike'`, deprecating `Filter` and the variants+* Moved `Filterable` and `Witherable` into a separate package, `witherable-class`++0.3.4+-------+* Exported `WrappedFoldable`+ 0.3.3 -------
src/Data/Witherable.hs view
@@ -4,9 +4,7 @@ {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE FunctionalDependencies #-}-#if __GLASGOW_HASKELL__ >= 702-{-# LANGUAGE Trustworthy #-}-#endif+{-# LANGUAGE EmptyCase #-} ----------------------------------------------------------------------------- -- | -- Module : Data.Witherable@@ -30,6 +28,7 @@ , FilterableWithIndex(..) , WitherableWithIndex(..) -- * Generalization+ , WitherLike, Wither, WitherLike', Wither' , FilterLike, Filter, FilterLike', Filter' , witherOf , forMaybeOf@@ -48,7 +47,7 @@ where import qualified Control.Lens as Lens-import qualified Data.Maybe as Maybe+import Data.Witherable.Class import qualified Data.IntMap.Lazy as IM import qualified Data.Map.Lazy as M import qualified Data.Map.Monoidal as MM@@ -66,29 +65,37 @@ import Control.Monad.Trans.Identity import Data.Hashable import Data.Functor.Identity-import Control.Monad.Trans.Maybe+import Data.Functor.Reverse (Reverse (..))+import Control.Applicative.Backwards (Backwards (..)) import Control.Monad.Trans.State.Strict import Data.Monoid import Data.Orphans ()-#if (MIN_VERSION_base(4,7,0)) import Data.Proxy import Data.Void-#endif import Data.Coerce (coerce)-import Prelude -- Fix redundant import warning+import Prelude hiding (filter) +type Filter s t a b = Wither s t a b+{-# DEPRECATED Filter "Use Wither instead" #-}+type FilterLike f s t a b = WitherLike f s t a b+{-# DEPRECATED FilterLike "Use WitherLike instead" #-}+type Filter' s a = Wither' s a+{-# DEPRECATED Filter' "Use Filter' instead" #-}+type FilterLike' f s a = WitherLike' f s a+{-# DEPRECATED FilterLike' "Use WitherLike' instead" #-}+ -- | This type allows combinators to take a 'Filter' specializing the parameter @f@.-type FilterLike f s t a b = (a -> f (Maybe b)) -> s -> f t+type WitherLike f s t a b = (a -> f (Maybe b)) -> s -> f t --- | A 'Filter' is like a <http://hackage.haskell.org/package/lens-4.13.2.1/docs/Control-Lens-Type.html#t:Traversal Traversal>,+-- | A 'Wither' is like a <http://hackage.haskell.org/package/lens-4.13.2.1/docs/Control-Lens-Type.html#t:Traversal Traversal>, -- but you can also remove targets.-type Filter s t a b = forall f. Applicative f => FilterLike f s t a b+type Wither s t a b = forall f. Applicative f => WitherLike f s t a b --- | A simple 'FilterLike'.-type FilterLike' f s a = FilterLike f s s a a+-- | A simple 'WitherLike'.+type WitherLike' f s a = WitherLike f s s a a --- | A simple 'Filter'.-type Filter' s a = forall f. Applicative f => FilterLike' f s a+-- | A simple 'Wither'.+type Wither' s a = forall f. Applicative f => WitherLike' f s a -- | This is used to characterize and clone a 'Filter'. -- Since @FilterLike (Peat a b) s t a b@ is monomorphic, it can be used to store a filter in a container.@@ -127,11 +134,7 @@ -- unknown arity, we don't want to slow things down to raise -- its arity. idDot :: (a -> b) -> a -> Identity b-#if __GLASGOW_HASKELL__ >= 708 idDot = coerce-#else-idDot = (Identity .)-#endif -- | 'mapMaybe' through a filter. mapMaybeOf :: FilterLike Identity s t a b -> (a -> Maybe b) -> s -> t@@ -153,37 +156,6 @@ filterOf w f = runIdentity . filterAOf w (idDot f) {-# INLINE filterOf #-} --- | Like 'Functor', but you can remove elements instead of updating them.------ Formally, the class 'Filterable' represents a functor from @Kleisli Maybe@ to @Hask@.------ A definition of 'mapMaybe' must satisfy the following laws:------ [/conservation/]--- @'mapMaybe' (Just . f) ≡ 'fmap' f@------ [/composition/]--- @'mapMaybe' f . 'mapMaybe' g ≡ 'mapMaybe' (f <=< g)@-class Functor f => Filterable f where- -- | Like 'Maybe.mapMaybe'.- mapMaybe :: (a -> Maybe b) -> f a -> f b- mapMaybe f = catMaybes . fmap f- {-# INLINE mapMaybe #-}-- -- | @'catMaybes' ≡ 'mapMaybe' 'id'@- catMaybes :: f (Maybe a) -> f a- catMaybes = mapMaybe id- {-# INLINE catMaybes #-}-- -- | @'filter' f . 'filter' g ≡ filter ('liftA2' ('&&') f g)@- filter :: (a -> Bool) -> f a -> f a- filter f = mapMaybe $ \a -> if f a then Just a else Nothing- {-# INLINE filter #-}--#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 707- {-# MINIMAL mapMaybe | catMaybes #-}-#endif- -- | An infix alias for 'mapMaybe'. The name of the operator alludes -- to '<$>', and has the same fixity. --@@ -215,48 +187,6 @@ ifilter f = imapMaybe $ \i a -> if f i a then Just a else Nothing {-# INLINE ifilter #-} --- | An enhancement of 'Traversable' with 'Filterable'------ A definition of 'wither' must satisfy the following laws:------ [/conservation/]--- @'wither' ('fmap' 'Just' . f) ≡ 'traverse' f@------ [/composition/]--- @'Compose' . 'fmap' ('wither' f) . 'wither' g ≡ 'wither' ('Compose' . 'fmap' ('wither' f) . g)@------ Parametricity implies the naturality law:------ @t . 'wither' f ≡ 'wither' (t . f)@-----class (T.Traversable t, Filterable t) => Witherable t where-- -- | Effectful 'mapMaybe'.- --- -- @'wither' ('pure' . f) ≡ 'pure' . 'mapMaybe' f@- wither :: Applicative f => (a -> f (Maybe b)) -> t a -> f (t b)- wither f = fmap catMaybes . T.traverse f- {-# INLINE wither #-}-- -- | @Monadic variant of 'wither'. This may have more efficient implementation.@- witherM :: Monad m => (a -> m (Maybe b)) -> t a -> m (t b)-#if MIN_VERSION_base(4,8,0)- witherM = wither-#elif __GLASGOW_HASKELL__ >= 708- witherM f = unwrapMonad . wither (coerce f)-#else- witherM f = unwrapMonad . wither (WrapMonad . f)-#endif- {-# INLINE witherM #-}-- filterA :: Applicative f => (a -> f Bool) -> t a -> f (t a)- filterA = filterAOf wither--#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 707- {-# MINIMAL #-}-#endif- -- | @'forMaybe' = 'flip' 'wither'@ forMaybe :: (Witherable t, Applicative f) => t a -> (a -> f (Maybe b)) -> f (t b) forMaybe = flip wither@@ -272,13 +202,7 @@ -- | @Monadic variant of 'wither'. This may have more efficient implementation.@ iwitherM :: (Monad m) => (i -> a -> m (Maybe b)) -> t a -> m (t b)-#if MIN_VERSION_base(4,8,0) iwitherM = iwither-#elif __GLASGOW_HASKELL__ >= 708- iwitherM f = unwrapMonad . iwither (coerce f)-#else- iwitherM f = unwrapMonad . iwither (\i -> WrapMonad . f i)-#endif ifilterA :: (Applicative f) => (i -> a -> f Bool) -> t a -> f (t a) ifilterA f = iwither (\i a -> (\b -> if b then Just a else Nothing) <$> f i a)@@ -317,8 +241,8 @@ {-# INLINE hashNub #-} -- | A default implementation for 'mapMaybe'.-mapMaybeDefault :: (Foldable f, Alternative f) => (a -> Maybe b) -> f a -> f b-mapMaybeDefault p = foldr (\x xs -> case p x of+mapMaybeDefault :: (F.Foldable f, Alternative f) => (a -> Maybe b) -> f a -> f b+mapMaybeDefault p = F.foldr (\x xs -> case p x of Just a -> pure a <|> xs _ -> xs) empty {-# INLINABLE mapMaybeDefault #-}@@ -331,7 +255,7 @@ {-# INLINABLE imapMaybeDefault #-} newtype WrappedFoldable f a = WrapFilterable {unwrapFoldable :: f a}- deriving (Functor, Foldable, Traversable, Applicative, Alternative)+ deriving (Functor, F.Foldable, T.Traversable, Applicative, Alternative) instance (Lens.FunctorWithIndex i f) => Lens.FunctorWithIndex i (WrappedFoldable f) where imap f = WrapFilterable . Lens.imap f . unwrapFoldable@@ -342,7 +266,7 @@ instance (Lens.TraversableWithIndex i f) => Lens.TraversableWithIndex i (WrappedFoldable f) where itraverse f = fmap WrapFilterable . Lens.itraverse f . unwrapFoldable -instance (Foldable f, Alternative f) => Filterable (WrappedFoldable f) where+instance (F.Foldable f, Alternative f) => Filterable (WrappedFoldable f) where {-#INLINE mapMaybe#-} mapMaybe = mapMaybeDefault @@ -350,71 +274,34 @@ {-# INLINE imapMaybe #-} imapMaybe = imapMaybeDefault -instance Filterable Maybe where- mapMaybe f = (>>= f)- {-# INLINE mapMaybe #-}- instance FilterableWithIndex () Maybe -instance Witherable Maybe where- wither _ Nothing = pure Nothing- wither f (Just a) = f a- {-# INLINABLE wither #-}- instance WitherableWithIndex () Maybe -instance Monoid e => Filterable (Either e) where- mapMaybe _ (Left e) = Left e- mapMaybe f (Right a) = maybe (Left mempty) Right $ f a- {-# INLINABLE mapMaybe #-}--instance Monoid e => Witherable (Either e) where- wither _ (Left e) = pure (Left e)- wither f (Right a) = fmap (maybe (Left mempty) Right) (f a)- {-# INLINABLE wither #-}--instance Filterable [] where- mapMaybe = Maybe.mapMaybe- catMaybes = Maybe.catMaybes- filter = Prelude.filter+-- Option doesn't have the necessary instances in Lens+--instance FilterableWithIndex () Option+--instance WitherableWithIndex () Option instance FilterableWithIndex Int [] -instance (Alternative f, Traversable f) => Witherable (WrappedFoldable f)+instance FilterableWithIndex Int ZipList -instance Witherable [] where- wither f = go where- go (x:xs) = liftA2 (maybe id (:)) (f x) (go xs)- go [] = pure []- {-# INLINE[0] wither #-}+instance (Alternative f, T.Traversable f) => Witherable (WrappedFoldable f) instance WitherableWithIndex Int [] -instance Filterable IM.IntMap where- mapMaybe = IM.mapMaybe- filter = IM.filter+instance WitherableWithIndex Int ZipList instance FilterableWithIndex Int IM.IntMap where imapMaybe = IM.mapMaybeWithKey ifilter = IM.filterWithKey -instance Witherable IM.IntMap where- instance WitherableWithIndex Int IM.IntMap where -instance Filterable (M.Map k) where- mapMaybe = M.mapMaybe- filter = M.filter- instance FilterableWithIndex k (M.Map k) where imapMaybe = M.mapMaybeWithKey ifilter = M.filterWithKey -instance Witherable (M.Map k) where-#if MIN_VERSION_containers(0,5,8)- wither f = M.traverseMaybeWithKey (const f)-#endif- instance WitherableWithIndex k (M.Map k) where #if MIN_VERSION_containers(0,5,8) iwither = M.traverseMaybeWithKey@@ -424,129 +311,88 @@ mapMaybe = MM.mapMaybe filter = MM.filter +instance Witherable (MM.MonoidalMap k)+ instance FilterableWithIndex k (MM.MonoidalMap k) where imapMaybe = MM.mapMaybeWithKey ifilter = MM.filterWithKey -instance Witherable (MM.MonoidalMap k)- instance WitherableWithIndex k (MM.MonoidalMap k) -instance (Eq k, Hashable k) => Filterable (HM.HashMap k) where- mapMaybe = HM.mapMaybe- filter = HM.filter- instance (Eq k, Hashable k) => FilterableWithIndex k (HM.HashMap k) where imapMaybe = HM.mapMaybeWithKey ifilter = HM.filterWithKey -instance (Eq k, Hashable k) => Witherable (HM.HashMap k) where- instance (Eq k, Hashable k) => WitherableWithIndex k (HM.HashMap k) where -#if (MIN_VERSION_base(4,7,0))-instance Filterable Proxy where- mapMaybe _ Proxy = Proxy- instance FilterableWithIndex Void Proxy -instance Witherable Proxy where- wither _ Proxy = pure Proxy- instance WitherableWithIndex Void Proxy-#endif -instance Filterable (Const r) where- mapMaybe _ (Const r) = Const r- {-# INLINABLE mapMaybe #-}--instance Witherable (Const r) where- wither _ (Const r) = pure (Const r)- {-# INLINABLE wither #-}--instance Filterable V.Vector where- mapMaybe = V.mapMaybe- instance FilterableWithIndex Int V.Vector where imapMaybe = V.imapMaybe ifilter = V.ifilter -instance Witherable V.Vector where- wither f = fmap V.fromList . wither f . V.toList- {-# INLINABLE wither #-}- instance WitherableWithIndex Int V.Vector -instance Filterable S.Seq where- mapMaybe f = S.fromList . mapMaybe f . F.toList- {-# INLINABLE mapMaybe #-}- instance FilterableWithIndex Int S.Seq -instance Witherable S.Seq where- wither f = fmap S.fromList . wither f . F.toList- {-# INLINABLE wither #-}- instance WitherableWithIndex Int S.Seq --- The instances for Compose, Product, and Sum are not entirely--- unique. Any particular composition, product, or sum of functors--- may support a variety of 'wither' implementations.--instance (Functor f, Filterable g) => Filterable (Compose f g) where- mapMaybe f = Compose . fmap (mapMaybe f) . getCompose- instance (Lens.FunctorWithIndex i f, FilterableWithIndex j g) => FilterableWithIndex (i, j) (Compose f g) where imapMaybe f = Compose . Lens.imap (\i -> imapMaybe (\j -> f (i, j))) . getCompose--instance (T.Traversable f, Witherable g) => Witherable (Compose f g) where- wither f = fmap Compose . T.traverse (wither f) . getCompose+ ifilter p = Compose . Lens.imap (\i -> ifilter (\j -> p (i, j))) . getCompose instance (Lens.TraversableWithIndex i f, WitherableWithIndex j g) => WitherableWithIndex (i, j) (Compose f g) where iwither f = fmap Compose . Lens.itraverse (\i -> iwither (\j -> f (i, j))) . getCompose--instance (Filterable f, Filterable g) => Filterable (P.Product f g) where- mapMaybe f (P.Pair x y) = P.Pair (mapMaybe f x) (mapMaybe f y)+ iwitherM f = fmap Compose . Lens.imapM (\i -> iwitherM (\j -> f (i, j))) . getCompose+ ifilterA p = fmap Compose . Lens.itraverse (\i -> ifilterA (\j -> p (i, j))) . getCompose instance (FilterableWithIndex i f, FilterableWithIndex j g) => FilterableWithIndex (Either i j) (P.Product f g) where imapMaybe f (P.Pair x y) = P.Pair (imapMaybe (f . Left) x) (imapMaybe (f . Right) y)--instance (Witherable f, Witherable g) => Witherable (P.Product f g) where- wither f (P.Pair x y) = liftA2 P.Pair (wither f x) (wither f y)+ ifilter p (P.Pair x y) = P.Pair (ifilter (p . Left) x) (ifilter (p . Right) y) instance (WitherableWithIndex i f, WitherableWithIndex j g) => WitherableWithIndex (Either i j) (P.Product f g) where- iwither f (P.Pair x y) = P.Pair <$> iwither (f . Left) x <*> iwither (f . Right) y--instance (Filterable f, Filterable g) => Filterable (Sum.Sum f g) where- mapMaybe f (Sum.InL x) = Sum.InL (mapMaybe f x)- mapMaybe f (Sum.InR y) = Sum.InR (mapMaybe f y)+ iwither f (P.Pair x y) = liftA2 P.Pair (iwither (f . Left) x) (iwither (f . Right) y)+ iwitherM f (P.Pair x y) = liftA2 P.Pair (iwitherM (f . Left) x) (iwitherM (f . Right) y)+ ifilterA p (P.Pair x y) = liftA2 P.Pair (ifilterA (p . Left) x) (ifilterA (p . Right) y) instance (FilterableWithIndex i f, FilterableWithIndex j g) => FilterableWithIndex (Either i j) (Sum.Sum f g) where imapMaybe f (Sum.InL x) = Sum.InL (imapMaybe (f . Left) x) imapMaybe f (Sum.InR y) = Sum.InR (imapMaybe (f . Right) y) -instance (Witherable f, Witherable g) => Witherable (Sum.Sum f g) where- wither f (Sum.InL x) = Sum.InL <$> wither f x- wither f (Sum.InR y) = Sum.InR <$> wither f y+ ifilter f (Sum.InL x) = Sum.InL (ifilter (f . Left) x)+ ifilter f (Sum.InR y) = Sum.InR (ifilter (f . Right) y) instance (WitherableWithIndex i f, WitherableWithIndex j g) => WitherableWithIndex (Either i j) (Sum.Sum f g) where iwither f (Sum.InL x) = Sum.InL <$> iwither (f . Left) x iwither f (Sum.InR y) = Sum.InR <$> iwither (f . Right) y -instance Filterable f => Filterable (IdentityT f) where- mapMaybe f (IdentityT m) = IdentityT (mapMaybe f m)+ iwitherM f (Sum.InL x) = Sum.InL <$> iwitherM (f . Left) x+ iwitherM f (Sum.InR y) = Sum.InR <$> iwitherM (f . Right) y -instance (FilterableWithIndex i f) => FilterableWithIndex i (IdentityT f) where- imapMaybe f (IdentityT m) = IdentityT (imapMaybe f m)+ ifilterA f (Sum.InL x) = Sum.InL <$> ifilterA (f . Left) x+ ifilterA f (Sum.InR y) = Sum.InR <$> ifilterA (f . Right) y -instance Witherable f => Witherable (IdentityT f) where- wither f (IdentityT m) = IdentityT <$> wither f m+deriving instance (FilterableWithIndex i f) => FilterableWithIndex i (IdentityT f) instance (WitherableWithIndex i f) => WitherableWithIndex i (IdentityT f) where iwither f (IdentityT m) = IdentityT <$> iwither f m+ iwitherM f (IdentityT m) = IdentityT <$> iwitherM f m+ ifilterA p (IdentityT m) = IdentityT <$> ifilterA p m -instance Functor f => Filterable (MaybeT f) where- mapMaybe f = MaybeT . fmap (mapMaybe f) . runMaybeT+deriving instance FilterableWithIndex i t => FilterableWithIndex i (Reverse t) -instance (T.Traversable t) => Witherable (MaybeT t) where- wither f = fmap MaybeT . T.traverse (wither f) . runMaybeT+-- | Wither from right to left.+instance WitherableWithIndex i t => WitherableWithIndex i (Reverse t) where+ iwither f (Reverse t) = fmap Reverse . forwards $ iwither (\i -> Backwards . f i) t+ -- We can't do anything special with iwitherM, because Backwards m is not+ -- generally a Monad.+ ifilterA p (Reverse t) = fmap Reverse . forwards $ ifilterA (\i -> Backwards . p i) t++deriving instance FilterableWithIndex i t => FilterableWithIndex i (Backwards t)++instance WitherableWithIndex i t => WitherableWithIndex i (Backwards t) where+ iwither f (Backwards xs) = Backwards <$> iwither f xs+ iwitherM f (Backwards xs) = Backwards <$> iwitherM f xs+ ifilterA f (Backwards xs) = Backwards <$> ifilterA f xs
witherable.cabal view
@@ -1,5 +1,5 @@ name: witherable-version: 0.3.4+version: 0.3.5 synopsis: filterable traversable description: A stronger variant of `traverse` which can remove elements and generalised mapMaybe, catMaybes, filter homepage: https://github.com/fumieval/witherable@@ -12,7 +12,7 @@ build-type: Simple extra-source-files: CHANGELOG.md cabal-version: >=1.10-tested-With: GHC == 8.2.2, GHC == 8.4.4, GHC == 8.6.3+tested-With: GHC == 8.2.2, GHC == 8.4.4, GHC == 8.6.3, GHC == 8.8.1 source-repository head type: git@@ -31,7 +31,12 @@ transformers, transformers-compat, unordered-containers,- vector+ vector,+ witherable-class+ if impl(ghc < 7.9)+ build-depends: void hs-source-dirs: src- ghc-options: -Wall -Wcompat+ ghc-options: -Wall default-language: Haskell2010+ if (impl(ghc>=8))+ ghc-options: -Wcompat