自分自身の型をパラメータに取るgenericな型を記述する

@nagiseさん：

ある木構造のノードをクラスで表現して、親の型をジェネリクスで受け取るNodeがあったとして、Node自身を親に出来るNodeを宣言できない。Node>となるんだけど、どうにかならないもんか。

Javaだと継承して、

public class ExtNode extends Node<ExtNode> {
  ...
}

とするくらいしか解決する手段は無さそうだけど、Scalaだともうちょっとうまい方法があるのではないかと考えたが、いいアイデアを思いつかなかったので、ぐぐってみたところ、

OCamlテクニック/再帰型(Equi-recursive)

というページを見つけた。このページで紹介されている、Equi-recursive typeが、まさに今やりたいことなのだが、あいにくScalaにはそのような機能は無いので、何か別の手段でそれをエミュレートする必要がある。ここで、「Haskellでムリヤリ近いことをやる」のテクニックがScalaにも応用できそうなので、試してみたところうまく行ったので紹介してみる。

まず、「Haskellでムリヤリ近いことをやる」のコードを見てみると、以下のようになっている。

newtype Rec t = R (t (Rec t))

ここでポイントなのは、型コンストラクタRecの型変数tに対してRec tが適用されているという部分で、これは、Scalaのtype constructor polymorphismを使えば表現することができて、コードは以下のようになる。

class R[T[_]](private var value: T[R[T]]) {
  def apply(): T[R[T]] = value
  def update(newValue: T[R[T]]): Unit = value = newValue
}

Rはtype constructor(genericな型) Tをパラメータに取るクラスで、T[ R[T] ]を要素として持つようなコンテナクラスでもある。

次に、木構造を表現するノードのクラスを以下のような形で定義してやる。この部分は、上のRを使うか否かによって変化しない部分なので、特に工夫する部分は無い。

class Node[T] {
  var parent: T = _
  var content: Int = 100
}

あとは、このNodeクラスに対して、R[Node]をパラメタとして与えた型のデータを作るだけでＯＫ。

val node = new Node[R[Node]]

値を取得/設定するコードは、以下のようになる。

node.parent = new R[Node](node)
println(node.parent().content)
node.parent().content = 200
println(node.parent().content)

R[Node]クラスを経由する分、コードは若干煩雑になる。