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

[Chris Smith]

On Fri, Mar 16, 2012 at 3:43 PM, serialhex <serialhex at gmail.com> wrote:
> an interesting question emerges:  even though i may be able to implement an
> algorithm with O(f(n)) in Haskell, and write a program that is O(g(n)) <
> O(f(n)) in C++ or Java...  could Haskell be said to be more efficient if
> time spent programming / maintaining Haskell is << C++ or Java??

There are two unrelated issues: (a) the efficiency of algorithms
implementable in Haskell, and (b) the efficiency of programmers
working in Haskell.  It makes no sense to ask a question that
conflates the two.  If you're unsure which definition of "efficient"
you meant to ask about, then first you should stop to define the words
you're using, and then ask a well-defined question.

That being said, this question is even more moot given that real
Haskell, which involves the IO and ST monads, is certainly no
different from any other language in its optimal asymptotics.  Even if
you discount IO and ST, lazy evaluation alone *may* recover optimal
asymptotics in all cases... it's known that a pure *eager* language
can add a log factor to the best case sometimes, but my understanding
is that for all known examples where that happens, lazy evaluation
(which can be seen as a controlled benign mutation) is enough to
recover the optimal asymptotics.

-- 
Chris Smith