On Fri, Mar 16, 2012 at 3:43 PM, serialhex
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