[Haskell-cafe] Theoretical question: are side effects necessary?

[Ryan Ingram]

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 at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120316/bced9f6b/attachment.htm>