Logarithmic Slowdown of Functional Languages?
The Wikipedia page on "Functional Programming" has some assertions about efficiency that sound questionable. I'm not the only one--someone else tagged the item with "citation needed" and started a discussion.
It currently says, "Any imperative algorithm is expressible in these languages with a logarithmic slowdown in the worst case." David Hopwood notes in the discussion that "Imperative algorithms are expressible with no asympotic slowdown," using some clever/complicated technique involving mutable arrays (citing a caml-list posting by one Tom Breuel).
All of this sounds a bit strange to me--as far as I know, there's no conclusive reason to think that functional languages must execute a particular algorithm more slowly than an imperative language. (Where does this "logarithmic slowdown" come from, anyway?) But I don't have a mastery of all the relevant literature. Can someone else jump in and straighten this out?
Comments
The logarithmic slowdown is from having to use immutable data structures, e.g. balanced trees for associative lookup instead of hash tables. There is a theorem saying the slowdown is unavoidable under some assumptions. Haskell gets around it with some mutable types enclosed in monads.
Posted by: asdf | February 27, 2008 7:41 AM
The logarithmic slowdown is from having to use immutable data structures, e.g. balanced trees for associative lookup instead of hash tables. There is a theorem saying the slowdown is unavoidable under some assumptions. Haskell gets around it with some mutable types enclosed in monads.
Posted by: asdf | February 27, 2008 7:42 AM
I don't see why that should lead to a logarithmic slowdown as such. It could be that you happen to have a data-structure whose depth is logarithmic in its total size (such as a balanced tree) and in that case updating a small piece of it would cause logarithmically-many operations in the worst case (re-creating the spine of the structure). But that's not a general "logarithmic slowdown" for functional languages, its a set of particular situations. The real outcome could be better or worse than that.
I'd like to see this theorem you mention.
Posted by: Ezra | September 10, 2008 12:59 PM