[m0nastic]

I feel like you're conflating "purity" with algorithms.

Just to clarify, in Haskell there is no issue with algorithms being contained inside functions.

Here's a naive implementation of quicksort:

  qsort [] = []
  qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
                 where
                 smaller = [a | a <- xs, a <= x]
                 larger = [b | b <- xs, b > x]

Nothing about this algorithm requires side-effects, it doesn't mutate any state, it doesn't make use of counters. You can implement it anywhere inside of a Haskell program.

People may charitably point out that this is a pretty bad naive implementation, because it doesn't just mutate values in the list up and down, which is inefficient. People uncharitably will take issue with even calling it quicksort, as some people believe that the property of just mutating values in the list is an integral part of it being quicksort. I'm not smart enough to have an opinion about whether or not it's a "true" quicksort.

But the point is that you can absolutely have algorithms in Haskell that are not restricted to only run in a Monad.

Monads exist in Haskell as a way to reason about side-effects. Whether or not an algorithm (or any function) needs to be executed inside a monad is a function of its use of side-effects, it's not fundamental.

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