4 ms·
I imagined it was more in the sense of the 'Have fun implementing Quicksort!' variety, where you're fighting the language constructs, basically, to do what you
by giantDinosaur 7y ago
I imagined it was more in the sense of the 'Have fun implementing Quicksort!' variety, where you're fighting the language constructs, basically, to do what you want.
- tmountain 7y agoHaskell has a huge catalog of libraries you can reach for, so you don’t have to reinvent the wheel. That said, the Haskell way can seem very different than what you see in most languages. As an example, IO—or anything causing a side effect—has to happen in the IO Monad. There are good reasons for this, but it takes some getting used to.
- vkou 7y agoThe parent poster is not lamenting that Haskell lacks a trivial sorting function. They are lamenting that implementing a trivial sorting function in Haskell is difficult.
- tmountain 7y agoI disagree. quicksort [] = [] quicksort (x:xs) = let smallerSorted = quicksort [a | a <- xs, a <= x] biggerSorted = quicksort [a | a <- xs, a > x] in smallerSorted ++ [x] ++ biggerSorted
- magicalhippo 7y agoNot that I know any Haskell, but wouldn't smallerSorted already include x due to <= operator? edit: also, how is the pivot element selected there?
- zests 7y agoBoth of your questions have the same answer. (x:xs) means x is the first element and xs is the rest.
- magicalhippo 7y agoAha! Thanks. Obviously picking first element as pivot makes for a very poor Quicksort. Though I presume a better approach, say median of first, mid and last elements, would add but an extra line?
- sullyj3 7y agoThe reason the first element is used as the pivot is that these are linked lists, not arrays, so it would take linear time to access the middle and end. This isn't a real quicksort.
- deleted 7y ago[deleted]
- edflsafoiewq 7y agoThat is (infamously) not quicksort.
- remcob 7y agoWhat's wrong with it?
- tossup8536 7y agoPerformance. Internal representation. You are not actually modifying things in place. Those are the equivalent of linked lists not arrays. That quicksort is not quick at all because the append operation in Haskell is linear. You can't use those lists to implement quicksort.
- lonelappde 7y agoHaskell is lazy. a ++ b === (head a) : ((tail a) ++ b) (plus the base case) It is only linear when you force it to evaluate, which ideally happens only once (amortized) in your program when the result is consumed. As long as you are careful, you don't get the bad quadratic performance that you'd get from something like eagerly appending a character to a string in a loop in Java. There are either gotchas, though, including relying on the compiler to do things in constant space that naively look linear, and also knowing when the compiler won't help you and you have to structure your computation manually.
- Koshkin 7y ago“Modifying things in place” is, from the logical standpoint, an unnatural and even dangerous thing. A person that is not familiar with (imperative) programming often has a hard time understanding variables and assignments (similar to some programmers not understanding pointers). Mathematics doesn’t have assignments, either. That should tell you something...
- recursive 7y agoIn that case, quicksort requires danger and artifice. In any case, it's not quicksort.
- CyberDildonics 7y agoWon't this have to iterate through linked lists and create multiple new heap allocations on each recursive step? Doesn't that imply n log n heap allocations just to sort a list?
- remcob 7y agoYes, but due to lazy-evaluation that won't happen until you do something with the sorted list. Your performance may just blow up in some seemingly unrelated place. My biggest problem with Haskell is how GC and lazy-evaluation makes it very difficult to reason about what the hardware is actually doing at a given point. I know there ways to inspect and control it, but I've found myself preferring languages that have simpler mental models.
- CyberDildonics 7y agoRight, by the time you have to control it, you are washing away all the advantages for using it.
- marceloabsousa 7y agoSpot on. There's a lot of wisdom in this comment.
- kadoban 7y agoDifferent things are hard or easy in Haskell compared to other languages. Mergesort would be the first one I'd reach for in Haskell if I'm implementing from scratch. Quicksort isn't really hard, you just do it in IO and it looks about like what you'd see in any imperative language. (or you can use ST, but then you have to know about ST).
- amelius 7y agoBut let's say I want to print something in a deeply nested function which isn't of the return-IO-Monad-type. Now I have to convert the entire call-chain of functions into Monad style. Is there some tool to do this automatically?
- kadoban 7y agoFor debug there is Debug.Trace which is about perfect. For non-debug, you may be overestimating how useful it is to output from pure functions in production. In general when you are in a situation where you need to change the Monad you're under, there's techniques and libraries for that (one way you define it once, give it a name, etc.). The biggest pain tends to be going from pure to monadic in the first place, which last I used Haskell there wasn't much for but to just do it. There may be more tooling now, haven't seen.
- hopia 7y agoWhy would you want to print inside a pure function though?
- AnimalMuppet 7y agoBecause some non-technical manager came to you and said, "Can't you just print out the value here? And can I get it in the next 15 minutes?" and it was pretty clear that "No" was not an acceptable answer.
- CyberDildonics 7y agoBut you do have to invent something or you wouldn't be writing a program in the first place. As soon as you need to control the order of execution, memory usage, IO, or any combination of those, you are fighting the language and into territory of things you can technically do and out of the realm of things the language makes easy.