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?

Kim Stebel · Accepted Answer · 2011-07-18T20:31:49.777

2

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)
  }
}

edited Jul 18 '11 at 20:31

answered Jul 18 '11 at 20:15

Kim Stebel

41,826
12
125
142

I'd have to say the OP's imperative version is clearer. It would be useful if there was a multiple-item dequeue function... – The Archetypal Paul Jul 18 '11 at 20:19
I cleared it up a bit, can't see what's clearer about the OP's version now. It's just a matter of what you're used to. – Kim Stebel Jul 18 '11 at 20:32
1

I don't think it's just what you're used it. It's the s - fst - snd +... etc. Not using a dequeue means you do things twice - once to access the two top elements to pass them to f. once to construct the remainder of the queue without them. Dequeue captures both of those neatly. An extractor to return the first two and the rest of the queue might help? – The Archetypal Paul Jul 18 '11 at 21:17

score 0 · Answer 2 · answered Jul 19 '11 at 07:18

Tried to improve @Kim Stebel's answer, but I think imperative variant is still more clear.

def process[A:Ordering](s: Set[A], f: (A, A) => A): A = {
  val ord = implicitly[Ordering[A]]
  @tailrec
  def loop(lst: List[A]): A = lst match {
    case result :: Nil => result
    case fst :: snd :: rest =>
      val insert = f(fst, snd)
      val (more, less) = rest.span(ord.gt(_, insert))
      loop(more ::: insert :: less)    
  }
  loop(s.toList.sorted(ord.reverse))
}

score 0 · Answer 3 · answered Jul 26 '11 at 18:50

0

Here's a solution with SortedSet and Stream:

def process[A : Ordering](as: Set[A], f: (A, A) => A): A = {
    Stream.iterate(SortedSet.empty ++ as)(  ss => 
        ss.drop(2) + f(ss.head, ss.tail.head))
    .takeWhile(_.size > 1).last.head
}

answered Jul 26 '11 at 18:50

Daniel C. Sobral

295,120
86
501
681

This is probably a different question, but is there a reason to prefer Stream.iterate over Iterator.iterate in this situation? – Garrett Rowe Jul 26 '11 at 23:30
@Garrett None at all -- on the contrary, in fact. But an `Iterator` is not functional, and if one is replacing "imperative" code with functional... – Daniel C. Sobral Jul 27 '11 at 14:57

Replacing imperative PriorityQueue in my algorithm

3 Answers3