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.

Jivan
  • 21,522
  • 15
  • 80
  • 131
  • 1
    Prior art: https://stackoverflow.com/questions/12654042/boolean-operators-over-multiple-elements, https://stackoverflow.com/questions/57414964/how-to-compose-functions-that-return-bools-to-one-function – amalloy Oct 20 '20 at 20:12
  • 1
    FYI, you *do* have composability: `filtered = (filter f1 . filter f2 . filter f3) [1..90]` – chepner Oct 21 '20 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 '20 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 '20 at 14:14
  • 2
    This is perhaps the best motivator for the confusingly named [Heyting Algebra](https://pursuit.purescript.org/packages/purescript-prelude/4.1.1/docs/Data.HeytingAlgebra) 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 '20 at 19:19

6 Answers6

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

Enlico
  • 23,259
  • 6
  • 48
  • 102
  • 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 '20 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.

Jivan
  • 21,522
  • 15
  • 80
  • 131
chi
  • 111,837
  • 3
  • 133
  • 218
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.

Jivan
  • 21,522
  • 15
  • 80
  • 131
Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
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]
chepner
  • 497,756
  • 71
  • 530
  • 681
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]
 λ> 
jpmarinier
  • 4,427
  • 1
  • 10
  • 23
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

  • 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 '20 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 '20 at 23:42
  • I still can't believe how this kind of answer is not eligible for deletion :) – Enlico Oct 21 '20 at 08:10
  • 6
    @Jivan no. The `liftMn` are basically obsolete since `Applicative` is a superclass of `Monad`. – leftaroundabout Oct 21 '20 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 '20 at 10:10