8

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.

  • Not Haskell, but in C#, you'll occasionally see the null-coalesce operator (??) used like that: return f1 ?? f2 ?? f3 ?? DefaultValue; – Telastyn Jul 27 '15 at 17:16
  • 4
    Yes it does - this is Alternative which is the symbol infix operator <|> and is defined in terms of a Monoid – Jimmy Hoffa Jul 27 '15 at 17:21
8

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
λ> 
  • I do not understand why <|> treats the identity of a monoid in a special way. Couldn't one pick an arbitrary element of an arbitrary set to play that special role? Why does the set have to be a monoid and the special element wrt <|> its identity? – Giorgio Jul 27 '15 at 17:43
  • 1
    @Giorgio perhaps that's why <|> doesn't rely on monoid and I have this all mixed up? It relies on Alternative typeclass. To be certain - I'm looking at my own answer and realizing it's not quite right as [1,2] <|> [3] gives the unexpected [1,2,3] so everything about using the monoid type class to identify an identity is right - and the other key is associativity is necessary to get the expected behaviour, perhaps Alternative doesn't give the behaviour I thought off hand... – Jimmy Hoffa Jul 27 '15 at 18:00
  • @JimmyHoffa it will depend on the typclass Maybe <|> will be different to List <|> no ? – jk. Jul 27 '15 at 18:01
  • @Giorgio look at my last 2 examples of f to see why associativity is a necessity. – Jimmy Hoffa Jul 27 '15 at 18:02
  • i.e. monoid for lists is the empty list and concat – jk. Jul 27 '15 at 18:02
5
import Data.Monoid

tryFunctions :: a -> [a -> Maybe b] -> Maybe b
tryFunctions x = getFirst . mconcat . map (First . ($ x))
  • This is clean and simple but fixed to Maybe... My solution is constrained by Eq, somehow I feel like we're both missing something available by way of Monoid generally... – Jimmy Hoffa Jul 27 '15 at 18:46
  • @JimmyHoffa: Do you mean you would like to generalize this solution so that it can work with other data types, e.g. either? – Giorgio Jan 17 '16 at 8:34
  • @Giorgio exactly. I wish the only constraint could be Monoid so that anything with an identity element could have a set of 2 functions (I think this is a type of binary field), where one of the functions chooses identity over all others, and the other function always chooses the non-identity element. I just don't know how to do this without an Eq to know which value is identity or not though.. obviously in additive or multiplicative monoids you get the ladder function by default (always choose non-identity elements using the monoids binary function) – Jimmy Hoffa Jan 22 '16 at 17:28
  • foldMap can be used in place of mconcat . map – 4castle Jul 5 '17 at 1:37
4

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'.

1

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.)

  • Interesting solutions (+1). I find the first more intuitive. – Giorgio Jan 17 '16 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.