[Haskell-beginners] Searching Maybe lists

[Alexander Dunlap]

On Mon, May 18, 2009 at 7:56 PM, aditya siram <aditya.siram at gmail.com> wrote:
> Hi all,
> I would like to define a function that takes a list and a function that
> evaluates each member of the list to a Maybe value and output the first
> element in the list that evaluates to 'Just y', or 'Nothing' once the list
> has been completely processed. So something like:
>
> findMaybe :: [a] -> (a -> Maybe b) -> Maybe b
>
> The problem is that I don't want it to go through the entire list, but
> short-circuit when it hits a 'Just ...'. So far I have:
>
> orMaybe :: Maybe a -> Maybe a -> Maybe a
> orMaybe m1 m2 = case (m1,m2) of
>                   (_, Just a) -> Just a
>                   (Just a, _) -> Just a
>                   _           -> Nothing
>
> findMaybe :: [a] -> (a -> Maybe b) -> Maybe b
> findMaybe as f = foldr (\a sofar -> sofar `orMaybe` (f a)) Nothing as
>
> 'findMaybe', as far as I can tell, traverses the entire input list which is
> undesirable for long lists. How can I fix it?
>
> Curiously, the regular 'Data.List.find' function that applies a Boolean
> predicate to each member of the list also seems to first traverse the entire
> list using 'filter' and then grabs the head of the result.
>
> Thanks ...
> -deech
>

find doesn't traverse the entire list. The filter function can
traverse the whole list, but only if you observe all of its values
afterwards. If you only look at the first value, like find does, then
filter only goes until it produces one value. This is because of
laziness.

We can test that filter doesn't examine the entire list by trying it
on an infinite list. If it traversed the entire list, it couldn't
possibly work on an infinite list!

$ ghci
GHCi, version 6.10.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> import Data.List
Prelude Data.List> find (==3) [1..]
Just 3
Prelude Data.List>

But it does work! It only looks at values until it finds one that
matches the predicate.

Alex