5 ms·

I have the same problems with haskell. My actual level of ignorance is: (anyone having traveled the path between imperative and functional, please correct me)

• yzzxy 12y ago
  Pure functions can very much be algorithms. Functional programming is just that and can include algorithms. Monads are not intrinsically related in any way to impurity, they are an instrument of control/data flow. They can be used to apparently cause side effects but do not actually introduce impurity.
• m0nastic 12y ago
  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 12y ago
    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 12y ago
      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.