Is there a Haskell idiom for trying several functions and stop as soon as one succeeds?

Question

In Haskell, I can use the type a -> Maybe b to model a function that either returns a value of type b, or returns nothing (it fails).

If I have types a1, ..., a(n+1) and functions f1, ..., fn, with fi :: ai -> Maybe a(i+1) for all i, 1 <= i <= n, I can chain the functions by using the >>= operator of the Maybe monad and write:

f1 x >>= f2 >>= f3 >>=... >>= fn

The >>= operator ensures that each function is applied as long as its predecessor has returned a meaningful value. As soon as a function in the chain fails, the whole chain fails (returns Nothing) and further functions in the chain are not evaluated.

I have a somewhat similar pattern in which I want to try several functions on the same input, and return as soon as one function succeeds. If all functions fail (return Nothing), the whole computation should fail. More precisely, I have functions f1, ..., fn :: a -> Maybe b and I define the function

tryFunctions :: [a -> Maybe b] -> a -> Maybe b
tryFunctions []       _ = Nothing
tryFunctions (f : fs) x = case f x of
                            Nothing    -> tryFunctions fs x
                            r@(Just _) -> r

In a sense this is dual to the Maybe monad in that a computation stops at the first success instead of at the first failure.

Of course, I can use the function I have written above but I was wondering if there is a better, well-established and idiomatic way of expressing this pattern in Haskell.

Answer 1

Given a closed set (fixed number of elements) S with elements {a..z} and a binary operator *:

There is a single identity element i such that:

forall x in S: i * x = x = x * i

The operator is associative such that:

forall a, b, c in S: a * (b * c) = (a * b) * c

You have a monoid.

Now given any monoid you can define a binary function f as:

f(i, x) = x
f(x, _) = x

What this means is that for the example of the Maybe monoid (Nothing is the identity element denoted above as i):

f(Nothing, Just 5) = Just 5
f(Just 5, Nothing) = Just 5
f(Just 5, Just 10) = Just 5
f(Nothing, f(Nothing, Just 5)) = Just 5
f(Nothing, f(Just 5, Nothing)) = Just 5

Surprisingly, I can't find this precise function in the default libraries, which is likely due to my own inexperience. If anyone else can volunteer this, I would sincerely appreciate it.

Here's the implementation I deduced off hand from the above example:

(<||>) :: (Monoid a, Eq a) => a -> a -> a
x <||> y
     | x == mempty = y
     | True = x

Example:

λ> [] <||> [1,2] <||> [3,4]
[1,2]
λ> Just "foo" <||> Nothing <||> Just "bar"
Just "foo"
λ> Nothing <||> Just "foo" <||> Just "bar"
Just "foo"
λ> 

Then if you want to use a list of functions as input...

tryFunctions x funcs = foldl1 (<||>) $ map ($ x) funcs

example:

instance Monoid Bool where
         mempty = False
         mconcat = or
         mappend = (||)

λ> tryFunctions 8 [odd, even]
True
λ> tryFunctions 8 [odd, odd]
False
λ> tryFunctions 8 [odd, odd, even]
True
λ> 

Answer 2

import Data.Monoid

tryFunctions :: a -> [a -> Maybe b] -> Maybe b
tryFunctions x = getFirst . mconcat . map (First . ($ x))

Answer 3

This sounds a lot like replacing failure by a list of successes

You're talking about Maybe a rather than [a], but in fact they're very similar: we can think of Maybe a as being like [a], except it can contain at most one element (ie. Nothing ~= [] and Just x ~= [x]).

In the case of lists, your tryFunctions would be very simple: apply all of the functions to the given argument then concatenate all of the results together. concatMap will do this nicely:

tryFunctions :: [a -> [b]] -> a -> [b]
tryFunctions fs x = concatMap ($ x) fs

In this way, we can see that the <|> operator for Maybe acts like concatenation for 'lists with at most one element'.

Answer 4

In the spirit of Conal, break it into smaller simpler operations.

In this case, asum from Data.Foldable does the main part.

tryFunction fs x = asum (map ($ x) fs)

Alternatively, a la Jimmy Hoffa's reply you can use the Monoid instance for (->) but then you need a Monoid instance for Maybe and the standard one doesn't do what you want. You want First from Data.Monoid.

tryFunction = fmap getFirst . fold . map (fmap First)

(Or mconcat for an older, more specialized version of fold.)