Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Applicative instance for State - order of data flow

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...

like image 278
radrow Avatar asked Jul 17 '17 21:07

radrow


2 Answers

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).

like image 147
leftaroundabout Avatar answered Oct 18 '22 02:10

leftaroundabout


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.

like image 6
amalloy Avatar answered Oct 18 '22 03:10

amalloy