On Feb 6, 2008 6:32 AM, Bas van Dijk
Is there a way to 'invert' an arbitrary Monad?
By 'inverting' I mean to turn success into failure and failure into success. Here are some specific inversions of the Maybe and List Monad:
invM :: Maybe a -> Maybe () invM Nothing = Just () invM (Just _) = Nothing
invL :: [] a -> [] () invL [] = [()] invL (_:_) = []
How can I define this for an arbitrary Monad m?
If you're doing any kind of backtracking or non-determinism, you might
consider the msplit operation defined in "Backtracking, Interleaving,
and Terminating Monad Transformers"
http://okmij.org/ftp/Computation/monads.html#LogicT.
Essentially, this defines a class of monads with zero, plus, and a
split operation:
class (MonadPlus m) => MonadSplit m where
msplit :: m a -> m (Maybe (a, m a))
Essentially, if 'm' returns no results, then 'msplit m' returns
Nothing, otherwise it returns Just (a, m'), where a is the first
result, and m' is a computation which produces the remaining results
(if any).
There is an obvious implementation for the list monad, but msplit can
also be defined for a monad transformer.
There are a bunch of useful operations using msplit, such as the "soft cut",
ifte :: (MonadSplit m) => m a -> (a -> m b) -> m b -> m b
ifte p th el = msplit p >>= maybe el (\(a,m) -> th a `mplus` (m >>= th))
'ifte p th el' is equivalent to 'p >>= th' if p returns any results,
and 'el' otherwise. Note that it is *not* the same as (p >>= th)
`mplus` el.
Here's your inverse operation:
mnot :: (MonadSplit m) => m a -> m ()
mnot m = msplit m >>= maybe (return ()) mzero
--
Dave Menendez