You can emulate mutation with at most O(log(n)) penalty using a map.  Given that memory is of fixed size, log2(n) <= 64, so for "real-world" programs this becomes O(1).  So any program you can implement using mutation can be implemented in a pure language with the same big-O running time (but much much worse constant factors, given this naive translation).

Other external state is harder to emulate.  For example, communication over a network most definitely requires some concept of a 'computation with side effects' since the network's response could change from request to request.

In GHC, even IO objects are pure, but they conceptually represent functions that modify the state of reality.

  -- ryan

On Fri, Mar 16, 2012 at 5:23 AM, Christopher Svanefalk <christopher.svanefalk@gmail.com> wrote:
Dear all,

there is a question I have been thinking about a bit. In short, we could simply formulate it like this:

Are there any problems which cannot be solved a side effect-free language (such as Haskell)? In other words, are there problems that would explicitly demand semantics that can only be provided by a language allowing direct modification of external state variables, such as Java and C++?

If not, are there problems which are simply infeasible to solve with a side effect-free language?

I realize this question is very broad, and I am not expecting an exact answer by any means. I am asking since I am curious about the relation between functional and imperative/procedural languages in general. I primarily come from a Java background, but I can program Haskell and Erlang, and have recently started exploring Scala, so this would be interesting to know.

--
Best,

Christopher Svanefalk

Student,
Department of Computer Science and Engineering
University of Gothenburg / Chalmers University of Technology


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe