# 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.
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.