色々な型の値をまとめて扱う際にはタプルを用いるが、Scalaのタプルは22個までしか値を入れることができない。もし23個の値を持つタプルが必要な場合は自力でそういうデータ型を作るしかない。しかし、例えば23個のタプルを作ったとしても、次に24個のタプルが欲しくなったらまた作る必要があり、これは大変なことになる。そこで、今回はこの問題を解決するためにHeterogeneous List（HList）を実装することにする。タプルの話題をしているのに、何故リストが出てくるのかと疑問に思うかもしれない。一般にリストとはある型の要素がいくつか入っているデータ構造であるが、HListは色々な型の要素を投入することができ、かつ値がいくつ入っているのかを管理しているデータ構造である。このようなHListはもはやタプルと同じように扱うことができる。

アイディア

まず普通のリストについて考える。普通のリストは次のようなデータ型である。

sealed trait List[A]
case class Cons[A](h: A, t: List[A]) extends List[A]
case object Nil extends List[Nothing]

これに対して、HListは次のようになる。

sealed trait HList
case class HCons[+A, +B <: HList](h: A, t: B) extends HList
sealed trait HNil extends HList

注目して欲しいのは、HConsのtがHListではない点である。ではここに何が入るのかと言うと、例えばHNilやHCons[Int, HNil]、他にもHCons[Int, HCons[String, HNil]]といった、型のリストを入れることができる。この仕組みを用いて、色々な型の値を入れられるが型安全であるという目標を実現する。

`HList`の定義

まず、HListをデータ型で次のように定義する。

package hlist

sealed trait HList
case class :*:[+A, +B <: HList](h: A, t: B) extends HList {
  def :*:[C](x: C): C :*: A :*: B = hlist.:*:(x, this)
}
sealed trait HNil extends HList {
  def :*:[A](x: A): A :*: HNil = hlist.:*:(x, this)
}

先ほどの例ではコンストラクタにHConsを用いていたが、例えばHCons(a, HCons(b, hnil))¹と書くのはやや大変なので、コンストラクタを:*:という記号にしてしまって、かつそのメソッドにも:*:を加えることで、a :*: b :*: hnilという記法が利用できるようになる。まず、コンストラクタ:*:が持つ:*:メソッドについて説明する。

def :*:[C](x: C): C :*: A :*: B = hlist.:*:(x, this)

ここでthisはA :*: Bという型である。それに対して新たに型Cの値xを用いてコンストラクタを呼び出すので、生成される型はC :*: A :*: Bとなる。 HNilに関しては次のようになる。

def :*:[A, B <: HList](x: A): A :*: HNil = hlist.:*:(x, this)

thisがHNilなので、生成される型はA :*: HNilとなる。

`hnil`

空のHListを表すhnilを次のよう定義する。

val hnil = new HNil {}

`head`と`tail`

HListを操作するメソッドheadとtailを定義する。headはHListの先頭の要素を得るメソッドであり、tailはHListの先頭以外のHListを得るメソッドである。

def head[A, B <: HList](l: A :*: B): A = l match {
  case h :*: _ => h
}

def tail[A, B <: HList](l: A :*: B): B = l match {
  case _ :*: t => t
}

まずheadはA :*: B型のHListを受け取り、先頭の型Aを返すので、返り値の型はAとなる。tailはA :*: B型のHListを受け取りB型のリストを返す。このheadとtailが正しくできているのか確認してみる。

val l = 1 :*: "string" :*: 1.0 :*: hnil
head(l) + 1
tail(tail(tail(tail(l)))) // compile error!

まず、HListlにIntやStringなど色々な型の値を入れることに成功しているのが分かる。そしてheadで先頭の要素を取り出すこともできる。最後の例が何故コンパイルエラーになるのかと言うと、まずlの型はInt :*: String :*: Double :*: HNilとなっている。このlに対してtailを3回用いるとHNilとなってしまい、tailが求める型A :*: Bを満すことができない。ゆえに4回目のtailはコンパイルエラーとなる。このように、HListは今どんな型がどれだけ入っているのかを管理しているので、空のHList（hnil）に対するheadやtailをコンパイル時に検出することができる。

`append`

二つのHListを結合するメソッドappendを実装したいものの、これは先ほど実装したheadやtailのようには型を定義することができない。なのでややトリッキーなことを行う必要がある。まず、普通のリストに対して用いるappendメソッドは次のようになる。

