<p>I'm consolidating my comments into an answer.</p>

<p>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.</p>

<p>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 <em>Purely Functional Data Structures</em> shows how to implement search trees in a functional language.</p>

<p>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.</p>

<p>As a comment below notes, <a href="https://stackoverflow.com/questions/6797216/haskell-algorithms-and-school#comment8108763_6797432">this question</a> on Stack Overflow is closely related. In particular Edward Kmett <a href="https://stackoverflow.com/questions/6797216/haskell-algorithms-and-school#comment8108763_6797432">gives references</a> 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. </p>

CC BY-SA 3.0
2013-02-06T11:35:31.497Z
I'd never realized that $\log n$ factor existed, interesting.
Jeff Burdges
CC BY-SA 3.0
2013-02-06T16:23:28.287Z
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
CC BY-SA 3.0
2013-02-06T19:51:03.670Z
According to [this comment](http://stackoverflow.com/questions/6797216/haskell-algorithms-and-school#comment8108763_6797432) 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
CC BY-SA 3.0
2013-02-06T09:43:39.683Z
2013-02-07T09:17:44.160Z
2017-05-23T12:40:09.333Z
adrianN
<p>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.</p>

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

CC BY-SA 3.0
2013-02-05T08:47:07.867Z
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
CC BY-SA 3.0
2013-02-05T15:19:14.150Z
@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
CC BY-SA 3.0
2013-02-05T16:27:22.720Z
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
CC BY-SA 3.0
2013-02-05T18:06:51.323Z
@adrianN this might constitute an answer to the question.
Suresh Venkat
CC BY-SA 3.0
2013-02-05T19:34:11.387Z
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
CC BY-SA 3.0
2013-02-05T19:34:51.137Z
Related question: [Is there a general theory for why certain algorithms are inefficient in high-level languages?](http://cstheory.stackexchange.com/questions/10287)
Tsuyoshi Ito
<reference-request><approximation-algorithms><functional-programming>
Is there any work on purely functional approximation algorithms?
Mike Izbicki
# Is there any work on purely functional approximation algorithms?

(Asked by: username_0 on 2013-02-05)

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.

**Tags:** reference-request, approximation-algorithms, functional-programming
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_2**: @adrianN this might constitute an answer to the question.  
> **username_3**: 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.  
> **username_3**: Related question: [Is there a general theory for why certain algorithms are inefficient in high-level languages?](http://cstheory.stackexchange.com/questions/10287)  

---

## 1 answers

### Answer by username_1 on 2013-02-06. Score: 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](https://stackoverflow.com/questions/6797216/haskell-algorithms-and-school#comment8108763_6797432) on Stack Overflow is closely related. In particular Edward Kmett [gives references](https://stackoverflow.com/questions/6797216/haskell-algorithms-and-school#comment8108763_6797432) 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.

> **Comments:**
> **username_4**: I'd never realized that $\log n$ factor existed, interesting.  
> **username_5**: 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.)  
> **username_6**: According to [this comment](http://stackoverflow.com/questions/6797216/haskell-algorithms-and-school#comment8108763_6797432) it's known that the logarithmic slowdown can be unavoidable in a call-by-value setting, but an open question with call-by-need.  

---

