State的应用实例-数据流的顺序

Question

我正在尝试为这种类型实现 Applicative 实例：

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

我对 (<*>) 函数有一些不同的想法。我想到的一种实现方法是

(<*>) :: 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)

或

(<*>) :: 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)

哪一个（或其中任何一个）是正确的，为什么？

它们都进行了类型检查，仅 "state" 转换顺序不同。我找不到任何好理由喜欢一个而不是另一个...

Answer 1

两者都有道理。请注意，您可以从另一个获取其中一个：

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

不过，"effects" 是从左到右执行的，这是图书馆的惯例。因此，第一个版本看起来更熟悉。

Answer 2

我相信两者都是正确的，因为据我所知，它们没有违反任何适用法律。但是，首先是实际使用的。我认为这是因为惯例：预计 <*> 的左手参数的效果首先应用，然后在其右手参数之前应用。与IO比较，例如where

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

先提示输入一个Int，再读取一个String。很高兴让 State 以类似的方式运行。

Answer 3

首先，我建议不要使用 (monadic!) do 语法来定义这样的应用实例，因为它会掩盖正在发生的事情。以下是仅使用标准函数语法的定义：

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

和

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

这也更清楚地表明，应用实例中实际上没有任何内在求值顺序（与 monad 实例不同）。

Answer 4

好吧，它取决于 Monad 的状态流绑定 >>= 作为 Applicative interchange law 并且它在评论中也被指出

适用的交换法

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

意味着如果 MonadState 状态从左向右流动，那么在应用程序中也应该如此，反之亦然。

但这并不意味着 applicative 应该依赖于 monad 实现或 do-notation 正如 @leftaroundabout

所说的那样它是不正确的

Applicative instance for State - order of data flow