[lucio]

Thank you very much m0nastic, it's a great explanation.

Now I can see the mathematical elegance of the haskell code.

An explicit algorithm of the same (pseudo)code (using a mutable list) could be:

   function qsort(list)
     if list is [], return []
     let x = extract_first_element(list) // car 
     let smaller = [a | a <- list, a <= x]
     let larger = [b | b <- list, b > x]  
     return qsort(smaller) ++ x ++ qsort(larger)

And by writing this pseudo-code, I can see that in the haskell code, "smaller" and "larger" are clearly parallelizable, while in the "imperative"-"explicit algorithm" pseudo-code, the compiler cannot do such optimization...

And then, I'm enlightened. Thank you.