# Is there any work on purely functional approximation algorithms?

It seems to me that approximating a solution to an NP-hard problem would be especially hard for the functional programmer. For example, graph problems are commonly NP-hard. But graphs are notoriously awkward to work with functionally. This makes me think that problems that can be easily solved in a purely functional sense are somehow easier than those that require state. This distinction in turn might shed some light on what makes hard problems hard.

So, is there any work on purely functional approximation algorithms? My general impression is that both communities ignore each other.

• I don't think this question is very well defined. Functional programming languages are turing complete, so there are no problems that 'require state'. Being awkward to work with is hard to make precise. Also, there are many algorithms that compute approximations on streams, e.g., via sampling. This can be easily adapted to functional style without being explicitely about functional approximation algorithms. – adrianN Feb 5 '13 at 8:47
• @adrianN It's true that they're Turing complete, but I don't think that it's true that every imperative algorithm running in time $f(n)$ also has a functional algorithm running in time $f(n)$. Sometimes, the best known functional algorithm takes asymptotically more time. So I'm not asking if the approximation ration is better or worse in a functional setting. I agree that wouldn't make sense. I'm asking for a comparison of the run times of approximation algorithms in a functional setting and imperative setting. It seems like these could differ dramatically. – Mike Izbicki Feb 5 '13 at 15:19
• Since you can simulate random access memory using a search tree (functional versions of which exist), you get at most a logarithmic overhead. That's not so dramatic. – adrianN Feb 5 '13 at 16:27
• Your question seems misleading. Your reasoning on why approximation algorithms seem difficult in functional programming style would equally apply to any graph algorithms, not necessarily approximation algorithms for graph problems. Indeed, some graph algorithms are hard to write in functional programming style, and I am pretty sure that they are studied in the programming language community. – Tsuyoshi Ito Feb 5 '13 at 19:34
• – Tsuyoshi Ito Feb 5 '13 at 19:34

From a more theoretical viewpoint, every algorithm that can be implemented on a RAM with runtime $f(n)$ can be implemented in a purely functional language with runtime at most $O(\log n * f(n))$. This is because functional languages are turing complete and the simulation of mutable, random access memory via search trees causes logarithmic slowdown. Chris Okasaki's Purely Functional Data Structures shows how to implement search trees in a functional language.
• I'd never realized that $\log n$ factor existed, interesting. – Jeff Burdges Feb 6 '13 at 11:35