Haskell 的 `mapM` 的执行顺序
Order of execution with Haskell's `mapM`
考虑以下 Haskell 语句：
mapM print ["1", "2", "3"]
确实，这会按顺序打印“1”、“2”和“3”。
问题：你怎么知道mapM会先打印“1”，然后然后打印“2”，最后打印“3”。是否可以保证它会这样做？或者它是如何在 GHC 中深入实施的巧合？
无法保证评估的顺序，但可以保证效果的顺序。有关详细信息，请参阅
You need to learn to make the following, tricky distinction:
- The order of evaluation
- The order of effects (a.k.a. "actions")
What
forM, sequence and similar functions promise is that the effects will
be ordered from left to right. So for example, the following is
guaranteed to print characters in the same order that they occur in
the string...
Note：“forM 是 mapM，其参数被翻转。对于忽略结果的版本，请参见 forM_。”
如果您通过扩展 mapM 的定义来评估 mapM print ["1", "2", "3"]，您将得出（忽略一些不相关的细节）
print "1" >> print "2" >> print "3"
您可以将 print 和 >> 视为无法进一步评估的 IO 操作的抽象构造函数，就像无法进一步评估 Just 这样的数据构造函数一样。
解释print s是打印s的动作，a >> b的解释是先执行a再执行[=21的动作=].所以，
的解读
mapM print ["1", "2", "3"] = print "1" >> print "2" >> print "3"
就是先打印1，再打印2，最后打印3。
这是如何实际上在 GHC 中实现的完全是另一回事，您不必担心很长时间。
初步说明：Reid Barton 和 Dair 的回答完全正确，完全涵盖了您的实际问题。我之所以提到这一点，是因为在这个答案的中途，人们可能会有这样的印象，即它与他们相矛盾，但事实并非如此，到我们结束时就会清楚。很明显，是时候沉迷于一些语言律师了。
Is there any guarantee that [mapM print] will [print the list elements in order]?
是的，正如其他答案所解释的那样。在这里，我将讨论什么可以证明这种保证。
在这个时代，mapM 默认情况下仅 traverse 专用于 monads：
traverse
:: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
mapM
:: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)
既然如此，接下来我将主要关注 traverse，以及我们对效果排序的期望与 Traversable class.
就效果的产生而言，traverse为遍历容器中的每个值生成一个Applicative效果，并通过相关的Applicative实例组合所有这些效果。 sequenceA 的类型清楚地反映了第二部分，可以说，应用上下文通过它从容器中分解出来：
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
-- sequenceA and traverse are interrelated by:
traverse f = sequenceA . fmap f
sequenceA = traverse id
The Traversable instance for lists，例如是：
instance Traversable [] where
{-# INLINE traverse #-} -- so that traverse can fuse
traverse f = List.foldr cons_f (pure [])
where cons_f x ys = (:) <$> f x <*> ys
很明显，效果的组合和排序是通过 (<*>) 完成的，所以让我们暂时关注一下。以 IO applicative functor 为例，我们可以看到 (<*>) 从左到右的排序效果：
GHCi> -- Superfluous parentheses added for emphasis.
GHCi> ((putStrLn "Type something:" >> return reverse) <*> getLine) >>= putStrLn
Type something:
Whatever
revetahW
(<*>)，但是，从左到右 by convention, and not for any inherent reason. As witnessed by the Backwards wrapper from transformers 的顺序效果，原则上总是可以用从右到左的顺序来实现 (<*>) 并且仍然得到一个合法的 Applicative 实例。在不使用包装器的情况下，也可以利用 Control.Applicative 中的 (<**>) 来反转顺序：
(<**>) :: Applicative f => f a -> f (a -> b) -> f b
GHCi> import Control.Applicative
GHCi> (getLine <**> (putStrLn "Type something:" >> return reverse)) >>= putStrLn
Whatever
Type something:
revetahW
鉴于翻转 Applicative 效果的顺序如此容易，有人可能想知道这一技巧是否可以转移到 Traversable。例如，假设我们实现...
esrevart :: Applicative f => (a -> f b) -> [a] -> f [b]
... 所以它就像列表的 traverse 除了使用 Backwards 或 (<**>) 来翻转效果的顺序（我将把它留作练习reader）。 esrevart 会是 traverse 的合法实现吗？虽然我们可能会通过尝试证明 identity and composition laws of Traversable hold, that is actually not necessary: given that Backwards f for any applicative f is also applicative, an esrevart patterned after any lawful traverse will also follow the Traversable laws. The Reverse wrapper 来解决这个问题，但 transformers 的一部分也提供了这种逆转的一般实现。
因此我们得出结论，可能存在合法的 Traversable 实例，其效果顺序不同。特别是，一个列表 traverse 从尾部到头部对效果进行排序是可以想象的。不过，这并没有使这种可能性变得不那么奇怪。为了避免完全的困惑，Traversable 实例通常使用简单的 (<*>) 实现，并遵循构造函数用于构建可遍历容器的自然顺序，在列表的情况下相当于预期的头-效应的尾序。此约定出现的一个地方是 the DeriveTraversable extension.
自动生成实例。
最后的历史记录。就 Traversable class 而言，讨论这个最终是关于 mapM 的讨论在不久的过去将是一个可疑的相关性举动。 mapM 仅在去年才有效地被 traverse 归入，但它存在的时间要长得多。例如，1996 年的 Haskell Report 1.3，在 Applicative 和 Traversable 出现之前的几年（事实上，甚至没有 ap），为 mapM:
accumulate :: Monad m => [m a] -> m [a]
accumulate = foldr mcons (return [])
where mcons p q = p >>= \x -> q >>= \y -> return (x:y)
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM f as = accumulate (map f as)
这里通过 (>>=) 强制执行的效果顺序是从左到右的，除了它是明智的做法之外没有其他原因。
P.S.: 值得强调的是，虽然在Monad操作方面可以写出从右到左的mapM（在Report 1.3这里引用的实现，例如，它只需要在 mcons 的右侧交换 p 和 q），没有通用的 Backwards 这样的东西单子。由于 x >>= f 中的 f 是一个 Monad m => a -> m b 函数，它根据值创建效果，因此与 f 相关的效果取决于 x。因此，像 (<*>) 那样的简单的顺序反转甚至不能保证有意义，更不用说合法了。
考虑以下 Haskell 语句：
mapM print ["1", "2", "3"]
确实，这会按顺序打印“1”、“2”和“3”。
问题：你怎么知道mapM会先打印“1”，然后然后打印“2”，最后打印“3”。是否可以保证它会这样做？或者它是如何在 GHC 中深入实施的巧合？
无法保证评估的顺序，但可以保证效果的顺序。有关详细信息，请参阅
You need to learn to make the following, tricky distinction:
- The order of evaluation
- The order of effects (a.k.a. "actions")
What forM, sequence and similar functions promise is that the effects will be ordered from left to right. So for example, the following is guaranteed to print characters in the same order that they occur in the string...
Note：“forM 是 mapM，其参数被翻转。对于忽略结果的版本，请参见 forM_。”
如果您通过扩展 mapM 的定义来评估 mapM print ["1", "2", "3"]，您将得出（忽略一些不相关的细节）
print "1" >> print "2" >> print "3"
您可以将 print 和 >> 视为无法进一步评估的 IO 操作的抽象构造函数，就像无法进一步评估 Just 这样的数据构造函数一样。
解释print s是打印s的动作，a >> b的解释是先执行a再执行[=21的动作=].所以，
mapM print ["1", "2", "3"] = print "1" >> print "2" >> print "3"
就是先打印1，再打印2，最后打印3。
这是如何实际上在 GHC 中实现的完全是另一回事，您不必担心很长时间。
初步说明：Reid Barton 和 Dair 的回答完全正确，完全涵盖了您的实际问题。我之所以提到这一点，是因为在这个答案的中途，人们可能会有这样的印象，即它与他们相矛盾，但事实并非如此，到我们结束时就会清楚。很明显，是时候沉迷于一些语言律师了。
Is there any guarantee that [
mapM print] will [print the list elements in order]?
是的，正如其他答案所解释的那样。在这里，我将讨论什么可以证明这种保证。
在这个时代，mapM 默认情况下仅 traverse 专用于 monads：
traverse
:: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
mapM
:: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)
既然如此，接下来我将主要关注 traverse，以及我们对效果排序的期望与 Traversable class.
就效果的产生而言，traverse为遍历容器中的每个值生成一个Applicative效果，并通过相关的Applicative实例组合所有这些效果。 sequenceA 的类型清楚地反映了第二部分，可以说，应用上下文通过它从容器中分解出来：
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
-- sequenceA and traverse are interrelated by:
traverse f = sequenceA . fmap f
sequenceA = traverse id
The Traversable instance for lists，例如是：
instance Traversable [] where
{-# INLINE traverse #-} -- so that traverse can fuse
traverse f = List.foldr cons_f (pure [])
where cons_f x ys = (:) <$> f x <*> ys
很明显，效果的组合和排序是通过 (<*>) 完成的，所以让我们暂时关注一下。以 IO applicative functor 为例，我们可以看到 (<*>) 从左到右的排序效果：
GHCi> -- Superfluous parentheses added for emphasis.
GHCi> ((putStrLn "Type something:" >> return reverse) <*> getLine) >>= putStrLn
Type something:
Whatever
revetahW
(<*>)，但是，从左到右 by convention, and not for any inherent reason. As witnessed by the Backwards wrapper from transformers 的顺序效果，原则上总是可以用从右到左的顺序来实现 (<*>) 并且仍然得到一个合法的 Applicative 实例。在不使用包装器的情况下，也可以利用 Control.Applicative 中的 (<**>) 来反转顺序：
(<**>) :: Applicative f => f a -> f (a -> b) -> f b
GHCi> import Control.Applicative
GHCi> (getLine <**> (putStrLn "Type something:" >> return reverse)) >>= putStrLn
Whatever
Type something:
revetahW
鉴于翻转 Applicative 效果的顺序如此容易，有人可能想知道这一技巧是否可以转移到 Traversable。例如，假设我们实现...
esrevart :: Applicative f => (a -> f b) -> [a] -> f [b]
... 所以它就像列表的 traverse 除了使用 Backwards 或 (<**>) 来翻转效果的顺序（我将把它留作练习reader）。 esrevart 会是 traverse 的合法实现吗？虽然我们可能会通过尝试证明 identity and composition laws of Traversable hold, that is actually not necessary: given that Backwards f for any applicative f is also applicative, an esrevart patterned after any lawful traverse will also follow the Traversable laws. The Reverse wrapper 来解决这个问题，但 transformers 的一部分也提供了这种逆转的一般实现。
因此我们得出结论，可能存在合法的 Traversable 实例，其效果顺序不同。特别是，一个列表 traverse 从尾部到头部对效果进行排序是可以想象的。不过，这并没有使这种可能性变得不那么奇怪。为了避免完全的困惑，Traversable 实例通常使用简单的 (<*>) 实现，并遵循构造函数用于构建可遍历容器的自然顺序，在列表的情况下相当于预期的头-效应的尾序。此约定出现的一个地方是 the DeriveTraversable extension.
最后的历史记录。就 Traversable class 而言，讨论这个最终是关于 mapM 的讨论在不久的过去将是一个可疑的相关性举动。 mapM 仅在去年才有效地被 traverse 归入，但它存在的时间要长得多。例如，1996 年的 Haskell Report 1.3，在 Applicative 和 Traversable 出现之前的几年（事实上，甚至没有 ap），为 mapM:
accumulate :: Monad m => [m a] -> m [a]
accumulate = foldr mcons (return [])
where mcons p q = p >>= \x -> q >>= \y -> return (x:y)
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM f as = accumulate (map f as)
这里通过 (>>=) 强制执行的效果顺序是从左到右的，除了它是明智的做法之外没有其他原因。
P.S.: 值得强调的是，虽然在Monad操作方面可以写出从右到左的mapM（在Report 1.3这里引用的实现，例如，它只需要在 mcons 的右侧交换 p 和 q），没有通用的 Backwards 这样的东西单子。由于 x >>= f 中的 f 是一个 Monad m => a -> m b 函数，它根据值创建效果，因此与 f 相关的效果取决于 x。因此，像 (<*>) 那样的简单的顺序反转甚至不能保证有意义，更不用说合法了。