Iterating over a Data.Set until success

user_1917160 0
Viewed 78

Suppose I have a function representing some computation that can fail

f :: a -> Maybe b

If I have a list l, I can find the first (when scanning left-to-right) item in the list on which f succeeds using findList f l, where findList is the following function

findList :: (a -> Maybe b) -> [a] -> Maybe b
findList f [] = Nothing
findList f (x : xs) = case f x of
  Nothing -> findList f xs
  Just y -> Just y

(or using, e.g., firstJust from the extra package).

Question.

What do I do if I want to do the same thing with a Set from containers?

That is, I want a function with signature

findSet :: (a -> Maybe b) -> Set a -> Maybe b

which is equivalent to

findSet f s = findList f (Set.toList s)

The line above works as an implementation. However, I don't want to create the intermediate list Set.toList s (even with lazy evaluation, there is still some unnecessary overhead, right?).

I also don't want to iterate over the entire set once a successful item has been found, as in the following implementation:

findSet f s = foldl g Nothing s
  where
    g Nothing x = f x
    g (Just y) _ = Just y

So is there a good way of traversing over a set "left-to-right", applying a computation that can fail to each member, and stopping at the first successful result?

option-type set haskell
2 Answers

I'd like to share a little trick somebody on IRC once showed me: early-exit-on-success is just another interpretation of early-exit-on-error. With that in mind, consider using Either b () instead of Maybe b; then

findOne :: (a -> Either b ()) -> Set a -> Either b ()
findOne = traverse_

Hardly even worth naming. If you must have Maybe, you can simply wrap this with the obvious isomorphism.

findOneMaybe :: (a -> Maybe b) -> Set a -> Maybe b
findOneMaybe f = to . traverse_ (from . f) where
    from = maybe (Right ()) Left
    to = either Just (const Nothing)
user_7916040

You can work with the fact that the Set is an instance of Foldable. You can thus implement a Fold function with:

import Control.Applicative((<|>))

findSet :: (a -> Maybe b) -> Set a -> Maybe b
findSet f = foldr ((<|>) . f) Nothing

this can in fact work with all instances of Foldable:

import Control.Applicative((<|>))

findSet :: (Alternative g, Foldable f) => (a -> g b) -> f a -> g b
findSet f = foldr ((<|>) . f) Nothing

or as @DanielWagner says, we can make use of First, since First will select the first Just, and thus work with:

import Control.Applicative((<|>))

findSet :: Foldable f => (a -> Maybe b) -> f a -> Maybe b
findSet f = getFirst . foldMap (First . f)

The implementation of toList is also implemented in terms of Foldable:

toList :: Foldable f => f a -> [a]
toList = foldr (:) []

so what we here do is instead of first wrapping it in a cons and then unwrap it, immediately apply f and work with the implementation of (<|>) :: Alternate f => f a -> f a -> f a.

user_675790
Related