On 11/20/14 5:09 PM, Walter Bright wrote:
On 11/20/2014 3:10 PM, "Ola Fosheim Grøstad"
<ola.fosheim.grostad+dl...@gmail.com>" wrote:
On Thursday, 20 November 2014 at 22:47:27 UTC, Walter Bright wrote:
On 11/20/2014 1:55 PM, deadalnix wrote:
All of this is beautiful until you try to implement a quicksort
in, haskell.
[…]
Monads!
I think Deadalnix meant that you cannot do in-place quicksort easily
in Haskell.
That's correct.
Non-mutating quicksort is easy, no need for monads:
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
https://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell
Except that isn't really quicksort. Monads are the workaround functional
languages use to deal with things that need mutation.
As I like to say, this troika has inflicted a lot of damage on both FP
and those beginning to learn it:
* Linear-space factorial
* Doubly exponential Fibonacci
* (Non)Quicksort
These losers appear with depressing frequency in FP introductory texts.
Andrei