def append[A](l1: List[A], l2: List[A]): List[A] = l1 match {
  case Nil     => l2
  case x :: xs => x :: append(xs, l2)
}

これをHListに対して行うには、どのようにすればよいだろうか。

実装の方針

例えば二つのHListをl1: Aとl2: Bであるとして、appendの型はどのようになるのだろうか。ここではappendの第一引数の型で場合分けして考えてみる。

第一引数のHListが型`HNil`の場合

つまり、第一引数のHListが型HNilであり、第二引数のHListが型Aであるならば、この二つをappendした結果は次のようになる。

def append[A <: HList](l1: HNil, l2: A): A

これは特に説明の必要はないと思う。

第一引数のHListが型`A`の場合に成り立つと仮定して、第一引数のHListの型が`X :*: A`の場合を考える

ここでは、数学的帰納法などでありがちな考え方を導入する。第一引数のHListの型がAであり、第二引数のHListの型がBである時に、appendの型がCとなるということを仮定する。

def append[A <: HList, B <: HList, C <: HList](l1: A, l2: B): C

そして、次に一番目のHListに型Xの値を一つ足したHListであるX :*: Aについて、次のような型を付けることができる。

def append[A <: HList, B <: HList, C <: HList, X](l1: X :*: A, l2: B): X :*: C

さて、これをどのようにScalaのコードへエンコードすればよいのだろうか。

型クラスとアドホック多相

このような型付けを行う際には、型クラスという機能を用いる。こちらのサイトでは型クラスを用いることで実現できるアドホック多相について、次のように書かれている。

アドホック多相とは何かというと

異なる型の間で共通したインターフェースでの異なる振る舞いを

定義済みの型に対して拡張する

ような多相のことです。

つまり今回のケースでは、同じappendメソッドであるものの、第一引数の型によって、次の二つのメソッドへ振り分ける必要がある。

append1: (A, HNil) => A
append2: (A, B) => Cを前提として、append3: (X :*: A, B) => X :*: C

従って、型クラスを用いてアドホック多相を実現することにする。

実装

まず、appendメソッドの型情報を定義するHAppendトレイトを作成する。

trait HAppend[A <: HList, B <: HList, C <: HList] {
  def append(l1: A, l2: B): C
}

このHAppendトレイトは、二つのHList（それぞれ型がAとB）を取り、返り値の型がCであるappendメソッドの型情報を定義する。そして、先ほどの二つのappendをそれぞれappendHNilとappendHListという名前で次のように実装する。

implicit def appendHNil[A <: HList] = new HAppend[HNil, A, A] {
  def append(l1: HNil, l2: A): A = l2
}

implicit def appendHList[A <: HList, B <: HList, C <: HList, X](implicit i: HAppend[A, B, C]) =
  new HAppend[X :*: A, B, X :*: C] {
    def append(l1: X :*: A, l2: B): X :*: C =
      cons(head(l1), i.append(tail(l1), l2))
  }

まず、appendHNilの実装について考える。第一引数l2の型がHNilであるので、appnendの結果としてはl2の値をそのまま返せばよく、従って型もl2の型と同じくAとなる。 appendHListについては、まずHAppend[A, B, C]を満すようなインスタンスiが存在することを仮定する。

(implicit i: HAppend[A, B, C])

そして、普通のリストの場合と同じように、appendメソッドを定義する。

def append(l1: X :*: A, l2: B): X :*: C =
  cons(head(l1), i.append(tail(l1), l2))

少々異なる点は再帰的に用いるappendメソッドがインスタンスiのメソッドになっていることだ。これは、現在定義したappendメソッドが(X :*: A, B) => X :*: Cという型を持つのに対して、投入したい引数はtail(l1): Aとl2: Bである。l2は問題ないが、tail(l1)は型AなのでX :*: Aと異なりエラーとなる。しかし、先ほど作成したインスタンスiは、append: (A, B) => Cというメソッドを持っているので、これを用いて帰納的な関数に対して型を付けられるようにしている。また、どうしてappendHNilの定義が必要なのかと疑問に思うかもしれないが、もしここでappendHNilがない場合は常にappendHListが呼び出され続けて無限に回り続けてしまう。それを防ぐために、appendHNilを用意している。後は二つのappendHNilとappendHListを振り分けるappendを実装すればよい。

def append[A <: HList, B <: HList, C <: HList](l1: A, l2: B)(implicit i: HAppend[A, B, C]) =
  i.append(l1, l2)

