Scala で Binary heap tree

何がきっかけで買おうと思ったのか不思議と全く思い出せないのだけど The fun of programming [1] という本が届いた（日本の Amazon には高いハードカバーしかなかったので出版元に直接注文して2週間くらいだった）ので、とりあえず第1章で紹介されている binary heap tree （のうち skew heap と呼ばれていたもの）を Scala で実装してみた。これは優先順位つきのキューに使える構造で、先頭要素（もっとも優先順位の高い要素）の参照は定数時間、取り出しと新規要素の追加は平均して対数時間（最悪で線形時間）という方式らしい。

abstract class BinaryHeapTree[T <% Ordered[T]] {
  def isEmpty: Boolean
  def top: T
  def pop: BinaryHeapTree[T]
  def insert(elem: T): BinaryHeapTree[T]
  def merge(that: BinaryHeapTree[T]): BinaryHeapTree[T]
}

case class Empty[T <% Ordered[T]] extends BinaryHeapTree[T] {
  def isEmpty = true
  def top = error("Empty.top")
  def pop = error("Empty.pop")
  def insert(elem: T): BinaryHeapTree[T] = Fork(elem, Empty[T], Empty[T])
  def merge(that: BinaryHeapTree[T]) = that
}

case class Fork[T <% Ordered[T]](label: T, left: BinaryHeapTree[T], right: BinaryHeapTree[T])
    extends BinaryHeapTree[T] {
  def isEmpty = false
  def top = label
  def pop = left.merge(right)
  def insert(elem: T): BinaryHeapTree[T] = this.merge(Fork(elem, Empty[T], Empty[T]))
  def merge(that: BinaryHeapTree[T]) = {
    if (that.isEmpty) this
    else if (this.top <= that.top) Fork(label, right, left.merge(that))
    else that.merge(this)
  }
}

object Main {
  def main(args: Array[String]) = {
    var t: BinaryHeapTree[Int] = Empty[Int]
    for (i <- 1 to 7) {
      t = t.insert(i)
      Console.println(t)
    }
  }
}

いま悩んでいること：
- 関数的な構造なので variance annotation をつけて covariant な型付けをさせたいが、なんかうまくいかない。「 <% Ordered[T] 」がついているとそういうことはできないのかも。頭が整理できない。

[1] http://web.comlab.ox.ac.uk/oucl/publications/books/fop/

コメント 8

covariantにできないのは、type parameterが引数の型として
あらわれているせいではないでしょうか？type parameterが
引数の位置に出現する型は、contravariantにはできても、
covariantにはできないはずです。試しに
BinaryHeapTree[+T ... ]とすると、次のようなエラーが出ました：
error: covariant type T occurs in contravariant position in type T of value elem
def insert(elem: T): BinaryHeapTree[T]
by みずしま (2007-08-08 19:45) 

コメントありがとうございます（LL魂で発表されてた方ですよね、拝見してました）。

おっしゃるとおりで、 Scala By Example にはこういう場合に

def insert[U >: T](elem: U): BinaryHeapTree[U]

のようにして回避するといいよ、と書いてあったので、それも試してみたのですが、今度は

BinaryHeapTree2.scala:13: error: no implicit argument matching parameter type (U) => Ordered[U] was found.
def insert[U >: T](elem: U): BinaryHeapTree[U] = Fork(elem, Empty[U], Empty[U])

などとなってしまうんですね。このエラーの意味もわからないんですが、別ルートで考えてみると、ひょっとして A <: Ordered[A] が B <: Ordered[B] のサブタイプだったとして BinaryHeapTree[A] に B 型の要素を insert して BinaryHeapTree[B] を得たとしても A と B を比較する手段が提供されるとは保証できるわけではないのかな？（本当？）とか、そうだとしたらそれは Ordered[T] が Ordered[+T] ではないことと関係があるのか？とか考えてちょっと整理がつかなくなりました。
by ether (2007-08-08 22:17) 

