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?

Fradin

fold with an accumulator function that calls each function and compose it according to your operator with the current result (e.g. ||)? – Bewick

I tried this, and maybe I just don't grasp the concept but I tried something like compose x f g = f x || g x but then the problem is that that does not work as an accumulator because it returns a Bool, and I need it to return a function that returns a Bool. – Fradin

Looks like you want to apply a list of functions to a single value and check if any results are True. – Equites

I tried what Khuldraeseth suggested and got it to work somewhat how I wanted it to with compose fs x = foldl (||) False $ map ($ x) fs which when supplied with a list of functions will compose them and return a function that takes a single variable. Thanks for the help! – Fradin

Willem's answer is nice. Consider that instead, but make sure you work through it and understand just what's going on! – Equites

Composition of functions has a specific meaning: the output of one function is used as the input of the next. You are not composing your input functions; you are applying each to the same argument and combining the results in some fashion. – Minter

try GHCi> :t (or .) . sequence. – Finicking

@WillNess while I see that your "(or .) . sequence" is incredibly elegant, it is also confusing to read compared to some of the other simpler functions that are maybe a little longer. – Fradin

@Fradin for me it is the only one I can read. :) the nested flips, I can't handle. – Finicking

So basically you were looking for a fold rather than a composition. A fold can always be transformed into recursion but usually the fold is more desirable – Euxenite

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.

Seed

flip id always seems a bit odd to me. Data.Function.(&) (or at least flip ($)) is equivalent and probably more suggestive of what is happening. – Minter

@chepner: you are correct, it is furthermore more "strong" w.r.t. the types, since it adds an extra contract that we deal with functions (although in the overall expression of course, this will be inferenced). – Seed

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

Predominance

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

Rating

Is getAny part of some module? – Fradin

It's part of the definition of the Any type, defined in Data.Monoid. newtype Any = Any {getAny :: Bool }. It's used to define the Boolean monoid with || as the operator. Any True <> Any False == Any True, as compared to, say, All True <> All False == All False (where All uses &&). – Minter

So I suppose the mconcat function in the second example is essentially just checking (||) for every function? – Fradin

map followed by mconcat is so common that it has its own function foldMap. This video nicely explains the use of foldMap youtube.com/watch?v=BovTQeDK7XI – Redroot

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

Bewick

@Fradin Thank for edit (of course it is False in the base case) – Bewick