Re[Haskell-cafe] cursive to foldr

[Luke Palmer]

On Tue, Nov 17, 2009 at 7:39 PM, David Menendez <dave at zednenem.com> wrote:
> On Tue, Nov 17, 2009 at 6:31 PM, Ezra Lalonde <ezra.lalonde at gmail.com> 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