On Tue, Nov 17, 2009 at 7:39 PM, David Menendez wrote:

On Tue, Nov 17, 2009 at 6:31 PM, Ezra Lalonde wrote:

...

Using the same basic structure you did, and foldr, I think below is the simplest method:

==================== import Data.Maybe

searchList :: (a -> Bool) -> [a] -> Maybe [a] searchList p xs = foldr (\x acc -> if p x then Just (x: fromMaybe [] acc) else acc) Nothing xs ====================

This might be considered simpler:

searchList p = foldr (\x -> if p x then Just . maybe [x] (x:) else id) Nothing

The real problem with searchList is that it's strict and can't be made lazy. Because it returns Nothing when nothing matches the predicate, it has to traverse the entire list before returning anything. Instead, I would recommend filter, which can be used as-is or defined in terms of foldr.

filter p = foldr (\x -> if p x then (x:) else id) []

Compare the behavior of "searchList even [0..]" and "filter even [0..]".

...? filter even [0..] --> [0,2,4,6,8,...] searchList even [0...] --> Just [0,2,4,6,8,...] searchList gives Nothing in exactly those cases that filter gives []. They give _|_ in exactly the same situations. searchList could well be defined as: searchList p xs = if null ys then Nothing else Just ys where ys = filter p xs null is strict, so searchList is just as strict as filter. Luke

It looks quite neat to use the Maybe monoid here:

import Data.Monoid searchList p = foldr (\x -> if p x then mappend (Just [x]) else id) Nothing

but it seems that the Maybe Monoid instance keeps this strict. I fiddled with this a bit, and came up with the following:

instance (Monoid m) => Monoid (Maybe m) where mempty = Nothing -- as usual mappend (Just x) y = Just $ mappend x (fromMaybe mempty y) mappend Nothing y = y

which results in the expected behaviour (it's unsatisfyingly asymmetric, since it should (but can't) produce a Just if the second argument is Just without pattern-matching on the first, but there is only so much one can do without involving scary things like unamb). I'd be interested in what people thought of the relative merits of this alternative Monoid instance, but perhaps that would be a subject for a different thread.