A very common technique is to use Maybe to represent a possibly failing function as in:

lookup :: Eq a => a -> [(a,b)] -> Maybe b
lookup k ((k',v):_) | k == k' = Just v
lookup k (_:xs) = lookup k xs
lookup k [] = Nothing
rather than force the use of maybe, let your function work with any monad whatsoever.
lookup :: (Monad m, Eq a) => a -> [(a,b)] -> m b
lookup k ((k',v):_) | k == k' = return v
lookup k (_:xs) = lookup k xs
lookup k [] = fail "key not found"
now, since Maybe is an instance of Monad, your new function can be used anywhere your old one could have been without change, plus you can use it in any state/io/parser/list/whatever monad seamlessly. this also works the other way, if you have to use code which returns maybe, you can use it as a monad, see ExceptionMonad

- JohnMeacham

You could also use ContinuationPassingStyle, but UsingMonads is probably better.

Is there an argument for abstracting the failure behaviour out of Monad?

class Failable m where
  fail   :: String -> m a

class Monad m where
  (>>=)  :: m a -> (a -> m b) -> m b
  return :: a -> m a
(Error fixed; thanks, Stefan.)

- AndrewBromage

I've always felt a little disgusted by fail in the Monad class. (Also, firstly I confused it with mzero).

- StefanLjungstrand

Answer to self: No there isn't. The failure behaviour is there to support PatternMatching in ?DoNotation.

- AndrewBromage

How the failure behaviour is there to support PatternMatching in ?DoNotation?

I agreed with StefanLjungstrand at first, but upon reading the translation of do-notation in the report it makes sense for fail to be in Monad for pragmatic reasons (I guess one could change the translation depending on whether the class was in MonadPlus (or a ?MonadZero class)). The usual translation of p <- m one sees is m >>= \p -> ... the actual translation as defined in the report is let ok p = ...;ok _ = fail "..." in m >>= ok. The result is that pattern match failure calls fail rather than throws an exception. So in the List monad say, you could do do Just x <- xs;return x to get the behavior of collecting all defined values and discarding Nothings. Since list comprehension notation is more or less equivalent to the list monad [x | Just x <- xs] has the same behavior.

- DerekElkins