Haskell idiom for trying several functions and stop as soon as one succeeds

functional programminghaskellpatterns-and-practices

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.

Best Answer

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
λ>
Related Topic