Applicative and Monad transformers
Hello, I have seen it said that all Monads are Applicative Functors because you can just do: instance (Monad f, Applicative f) => Applicative (ReaderT r f) where pure = return (<*>) = ap However, that instance for ReaderT does not exhibit the properties I was hoping for. By substitution the definition of ap: ap :: (Monad m) => m (a -> b) -> m a -> m b ap = liftM2 id liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) } we see that it becomes: instance (Monad f, Applicative f) => Applicative (ReaderT r f) where pure = return f <*> x = do { f' <- f; x' <- x; return (f' x') } What I would prefer is: instance (Monad f, Applicative f) => Applicative (ReaderT r f) where pure a = ReaderT $ const (pure a) f <*> a = ReaderT $ \r -> ((runReaderT f r) <*> (runReaderT a r)) I assume that only one version is correct, but I am having a hard time figuring out which one. I have attached a file which shows my motivation for prefering the second variation. There is a 'looker' function which does three lookups and combines the results using the Applicative Functor. With the first Applicative instance for ReaderT you will only get a failure message for the first lookup that fails -- which is what you expect with monadic behaviour. With the second instance, you get back a list of all the lookups that failed, which seems like what I would expect with Applicative Functor behaviour. Thanks! - jeremy {-# LANGUAGE FlexibleContexts, FlexibleInstances #-} module Main where import Control.Applicative (Applicative((<*>), pure), (<$>)) import Control.Monad (Monad((>>=), return), ap) import Control.Monad.Reader (MonadReader(ask, local), ReaderT(ReaderT, runReaderT)) import Data.Monoid(Monoid(mappend)) instance (Monad f, Applicative f) => Applicative (ReaderT r f) where pure = return (<*>) = ap {- instance (Monad f, Applicative f) => Applicative (ReaderT r f) where pure a = ReaderT $ const (pure a) f <*> a = ReaderT $ \r -> ((runReaderT f r) <*> (runReaderT a r)) -} instance (Monoid e) => Applicative (Either e) where pure = Right (Left errF) <*> (Left errA) = Left (errF `mappend` errA) (Left err) <*> _ = Left err _ <*> (Left err) = Left err (Right f) <*> (Right a) = Right (f a) instance Monad (Either [String]) where return = Right (Right a) >>= f = f a (Left e) >>= f = (Left e) fail str = Left [str] lookupE :: (Eq a) => a -> [(a,b)] -> (Either a b) lookupE a env = case lookup a env of Just b -> Right b Nothing -> Left a look :: String -> ReaderT [(String,b)] (Either [String]) b look a = do env <- ask case lookup a env of Just b -> return b Nothing -> fail a looker :: ReaderT [(String, Int)] (Either [String]) (Int, Int, Int) looker = ((,,) <$> look "foo" <*> look "bar" <*> look "baz") test :: Either [String] (Int, Int, Int) test = runReaderT looker [("bar", 1)]
Attached is as slight better test example which does not rely on the 'fail' method. Doesn't really change anything significant though. {-# LANGUAGE FlexibleContexts, FlexibleInstances #-} module Main where import Control.Applicative (Applicative((<*>), pure), (<$>)) import Control.Monad (Monad((>>=), return), ap) import Control.Monad.Reader (MonadReader(ask, local), ReaderT(ReaderT, runReaderT), mapReaderT) import Data.Monoid(Monoid(mappend)) {- instance (Monad f, Applicative f) => Applicative (ReaderT r f) where pure = return (<*>) = ap -} instance (Monad f, Applicative f) => Applicative (ReaderT r f) where pure a = ReaderT $ const (pure a) f <*> a = ReaderT $ \r -> ((runReaderT f r) <*> (runReaderT a r)) instance (Monoid e) => Applicative (Either e) where pure = Right (Left errF) <*> (Left errA) = Left (errF `mappend` errA) (Left err) <*> _ = Left err _ <*> (Left err) = Left err (Right f) <*> (Right a) = Right (f a) instance Monad (Either e) where return = Right (Right a) >>= f = f a (Left e) >>= f = (Left e) -- fail str = Left [str] lookupE :: (Eq a) => a -> [(a,b)] -> (Either a b) lookupE a env = case lookup a env of Just b -> Right b Nothing -> Left a look :: (Eq a) => a -> ReaderT [(a,b)] (Either [a]) b look a = do env <- ask case lookup a env of (Just b) -> return b Nothing -> asLeft a asLeft :: a -> ReaderT r (Either [a]) b asLeft a = mapReaderT (\m -> case m of (Left as) -> Left (a:as) (Right _) -> Left [a]) (return ()) looker :: ReaderT [(String, Int)] (Either [String]) (Int, Int, Int) looker = ((,,) <$> look "foo" <*> look "bar" <*> look "baz") test :: Either [String] (Int, Int, Int) test = runReaderT looker [("bar", 1)]
Jeremy Shaw wrote:
What I would prefer is:
instance (Monad f, Applicative f) => Applicative (ReaderT r f) where pure a = ReaderT $ const (pure a) f <*> a = ReaderT $ \r -> ((runReaderT f r) <*> (runReaderT a r))
Right. This doesn't only go for ReaderT, it already goes for Either, too: you don't want the 'ap' implementation for <*> there either. These are beautiful examples of how applicative style gives the caller less power, but the callee more information, allowing more information to be retained. In this case it allows you to concatenate errors using mappend. Another example is parsing: I believe Doaitse's parsers allow more optimization if they are only used in applicative style (but I'm not sure of this). This shows there can be several sensible implementations of a type class. You ask which instance is right--that depends entirely on what you want it to do! Setting (<*>) = ap is just one of them, one you happen to get for free if your functor is already a monad. Hope this helps, Martijn.
On Wed, Aug 26, 2009 at 12:04 PM, Martijn van Steenbergen < martijn@van.steenbergen.nl> wrote:
Another example is parsing: I believe Doaitse's parsers allow more optimization if they are only used in applicative style (but I'm not sure of this).
That is correct. When you glue together P_m's applicatively the applicative P_f 'future' parser can be used, but when you use it monadically the context sensitive parts are glued together using the monadic P_h 'history' parser. -Edward Kmett
You could test your instance using the checkers package on hackage (has quickcheck properties for common typeclasses) to see if it fulfills the applicative laws. But I'm not sure if it is acceptable to define applicative instances that don't match the monad instance. Does anyone know of libraries that depend on applicative instances matching their corresponding monad instance? I've often wanted an applicative instance for a datatype that didn't match the monad instance. For example, I find the "zipping" applicative list instance more useful than the current "choice" applicative list instance instance Applicative [] where pure x = repeat x fs <*> xs = zipWith ($) fs xs This actually also has a corresponding Monad instance (with a couple restrictions). It would be nice if there was a way to hide instances so that they could be redefined. - Job On Wed, Aug 26, 2009 at 12:04 PM, Martijn van Steenbergen < martijn@van.steenbergen.nl> wrote:
Jeremy Shaw wrote:
What I would prefer is:
instance (Monad f, Applicative f) => Applicative (ReaderT r f) where pure a = ReaderT $ const (pure a) f <*> a = ReaderT $ \r -> ((runReaderT f r) <*> (runReaderT a r))
Right. This doesn't only go for ReaderT, it already goes for Either, too: you don't want the 'ap' implementation for <*> there either.
These are beautiful examples of how applicative style gives the caller less power, but the callee more information, allowing more information to be retained. In this case it allows you to concatenate errors using mappend.
Another example is parsing: I believe Doaitse's parsers allow more optimization if they are only used in applicative style (but I'm not sure of this).
This shows there can be several sensible implementations of a type class. You ask which instance is right--that depends entirely on what you want it to do! Setting (<*>) = ap is just one of them, one you happen to get for free if your functor is already a monad.
Hope this helps,
Martijn. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
At Thu, 27 Aug 2009 10:47:43 -0400, Job Vranish wrote:
I've often wanted an applicative instance for a datatype that didn't match the monad instance.
It would be nice if there was a way to hide instances so that they could be redefined.
Yeah, this is similar to the issue of multiple sensible instances for Data.Monoid. This issue has come up several times for me recently. A bit of a shortcoming in the type class design I think. There was once a proposal to help address this, but it never gained tracation: http://scholar.google.com/scholar?hl=en&lr=&cluster=8306039955712318110&um=1&ie=UTF-8&ei=JTmXSvmTJ4a4M6TJlfkN&sa=X&oi=science_links&resnum=1&ct=sl-allversions Recently I have wondered if module functors might somehow be a solution somehow. But I have not actually investigated at all. - jeremy
Hi Jeremy,
I have seen it said that all Monads are Applicative Functors because you can just do:
instance (Monad f, Applicative f) => Applicative (ReaderT r f) where pure = return (<*>) = ap
However, that instance for ReaderT does not exhibit the properties I was hoping for.
OK, let's calculate. Here are the necessary definitions for the reader monad (not the monad transformer). m >>= k = \ x -> k (m x) x u <*> v = \ x -> (u x) (v x) return a = pure a = \ x -> a So, <*> is the S combinator and pure is the K combinator. u >>= \ f -> v >>= \ a -> return (f a) = { definition of >>= } \ x -> (\ f -> v >>= \ a -> return (f a)) (u x) x = { beta } \ x -> (v >>= \ a -> return ((u x) a)) x = { definition of >>= } \ x -> (\ a -> return ((u x) a)) (v x) x = { beta } \ x -> return ((u x) (v x)) x = { definition of return } \ x -> (u x) (v x) = { definition of <*> } u <*> v Yes, both definitions are, in fact, equal. So, what went wrong in your program? Observe that the first instance declaration can be simplified to instance (Monad f) => Applicative (ReaderT r f) where pure = return (<*>) = ap which is suspicious. Hope this helps, Ralf
On 27 Aug 2009 at 07:48, Ralf Hinze wrote:
\ x -> (v >>= \ a -> return ((u x) a)) x = { definition of >>= } \ x -> (\ a -> return ((u x) a)) (v x) x
Something seems to have gone wrong here - shouldn't that be \x -> (\y -> (\a -> return ((u x) a)) (v y) y) x = { beta } \x -> (\a -> return ((u x) a)) (v x) x ? ... but then we appear to end up in the same place. Now all I've got to do is figure out what you were trying to establish in the first place. :-) I don't entirely follow what the OP's up to, so you may have a point, but it's far from clear. You're talking about the reader monad, whereas he's talking about the effects in the ReaderT-transformed monad. -- Iain Alexander ia@stryx.demon.co.uk
At Fri, 28 Aug 2009 01:01:09 +0100,
I don't entirely follow what the OP's up to, so you may have a point, but it's far from clear. You're talking about the reader monad, whereas he's talking about the effects in the ReaderT-transformed monad.
oops. Apparently I forgot to explictly state the issue :) I am using ReaderT to lookup symbols in an environment. I am using the inner monad/applicative functor to record whether the lookup failed or succeeded. So I essential have the type:
ReaderT [(a,b)] (Either [a]) b
[(a,b)] is the environment. In the end I get back a value: Either [a] b where [a] is all the symbols that weren't found or 'b' is the final value. For example, if I have: looker :: ReaderT [(String, Int)] (Either [String]) (Int, Int, Int) looker = ((,,) <$> look "foo" <*> look "bar" <*> look "baz") and none of the symbols are in the enviroment then I should get: Left ["foo", "bar", "baz"] The issue is that if I use the free (?) applicative functor instance for ReaderT then I only get back the *first* failure: Left ["foo"] But, if I used my alternative definition, then I get back all the failures. My concern is that my alternative version was somehow violating an applicative functor law. My secondary concern was the free version was somehow violating a law. It seems though, that both are valid... - jeremy
participants (6)
-
Edward Kmett -
Iain Alexander -
Jeremy Shaw -
Job Vranish -
Martijn van Steenbergen -
Ralf Hinze