# Do functional algorithms require more memory than imperative algorithms? [closed]

Let's suppose we are counting words in string. We split it so what we have is an array of strings. I'll use Python as an example.

The imperative approach would as follows:

wordcount = {}
for word in words:
wordcount[word] += 1


The functional would be:

uniquewords = set(words)
wordcount = [words.count(w) for w in words]


For each word w we are doing a full scan on the words array, while the imperative approach goes over each word just once. Am I right to suppose that the functional way of doing it will consume a lot more resources than the imperative one?

• The functional one only does one pass of the array as well. What resources it uses depends on the back-end implementation - it may look no different in machine code to the imperative approach. – Luke Mathieson Jun 28 '15 at 1:22
• I don't think it is fair to compare functional approaches to imperative ones, by using different algorithms with different asymptotical time complexities (one is $O(n^2)$, and the other is $O(n)$). – hengxin Jun 28 '15 at 1:34
• They is no reason to assume that smart compilers can output very similar machine code for either paradigm. You'll have to dig a little deeper and make assumptions resp. impose restrictions on the functional compiler. – Raphael Jun 28 '15 at 9:46
• What do you mean by "functional algorithms"? It sounds like you're asking if the implementation of an algorithm expressed functionally requires more memory than the implementation of the same algorithm expressed imperatively. But that depends entirely on the quality of the two implementations (i.e., compilers). Could you clarify your question? – David Richerby Jun 28 '15 at 9:52
• Also, your "functional" example doesn't look at all functional to me. – David Richerby Jun 28 '15 at 9:53

Your example of "functional programming" is a pretty poor one. For starters, it is not functional because it uses state (it stores something in words and behind the scenes set(words) is doing stateful stuff as well). To actually learn what functional programming is about, you should look outside an imperative language such as Python. Python often uses imperative features dressed up as functional programming. Have a look at Ocaml or Haskell.

As for your question, people have thought about just how efficiently one can implement functional programs on standard hardware (which I think is what you're asking). At LICS 2015 the following paper has been accepted:

B. Accattoli, C. Sacerdoti Coen. On the Relative Usefulness of Fireballs. LICS 2015.

In it the authors show that a RAM machine (standard hardware) can simulate $\lambda$-calculus (functional programming) with a linear-time overhead with respect to the number of computation steps ($\beta$-reductions) of the functional program. This shows that functional programs can be efficiently implemented on existing hardware and will not in general consume a lot more resources.

Let me also point out that you cannot make the comparison you're trying to make in a sensible way. You are comparing two different algorithms that compute the same function. Instead, you should be comparing two implementations of the same algorithm in an imperative and a functional style. For instance sorting algorithms would do. And you should use a language that supports both imperative and functional programming. For instance, we could take merge sort and use the rosettacode.org functional implementation of merge srot in OCaml. Perhaps someone has the time to play with this and post some comparisons.