How to compose functions that return Bools to one function

Question

There is a similar question I found here that asks almost the same thing, but not quite.

The question I have is how to compose a list of functions of type (a -> Bool) to be one function that is also (a -> Bool).

Ex.

compose :: [(a -> Bool)] -> (a -> Bool)
compose []     = **?**
compose (x:xs) = x **?** compose xs

The question that was similar to this was taking three functions and mixing them all like so:

newFunction x f g y = f x || g x || y x

But this is very limited because you have to supply a specific number of functions, and it does not return another function, it returns a Boolean. I essentially want a function that gives me the above function without functions as arguments.

I tried messing with Monoids to make this work but I ran into issues with wrapping the functions into a Monoid in the first place, let alone actually composing them together as newFunction does.

Is there a way to compose a list of functions of type (a -> Bool) to one function of the same type?

Answer 1

We can make use of any :: Foldable => (a -> Bool) -> f a -> Bool here:

compose :: Foldable f => f (a -> Bool) -> a -> Bool
compose = flip (any . flip ($))

or as @chepner suggests, with a (&):

import Data.Function((&))

compose :: Foldable f => f (a -> Bool) -> a -> Bool
compose = flip (any . (&))

or without the point-free styling (and probably simpler to understand):

compose :: Foldable f => f (a -> Bool) -> a -> Bool
compose l x = any ($ x) l

The above will work with any sort of Foldable, so a list [], Maybe, etc.

Answer 2

Look: compose xs in your definition is a function. So you can call it with an argument - like compose xs a, - and that will return a Bool.

You can use this to define the recursive case.

First of all, the recursive case must return a function - because that's what your type signature states. So it must look something like:

compose (x:xs) = \a -> ...

Now, the logic would go like this: first of all, call the first function in the list - like x a, - and if it returns true, then that's the result; otherwise, call the composition of the tail - like compose xs a. Let's write that down:

compose (x:xs) = \a -> x a || compose xs a

Next up, you need to decide what to do with the empty list. Obviously it can be either a function that always returns True or a function that always returns False, there can be no other options unless you can inspect the argument somehow, which you can't, because it's of generic type.

So, should it return True or False? Let's see: if it returns True, then any composition will always be True, that's how the || operator works. So we might as well just write compose _ = \_ -> True. Therefore, the only sane variant is for it to return False.

Summing up all of the above, here's your definition:

compose [] = \a -> False
compose (x:xs) = \a -> x a || compose xs a

And of course, you can use a shorter syntax instead of returning lambdas:

compose [] a = False
compose (x:xs) a = x a || compose xs a

Answer 3

To implement this using monoids you can use the Any (from Data.Monoid) boolean wrapper which implements the disjunction behaviour you want when combining values e.g.

(Any False) `mappend` (Any True)
=> Any {getAny = True}

Functions which return monoidal values are themselves monoids - mappending two such functions returns a function which evalulates the argument on both functions and mappends the results e.g.

f :: Int -> Any
f x = Any $ x > 10

g :: Int -> Any
g x = Any $ x < 3

comp :: Int -> Any
comp = f `mappend` g

comp 0
=> Any {getAny = True}

comp 4
=> Any {getAny = False}

comp 11
=> Any {getAny = True}

So if you lift each a -> Bool into a function a -> Any then these be composed with mappend.

mconcat reduces a list of monoidal values into a single value so applying this to a list of a -> Any function returns a function which applies the disjunction to each result. You then need to unwrap the Bool from the resulting Any value with getAny.

import Data.Monoid

compose :: [(a -> Bool)] -> (a -> Bool)
compose fs x = let anyfs = map (\f -> Any . f) fs
                   combined = mconcat anyfs
                   anyResult = combined x
                in getAny anyResult

This can also be written as:

compose :: [(a -> Bool)] -> (a -> Bool)
compose = (getAny .) . mconcat . (map (Any .))

As danidiaz points out in the comments, you can also use foldMap. This also has a more general type:

compose :: Foldable t => t (a -> Bool) -> a -> Bool
compose = (getAny .) . foldMap (Any .)

Answer 4

A simpler example (I am no Haskeller), based on your requirements:

compose :: [(a -> Bool)] -> (a -> Bool)
compose []     = (\y -> False)
compose (x:xs)  = (\y -> (x y) || ((compose xs) y))