[lucio]

Thanks. As I said in my comment I know my ignorance and I'm looking for enlightenment (my confession didn't stop the downvotes though)

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?

[m0nastic]

Ok, here let's step through what this function is doing with a simple example (sort a list that looks like this: [3, 5, 1, 4, 2]:

  qsort [] = []

This means that if you hand the qsort function an empty list, you get an empty list ([] is the empty list in Haskell).

    qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger

Ok, so this means that we are making a list out of three parts: (qsort smaller, x, and qsort larger). The '++' operator is just concatenation.

                  where
                  smaller = [a | a <- xs, a <= x]
                  larger = [b | b <- xs, b > x]

Here we're defining what "smaller" and "larger" are. They're list comprehensions. "Smaller" returns a list that is made up of pulling out all the numbers that are less than or equal to x. "Larger" pulls out all the numbers that are greater than x. Then it does it again.

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]

That "step-by-step procedure" is an algorithm.

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.

[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.

[kazagistar]

(You made a small mistake qsort [1, 2] ++ [3] ++ [5, 4] should be qsort [1, 2] ++ [3] ++ qsort [5, 4])

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.

[m0nastic]

Ah, you're correct. (It's too late for me to fix my comment).

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.