instance Applicative f => Applicative (StateT s f)
Hello all, How do I implement the following? instance Applicative f => Applicative (StateT s f) The implementation of pure is trivial, but I can't figure out an implementation for <*>. Is it possible at all, or do I need to require f to be a monad? Thanks in advance, Martijn.
On Fri, Dec 05, 2008 at 04:35:51PM +0100, Martijn van Steenbergen wrote:
How do I implement the following?
instance Applicative f => Applicative (StateT s f)
The implementation of pure is trivial, but I can't figure out an implementation for <*>. Is it possible at all, or do I need to require f to be a monad?
Yes, because you need part of the value generated by the first computation, namely the state (inside the f), to construct the second one. You can do that in a Monad, but not in an Applicative.
On 5 Dec 2008, at 16:54, Ross Paterson wrote:
On Fri, Dec 05, 2008 at 04:35:51PM +0100, Martijn van Steenbergen wrote:
How do I implement the following?
instance Applicative f => Applicative (StateT s f)
The implementation of pure is trivial, but I can't figure out an implementation for <*>. Is it possible at all, or do I need to require f to be a monad?
Yes, because you need part of the value generated by the first computation, namely the state (inside the f), to construct the second one. You can do that in a Monad, but not in an Applicative.
I don't think that's true, although I'm yet to decide if Applicative for State is possible. someState <*> someOtherState should take the value out of the first state, take the value out of the second state, apply one to the other, and return a new stateful value as the result. At no point in that description do I make mention of the previous state of one of these values. Bob
On Fri, Dec 05, 2008 at 04:59:04PM +0100, Thomas Davie wrote:
On 5 Dec 2008, at 16:54, Ross Paterson wrote:
On Fri, Dec 05, 2008 at 04:35:51PM +0100, Martijn van Steenbergen wrote:
How do I implement the following?
instance Applicative f => Applicative (StateT s f)
The implementation of pure is trivial, but I can't figure out an implementation for <*>. Is it possible at all, or do I need to require f to be a monad?
Yes, because you need part of the value generated by the first computation, namely the state (inside the f), to construct the second one. You can do that in a Monad, but not in an Applicative.
I don't think that's true, although I'm yet to decide if Applicative for State is possible.
someState <*> someOtherState should take the value out of the first state, take the value out of the second state, apply one to the other, and return a new stateful value as the result. At no point in that description do I make mention of the previous state of one of these values.
That would be incompatible with the ap of the monad where it exists, but it's worse than that. Which state will you return? If you return one of the states output by one or other of the arguments, you'll break one of the laws: pure id <*> v = v u <*> pure y = pure ($ y) <*> u You're forced to return the input state, so the Applicative would just be an obfuscated Reader.
That would be incompatible with the ap of the monad where it exists, but it's worse than that. Which state will you return? If you return one of the states output by one or other of the arguments, you'll break one of the laws:
pure id <*> v = v u <*> pure y = pure ($ y) <*> u
You're forced to return the input state, so the Applicative would just be an obfuscated Reader.
Which reminds me ofc, that there is a valid applicative for states (assuming the monad instance is valid): instance Applicative (StateT s f) where pure = return (<*>) = ap All monads are also applicatives ;) Bob
On Fri, Dec 05, 2008 at 06:56:46PM +0100, Thomas Davie wrote:
Which reminds me ofc, that there is a valid applicative for states (assuming the monad instance is valid):
instance Applicative (StateT s f) where pure = return (<*>) = ap
All monads are also applicatives ;)
Sure, as long as you add the assumption Monad f.
Ross Paterson wrote:
Yes, because you need part of the value generated by the first computation, namely the state (inside the f), to construct the second one. You can do that in a Monad, but not in an Applicative.
This makes me wonder: does that mean there is no such thing as an applicative transformer? Martijn.
On Fri, Dec 05, 2008 at 06:52:31PM +0100, Martijn van Steenbergen wrote:
Ross Paterson wrote:
Yes, because you need part of the value generated by the first computation, namely the state (inside the f), to construct the second one. You can do that in a Monad, but not in an Applicative.
This makes me wonder: does that mean there is no such thing as an applicative transformer?
StateT isn't an applicative transformer, but ErrorT, ReaderT and WriterT are, and there are others that don't correspond to monad transformers, starting with product and composition. The accumulating exceptions applicative (originally due to Duncan Coutts) generalizes to a transformer. Underneath the permutation phrase parser of Arthur Baars, Andres Löh and Doaitse Swierstra is an applicative transformer.
This makes me wonder: does that mean there is no such thing as an applicative transformer?
Applicative functors compose much more simply than monads, so you don't need transformers.
newtype Compose f g a = O (f (g a)) unO (O x) = x
instance (Functor f, Functor g) => Functor (Compose f g) where fmap f o = O $ fmap (fmap f) $ unO o
instance (Applicative f, Applicative g) => Applicative (Compose f g) where pure x = O $ pure $ pure x
-- unO of :: f (g (a -> b)) -- unO ox :: f (g a) -- to get result :: f (g b) -- we need to lift of to f (g a -> g b) -- which we do via (fmap (<*>)) :: f (g (a -> b)) -> f (g a -> g b) of <*> ox = O ((<*>) <$> unO of <*> unO ox)
Prettier implementations of this are available in the TypeCompose library. -- ryan
participants (4)
-
Martijn van Steenbergen -
Ross Paterson -
Ryan Ingram -
Thomas Davie