3
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jun 9, 2014 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. ♦
    Commented Jun 9, 2014 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
    Commented Jun 9, 2014 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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