为什么Haskell列表理解不能并行执行？

Question

我正在为家庭作业做Euler项目的第21题，我有以下清单：

amicableNumberSums = [ x+y | x<-[1..10000], y <-[1..10000], (amicable x y)]

这需要很长时间来执行(在测试10000^2对数字时是可以理解的)，看看我的cpu使用情况，就会发现只使用了一个核心。

由于对列表的理解没有任何副作用，同时测试的多对数字没有危险。有没有一种方法可以让Haskell自动完成这个任务，或者如果不是，如何修改我的代码来完成这个任务？

(编辑)运行打印时出错(amicableNumberSums using parList)：

Couldn't match type `a0 -> Eval a0' with `[Int]'
Expected type: Strategy [Int]
  Actual type: Strategy a0 -> Strategy [a0]
In the second argument of `using', namely `parList'
In the first argument of `print', namely
  `(amicableNumberSums `using` parList)'
In the expression: print (amicableNumberSums `using` parList)

(编辑)建议的两种方法的执行情况：

Ørjan Johansen's method: 218.79s elapsed parallel (4 cores + 4 hyperthreading)
                         279.37s elapsed sequential (single core)
bheklilr's method: 247.82s elapsed parallel (4 cores + 4 hyperthreading)
                   274.10s elapsed sequential (single core)
Original method: 278.69s elapsed

这并不是我所期望的那么大的速度，但我现在对这个问题有了正确的答案，直到我学到更多的哈斯克尔，这就足够了。

Answer 1

@bheklilr的答案处理了并行化策略的一般方法，但正如我在上面的评论中所暗示的那样，最初的列表理解方式迫使所有amicable测试在parList-based策略能够到达其元素并开始评估它们之前发生，因此我认为@bheklilr的代码不会在这个特定情况下很好地工作。

这是我改进的建议。您需要重写您的列表理解，以便将工作划分为定义良好和独立的块，例如将中间列表中的x值组合在一起。例如，它可以等效地写成

concat [[ x+y | y <-[1..10000], (amicable x y)] | x <- [1..10000]]

现在，您可以在理解和最终的concat之间放置一个并行的评估策略。

concat ([[ x+y | y <-[1..10000], (amicable x y)] | x <- [1..10000]]
        `using` parList rdeepseq)

(我在这里使用rdeepseq，因为预格式化列表中的元素也是列表，我们希望计算它们的所有元素，它们都是整数。)