CODEWITHSUNDEEP
haskell
piggyback
piggyback

Reputation: 9264

Using foldl to return True if a list has only True values, otherwise false

here is my code:

boolTrueList :: [Bool] -> Bool
boolTrueList xs
  | length (filterFalse xs) > 0 = False
  | otherwise = True
  where
    filterFalse = filter (==False)

This is perfectly working, however I would like to rewrite the same thing with foldr/foldl, but I am stuck.

My idea is to fold a list until I find a false value and then, stop. Any hint?

Upvotes: 0

Views: 1882

Answers (2)

RonaldBarzell
RonaldBarzell

Reputation: 3830

There's a way to think about folds that I have found very useful and intuitive (I probably read this somewhere). Please note this may not lead to the most efficient solution, but my concern here is with clarity.

Don't think of fold as a function that builds a value from a list, and instead think of it as a way to insert an operator between elements of the list. When you do that, fold then becomes a way of transforming a list into an expression. So for example, the following:

foldr op I [A,..,Z]

Will produce the following expansion:

A op .. op Z op I

If you apply that thinking to your issue, all you need to do is ask yourself what should op and I be to ensure that you only get True if A .. Z are True? As a hint, I is usually the identity element with respect to op (a value that doesn't change the expression, like 0 would be for addition).

Well, we know from logic that and (&&) is only true if ALL its operands are true. Likewise, True is the identity element with respect to &&. So with that said, your expansion would be:

A && .. && Z && True

So your fold would be:

foldr (&&) True [A,..,Z]

Which means your function would be: 

boolTrueList x = foldr (&&) True x

Or in a more point-free style:

boolTrueList = foldr (&&) True

It isn't enough to use higher-order functions to avoid iteration, we should avoid the iterative mindset. Think in terms of open-ended expressions and not "at this point, this value will propagate". More often than not, iterations are simply low level ways of generating open-ended expressions, and because our languages forced us to do this, our mindset has often been stuck at it, even when we have languages that allow us to think at the expression level.

Upvotes: 5

Daniel Fischer
Daniel Fischer

Reputation: 183888

My idea is to fold a list until I find a false value and then, stop. Any hint?

If you want to stop early, you have to use foldr. foldl always has to traverse the entire list (so doesn't work at all on infinite lists).

So you want

foldr combine default list

The default is the result for an empty list, that would be True here. Now, how would we want to combine?

When a False is encountered, we want to return False immediately, so

combine False _ = False

and when the value is True, we must go on, so

combine True more = more

In other words, combine = (&&), so

boolTrueList = foldr (&&) True

or, even shorter

boolTrueList = and

Upvotes: 12

Related Questions