Write a function using recursion or higher order functions

Question

How to write a function that takes a predicate f and a list xx and reutrns true if fx is true for some x∈xs?

For example:

 ghci>exists (>2) [1,2,3]
     True

This is the function I wrote:

 exists :: (t->Bool)->[t]->Bool
    exists f a []=error
    exists f a (x:xs)
                |if x∈f a  =True
                |otherwise= x:f a xs

I know this is not right, but I don't know why. Do I need to write this predicate function f first, then used it inside the function exists. Because I really don't know how to compare one element of list xs with the function.

Answer 1

If we take a look at your definition,

exists :: (t -> Bool) -> [t] -> Bool
exists f a []=error
exists f a (x:xs)
            |if x∈f a  =True
            |otherwise= x:f a xs

We see that your type is

exists :: (t -> Bool) -> [t] -> Bool

So exists must take two parameters, one predicate function of type (t -> Bool) and one list of type [t]. It returns a Bool. This seem okay as per our intention of the specification.

Let us look at the first line of your terms:

exists f a [] = error

This function suddenly takes three parameters. The f and the empty list constructor [] looks okay, but the a is not mentioned in the type specification. Hence, we prune it out:

exists f [] = error

Now, the error returned is not of boolean value. But the spec says it must be. Let us suppose we are asking exists (<2) []. Then would a natural answer to the question be True or False? Or paraphrased, is there any element x in [] satisfying the predicate f x ?

On to the next line,

exists f a (x:xs)
      |if x∈f a  =True
      |otherwise= x:f a xs

We learned that the a has to go by the type specification, so let us prune it. Since we have now grown a natural dislike for the a, why not prune it everywhere it occur. Also, since the if will produce a syntax error, lets rid ourselves of that too:

exists f (x:xs)
      | x∈f    = True
      | otherwise = x:f xs

The x∈f does not make much sense, but f x does. The guard variant will be taken if f x returns true. Now, the True which is returned here sounds about right. It signifies that we have found an element in the list matching the predicate - and lo n' behold, x might be it!

So we turn our attention to the final line. The otherwise means that the guard f x did not return True. As a consequence, the x is not satisfying the predicate, so we must search the rest of the list.

The Right-hand-side x : f xs is peculiar. The : means that we will try to return a list, but the return type of the function is something of type Bool. The type checker won't like us if we try this. Furthermore, we have no reason to look at the x anymore since we just determined it does not satisfy the predicate.

The key thing you are missing is that we need recursion at this point. We need to search the tail xs of the list somehow - and recursion means to invoke the exists function on the tail.

Your general track is right, but ask again if something is unclear. One trick might be to go by the types for the recursion case: "What do i have to supply exists for it to return a Bool value?".

Answer 2

Actually your original version wasn't too far from working. To fix it, write:

exists :: (t -> Bool) -> [t] -> Bool
exists _ [] = False
exists f (x:xs)
            | f x = True
            | otherwise = exists f xs

Answer 3

Your desired example usage is this

ghci>exists (>2) [1,2,3]
True

Stop. Hoogle time. ( <------ This should be the Haskell motto imho)

You want a function ("exists") that takes two parameters. The first is a unary function (a -> Bool) and the second is a list [a]. The desired result is a Bool

Hoogling that type signature, (a -> Bool) -> [a] -> Bool, the top hits are any, all, and find. As Andrew has noted, any is the one that behaves like the "exists" function.

As a side note, my first thought was to use find, which returns a Maybe a, and then pattern match. If it returns Nothing, then the result would be False, otherwise True.

As another side note, the actual implementation is simply any p = or . map p.

The third side note is probably the answer to your actual question. How is map defined? Hoogle is once again your friend. Search for the method's name and you can find a page that links to the source. I suggest you do this for map and or, but will only show map here.

map _ []     = []
map f (x:xs) = f x : map f xs

That's the basic way to recurse over a list. recursiveCall f (x:xs) = f x : recursiveCall f xs But if it can be written with map, filter, or foldl/foldr, then you should do it with these recursive methods. (Stop. Hoogle time. Search for those method names and check out the source; it's pretty straightforward.)

Answer 4

I think the function you want already exists -- any:

Prelude> :t any
any :: (a -> Bool) -> [a] -> Bool
Prelude> any (<3) [1, 2, 3, 4]
True
Prelude> any (<3) [3, 4, 5, 6]
False

And then, in the spirit of your question -- not just getting a working function but working out how it's done -- we can look up the definition in the prelude:

any p xs = or (map p xs)

We map the function over the list to get a new [Bool] list, and then check with or to see if any of them are True, which by the way thanks to lazy evaluation short circuits as needed:

Prelude> any (<3) [1, 2..]
True

Answer 5

Instead of using x in f, just apply f to x using f x as the predicate in the if statement. Your otherwise clause should also return a Bool: the result of exists on the rest of the list.