[Haskell-cafe] Theoretical question: are side effects necessary?
Felipe Almeida Lessa
felipe.lessa at gmail.com
Fri Mar 16 13:35:54 CET 2012
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.
More information about the Haskell-Cafe