6 ms·
Trying Haskell
- ionfish 16y agoObligatory comment pointing out that the fabled "quicksort" example in Haskell is not actually quicksort proper since it's not in-place.
- merijnv 16y agoNot to mention that Haskell's sort function is actually quite a bit more complex than the stereotypical "quicksort" example shown.
- aristidb 16y agoC++'s std::sort in turn is a lot more complex than the quicksort example shown.
- CJefferson 16y agoTo be fair, that is because it is a carefully tuned combination of 3 sort routines (quicksort, heapsort, insertion sort), and also optimisations to avoid unnecessary checks for pointers reaching the end of arrays where they can be avoided. I would be impressed if a sort which used the same 3 combined techniques could be faster. (Of course, there might be better sorts, such as TimSort, but that's a change of algorithm, not language).
- Peaker 16y agoI think timsort is trying to optimize on comparison counts, because comparisons might call back into Python code, which is expensive. Other sorting algorithms optimize different operations.
- danieldk 16y agoFor reference, Data.List.sort in GHC: http://www.haskell.org/ghc/docs/7.0.2/html/libraries/base-4.3.1.0/src/Data-List.html#sort http://www.haskell.org/ghc/docs/7.0.2/html/libraries/base-4.... It's still short and sweet ;).
- chris_j 16y agoIs it actually possible to implement quicksort in a pure functional language like Haskell (with immutable data structures)? Sorting in place would seem to involve mutating the list every time two values are swapped.
- jmillikin 16y agoHaskell has mutable data structures; you could easily implement in-place quicksort with vectors, arrays, or pointers.
- Hemospectrum 16y agoHaskell is designed to quarantine side effects, not remove them altogether. There's a special monad for building data structures that are mutable at creation time but appear immutable outside that block of code. In normal circumstances, you'd probably still have to copy the contents of the input into a new array before sorting it, though. So, it would still be less memory efficient on large inputs.
- danieldk 16y agoYes. For example, the vector package provides mutable arrays: http://hackage.haskell.org/package/vector-0.7.0.1 http://hackage.haskell.org/package/vector-0.7.0.1 Mutability is attained by using the ST monad. The ST monad uses mutable memory, but since it does not allow other interactions with the outside world, its value can be extracted (unlike the IO monad). When you are done with the modification of the vector, it can be frozen to obtain a pure vector. The IO monad can also be used, but not if you want to return a pure value. A good tutorial can be found at: http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Vector_Tutorial http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Vector... I used mutable vectors in the ST monad in maximum entropy training software, and they are really performant.
- KirinDave 16y agoWhat blew my mind about the ST monad is that despite its promise of single-threading, it still allows for recursive division of labor. I was like, "Wait. Wait. Waaaiiiitt. How does it do that?"
- stianan 16y agoNot only is it not proper quicksort, it's very memory inefficient.
- eru 16y agoDepends on your GC and compiler.
- stianan 16y agoI'd argue that it's a good thing to use an algorithm that is efficient in and of itself. (And perhaps a language which invites the use of such an algorithm.)
- eru 16y agoThe efficiency of algorithms depends on the language / model of computation you are using. For an extreme example, the best way to write an efficient matrix multiplication in Fortran is to write a naive matrix multiplication. The compiler will recognize the pattern, and transform it.
- KirinDave 16y agoObligatory comment about quicksort being excessively popular because of its catchy name, and all-too-often delivering inferior performance on large datasets due to partial orderings & bad pivot choices. Obligatory comment about how sorting algorithm speed is far more important when dealing with incredibly large datasets, spanning across multiple machines. Uninsightful (and perhaps glib) point about how Machines Are So Fast These Days that even Bubble Sort appears fast for medium-sized datasets. Cleverly-worded comment about how Merge Sort is not the sort of sort to let you down in a jam, and how it is particularly suited to distributed computation (where the overhead of allocation is rendered meaningless by the I/O requirements).
- megrimlock 16y agoGenuine appreciation for concise recapitulation. I felt I could hear the Tivo fast-forward beep-boop sound while reading your comment.
- sfddf 16y agoHello, everybody, the good shoping place Welcome to: http://www.findsoso.com/ http://www.findsoso.com/ We specialized in the exportation of sport shoes and other products(clothing, bag,sunglasses,watches,belts,etc )which have great enjoyed popularty in the world market Many of our goods are on sales ,we can guarantee the crediblity by Pay-pal and delivery time .we would like to make a long termship. http://www.findsoso.com/ http://www.findsoso.com/ c.l.o.t.h.i.n.g,j.e.a.n,,h.a.n.d.b.a.g,(f.r.e.e)s.h.i.p.p.i.n.g Cheap Sweater >>>------I love you! ----> http://www.findsoso.com/ http://www.findsoso.com/ Believe you will love it. Accept paypal or credit card and free shipping.
- Tiomaidh 16y ago"Oh look, Haskell is great! Why? Static typing and concise code and no side effects!" I don't disagree on any particular point, but this is hardly news (on HN, at least), and is rather lacking in substance.
- Peaker 16y agoHaskell's type system can also express interesting things most languages' type systems can't. For example: https://github.com/yairchu/red-black-tree/blob/master/AvlTree.hs https://github.com/yairchu/red-black-tree/blob/master/AvlTre... -- in lines 13..21, an AVLTree type is defined -- with its invariants encoded in the type system. If there's a mistake in these 9 lines, you may get a wrong program. But the nice thing is that if you get just these 9 lines right -- then the hundreds of lines below it that implement an AVL tree cannot get the AVL invariants wrong. The same is also true for Red Black Trees: https://github.com/yairchu/red-black-tree/blob/master/RedBlackTree.hs https://github.com/yairchu/red-black-tree/blob/master/RedBla... Lines 26..36 inclusive encode the RBTree type such that the invariants are enforced by the type-checker. In case this is unclear: the type-checker enforcing the correctness of the invariants is at compile-time. A running program is a correct program, at least from the invariants' perspective.
- deleted 16y ago[deleted]
- billmcneale 16y agoThis might be beautiful code but come on, not a single comment?
- KirinDave 16y agoComments: the great deceivers. To paraphrase: Some people write tricky code and say, "Ah! I will use a comment to make this clear." Now they have two problems.
- Peaker 16y agoYou might be assuming a little much about the purpose and target audience of this code :-) I didn't write it, by the way.
- silentbicycle 16y agoSee those type declarations? Those are comments. Comments that are automatically checked.
- pdhborges 16y agoC++ quicksort :| #include <algorithm> #include <iterator> #include <functional> using namespace std; template <typename T> void sort(T begin, T end) { if (begin != end) { T middle = partition (begin, end, bind2nd(less<iterator_traits<T>::value_type>(), *begin)); sort (begin, middle); sort (max(begin + 1, middle), end); } } from wikipedia
- chc 16y agoHis version is explicit, sort of a C++ translation of the C algorithm (though still a bit longer than necessary even for C). I think he meant to imply "in simple C++ without STL." The awkwardness of partition() is not quite enough to overcome the LOC savings, but it's making a good effort. The Haskell version also refrains from importing the equivalent Data.List, which would allow us to define `more` and `less` as simply `partition (< x) xs`.