Applicative instance for State - order of data flow

Question

I am trying to implement Applicative instance for such a type:

newtype State s a = State {runState :: s -> (a, s)}

I have some different ideas for (<*>) function. One way to implement it that comes to my mind is

(<*>) :: State s (a -> b) -> State s a -> State s b
State f <*> State s = State $ do
    (fa, fs) <- f
    let (sa, ss) = s fs
    return (fa sa, ss)

Or

(<*>) :: State s (a -> b) -> State s a -> State s b
State f <*> State s = State $ do
    (sa, ss) <- s
    let (fa, fs) = f ss
    return (fa sa, fs)

Which one (or does even any of them) is correct and why?

They both typecheck and differ only by "state" transformations order. I cannot find any good reason to prefer one over another...

Brinkley

This question seems like a ripe opportunity to nerd snipe. Here's a puzzling (but valid!) definition of >>= for a State-like monad for you to think about: State f >>= g = State $ \s -> let { (u, x) = f t; (t, y) = runState (g x) s } in (u, y). Observe how x, y go from top to bottom but s, t, u go from bottom to top. Still makes my brain hurt :) – Almonte

If you haven't seen it, you might like this – Chemesh

@BenjaminHodgson That's oddly beautiful – Sanguinolent

@BenjaminHodgson: Why not both? – Atoll

both do blocks in this question are in "functions" monad. do { z <- f; y <- g; return (z y) } = \x -> let {z = f x; y = g x } in (const $ z y) x, iff f :: a -> b for some a, b. (just making this comment below more easily noticeable). – Graham

Answer 1

I believe both are correct because they don't violate any Applicative laws as far as I can see. However, the first is what is actually used. I think this is because of convention: it is expected that the effects of <*>'s left-hand arguments apply first, before its right-hand argument. Compare with IO, for example, where

(,) <$> readLn <*> getLine :: IO (Int, String)

prompts for an Int first, and then reads a String. It's nice to have State behave in a similar way.

Excited

I don’t think this is completely true, assuming a Monad instance is given for State. The Applicative laws state that if f is also a Monad, it should satisfy (<*>) = ap, which the first definition would violate, assuming the usual Monad instance. – Tripartite

Answer 2

First off, I'd recommend not using (monadic!) do syntax for defining an applicative instance like that, because it rather obscures what's happening. Here's your definitions using only standard functional syntax:

State f <*> State s = State $ \q
     -> let (fa, fs) = f q
            (sa, ss) = s fs
        in (fa sa, ss)

and

State f <*> State s = State $ \q
     -> let (fa, fs) = f ss
            (sa, ss) = s q
        in (fa sa, fs)

This also makes it clearer that there's not really any intrinsic evaluation order in an applicative instance (unlike a monad instance).

Spoof

Thanks for tip! I will try not to overuse this notation then. – Brinkley

@Ikciwor There's nothing wrong with using this notation in general. The advice is to not use it here because it's sorta backwards dependency-wise: Monad is a more powerful feature built on top of Applicative, and so using monadic notation to define <*> is sorta like a circular dependency. Of course in practice you can define them in either order if you know both will exist, but when you're trying to understand how they work it's better to build them up in order from least to most powerful. – Excited

Exactly, that's what I mean't – monad is strictly more special than applicative. This isn't really that critical here because the do actually uses a completely different monad from the one you're defining (function/reader monad), but then again that is a monad instance that gives you very little that couldn't be written just as well or better with explicit lambdas etc., so I do avoid that specific monad quite generally. – Spoof

Answer 3

Both are reasonable. Note that you can get either of them from the other one:

x <*2> y = flip ($) <$> y <*1> x

It is a library convention, though, that the "effects" are performed left-to-right. Hence, the first version looks more familiar.

Feminize

Answer 4

Well its depends upon State flow of Monad bind >>= as Applicative interchange law and its been pointed out in comment as well that

Applicative Interchange Law

If f is also a Monad, it should satisfy pure = return (<*>) = ap

mean if MonadState state flows from left to right, so should in applicative and vice versa.

but it does not means that applicative should depends upon monad implementation or do-notation it's incorrect as told by @leftaroundabout

Nanny

I don't like this explanation because it assumes that the Applicative part relays on the Monadic one. Since a Monad is stronger than an Applicative I would rather say that the implementation of bind depends upon <*>. Although, I am aware that it is technically correct – just subjectively less convincing. – Brinkley