Lower complexity bounds tend to be a very hard problem in general. Despite this, I was wondering if there are any theoretical results that relate lower complexity bounds for some class of problems in the case where mutation is allowed and in the case it's not allowed? In particular, what type of problems would be inherently harder to solve in a purely functional language on a RAM machine?

The following problem is why I started thinking about this: https://stackoverflow.com/questions/24105301/number-of-occurrences-in-list-of-each-element


See the section labelled "Negative result: you cannot avoid some slowdown, for some data structures" of https://cs.stackexchange.com/a/18266/755 for examples of problems whose solution in a functional language is inherently a bit slower than a solution in an imperative language with mutation. One example is an array data structure; with mutation, you can achieve $O(1)$ worst-case time for both mutation and lookup, but with a functional language (with persistent data structures), you cannot.

  • $\begingroup$ Does this computational model have a name? Before asking this question I did a quick search on google scholar, but could not find anything about this. I'd like to know if there's any useful theory that classifies types of problems that are known to be harder without mutation. $\endgroup$ – Edvard Fagerholm Jun 9 '14 at 20:39
  • $\begingroup$ @EdvardFagerholm, there's a lot of research into persistent data structures (including an overview in the answer I linked to). You could start by reading references on persistent data structures. Searching for persistent data structures on this site might give you some references, too. It's only the data structures part of things, not the algorithms part, but it seems relevant. $\endgroup$ – D.W. Jun 9 '14 at 20:41
  • $\begingroup$ OK, the persistent data structure literature probably contains pointers to what I'm looking for. I need to look into it more closely. Thanks. $\endgroup$ – Edvard Fagerholm Jun 9 '14 at 20:46

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.