CODEWITHSUNDEEP
haskellfold
Rohit Sharma
Rohit Sharma

Reputation: 6500

Get first item matching a criteria using foldr

I am giving my self exercises and wondering if there is a way to find the first item from left in the list matching a certain criteria using just foldr? I want the recursion to stop when the first item is found (I know I could probably combine using take) but I am curious to know if it is possible to do just using foldr?

firstFind (\x -> x > 1000) [] xs

Upvotes: 2

Views: 1559

Answers (1)

chi
chi

Reputation: 116174

The problem: find f and b.

firstFind :: (a -> Bool) -> [a] -> Maybe a
firstFind p list = foldr f b list
   where f = ???
         b = ???

We want:

firstFind p [] = Nothing

but we also have

firstFind p [] 
= def. firstFind
foldr f b []
= def. foldr
b

from which we see what b must be.

Further, take list = x:xs

firstFind p list
= def. firstFind
foldr f b (x:xs)
= def. foldr
f x (foldr f b xs)
= def. firstFind
f x (firstFind p xs)

Now, we just need to find f so that this chooses the first match.

Recall that f can depend on p. What should f return when p x is true? What in the opposite case?

where -- f :: a -> Maybe a -> Maybe a
      f x y = ???

(Note: above I wrote the type signature for f for clarity, but you don't have to include it in your code. If you add it, uncommented, you will trip into a type variable confusion: that a is not the same a as in findFirst because it is generalized locally -- since you are just beginning, ignore this and simply remove it for the moment being.)

Upvotes: 9

Related Questions