summaryrefslogtreecommitdiff
path: root/Data/Filtrable.hs
diff options
context:
space:
mode:
Diffstat (limited to 'Data/Filtrable.hs')
-rw-r--r--Data/Filtrable.hs19
1 files changed, 14 insertions, 5 deletions
diff --git a/Data/Filtrable.hs b/Data/Filtrable.hs
index e6bfac5..f9bf18c 100644
--- a/Data/Filtrable.hs
+++ b/Data/Filtrable.hs
@@ -7,11 +7,13 @@ module Data.Filtrable
import Prelude hiding (filter)
import Control.Applicative
+import Control.Applicative.Backwards
import Control.Monad
import qualified Control.Monad.Trans.State as M
import Data.Bool (bool)
import Data.Functor.Compose
import Data.Functor.Product
+import Data.Functor.Reverse
import Data.Functor.Sum
import Data.Proxy
import Data.Traversable
@@ -92,11 +94,18 @@ instance (Filtrable f, Filtrable g) => Filtrable (Product f g) where
mapMaybe f (Pair as bs) = Pair (mapMaybe f as) (mapMaybe f bs)
instance (Filtrable f, Filtrable g) => Filtrable (Sum f g) where
- mapMaybe f (InL as) = InL (mapMaybe f as)
- mapMaybe f (InR bs) = InR (mapMaybe f bs)
+ mapMaybe f = \ case
+ InL as -> InL (mapMaybe f as)
+ InR bs -> InR (mapMaybe f bs)
instance (Functor f, Filtrable g) => Filtrable (Compose f g) where
- mapMaybe f (Compose as) = Compose (mapMaybe f <$> as)
+ mapMaybe f = Compose . (fmap . mapMaybe) f . getCompose
+
+instance Filtrable f => Filtrable (Backwards f) where
+ mapMaybe f = Backwards . mapMaybe f . forwards
+
+instance Filtrable f => Filtrable (Reverse f) where
+ mapMaybe f = Reverse . mapMaybe f . getReverse
infixl 4 <$?>, <*?>
@@ -119,12 +128,12 @@ nubBy eq = fmap (flip M.evalState []) . filterA $ \ a -> do
let b = all (not . eq a) as
b <$ when b (M.modify (a:))
--- | \(\mathcal{O}(n^2)\)
+-- | \(\mathcal{O}(n\;\mathrm{log}\;n)\)
-- Delete all but the first copy of each element, special case of 'nubOrdBy'.
nubOrd :: (Filtrable f, Traversable f, Ord a) => f a -> f a
nubOrd = nubOrdBy compare
--- | \(\mathcal{O}(n^2)\)
+-- | \(\mathcal{O}(n\;\mathrm{log}\;n)\)
-- Delete all but the first copy of each element, with the given relation.
nubOrdBy :: (Filtrable f, Traversable f) => (a -> a -> Ordering) -> f a -> f a
nubOrdBy compare = fmap (flip M.evalState Set.empty) . filterA $ \ a -> M.state $ \ as ->