[Haskell-cafe] instance Applicative f => Applicative (StateT s f)

[Ross Paterson]

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.