`nth`

タプルやリストでは$n$番目の要素へアクセスする手段を提供している。今回のHListではどのようにそれを実装したらよいだろうか。ちなみに普通のリストに対するnthは次のように実装できる。

def nth[A](l: List[A], n: Int) = l match {
  case x :: xs if n == 0 => x
  case x :: xs           => nth(n - 1, xs)
}

実装の方針と問題点

そこでappendの時と同様に場合分けして考えることにする。

$0$番目にアクセスする場合
$n$番目にアクセスできると仮定して、$n + 1$番目にアクセスする場合

このように二つに区別すればよさそうな気がするが、実はこれには問題がある。先程の例ではHListがHNilまたはA :*: HListのどちらかであるという型情報を用いて分岐させていたが、今回分岐の対象として用いる数字（Int）は0であっても、その他の数であっても両方Int型なので、これを使って分岐させることはできない。

自然数の実装

そこで$0$とそれ以外の数字を区別するような型を定義する。自然数の型Natは次のようになる。

sealed trait Nat
sealed trait Zero extends Nat
case class Succ[A <: Nat](n: A) extends Nat

自然数の世界にはZeroと自然数に1を足すSuccが存在する。自然数を操作するためメソッドを次のように定義する。

object Nat {
  val nzero = new Zero {}
  def succ[A <: Nat](n: A): Succ[A] = Succ(n)
  def pred[A <: Nat](n: Succ[A]): A = n match {
    case Succ(n) => n
  }
}

例えば$3$はsucc(succ(succ(nzero)))と表現でき、その型はSucc[Succ[Succ[Zero]]]となる。こうすることで自然数を型の情報へエンコードすることができる。

実装

まずはappendの時と同様に、型クラスに用いるトレイトを定義する。

trait HNth[A <: HList, B <: Nat, C] {
  def nth(l: A, n: B): C
}

そして、次のように二つのメソッドを定義して分岐させる。

implicit def nthZero[A, B <: HList] = new HNth[A :*: B, Zero, A] {
  def nth(l: A :*: B, n: Zero): A = head(l)
}

implicit def nthN[A <: HList, B <: Nat, C, D](implicit i: HNth[A, B, C]) = new HNth[D :*: A, Succ[B], C] {
  def nth(l: D :*: A, n: Succ[B]): C = i.nth(tail(l), Nat.pred(n))
}

def nth[A <: HList, B <: Nat, C](l: A, n: B)(implicit i: HNth[A, B, C]) =
  i.nth(l, n)

このようにすることで、Zeroの場合とSucc[Nat]の場合に上手く分岐させることができる。

実装

今回作成したコードはGistにアップロードしてある。

まとめ

今回作成したHListを用いれば、100個や200個の型が異なるデータを持つ型安全なリストを扱うプログラムを記述できる。また、型クラスを利用して実用的なプログラムの例を考えることができた。なお、今回実装したHListはshapelessというライブラリの中に（おそらく）より高機能なものがあるので、実用したい方はそちらを使う方がいいかもしれない。

参考文献

後で説明するが、hnilは型HNilを持つ値である。↩

yyu's notes

このブログを検索

色々な型の値をいくつでも入れられる型安全な“HList”を実装する

アイディア

`HList`の定義

`hnil`

`head`と`tail`

`append`

実装の方針

第一引数のHListが型`HNil`の場合

第一引数のHListが型`A`の場合に成り立つと仮定して、第一引数のHListの型が`X :*: A`の場合を考える

型クラスとアドホック多相

実装

`nth`

実装の方針と問題点

自然数の実装

実装

実装

まとめ

参考文献

コメント

コメントを投稿

色々な型の値をいくつでも入れられる型安全な“HList”を実装する

アイディア

HListの定義

hnil

headとtail

append

実装の方針

第一引数のHListが型HNilの場合

第一引数のHListが型Aの場合に成り立つと仮定して、第一引数のHListの型がX :*: Aの場合を考える

型クラスとアドホック多相

実装

nth

実装の方針と問題点

自然数の実装

実装

実装

まとめ

参考文献

コメント

コメントを投稿

`HList`の定義

`hnil`

`head`と`tail`

`append`

第一引数のHListが型`HNil`の場合

第一引数のHListが型`A`の場合に成り立つと仮定して、第一引数のHListの型が`X :*: A`の場合を考える

`nth`