I do not "see" any clear algorithm in the code (no step-by-step procedure). I see recursion only.
¿Can you explain in words what this code is doing?
¿Can you implement this without using recursion?
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
where
smaller = [a | a <- xs, a <= x]
larger = [b | b <- xs, b > x]
Using that example list above ([3, 5, 1, 4, 2]), here's if we did it by hand:
qsort [3, 5, 1, 4, 2]
= {applying qsort}
qsort [1, 2] ++ [3] ++ [5, 4]
= {applying qsort}
(qsort [] ++ [1] ++ qsort [2]) ++ [3] ++ (qsort [4] ++ [5] ++ qsort[])
= {applying qsort}
([] ++ [1] ++ [2]) ++ [3] ++ ([4] ++ [5] ++ [])
= {applying ++}
[1,2] ++ [3] ++ [4,5]
= {applying ++}
[1,2,3,4,5]
Is it that there are no loops that you don't see how it's an algorithm? It is definitely true that some algorithms are very obvious to implement using loops (quicksort is actually one such algorithm), and can in fact be a pain in the neck to implement in some functional languages.
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 then, I'm enlightened. Thank you.
Also, quicksort is a pretty bad example of an pure algorithm, since it loses a lot of its performance benefits when not done in place.
I went over the issues with this version of quicksort in the original comment, but I still think it was a good example because most people are familiar with quicksort, and I was trying to address the original posters claim that algorithms in Haskell could only be used in Monads.
Also, quicksort is one of the few I can do from memory.