Hello, 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? More specifically, I would like to define: inv :: (Monad m, M.MonadPlus m, ???) => m a -> m () inv m = if m fails then return () if m succeeds then fail The following obviously doesn't work: inv m = (m >> mzero) `mplus` return () because it will always return (). There's also a 'inversion' for natural numbers: invN :: Int -> Int invN 0 = 1 invN n = 0 but how can I define that without pattern matching, so only using arithmetic operations, +, -, *, ^, ...? The reason I ask this is that I'm writing a parser combinator library to understand parser a bit better. And I would like to define the combinator: notFollowedBy :: P t m a -> P t m () 'notFollowedBy p' fails when p succeeds and returns () when p fails. I will share the code when it's a bit more polished. Thanks, Bas
On Feb 6, 2008 9:39 AM, Miguel Mitrofanov <miguelimo38@yandex.ru> wrote:
How can I define this for an arbitrary Monad m?
Such as Identity?
An arbirtrary monad can't be inverted, however there's Error and ErrorT that provide throwing and catching abilities. I guess your parser is a monad transformer, so *maybe* the solution is to require MonadError from the inner monad. Cheers, -- Felipe.
On Feb 6, 2008 12:45 PM, Felipe Lessa <felipe.lessa@gmail.com> wrote:
I guess your parser is a monad transformer, so *maybe* the solution is to require MonadError from the inner monad.
Indeed my parser 'P t m a' is a monad transformer. I will try out requiring 'm' to have a 'MonadError' constraint and see how far I come with that. I'll let you know. Thanks, Bas
On Feb 6, 2008 12:51 PM, Bas van Dijk <v.dijk.bas@gmail.com> wrote:
I will try out requiring 'm' to have a 'MonadError' constraint and see how far I come with that.
I'm now trying to define 'inv' using 'catchError` but I can't get it to work. The following obviously doesn't work: import Control.Monad.Error inv :: MonadError e m => m a -> m () inv m = (m >> fail "") `catchError` \_ -> (return ()) Bas
Bas van Dijk wrote:
The following obviously doesn't work:
import Control.Monad.Error
inv :: MonadError e m => m a -> m () inv m = (m >> fail "") `catchError` \_ -> (return ())
What about this? inv :: MonadError e m => m a -> m () inv m = join $ (m >> return mzero) `catchError` \_ -> return (return ()) Tillmann
On Feb 6, 2008 8:27 PM, Tillmann Rendel <rendel@rbg.informatik.tu-darmstadt.de> wrote:
What about this?
inv :: MonadError e m => m a -> m () inv m = join $ (m >> return mzero) `catchError` \_ -> return (return ())
Beautiful! That's the one I'm looking for! I was already defining a 'MonadInvert' class and a bunch of instances like below but this is a much more flexible solution. ------------------------------------------------------------------------------------------------- -- | A Monad that supports inversion. -- Turning success into failure and failure into success. class Monad m => MonadInvert m where -- | @invert m@ fails when @m@ is successfull (returns a value) -- and returns @()@ when @m@ fails . invert :: m a -> m () instance MonadInvert Maybe where invert Nothing = Just () invert (Just _) = Nothing instance MonadInvert [] where invert [] = [()] invert (_:_) = [] instance E.Error e => MonadInvert (Either e) where invert (Left _) = Right () invert (Right _) = Left E.noMsg instance (E.Error e, MonadInvert m) => MonadInvert (E.ErrorT e m) where invert = T.lift . invert . E.runErrorT instance MonadInvert m => MonadInvert (S.StateT st m) where invert m = S.StateT $ \s -> (invert $ S.runStateT m s) >>= \u -> return (u, s) ... ------------------------------------------------------------------------------------------------- Thanks very much. Bas
G'day all. On Feb 6, 2008 12:45 PM, Felipe Lessa <felipe.lessa@gmail.com> wrote:
I guess your parser is a monad transformer, so *maybe* the solution is to require MonadError from the inner monad.
Quoting Bas van Dijk <v.dijk.bas@gmail.com>:
Indeed my parser 'P t m a' is a monad transformer. I will try out requiring 'm' to have a 'MonadError' constraint and see how far I come with that.
I've occasionally found this useful: class (Monad m) => MonadNegate m where mtrue :: m () mfalse :: m () mnot :: m a -> m () mtrue = return () mfalse = fail "False" Cheers, Andrew Bromage
On Feb 6, 2008 12:39 PM, Miguel Mitrofanov <miguelimo38@yandex.ru> wrote:
invM :: Maybe a -> Maybe () invM Nothing = Just () invM (Just _) = Nothing
invL :: [] a -> [] () invL [] = [()] invL (_:_) = []
How can I define this for an arbitrary Monad m?
Such as Identity?
Well in: inv :: (Monad m, ...) => m a -> m () inv m = ... I don't mind that there are more constraints on 'm' than just Monad maybe a MonadPlus constraint or others are needed. (I was even thinking about a MonadTimes class as in: class MonadPlus m => MonadTimes m where mone :: m () mtimes :: m a -> m a -> m a ) Thanks, Bas
On Feb 6, 2008 12:50 PM, Miguel Mitrofanov <miguelimo38@yandex.ru> wrote:
class Monad m => MonadInv m where inv :: m a -> m ()
With this constraint you certainly can have your "inv".
Yes indeed. But I was kind of hoping that I could use standard Haskell classes without adding my own. (BTW I would like to know of other possible applications of 'inv' besides my parser. So yell if you find one please) Thanks, Bas
On Feb 6, 2008 11:32 AM, Bas van Dijk <v.dijk.bas@gmail.com> wrote:
The following obviously doesn't work:
inv m = (m >> mzero) `mplus` return ()
because it will always return ().
How about: inv m = do success <- (m >> return True) `mplus` return False if success then mzero else return () Luke
On Feb 6, 2008 1:49 PM, Lutz Donnerhacke <lutz@iks-jena.de> wrote:
inv m = if m == mzero then return () else mzero `asTypeOf` m
Interesting!
:t inv inv :: (MonadPlus m, Eq (m ())) => m () -> m ()
The 'Eq' constraint on 'm ()' is a bit problemetic I think in case 'm' is a function like a 'State'. Thanks, Bas
On Feb 6, 2008 6:32 AM, Bas van Dijk <v.dijk.bas@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@zednenem.com> <http://www.eyrie.org/~zednenem/>
On Feb 7, 2008 4:58 AM, David Menendez <dave@zednenem.com> wrote:
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>.
Thanks for pointing me to this very interesting paper! Bas
participants (8)
-
ajb＠spamcop.net -
Bas van Dijk -
David Menendez -
Felipe Lessa -
Luke Palmer -
Lutz Donnerhacke -
Miguel Mitrofanov -
Tillmann Rendel