Elegant way to combine multiple filtering functions in Haskell

Question

Given the following filtering functions as unary predicates,

Click to copy

f1 :: Int -> Bool
f1 x = x > 30

f2 :: Int -> Bool
f2 x = x < 60

f3 :: Int -> Bool
f3 x = x `mod` 3 == 0

I'd like to filter a list of integers through all of them. Currently I'm doing something along the lines of:

Click to copy

filtered = filter f1 $ filter f2 $ filter f3 [1..90]
-- [33,36,39,42,45,48,51,54,57]

but it hardly feels like this is the most elegant solution possible; especially I don't like the multiple repetitions of filter and the lack of composability.

Would there be a way to compose all these predicates into one, let's name it <?>, so that a possible syntax would resemble something like the following?

Click to copy

filtered = filter (f1 <?> f2 <?> f3) [1..90]
-- [33,36,39,42,45,48,51,54,57]

The type signature of this hypothetical <?> operator would then be (a -> Bool) -> (a -> Bool) -> (a -> Bool) but I wasn't able to find any such thing on Hoogle.

Answer 1

What about this?

Click to copy

import Control.Applicative (liftA2)
-- given f1 etc.
filtered = filter (f1 <&&> f2 <&&> f3) [1..90]
  where
    (<&&>) = liftA2 (&&)

Here, lifting && to Applicative gives what you marked as <?>, i.e. an operator to "and" together the results of two unary predicates.

---

I initially used the name .&&. for the lifted operator, but amalloy suggested that <&&> would be a better name by analogy with the other Functor/Applicative lifted operators like <$>.

Answer 2

Click to copy

> filter (and . sequence [f1, f2, f3]) [1..100]
[33,36,39,42,45,48,51,54,57]

Essentially the above works because sequence (on the (->) a monad as used above) takes a list-of-functions and returns a function-returning-a-list. E.g.

Click to copy

sequence [f, g, h] = \x -> [f x, g x, h x]

Post-composing with and :: [Bool] -> Bool gives you a single boolean result, so you can use that in filter.

Also, there is no shame in being point-ful:

Click to copy

> filter (\x -> f1 x && f2 x && f3 x) [1..100]

is only marginally longer, and arguably simpler to read.

Answer 3

You can work with the (&&^) :: Monad m => m Bool -> m Bool -> m Bool of the extra package:

Click to copy

import Control.Monad.Extra((&&^))

filtered = filter (f1 &&^ f2 &&^ f3) [1..90]

this gives us:

Click to copy

Prelude Control.Monad.Extra> filter (f1 &&^ f2 &&^ f3) [1..90]
[33,36,39,42,45,48,51,54,57]

The (&&^) function is implemented as [src]:

Click to copy

ifM :: Monad m => m Bool -> m a -> m a -> m a
ifM b t f = do b <- b; if b then t else f

-- …

(&&^) :: Monad m => m Bool -> m Bool -> m Bool
(&&^) a b = ifM a b (pure False)

This works because a function type is a Monad:

Click to copy

instance Monad ((->) r) where
    f >>= k = \ r -> k (f r) r

This thus means that the ifM is implemented as for a function as:

Click to copy

-- ifM for ((->) r)
ifM b t f x
    | b x = t x
    | otherwise = f x

The (&&^) function thus checks if the first condition b x is True, in case it is not, it will return False (since f is const False, and f x is thus False). In case b x is True, it will check the next element in the chain.

Answer 4

Data.Monoid defines a Predicate type that can be used to represent your functions:

Click to copy

import Data.Monoid

-- newtype Predicate t = Predicate { getPredicate :: t -> Bool }
p1 :: Predicate Int
p1 x = Predicate $ x > 30

p2 :: Predicate Int
p2 x = Predicate $ x < 60

p3 :: Predicate Int
p3 x = Predicate $ x `mod` 3 == 0

Predicate has a Semigroup instance that combines two predicates into one that is satisfied if both input predicates are satisfied.

Click to copy

-- instance Semigroup (Predicate a) where
-- Predicate p <> Predicate q = Predicate $ \a -> p a && q a

filtered = filter (getPredicate (p1 <> p2 <> p3)) [1..90]

It's unfortunate that you need to unwrap the combined predicates before you can use them with filter. You might define your own filterP function and use that in place of filter:

Click to copy

filterP :: Predicate t  -> [t] -> [t]
filterP = filter . getPredicate

filtered = filterP (p1 <> p2 <> p3) [1..90]

---

There is also a Monoid instance (with the identity being a predicate that always returns True), which you could use like

Click to copy

filtered = filter (getPredicate (mconcat [p1, p2, p3]))

which again you could re-factor to something like

Click to copy

filterByAll = filter . getPredicate . mconcat

filtered = filterByAll [p1, p2, p3] [1..90]