Get first item matching a criteria using foldr

Question

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

*hint*: implement `filter` using a fold and then just use `head` (or a variant that does not bottom out on empty lists if it's important for you) — Random Dev, Aug 30 '14 at 12:34
mind that finding the first item from the left while examining the list from the right will traverse the whole list anyway. — soulcheck, Aug 30 '14 at 12:35
@soulcheck I don't think that's right. If we assume we've found the first element `x'` matching `p` in `xs`, and we find that `x` matches `p`, we do not need to inspect `x'` (hence need not compute `x'`) to find the first element matching `p` in `x:xs`. — Daniel Wagner, Aug 30 '14 at 14:45
@DanielWagner you don't know which one is first if you start from the right. Imagine a simple case where you want to find the first (from the left) odd number in a list, starting from the right. No way to know if there's no more odd numbers to the left of what you found so far unless you actually test them. — soulcheck, Aug 30 '14 at 15:16
@soulcheck That would be a problem if you were implementing this using `foldl`. `foldr` doesn't start from the right, it associates to the right: http://stackoverflow.com/a/384919/2476735. — David Young, Aug 30 '14 at 15:39
@DavidYoung Ahh, right. It can skip evaluating the right argument if the predicate is true.I always forget how lazy haskell is. — soulcheck, Aug 30 '14 at 16:00
Surprised nobody's mentioned the `First` monoid. Combine that with the default definition of `foldMap` to get a working implementation. — John L, Aug 30 '14 at 18:02
@JohnL It's a bit voodoo, but yes, throw in Control.Newtype and you have `ala' First foldMap :: (a -> Maybe b) -> [a] -> Maybe b`. — pigworker, Aug 31 '14 at 06:28

chi · Accepted Answer · 2014-08-30T21:09:21.910

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.)

Just a minor note: the monomorphism restriction doesn't apply if you give an explicit type signature, so adding it should be fine. — bennofs, Aug 30 '14 at 21:04

Get first item matching a criteria using foldr

1 Answers1