Why are Haskell list comprehensions not executed in parallel?

Question

I am doing Project Euler problem 21 for homework and I have this list comprehension:

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

This takes a very long time to execute (understandable as it tests 10000^2 pairs of numbers) and looking at my cpu usage it shows that only 1 core is being used.

As there are no side effects to the list comprehension there is no danger in multiple pairs of numbers being tested at the same time. Is there a way to make Haskell do this automatically or if not how could my code be modified to do this?

(Edit) Error when running print (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)

(Edit) Performance of the two suggested methods:

Ø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

This is not as large a speed up as I was hoping for but I now have the correct answer to the problem and until I have learnt some more Haskell this is sufficient.

Answer 1

@bheklilr's answer handles the general method of parallelizing strategies, but as I implied in the comment above, the way the original list comprehension is written forces all amicable tests to happen before a parList-based strategy on it can get to its elements and start evaluating them, so I don't think @bheklilr's code will quite work for this specific case.

Here's my suggestion for an improvement. You need to rewrite your list comprehension such that it divides the work into well-defined and independent chunks, e.g. by combining the x values in intermediate lists. For example it can be written equivalently as

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

Now you can put a parallel evaluation strategy in between the comprehension and the final concat:

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

(I use rdeepseq here because the elements of the pre-concatted list are also lists, and we want to evaluate all their elements which are integers.)