Applicative and Monad transformers

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Applicative and Monad transformers

Jeremy Shaw-3
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)]





_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative and Monad transformers

Jeremy Shaw-3
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)]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative and Monad transformers

Martijn van Steenbergen-2
In reply to this post by Jeremy Shaw-3
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative and Monad transformers

Edward Kmett-2
On Wed, Aug 26, 2009 at 12:04 PM, Martijn van Steenbergen <[hidden email]> 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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative and Monad transformers

Ralf Hinze-2
In reply to this post by Jeremy Shaw-3
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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative and Monad transformers

Job Vranish
In reply to this post by Martijn van Steenbergen-2
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 <[hidden email]> 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative and Monad transformers

Iain Alexander
In reply to this post by Ralf Hinze-2
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      [hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative and Monad transformers

Jeremy Shaw-3
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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative and Monad transformers

Jeremy Shaw-3
In reply to this post by Job Vranish
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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe