4

考虑以下 Haskell 语句：

mapM print ["1", "2", "3"]

实际上，这会按顺序打印“1”、“2”和“3”。

问题：你怎么知道mapM会先打印“1”，然后打印“2”，最后打印“3”。有没有保证它会这样做？或者它是如何在 GHC 深处实施的巧合？

4

3 回答 3

10

如果你mapM print ["1", "2", "3"]通过扩展你的定义来评估mapM你会到达（忽略一些不相关的细节）

print "1" >> print "2" >> print "3"

您可以将printand>>视为无法进一步评估的 IO 操作的抽象构造函数，就像Just无法进一步评估的数据构造函数一样。

解释print s是印刷的动作，s解释a >> b是先执行a后执行的动作b。所以，解释

mapM print ["1", "2", "3"] = print "1" >> print "2" >> print "3"

就是先打印1，再打印2，最后打印3。

如何在 GHC 中实际实现这完全是另一回事，您不必担心很长时间。

于 2016-11-03T22:34:01.080 回答
7

无法保证评估的顺序，但可以保证效果的顺序。有关更多信息，请参阅讨论的这个答案forM。

您需要学习做出以下棘手的区分：

  1. 评价顺序
  2. 效果顺序（又名“动作”）

forM、sequence 和类似函数所承诺的是效果将从左到右排序。因此，例如，以下内容保证以与它们在字符串中出现的顺序相同的顺序打印字符......

注意：“forM它mapM的参数被翻转了。对于忽略结果的版本，请参阅forM_。”

于 2016-11-03T22:17:50.747 回答
4

初步说明：Reid Barton 和 Dair 的答案完全正确，完全涵盖了您的实际问题。我提到，因为在这个答案的中途，人们可能会有这样的印象，即它与他们相矛盾，但事实并非如此，当我们结束时会很清楚。很明显，是时候沉迷于一些语言律师了。

是否有任何保证 [ mapM print] 将 [按顺序打印列表元素]？

是的，正如其他答案所解释的那样。在这里，我将讨论什么可以证明这种保证是合理的。

在这个时代，mapM默认情况下，traverse它只专门用于 monad：

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课程之间的关系。

就效果的产生而言，为遍历的容器中的每个值traverse生成一个效果，并通过相关实例组合所有这些效果。第二部分由 的类型清楚地反映，通过它，应用上下文可以说是从容器中分解出来的：ApplicativeApplicativesequenceA

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

Traversable例如，列表的实例是：

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

很明显，效果的组合和排序是通过 完成的(<*>)，所以让我们暂时关注它。以IOapplicative functor 为例，我们可以看到(<*>)从左到右的排序效果：

GHCi> -- Superfluous parentheses added for emphasis.
GHCi> ((putStrLn "Type something:" >> return reverse) <*> getLine) >>= putStrLn
Type something:
Whatever
revetahW

(<*>)，然而，按照惯例，从左到右排列效果，而不是出于任何固有的原因。正如来自transformers的Backwards包装器所见证的那样，原则上，始终可以(<*>)使用从右到左的顺序来实现并且仍然可以获得合法的Applicative实例。在不使用包装器的情况下，也可以利用(<**>)fromControl.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或(<**>)翻转效果的顺序（我将把它作为练习留给读者）。会esrevart是合法的执行traverse吗？虽然我们可以通过尝试证明持有的恒等律和组合律来Traversable解决这个问题，但这实际上是没有必要的：鉴于Backwards f任何应用程序f也是应用程序，esrevart任何合法之后的模式traverse也将遵循Traversable法律。包装器，也是转换器的Reverse一部分，提供了这种反转的一般实现。

因此，我们得出结论，可能存在效力Traversable顺序不同的法律实例。特别是，traverse可以想象一个从尾到头对效果进行排序的列表。不过，这并没有让这种可能性变得不那么奇怪。为了避免完全困惑，Traversable实例通常以简单的方式实现，(<*>)并遵循构造函数用于构建可遍历容器的自然顺序，在列表的情况下，这相当于预期的从头到尾的效果排序。这种约定出现的一个地方是通过扩展自动生成DeriveTraversable实例。

最后的历史记录。在不远的过去，将mapM这个最终关于. 仅在去年才有效地被纳入，但它存在的时间要长得多。例如，1996 年的Haskell 报告 1.3 ，早在几年前就已经出现（实际上甚至不存在），提供了以下规范：TraversablemapMtraverseApplicativeTraversableapmapM

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)

在这里通过 强制执行的效果顺序(>>=)是从左到右的，没有其他原因，只是这样做是明智的。

PS：值得强调的是，虽然在操作mapM方面可以写一个从右到左的Monad（例如这里引用的Report 1.3实现，它只需要在右侧交换p和） ，没有像一般的单子这样的东西。由于in是一个从值创建效果的函数，因此与相关的效果取决于. 因此，一个简单的排序倒置甚至不能保证是有意义的，更不用说合法了。qmconsBackwardsfx >>= fMonad m => a -> m bfx(<*>)

于 2016-11-04T07:33:51.433 回答