3

現在、scala.collection.mutable.PriorityQueue を使用して要素を特定の順序で結合するメソッドがあります。たとえば、コードは次のようになります。

 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
 }

コードは書かれたとおりに機能しますが、必然的にかなり必須です。私は PriorityQueue の代わりに SortedSet を使用することを考えましたが、私の試みはプロセスをより複雑に見せます。私がやりたいことを行うための、より宣言的で簡潔な方法は何ですか?

4

3 に答える 3

2

f が既に Set にある要素を生成しない場合は、実際に a を使用できますSortedSet。(そうであれば、不変の優先キューが必要です。)これを行う宣言的な方法は次のようになります。

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)
  }
}
于 2011-07-18T20:15:12.113 に答える
0

@Kim Stebelの回答を改善しようとしましたが、命令型のバリアントはさらに明確だと思います。

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))
}
于 2011-07-19T07:18:48.187 に答える
0

SortedSetとを使用したソリューションは次の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
}
于 2011-07-26T18:50:27.097 に答える