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

[Felipe Almeida Lessa]

On Fri, Mar 16, 2012 at 9:23 AM, Christopher Svanefalk
<christopher.svanefalk at gmail.com> wrote:
> 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++?

Haskell, Java, C++ and most other languages out there are
Turing-complete.  That means that all of them are able to compute the
same things.  Assuming that the Church-Turing hypothesis is true, all
algorithms may be coded in all of them.

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

If you're asking about performance, as in "is there a problem that can
be solved in O(f(n)) time in Java but not in Haskell-sans-IO-and-ST?",
then it becomes a harder question.  I'm not sure what the answer is.

Cheers,

-- 
Felipe.