Elegant way to combine multiple filtering functions in Haskell

Question

Given the following filtering functions as unary predicates,

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:

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?

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?

import Control.Applicative (liftA2)
-- given f1, f2, and f3
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

The other answers are pretty good, but I'll give the way that I like to combine functions, that's pretty compact. I'm a big fan of using the lift functions from Control.Monad

filter $ liftM2 (&&) f1 f2

liftM2 works by promoting the (&&) function to a monad and taking f1 and f2 as arguments.

I know that there's a function called liftM3, but I'm not sure if it would work in this context.

https://hackage.haskell.org/package/base-4.14.0.0/docs/Control-Monad.html#v:liftM3

Answer 3

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

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

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

this gives us:

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]:

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:

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

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

-- 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

> 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.

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:

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

is only marginally longer, and arguably simpler to read.

Answer 5

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

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.

-- 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:

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

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

which again you could re-factor to something like

filterByAll = filter . getPredicate . mconcat

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

Answer 6

We need a way to use a function like and to combinate predicates instead of just boolean values.

A lazy way consists in asking Hoogle for a type signature like Functor f => ([b]-> b) -> [f b] -> f b, where f is presumably something like Int ->. Meet library function cotraverse.

It seems to work fine:

 λ> 
 λ> f1 x = x > 30
 λ> f2 x = x < 60
 λ> f3 x = (mod x 3) == 0
 λ> 
 λ> import Data.Distributive (cotraverse)
 λ> :t cotraverse
 cotraverse
  :: (Distributive g, Functor f) => (f a -> b) -> f (g a) -> g b
 λ> 
 λ> filter  ( cotraverse and [f1,f2,f3] )  [1..90]
 [33,36,39,42,45,48,51,54,57]
 λ> 

Checking:

 λ> 
 λ> filter  (\x -> and (map ($ x) [f1,f2,f3]))  [1..90]
 [33,36,39,42,45,48,51,54,57]
 λ>