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$ May 16 '18 at 18:58
  • $\begingroup$ I'm asking about functional programming languages in general and I removed the reference to Haskell $\endgroup$ 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$ 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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.