Given a list of list of Booleans, return a Boolean

user_10699624 0
Viewed 1293

I have a function, defined as follows, that is given a list of lists of Booleans and returns a Boolean:

evaluates :: [[Bool]] -> Bool

I tried the following way:

evaluates  :: [[Bool]] -> Bool
evaluates  ((y:ys):xs) = (y && (head ys)) || evaluates (tail xs)

but this doesn't work.

The result I expect is:

[True && False && True] ||  [True] || [False && False]] = True

For an entry of: [[True, False, True], [True], [False, False]]

haskell
1 Answers

You try to do too much in a single function. Let us solve the problem in three steps:

  1. create a function that takes a list of Bools, and returns the logical AND of these Bools;
  2. create a function that takes a list of Bools and returns the logical OR of these Bools; and
  3. create a function that takes a list of [Bool]s, first maps it with the first function, and then performs the second function on that.

We can implement the first function with a foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b:

_and :: [Bool] -> Bool
_and = foldr (&&) True

in fact, the Haskell prelude already has an and :: Foldable f => f Bool -> Bool function.

The second function can be implemented with a foldr as well:

_or :: [Bool] -> Bool
_or = foldr (||) False

The Haskell prelude already has an or :: Foldable f => f Bool -> Bool function.

Now we can define evaluate with map :: (a -> b) -> [a] -> [b]:

evaluate :: [[Bool]] -> Bool
evaluate = _or . map _and

We can even generalize the above to work with two (possibly different) Foldables:

evaluate :: (Foldable f, Foldable g) => f (g Bool) -> Bool
evaluate = foldr ((||) . and) False

or like @DanielWagner says, we can use any :: Foldable f => (a -> Bool) -> f a -> Bool:

evaluate :: (Foldable f, Foldable g) => f (g Bool) -> Bool
evaluate = any and

For example:

Prelude> evaluate [[True, False, True], [True], [False, False]]
True
Prelude> evaluate [Just False, Just False, Nothing]
True
Prelude> evaluate [Just False, Just False, Just False]
False
Prelude> evaluate (Just [True, False, True])
False
Prelude> evaluate (Just [True, True, True])
True
user_675790
Related