[Haskell-cafe] Inverting a Monad
David Menendez
dave at zednenem.com
Wed Feb 6 22:58:52 EST 2008
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/>
More information about the Haskell-Cafe
mailing list