How would a priority queue be coded efficiently in a functional programming language? I'm new to functional programming, but I'm having difficulty understanding how a data structure that seems to require mutability would be coded in a functional programming language, or how to take advantage of lazy evaluation to pull this off.

Are there any working examples of priority queues being coded in a functional programming language?

  • $\begingroup$ Questions about particular programming languages are off-topic here. $\endgroup$ – Yuval Filmus May 16 '18 at 18:58
  • $\begingroup$ I'm asking about functional programming languages in general and I removed the reference to Haskell $\endgroup$ – Jorge Perez May 16 '18 at 19:02
  • 4
    $\begingroup$ Check Chris Okasaki's thesis Purely Functional Data Structures or his book of the same name. It is, without a doubt, one of the most significant references for this question. He also had a nice chapter in The Fun of Programming that provides a very simple implementation of a heap with decent (though not the absolute best) asymptotic performance. $\endgroup$ – Derek Elkins May 16 '18 at 20:25
  • $\begingroup$ cs.stackexchange.com/q/18262/755 $\endgroup$ – D.W. May 17 '18 at 0:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.