Haskell：并行do表示法与列表推导式的转换及并行化实现

列表推导的并行实现示例 #

先看列表推导式的并行写法，借助Control.Parallel.Strategies里的parList rdeepseq策略，让列表元素的计算并行执行：

import Control.Parallel.Strategies
import Control.Monad (replicateM)

-- 模拟Yahtzee风格的条目计算
entry :: Int -> [Int]
entry n = [calculateScore roll | roll <- generateAllRolls n] `using` parList rdeepseq
  where
    -- 生成n次骰子投掷的所有可能组合
    generateAllRolls k = replicateM k [1..6]
    -- 计算单组投掷的得分（示例逻辑）
    calculateScore = sum

转成do表示法的并行实现 #

列表是Monad实例，列表推导式可以直接转写成do表示法，并行策略的用法完全一致——因为do块最终生成的还是列表，直接在后面加using parList rdeepseq即可：

import Control.Parallel.Strategies
import Control.Monad (replicateM)

entryDo :: Int -> [Int]
entryDo n = do
    roll <- generateAllRolls n
    return $ calculateScore roll
  `using` parList rdeepseq
  where
    generateAllRolls k = replicateM k [1..6]
    calculateScore = sum

列表推导转do表示法的简便方法 #

其实没有复杂技巧：列表推导的[expr | x <- list]和do块do { x <- list; return expr }是完全等价的语法糖。如果是带多个生成器的列表推导（比如[a+b | a <- as, b <- bs]），转成do表示法就是：

do
    a <- as
    b <- bs
    return $ a + b

之后直接保留using parList rdeepseq的并行策略就行，不需要额外修改。

递归并行的理解验证 #

你关于“并行化entry n需等待entry (n-1)处于范式”的理解是正确的，但要分具体场景：

• 如果generateAllRolls n或者calculateScore依赖entry (n-1)的结果，Haskell的惰性求值会先触发entry (n-1)的求值，直到它完全变成范式——因为并行列表推导需要遍历生成的列表元素，而这些元素的生成依赖entry (n-1)的最终结果。
• 如果entry (n-1)本身也使用了并行策略，它的求值会被并行处理，但entry n必须等它完成后才能开始自己的并行计算。
• 要是递归调用出现在每个列表元素的计算逻辑里（比如calculateScore里调用entry (n-1)），每个并行执行的calculateScore都会触发entry (n-1)的求值，这时候会产生大量重复计算，建议用记忆化（memoization）优化，比如借助Data.MemoCombinators库的工具缓存entry的结果。

内容的提问来源于stack exchange，提问作者Randall Fairman