How to implement this using map/filter

2

votes

I'm supposed to come up with a function and::[Bool]->Bool, where (and xs) is True only if xs containst no False elements.

I am perfectly able to write this using recursion. I even tried it using map, BUT map ALWAYS return a list, which conflicts my return type.

Here's my code using recursion: (it works just fine)

isTrue::[Bool]->Bool
isTrue []       =True
isTrue (x:xs)
 | (x == True)  =isTrue(xs)
 | otherwise    =False

I tried doing this with map: (this will never work)

and::[Bool]->Bool
and xs = map (True ==) xs

So how in the world can I use map, filter or foldr to implement this crazy function? Thanks

haskellhigher-order-functions

3

votes

Consider also takeWhile in a similar fashion as filter, yet halting the filtering once the first False is encountered, as follows,

and' :: [Bool] -> Bool
and' xs = xs == takeWhile (== True) xs

2

votes

Filter True values and check if the result is an empty list:

and' :: [Bool] -> Bool
and' = null . filter (== False)

More classic approach using foldr:

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

2

votes

foldr is the way to go:

There are various ways to get to that. The first is to think about folding as inserting a binary operation between pairs of elements:

foldr c n [x1,x2,x3,...,xn] =
    x1 `c` (x2 `c` (x3 `c` (... `c` (xn `c` n))))

So in this case,

foldr (&&) True [x1,x2,x3,...,xn] =
    x1 && x2 && x3 && ... && xn && True

Note that && is right associative, so we don't need the parentheses there.

Another approach is to figure out how to convert the recursive form you gave into a fold. The thing to read to see how this works in general is Graham Hutton's "A Tutorial on the Universality and Expressiveness of Fold".

Start with your recursive form:

and::[Bool]->Bool
and []       =True
and (x:xs)
 | (x == True)  = and (xs)
 | otherwise    = False

Now there's no reason to ask if x==True because that's actually just the same as testing x directly. And there's no need for extra parentheses around a function argument. So we can rewrite that like this:

and []        = True
and (x:xs)
  | x         = and xs
  | otherwise = False

Now let's see if we can write this as a fold:

and xs = foldr c n xs

Because and [] = True we know that n = True:

and xs = foldr c True xs

Now look at the recursive case:

and (x:xs)
  | x         = and xs
  | otherwise = False

You can see that this depends only on x and on and xs. This means that we will be able to come up with a c so the fold will work out right:

c x r
  | x         = r
  | otherwise = False

r is the result of applying and to the whole rest of the list. But what is this c function? It's just (&&)!

So we get

and xs = foldr (&&) True xs

At each step, foldr passes (&&) the current element and the result of folding over the rest of the list.

We don't actually need that xs argument, so we can write

and = foldr (&&) True

How to implement this using map/filter

3 Answers