2009/12/25 Svein Ove Aas <[email protected]>: > On Mon, Jun 15, 2009 at 4:18 AM, Richard O'Keefe <[email protected]> wrote: >> There's a current thread in the Erlang mailing list about >> priority queues. I'm aware of, for example, the Brodal/Okasaki >> paper and the David King paper. I'm also aware of James Cook's >> priority queue package in Hackage, have my own copy of Okasaki's >> book, and have just spent an hour searching the web. >> >> One of the correspondents in that thread claims that it is >> provably impossible to have an efficient priority queue implementation >> without mutability. I think he's cuckoo. But I'd like to have some >> numbers to back me up. >> > Regardless of whether he is correct or not, the result would not apply > to haskell. > > Lazyness can be considered to be a controlled form of mutation, which > Okasaki takes advantage of in a number of his data structures. Most > (all I've seen) arguments stating that purely functional languages > have asymptotic performance worse than mutating languages simply don't > apply to lazy ones. >
To be fair, I am not aware of any asymptotically efficient (as efficient as their imperative counterparts) purely functional (t.i. not using mutation) implementations of, say, the "union-find" datastructure. However, that does not pose any constraints on the efficiency of Haskell because of the existence of the ST monad. > > -- > Svein Ove Aas > _______________________________________________ > Haskell-Cafe mailing list > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Eugene Kirpichov Web IR developer, market.yandex.ru _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
