Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The difference is entirely in the types. A sort function in Haskell has type:

    Ord a => [a] -> [a]
You therefore know that the implementation of the function can only make use of functions provided by Ord, and manipulation of the list structure. The function cannot inspect the values in the list except via comparison. This is an incredibly powerful guarantee. It's also really useful when you go to implement the function because this level of parametricity guarantees that there are only so many valid implementations and only a couple of them are even close to correct.



All true. On the other hand, std::sort in C++ works on RandomAccessIterator, which means that it can sort vectors, C arrays, deques, strings, your custom container type, etc. The Haskell implementation can only sort lists. Furthermore, the Haskell type signature fails to express that the input and output have the same size. But std::sort necessarily preserves its size, because you pass it a range, and a range cannot access its underlying container to change its size (a limitation leading to bizarre APIs like std::unique).


You can define a mutable std::sort like function in Haskell:

  mutableSort :: (MArray arr elem m, Ord elem, Ix ix) => arr ix elem -> m ()
This can work on mutable arrays in the IO, ST, or other mutable-array supporting monads. It also has a generalized index type (though newer array libraries threw that part away, so it's not considered a good idea anymore).




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: