Haskell中`mapM`的执行顺序

4
考虑以下 Haskell 语句:
mapM print ["1", "2", "3"]

的确,这将按顺序打印出 "1"、 "2" 和 "3"。

问题:你是如何知道 mapM 将首先打印 "1",然后打印 "2",最后打印 "3" 的?它是否有保证会这样做?还是这只是 GHC 深层实现的巧合?

3个回答

10

如果你通过扩展mapM的定义来评估mapM print ["1", "2", "3"],你会得到以下结果(忽略一些无关细节)

print "1" >> print "2" >> print "3"
你可以将print>>看作是无法进一步评估的IO操作的抽象构造函数,就像Just这样的数据构造函数一样不能进一步评估。 print s的解释是打印s,而a >> b的解释是首先执行a,然后执行b。因此,的解释是
mapM print ["1", "2", "3"] = print "1" >> print "2" >> print "3"

先打印1,然后打印2,最后打印3。

实际上,GHC中如何实现完全是另一回事,你不需要长时间担心这个问题。


我更喜欢将其分解为print = putStrLn . show。你可以再深入一些,但至少这解释了Show的作用。 - dfeuer

7
没有对评估顺序的保证,但是对效果顺序有保证。更多信息请参见这个回答讨论forM

您需要学会以下棘手的区别:

  1. 评估顺序
  2. 效果顺序(也称为“操作”)

forM、sequence和类似函数承诺效果将从左到右排序。因此,例如,以下内容保证按字符串中出现的顺序打印字符...

注意:“forM是将其参数翻转的mapM。忽略结果的版本请参见forM_。”


所以在我的例子中,我可以保证“1”会在“2”之前打印,而“2”会在“3”之前打印,因为“1”在“2”的左边,在“3”的左边,而打印是一种效果。 - George
是的。它们被打印的顺序被保留。 - Dair
你链接的答案很好。我不明白的是,为什么你没点赞它呢? - leftaroundabout

4
初步说明:Reid Barton和Dair的回答完全正确并充分涵盖了您的实际关注点。我提到这一点是因为在回答的过程中,人们可能会有一种它与他们的回答相矛盾的印象,但事实并非如此,到最后就会清楚。既然这一点已经明确,现在该沉迷于一些语言学习了。

有没有保证 [mapM print] 将按顺序打印列表元素?

是的,正如其他答案所解释的那样。在这里,我将讨论可能证明这个保证的原因。

在当今时代,mapM 默认情况下仅是对单子进行特殊化的 traverse

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”为遍历容器中的每个值生成一个“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

例如,对于列表来说,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

很明显,组合和排序效果是通过(<*>)完成的,因此让我们专注于它一会儿。以IO应用函子为例,我们可以看到(<*>)从左到右顺序排列效果:
GHCi> -- Superfluous parentheses added for emphasis.
GHCi> ((putStrLn "Type something:" >> return reverse) <*> getLine) >>= putStrLn
Type something:
Whatever
revetahW

(<*>),然而,序列效果从左到右是惯例,而不是任何固有原因。正如transformersBackwards包装器所证明的那样,原则上,始终可以使用从右到左的排序实现(<*>)并仍然获得合法的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(<**>)来翻转效果的排序(我将把这留给读者作为练习)。esrevart是否可以是traverse的合法实现?虽然我们可以试图证明Traversable身份和组合律成立,但实际上这并不是必要的:鉴于任何可应用的fBackwards f也是可应用的,一个模仿任何合法的traverseesrevart也将遵循Traversable的法律。Reverse包装器,也是transformers的一部分,提供了这种反转的通用实现。

我们因此得出结论,可能存在在效果排序上不同的合法Traversable实例。特别地,可以构造一个从尾到头顺序排列效果的列表traverse。然而,这并不会使这种可能性变得更加常规。为了避免彻底的迷惑,Traversable实例通常使用普通的(<*>)来实现,并沿用用于建立可遍历容器的构造函数的自然顺序,对于列表而言,这意味着按照预期的从头到尾的效果排序。其中一个体现这种约定的地方是由 DeriveTraversable扩展自动生成实例。

最后,一个历史性的注释。用Traversable类来表述这个讨论,最终是关于mapM的,这在不久的过去可能是一个毫无相关性的举动。 mapM实际上已经存在很长时间了,但直到去年才被traverse有效地取代。例如,1996年的Haskell Report 1.3,早在ApplicativeTraversable出现之前(事实上,甚至没有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的右侧交换pq即可),但是对于单子而言,并不存在通用的Backwards。由于x >>= f中的f是一个Monad m => a -> m b函数,用于从值创建效果,与f相关联的效果取决于x。因此,像(<*>)那样简单地反转排序甚至不能保证有意义,更别说合法了。


1
Data.Functor.Reverse 实现 Traversable 实例并不是一项轻松的任务,它基本上依赖于 Backwards。需要注意的是,对于 Monad 类别来说,并不存在类似于 Backwards 的东西。 - dfeuer
@dfeuer [1] 确实如此。(稍微棘手的是,在一般的 (Traversable f) => Traversable (Reverse f) 情况下,你既不能玩弄 (<*>) 也不能玩弄(未知的)Traversable 的结构。)顺便说一句,我会添加一个到 Data.Functor.Reverse 的链接。[2] 这绝对值得一提;我会加上一条注释。(我选择不包括有关 Monad 的额外段落,并且那个评论应该在其中某个地方被提到。)有用的提醒,谢谢。 - duplode

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接