On Mon, May 18, 2009 at 7:56 PM, aditya siram
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