| For C/C++ all that is usually needed is to implement a few helper functions. E.g. the quicksort example is one of my favourite pet peeves, because the reason the C version sorts in place is that the archetypical C implementation after Hoare sorts in place. Many of the FP versions of quicksorts like this end up requiring a lot of additional memory. Maybe it is becoming reasonable to assume they will optimise it into an in-place sort these days, but it didn't use to be. Meanwhile, with a couple of small, generic helper functions, you can get down to nearly the same complexity in C/C++. For C++ the only helper you absolutely need to cut down on the verbosity has been a part of the standard library since C++98 I wrote a blog post about this back in 2005 [1] about one of the other typical Haskell quicksort examples, and referenced an article by Alexandrescu that gave an example implementation of quicksort in C++ with the (generic) partitioning, as well as the pivot selection split out that looks like this: template <class Iter>
void Sort(Iter b, Iter e)
{
const pair<Iter, Iter> midRange = Partition(b, e, SelectPivot(b, e));
Sort(b, midRange.first);
Sort(midRange.second, e);
}
You can do the same in C easily enough. So what Haskell had over C/C++ in this respect was mainly a more expressive standard library. C++ has long had std::partition(), so it can be done entirely with the standard library too if you're willing to do the same (bad) fixed/dumb pivot selection that the typical Haskell versions (as well as the archetypical C version) use.Unfortunately the link to the CUJ article is dead, as it was a quite fascinating walk through optimising sorting (including better pivot selection). [1] http://www.hokstad.com/archives/2005/03/about_haskell_a |