5 ms·

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 t

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.

kazagistar 12y ago
(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 12y ago
  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.
lucio 12y ago
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 12y ago

(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 12y ago
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.

lucio 12y ago

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.