You can emulate mutation with at most O(log(n)) penalty using a map.  Given that memory is of fixed size, log2(n) &lt;= 64, so for &quot;real-world&quot; 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).<br>
<br>Other external state is harder to emulate.  For example, communication over a network most definitely requires some concept of a &#39;computation with side effects&#39; since the network&#39;s response could change from request to request.<br>
<br>In GHC, even IO objects are pure, but they conceptually represent functions that modify the state of reality.<br><br>  -- ryan<br><br><div class="gmail_quote">On Fri, Mar 16, 2012 at 5:23 AM, Christopher Svanefalk <span dir="ltr">&lt;<a href="mailto:christopher.svanefalk@gmail.com">christopher.svanefalk@gmail.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Dear all,<div><br></div><div>there is a question I have been thinking about a bit. In short, we could simply formulate it like this:</div>
<div><br></div><div>Are there any problems which <i>cannot </i>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++?</div>

<div><br></div><div>If not, are there problems which are simply <i>infeasible </i>to solve with a side effect-free language?</div><div><br></div><div>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.<span class="HOEnZb"><font color="#888888"><br clear="all">

<div><br></div>-- <br>Best,<div><br></div><div>Christopher Svanefalk</div><div><br></div><div>Student,</div><div>Department of Computer Science and Engineering</div><div>University of Gothenburg / Chalmers University of Technology</div>

<br>
</font></span></div>
<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br>