I'm trying to implement counting sort in Haskell for a list of type (Int, String). I've been trying to do it according to Wikipedia's description.

After some attempts, I gave up, because the Wikipedia description makes heavy use of mutation in different places throughout the algorithm, which I just don't know how to translate to a declarative language.

So my question is, does counting sort require mutation or can it be implemented in a language like Haskell without fancy constructs?

  • $\begingroup$ In principle, can't you do everything without mutation? Can't you, for example, represent the state of a Turing machine as a list of the used portion of the tape with an appropriate marker for the head position and state and manipulate that list without mutation? Assuming I'm correct about that, the CS answer is basically "Yes, you can do it without mutation because you can do everything without mutation" and then the rest of your question is just a programming exercise, which is off-topic, here. $\endgroup$ – David Richerby Mar 9 '18 at 16:50

First off, a persistent map from address to value can simulate RAM. There is a time overhead of $O(\log(s))$ and a space overhead of $O(s)$, where $s$ is the space used.* So an algorithm that runs in time $t$ and space $s$ in RAM has a purely functional algorithm in time $O(t \log(s))$ and space $O(s)$. However, simulating the RAM itself, at least conceptually, creates a purely functional computer, not version of the particular algorithm in question, so it probably isn't what you're looking for.

Fortunately this algorithm can be tweaked slightly to be purely functional. Using a persistent sorted map from list item to count, you can traverse the list, updating the count in the map for each list item encountered in $\theta(n \log(c))$ time and $\theta(c)$ space, excluding input and output lists, where $c$ is the number of distinct values. Then, you can concatMap the (list item, count) pairs to count occurrences of the list item. As the map is already sorted by list item, the resulting list will be sorted.

The original algorithm runs in $\theta(n)$ time and $\theta(c)$ mutable space, excluding input and output lists, so the functional version introduces a factor of $\log(c)$ in its run time, which is the same factor introduced by simulating the RAM.

* Specifically, as far as time is concerned, $s$ is the mutable space used, as any immutable space can be provided separately in a read-only array so it doesn't impose any time penalty.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.