[Haskell-cafe] Inverting a Monad

[David Menendez]

On Feb 6, 2008 6:32 AM, Bas van Dijk <v.dijk.bas at gmail.com> wrote:
> 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 <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>