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

Question

我正在尝试为这样一种类型实现应用实例：

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)

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

它们都可以通过类型检查，只是“状态”转换顺序不同。我找不到任何好的理由来推荐其中一个而不是另一个...

- radrow

---

这个问题似乎是一个很好的机会来nerd snipe。这里有一个令人困惑（但有效！）的>>=定义，适用于像State一样的单子，让你思考：State f >>= g = State $ \s -> let { (u, x) = f t; (t, y) = runState (g x) s } in (u, y)。注意x，y从上到下，但s，t，u从下到上。这仍然让我的大脑感到疼痛 :) - Benjamin Hodgson

如果您还没有看过，您可能会喜欢这个链接。 - luqui

@BenjaminHodgson 这真是奇妙而美丽的。 - 4castle

@BenjaminHodgson: 为什么不两者兼得？ - Cactus

此问题中的两个 do 块都在“函数”单子中。当且仅当 f :: a -> b 对于某些 a, b 时，do { z <- f; y <- g; return (z y) } = \x -> let {z = f x; y = g x } in (const $ z y) x。（只是为了使 下面的这条评论 更容易被注意到）。 - Will Ness

Answer 1

首先，我建议不要使用（单子！）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)

这也更清晰地表明，在应用实例中没有真正的内在评估顺序（不像单子实例）。

- leftaroundabout

---

谢谢你的提示！我会尽量避免过度使用这种符号。 - radrow

@Ikciwor 一般而言，在代码中使用这种表示法没有问题。但是建议不要在此处使用它，因为从依赖关系来看有些倒叙：Monad 是基于 Applicative 的更强大的特性，因此使用 monadic 表示法定义 <*> 就像是循环依赖。当然，如果你知道两者都存在，你可以按任何顺序定义它们，但是当你试图理解它们的工作原理时，最好按照从最弱到最强的顺序逐步构建它们。 - amalloy

没错，这就是我所指的——单子（Monad）比应用函子（Applicative）更为特殊。尽管在这里这并不是非常关键，因为“do”实际上使用了与您正在定义的那个单子（函数/读取器单子）完全不同的单子实例，但那确实是一个单子实例，它给您提供了非常少的东西，而这些东西只需使用显式 lambda 等写得好一些，所以我通常会避免特定的单子实例。 - leftaroundabout

Answer 2

两种都是合理的。请注意，你可以从其中一种获取另一种：

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

然而，按照库的惯例，“效果”是从左到右执行的。因此，第一个版本更为常见。

- chi

Answer 3

我认为两种写法都是正确的，因为我没有发现它们违反任何应用定律。然而，第一种写法是实际使用的。我认为这是因为惯例：人们期望 <*> 左侧参数的效果先应用，然后再应用右侧参数。例如，与 IO 进行比较。

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

首先提示输入一个整数，然后读取一个字符串。让状态以类似的方式运行是很好的。

- amalloy

---

假设State已经有了一个Monad实例，我认为这并不完全正确。根据Applicative法则，如果f也是一个Monad，它应该满足(<*>) = ap，而第一个定义会违反这个法则，假设通常的Monad实例。 - Alexis King

Answer 4

这取决于Monad bind的状态流程>>=，根据Applicative交换律，评论中也已经指出了这一点。

Applicative交换律

如果f也是一个Monad，那么它应该满足 pure = return (<*>) = ap

这意味着，如果MonadState从左到右流动，那么Applicative也应该如此，反之亦然。

但这并不意味着applicative应该依赖于monad实现或do-notation，正如@leftaroundabout所说的那样是不正确的。

- hanan

---

我不喜欢这个解释，因为它假设 Applicative 部分依赖于 Monad。由于 Monad 比 Applicative 更强大，我更愿意说 bind 的实现取决于 <*>。尽管如此，我知道这在技术上是正确的 - 只是主观上不太令人信服。 - radrow