CODEWITHSUNDEEP
functionhaskellfunctional-programming
Ddota
Ddota

Reputation: 163

function that accepts a function and a list and returns boolean

I am very new to Haskell and functional programming. I am trying to implement the task below:

Create a function that accepts a function and a list and returns true if the function returns true for at least one item in the list, and false otherwise. Should work polymorphically.

I have searched many ways to do it, including Prelude and the any function

any :: Foldable t => (a -> Bool) -> t a -> Bool

However, I am struggling to implement them. This is what I have:

list = [2,3,45,17,78]

checkMatch :: Int -> Bool 
checkMatch x 
    | x `elem` list = True
    | otherwise = False

main = do
    print (checkMatch 45)

Any help how to use the Prelude or any function for this task. Don't just provide the answer, please do explain the procedure. Regards.

Upvotes: 3

Views: 3712

Answers (2)

Davislor
Davislor

Reputation: 15134

Okay. Not a complete answer, because you want to solve the problem yourself, but some hints.

I’d strongly suggest you start out by writing the type signatures until you get a shell that compiles and handles a few cases, and then filling in the function definitions. So let’s start with the correct type signature.

In Haskell, if you want a function that takes any types of argument, you name each type with a different lowercase name, typically a letter. Specific types have uppercase names, generic types lowercase letters. So a function that takes any type of argument and returns a Bool would have the type signature a -> Bool. For your second argument, you want to take a list of some arbitrary type of element. You want to pass its elements to your function, so it has to contain the same type as the domain of the function, which we called a. (If it could hold anything, we would pick another lowercase name, such as b.) You write that list type as [a]. You want to return a Bool.

Therefore, your type signature should be (a -> Bool) -> [a] -> Bool. Typically when we write a function that operates on lists, a good approach is tail-recursion, where we split the list into its head and tail (x:xs), do something with x, and then call the function again on xs until you end up with an empty list. You were on the right track with your pattern guards, so you can start with the following skeleton:

checkMatch :: (a -> Bool) -> [a] -> Bool
checkMatch _ [] = _
checkMatch f (x:xs) | f x       = _
                    | otherwise = _

main :: IO()
main = do
  let shouldBeFalse = [1,3,5,7,9] :: [Int]
  let shouldBeTrue = [1..10] :: [Int]

  print (checkMatch (== " ") []) -- Does the empty string contain a space?
  print (checkMatch even shouldBeFalse)
  print (checkMatch even shouldBeTrue)

If you compile this, GHC will tell you that it found three “holes” in the program, which are the three _ symbols on the right side of the equals sign in lines 2, 3 and 4. (The _ in the pattern to the left of the equals sign means something different: that we don’t care what the function argument is when the list is empty. Why is that?) It will also tell you that the type it needs to fill each hole is an expression returning Bool. It will also give you a list of the local functions and variables that have that type. If you try to partly fill in one of the holes, say with f _ or checkMatch _ _, it will tell you what type you need to fill in the new holes you created.

Fill in all the holes with the correct program logic, and your program will work.

Upvotes: 6

nicodp
nicodp

Reputation: 2392

What you are looking for given your description is a function that takes a predicate (this is, a function that takes one or more arguments and returns a boolean) and a list, and returns true if at least one element of the list satisfies the predicate.

In Haskell, the predicate above is a function of type: a -> Bool. A simple example of this could be:

isEven :: Int -> Bool
isEven x = mod x 2 == 0`

which takes an integer number and returns whether or not it's even.

So, our function would be something like this:

isSatisfied :: (a -> Bool) -> [a] -> Bool
isSatisfied p [] = False
isSatisfied p (x:xs) = if (p x) then True else isSatisfied p xs

This defines a function that takes two parameters. The first one, p, is a predicate over the elements of the second argument. It takes an element of type a, and returns true whether or not it satisfies the predicate. For example, isEven will return true if there's some element in the list which is even:

Prelude> isSatisfied isEven [1]
False

But, if there's some even in the list:

Prelude> isSatisfied isEven [1,3,5,2,1,2]
True

I used pattern matching to define isSatisfied: the first case is the empty list, since the list has no elements there's no element that satisfies the predicate so it should evaluate to False. The non-empty case works in a recursive way as follows: first check the predicate against the head of the list x, leading to two possibilities. If x satisfies the predicate, we found an element and we should return True. Otherwise, we proceed checking on the rest of the list.

Basically, this is the definition of any from the Prelude:

Prelude> any isEven [1,2,3,4,5]
True
Prelude> any isEven []
False

Upvotes: 1

Related Questions