えーと、まずエラーメッセージの意味についてなんですが、
これは、<%の意味に関係してきます。で、<%の意味なんですが、
例えばU <% Ordered[U]というのは、type parameter U は
Ordered[U]に暗黙に変換可能な型であることを意味しています。この
暗黙の変換というのは、
implicit def Int2String(x :int) = x.toString
のようにして定義します(ここではintからStringの型変換を定義
しています)。問題のエラーメッセージでは、おそらくU型(これは
Ordererd[T]のスーパータイプ)からOrdered[U]への暗黙の
変換が定義されていないと文句を言っているのだと思います。
もし、U <: Ordered[U]であれば、UからOrdered[U]への
変換も同時に可能なわけですが、そうではないため、
暗黙の変換が定義されているかどうかを探したが、定義されて
いなかったということだと思います。

次に解決方法なんですが、これはちょっとまだ思いついて
いません。Ordered[T]がOrdered[+T]ならば、
def insert[U >: T <: Ordered[U]](...) = ...
のようにすることで解決できそうですが、あいにくそうでない
ので、この方法は使えそうにありません。
by みずしま (2007-08-09 00:47) 

訂正です。上の
> U型(これはOrdererd[T]のスーパータイプ)
は間違いで、
> U型(これはTのスーパータイプ)
が正しいですね。
by みずしま (2007-08-09 00:48) 

連続コメントですいません。色々考えてみたんですが、結論としては
「covariantにすることはできない」のではないかと思います。
理由としてはetherさんがコメントでおっしゃられたのが近いんですが、
AとBが同一の型でない状況で、A <: Ordered[A] が B <: Ordered[B] のサブタイプであるという状況がそもそも変なんだと
思います。というのは、OrderedはScalaで次のように定義されている
わけですが、

trait Ordered[T] {
def < (o :T) :Boolean
def <= (o :T) :Boolean
..
}

ここで、AとBのそれぞれのメソッドのシグニチャは次のようになると考えられます。

A：
<(o :A) :Boolean
<=(o :A) :Boolean
...
B：
<(o :B) :Boolean
<=(o :B) :Boolean
...

ここでA <: Bが成り立つためには、引数の型がcontravariantであること、つまりB >: Aがなりたつ必要がありますが、これはA = Bのときにしか成り立ちません。というわけで、そもそも前提が変だったのではと
思います。
by みずしま (2007-08-10 00:00) 

def insert[U >: T <: Ordered[U]] でなく insert[U >: T <% Ordered[U]] とすると一応コンパイルは通りました。頭の整理はつかないままですが…（このようにして出来た型はどんなときに便利なのか？）
もう少し考えて見ます。

ちなみにですが Ordered の型はあるとき突然 Ordered[+a] から Ordered[a] に変わっていたみたいですね。Change History を追っても動機はよくわかりません。

http://scalasvn.epfl.ch/cgi-bin/viewvc.cgi/scala/trunk/src/library/scala/Ordered.scala?r1=6848&r2=8247
by ether (2007-08-10 00:19) 

あ、00:19 のコメントを投稿してからみずしまさんの00:00のコメントに気づきました。

＞ここでA <: Bが成り立つためには、引数の型がcontravariantであること、つまりB >: Aがなりたつ必要がありますが、これはA = Bのときにしか成り立ちません。というわけで、そもそも前提が変だったのではと
思います。

なるほど、かなりすっきりしました。どうもありがとうございます。
by ether (2007-08-10 00:31) 

> def insert[U >: T <: Ordered[U]] でなく insert[U >: T <% Ordered[U]] とすると一応コンパイルは通りました。

なるほど！確かにそれならコンパイルを通りますね。気付きません
でした。ただ、実際のところどのような場面で便利なのかは
よくわかりませんが。

> Ordered の型はあるとき突然 Ordered[+a] から Ordered[a] に変わっていたみたいですね。

以前はOrdered[+a]だったんですね。知りませんでした。情報ありがとうございます。しかし、そうなると、Ordered[+a]を実装したクラスは(compare
メソッドの引数の型に関して得られる情報がほとんど無いのに)
一体どうやってcompareメソッドなどを実装していたのか…というのが
気になったので、ちょっと調べてみたら、どうやら引数に対して
パターンマッチングを行っていたみたいですね(
http://scalasvn.epfl.ch/cgi-bin/viewvc.cgi/scala/trunk/src/library/scala/Predef.scala?view=markup&pathrev=6848
のtuple22orderedに書いてありました)。
by みずしま (2007-08-10 01:38)