33

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.

5
  • 1
  • 1
    FYI, you do have composability: filtered = (filter f1 . filter f2 . filter f3) [1..90]
    – chepner
    Oct 21, 2020 at 13:56
  • @chepner for sure, but I was especially looking for something which factors the filter out in the expression you typed — but effectively, I didn't mention that in my question and this is already better than filter f1 $ filter f2 $ filter f3... even though it's only replacing $'s by .'s
    – Jivan
    Oct 21, 2020 at 14:08
  • 2
    You might be interested in my semigroup-based answer. The Semigroup instance for predicates is essentially liftA2 (&&), as in your accepted answer.
    – chepner
    Oct 21, 2020 at 14:14
  • 2
    This is perhaps the best motivator for the confusingly named Heyting Algebra data type in PureScript (I say confusingly named because one would expect (&&) to operate just on booleans). It has a function instance so you can simply write filter (f1 && f2 && f3).
    – cole
    Oct 21, 2020 at 19:19

6 Answers 6

34

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

1
  • 1
    I've ended up using this solution as it is the closest from what I initially envisioned, and it also doesn't need any additional package. Lastly it uses an applicative functor instead of a monad. I actually implemented the (<&&>) = liftA2 (&&) function directly in Utils.hs for convenience, but the compiler required to add typing information, which I did with (<&&>) :: (a -> Bool) -> (a -> Bool) -> (a -> Bool)
    – Jivan
    Oct 20, 2020 at 20:31
24
> 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.

9

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.

0
9

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

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]
 λ> 
1

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

5
  • 6
    This is essentially what the accepted answer suggests, except using a monadic lift instead of an applicative one. Is there any specific advantage of using a monad versus an applicative in this case?
    – Jivan
    Oct 20, 2020 at 23:37
  • 1
    Also, liftM3 would definitely work but lacks the flexibility of using liftM2 to produce the lifted infix operator which can then be composed e.g. f1 <&&> f2 <&&> f3 <&&> f4 ...
    – Jivan
    Oct 20, 2020 at 23:42
  • I still can't believe how this kind of answer is not eligible for deletion :)
    – Enlico
    Oct 21, 2020 at 8:10
  • 6
    @Jivan no. The liftMn are basically obsolete since Applicative is a superclass of Monad. Oct 21, 2020 at 14:53
  • @Jivan for liftM3 to work you'd have to supply it with a ternary &&, but && is binary. so it is actually filter $ liftM2 (&&) (liftM2 (&&) f1 f2) f3.
    – Will Ness
    Oct 27, 2020 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.