5

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.

Mike Izbicki
  • 1,073
  • 7
  • 15
  • 7
    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 05 '13 at 08: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 05 '13 at 15:19
  • 4
    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 05 '13 at 16:27
  • @adrianN this might constitute an answer to the question. – Suresh Venkat Feb 05 '13 at 18:06
  • 1
    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 05 '13 at 19:34
  • 4
    Related question: Is there a general theory for why certain algorithms are inefficient in high-level languages? – Tsuyoshi Ito Feb 05 '13 at 19:34

1 Answers1

7

I'm consolidating my comments into an answer.

First, it is hard to make being "awkward to implement" precise, so an empirical study of program length or development time for a number of approximation algorithms is in order to answer that question.

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.

Nowadays many approximation algorithms are designed for huge datasets and are written in the language of MapReduce or Pregel. This type of algorithm is very easy to translate to functional languages, as these distributed computing paradigms generally avoid stateful computations.

As a comment below notes, this question on Stack Overflow is closely related. In particular Edward Kmett gives references that show that under strict evaluation (i.e. not like the lazy evaluation you see in Haskell) there are examples where the logarithmic slowdown is necessary. It seems to be open whether this is also true in lazy settings.

Community
  • 1
adrianN
  • 877
  • 10
  • 13
  • I'd never realized that $\log n$ factor existed, interesting. – Jeff Burdges Feb 06 '13 at 11:35
  • 1
    This is an interesting/useful answer, but I think it leaves room for further responses to the original question as well, e.g. are there any examples of purely functional approximation algorithms proposed in the literature? Or any that are actually used in practice? (Rather than just the fact that existing impure algorithms may be converted without losing too much.) – usul Feb 06 '13 at 16:23
  • 2
    According to this comment it's known that the logarithmic slowdown can be unavoidable in a call-by-value setting, but an open question with call-by-need. – C. A. McCann Feb 06 '13 at 19:51