Higher order OR in Haskell [duplicate]

Question

Here is an example problem I'm thinking about: Take the sum of every x from 1 to n where x is evenly divisible by 3 or 5, so something like this:

divisible a b = rem b a == 0
sum3or5 n = sum [x | x <- [1..n], divisible 3 x || divisible 5 x]

Coming from Scheme, I would like to implement this using a filter, something like this:

divisible a b = rem b a == 0
sum3or5 n = sum $ filter div3or5 [1..n] where
    div3or5 n = (divides 3 n) || (divides 5 n)

I'm thinking, is there a higher-order logical OR (||), so that I could write 'div3or5' point-free style, something like this?:

divisible a b = rem a b == 0
sum3or5 = sum $ filter (divisible 3 || divisible 5) . range

Thank you for your help.

Answer 1

Yes. You can "lift" (||) from booleans to functions from something to booleans. So you want something like

(||) :: Bool -> Bool -> Bool

to turn into

(||) :: (r -> Bool) -> (r -> Bool) -> (r -> Bool)

This happens to be exactly what the applicative instance of functions are good for.

liftA2      :: (a -> b -> c) -> (r -> a) -> (r -> b) -> (r -> c)

so

liftA2 (||) :: (r -> Bool) -> (r -> Bool) -> (r -> Bool)

which means, in your case, you can write your filter as

filter (liftA2 (||) (divides 3) (divides 5))

which takes an integral number and decides if it's divisible by 3 or 5.

---

If you want, you can define something like

(<||>) = liftA2 (||)

or, equivalently,

f <||> g = \x -> f x || g x

and then you can write your filter as

filter (divisible 3 <||> divisible 5)

Wrapping angle brackets around operators is sort of an idiom for showing that they are lifted into something else (functor, applicative, monoid).