Replacing imperative PriorityQueue in my algorithm

Question

I currently have a method that uses a scala.collection.mutable.PriorityQueue to combine elements in a certain order. For instance the code looks a bit like this:

 def process[A : Ordering](as: Set[A], f: (A, A) => A): A = {
   val queue = new scala.collection.mutable.PriorityQueue[A]() ++ as
   while (queue.size > 1) {
     val a1 = queue.dequeue
     val a2 = queue.dequeue
     queue.enqueue(f(a1, a2))
   }
   queue.dequeue
 }

The code works as written, but is necessarily pretty imperative. I thought of using a SortedSet instead of the PriorityQueue, but my attempts make the process look a lot messier. What is a more declarative, succinct way of doing what I want to do?

Answer 1

If f doesn't produce elements that are already in the Set, you can indeed use a SortedSet. (If it does, you need an immutable priority queue.) A declarative wayto do this would be:

def process[A:Ordering](s:SortedSet[A], f:(A,A)=>A):A = {
  if (s.size == 1) s.head else {
    val fst::snd::Nil = s.take(2).toList
    val newSet = s - fst - snd + f(fst, snd)
    process(newSet, f)
  }
}