再びコードはこちら( ⁰⊖⁰)
GitHub - matsu-chara/HListQuickSort: コンパイル時クイックソート

HList

さて、前回までで自然数の比較ができるようになりました。今回はHListをある自然数より大きいHListと、それ以下のHListへの分割を行いたいと思います。

今回使用するHListの実装は、この辺です。

head, tail, append, nthが実装されています。これらは色々な型の値をいくつでも入れられる型安全な“HList”を実装する - Qiitaに解説があるので、必要に応じて参照してみてください。( ⁰⊖⁰) 基本的な使い方はListと同じです。

HListの分割

では、ある基準値よりもLess Than Equalなリストを元のリストからフィルターする関数を作っていきましょう。

全体のコードはこちら HListCompare.scala

Less Than Equals編

trait LTEqs[H <: HList, A <: Nat, Out <: HList]

まず、H, A, Outという型パラメータを受け取るtraitを用意します。ここで、Hはフィルターの対象となるHList、Aはフィルター基準値です。 Outにはフィルター後の結果が入るようにしたいわけですが、これを実現するためにさらに実装を進めていきます。

object LTEqs {

  implicit def hNilLTEqs[A <: Nat] = new LTEqs[HNil, A, HNil] {}

  implicit def hlistLTEqsLower[A <: Nat, H <: Nat, T <: HList, LtsOut <: HList](implicit lts: LTEqs[T, A, LtsOut], l: H <= A) =
    new LTEqs[H :: T, A, H :: LtsOut] {}

  implicit def hlistLTEqsGreater[A <: Nat, H <: Nat, T <: HList, LtsOut <: HList](implicit lts: LTEqs[T, A, LtsOut], l: A < H) =
    new LTEqs[H :: T, A, LtsOut] {}

  def apply[H <: HList, A <: Nat, LtsOut <: HList](implicit lts: LTEqs[H, A, LtsOut]) = lts
}

全体としては、headがHNilのとき、A以下のとき、Aより大きい時の３つに分けて処理を行っています。

まずはHNilのときから。

  // if true then: LtEqs(HNil, A) should_be HNil
  implicit def hNilLTEqs[A <: Nat] = new LTEqs[HNil, A, HNil] {}

前回書いた、implicit parameterを取るimplicit defが出てきますので、それに沿ったコメントを記述してあります。ここでは、A∈NatとHNilをLtEqsの入力にするとHNilがかえってくることを表現しています。

次は、HListのheadがA以下の場合です。

  // if (LtEqsLower(T, A) is defined_and_result_is lts) and (H <= A) then:
  //   LtEqsLower(H :: T, A) should_be H :: lts.Out
  implicit def hlistLTEqsLower[A <: Nat, H <: Nat, T <: HList, LtsOut <: HList](implicit lts: LTEqs[T, A, LtsOut], l: H <= A) =
    new LTEqs[H :: T, A, H :: LtsOut] {}

型パラメータのAは基準値、H, Tは対象HListのhead, tailです。
　ここは前提が長くなってしまいましたが、LtEqsLower(T, A)（つまりHeadを除いた部分がフィルター可能)でH <= Aであることが要求されています。対象のHListをH :: Tとして分解していくといずれ、先ほど定義したHNilのパターンに引っかかるのでLtEqsLower(T, A)は定義されていると考えてよさそうです。
　結論は[H :: T, A, H :: LtsOut]となっています。LtsOutはimplicit parameterとして渡ってきたLTEqs[T, A, LtsOut] で使われていたものです。
　まとめると、HeadがA以下なら末尾部分をフィルターした結果の型にHeadをくっつけたものが結果の型だよ、と言っていることになります。

これを理解してしまえば次のパターンは簡単です。

  // if (LtEqsGreater(T, A) is defined_and_result_is lts) and (A < H) then:
  //   LtEqsLower(H :: T) should_be lts.Out
  implicit def hlistLTEqsGreater[A <: Nat, H <: Nat, T <: HList, LtsOut <: HList](implicit lts: LTEqs[T, A, LtsOut], l: A < H) =
    new LTEqs[H :: T, A, LtsOut] {}

ここではHがAより大きかったら、Headを結果に加えない(無視する)で、末尾部分をフィルターした結果の型をそのまま返しています。

あとは、LTEqsに適当なHList,とAを入れられるようにapplyを定義するだけです。

  def apply[H <: HList, A <: Nat, LtsOut <: HList](implicit lts: LTEqs[H, A, LtsOut]) = lts

できました！ちょっと試してみましょう。前回のと合わせると膨大になってしまうので、githubからcloneしてsbt consoleで読み込ませるといいかもしれません。今までの実装も含め、コンパイルしてimport可能にしてくれます。

$ git clone https://github.com/matsu-chara/HListQuickSort
$ cd HListQuickSort
$ sbt console

scala> import HList._
import HList._

scala> import Nat.Nat._
import Nat.Nat._

scala> LTEqs[_1 :: _0 :: _3 :: _2 :: HNil, _2, _1 :: _0 :: _2 :: HNil]
res2: HList.LTEqs[HList.::[Nat.Nat._1,HList.::[Nat.Nat._0,HList.::[Nat.Nat._3,HList.::[Nat.Nat._2,HList.HNil]]]],Nat.Nat._2,HList.::[Nat.Nat._1,HList.::[Nat.Nat._0,HList.::[Nat.Nat._2,HList.HNil]]]] = HList.LTEqs$$anon$2@7999e9e5

できました！ _1 :: _0 :: _3 :: _2 :: HNilのうち、_2以下のものHListは,_1 :: _0 :: _2 :: HNilですね。

しかし、これ、結果の型を明示的に指定しないと動きません(◞‸◟)
　この辺を解決するトリックは後ほど紹介します。元記事では、最初から使っているのですが、説明のために不便にしてみました。

Greater Than 編

LTEqsが出来たので、Greater Thanも作っていきます。

trait GTs[H <: HList, A <: Nat, Out <: HList]

object GTs {
  implicit def hnilGTEqs[A <: Nat] = new GTs[HNil, A, HNil] {}

  implicit def hlistGTEqsLower[A <: Nat, H <: Nat, T <: HList, GtsOut <: HList](implicit gts: GTs[T, A, GtsOut], l: A < H) =
    new GTs[H :: T, A, H :: GtsOut] {}

  implicit def hlistGTEqsGreater[A <: Nat, H <: Nat, T <: HList, GtsOut <: HList](implicit gts: GTs[T, A, GtsOut], l: H <= A) =
    new GTs[H :: T, A, GtsOut] {}

  def apply[H <: HList, A <: Nat, GtsOut <: HList](implicit gts: GTs[H, A, GtsOut]) = gts
}

内容はおなじなので説明は省略します！疲れたからじゃないよ( ⁰⊖⁰)

QuickSort

ついに下準備が揃いました。クイックソートを実装しましょう。

trait HListQuickSort[L <: HList] {
  type Out <: HList
}

LはソートしたいHListだからいいとして、今回はtraitの中で抽象型が宣言されています。さっきまでのフィルターと同じ方法だったら

trait HListQuickSort[L <: HList, Out <: HList]

としていたところです。
このようにしてしまうと、いざクイックソートを行う際に、結果の型を自分で書かなければいけないんでした。それを回避するために抽象型を利用します。（どう使うかはこの後で説明します。）

次にソートを行うコードです。まず全体から。

object HListQuickSort {
  type Aux[L <: HList, Out0 <: HList] = HListQuickSort[L] {type Out = Out0}

  implicit def hnilSorted: Aux[HNil, HNil] = new HListQuickSort[HNil] {
    type Out = HNil
  }

  implicit def hlistSorted[H <: Nat, T <: HList, lsOut <: HList,
  gsOut <: HList, smOut <: HList, slOut <: HList, prepOut <: HList]
  (implicit
   ls: LTEqs[T, H, lsOut],
   gs: GTs[T, H, gsOut],
   sortedSmaller: HListQuickSort.Aux[lsOut, smOut],
   sortedLarger: HListQuickSort.Aux[gsOut, slOut],
   preps: HAppend[smOut, H :: slOut, prepOut]) =
    new HListQuickSort[H :: T] {
      type Out = prepOut
    }

  def apply[L <: HList](implicit sorted: HListQuickSort[L]): Aux[L, sorted.Out] = sorted
}

先頭から見ていきましょう。まず、

  type Aux[L <: HList, Out0 <: HList] = HListQuickSort[L] {type Out = Out0}

の部分では補助的な型を用意しています。先ほど抽象型に移動させたOutをそのまま型パラメータに持ってきた形です。なおAuxはauxiliary（補助の〜）という単語の略みたいです。（多分）

次にHNilのソートを定義します。

  implicit def hnilSorted: Aux[HNil, HNil] = new HListQuickSort[HNil] {
    type Out = HNil
  }

HNilをソートしたら結果は当然HNilです。またtype Out = HNilとOutの実際の型を指定しています。

続いて、HNil以外のソートです。

  implicit def hlistSorted[H <: Nat, T <: HList, lsOut <: HList,
  gsOut <: HList, smOut <: HList, slOut <: HList, prepOut <: HList]
  (implicit
   ls: LTEqs[T, H, lsOut],
   gs: GTs[T, H, gsOut],
   sortedSmaller: HListQuickSort.Aux[lsOut, smOut],
   sortedLarger: HListQuickSort.Aux[gsOut, slOut],
   preps: HAppend[smOut, H :: slOut, prepOut]) =
    new HListQuickSort[H :: T] {
      type Out = prepOut
    }

implicitがとても長いですが、型パラメータから落ち着いて読んでいきます。

[H <: Nat, T <: HList, lsOut <: HList,  gsOut <: HList, smOut <: HList, slOut <: HList, prepOut <: HList]

まずH, TはソートしたHListのhead, tailです。またlsOut, gsOutはフィルターあとの結果が入る型になります。
　smOut, slOutはフィルター後のそれぞれのHListをソートした結果です。（再帰的に分割されていくので、いずれHNilのパターンにひっかかります。)
　そしてprepOutは各々のソート後のHListをappendでマージした結果です。

続いてimplicit parameterと返り値です。

   ls: LTEqs[T, H, lsOut],
   gs: GTs[T, H, gsOut],
   sortedSmaller: HListQuickSort.Aux[lsOut, smOut],
   sortedLarger: HListQuickSort.Aux[gsOut, slOut],
   preps: HAppend[smOut, H :: slOut, prepOut]) =

LTEqsの結果が存在して、それをlsOutとして、さらにGTsの結果が存在して、それをgsOutとしてさらにHListQuickSort(lsOut)の結果が存在して、それをsmOutとして、さらにHListQuickSort(gsOut)の結果が存在して、それをgsOutとして、さらに２つのリストのHAppendの結果がprepOutだったときに、 hlistSortedの結果は

 new HListQuickSort[H :: T] {
      type Out = prepOut
    }

となる。ということが書いてあります。 implicitの中でプログラミングするのやめて！と言いたくなりますね(∩´﹏`∩)

かなり無理矢理ですが、入力のHListからフィルターした結果の型はもちろん推論できますし、それらを分割していってHNilになったあとに、appendされたあとの型もきちんと推論できるので、ソート結果も結果的に推論できちゃうんです。すごい( ⁰⊖⁰)

あとは、いつものようにapplyを定義します。

  def apply[L <: HList](implicit sorted: HListQuickSort[L]): Aux[L, sorted.Out] = sorted

Auxの型パラメータにsorted.Outを使うことで、apply時に明示的に結果の型を与えなくて済むようになっています。結果の型はapply時には指定しませんが、Auxの中できちんと推論されて返ってくる型の中に含まれるようになっています。

実際に試してみましょう。

scala> HListQuickSort[_1 :: _0 :: _3 :: _2 :: HNil]
res3: HList.HListQuickSort[HList.::[Nat.Succ[Nat.Zero],HList.::[Nat.Zero,HList.::[Nat.Succ[Nat.Succ[Nat.Succ[Nat.Zero]]],HList.::[Nat.Succ[Nat.Succ[Nat.Zero]],HList.HNil]]]]]{type Out = HList.::[Nat.Zero,HList.::[Nat.Succ[Nat.Zero],HList.::[Nat.Succ[Nat.Succ[Nat.Zero]],HList.::[Nat.Succ[Nat.Succ[Nat.Succ[Nat.Zero]]],HList.HNil]]]]} = HList.HListQuickSort$$anon$2@2b789b83

_1 :: _0 :: _3 :: _2 :: HNil をソートすると

type Out = HList.::[Nat.Zero,HList.::[Nat.Succ[Nat.Zero],HList.::[Nat.Succ[Nat.Succ[Nat.Zero]],HList.::[Nat.Succ[Nat.Succ[Nat.Succ[Nat.Zero]]],HList.HNil]]]]

となっていて、これは_0 :: _1 :: _2 :: _3 :: HNil のことですから・・・できました！٩( ˘ω˘ )و

ということでクイックソートが無事実装できました！ピボットの選択？先頭を選べばいいんだよ！！！！

type Out & Aux のようなパターンはshapelessでも実際に利用されている(例えば、 https://github.com/milessabin/shapeless/blob/675a35fa383b27b4a69a5003bc7f1e65544a602e/core/src/main/scala/shapeless/ops/nat.scala#L26-L34)ので、このようにする動機を理解しておくとコードを読む際に助かると思います。

またapplyを使わないで、別に関数を定義してしまっても、結果の型を書くことを回避できます。（今回はshapelessっぽい方式にしてみました。）はじめから全部にAuxを使用するとどういった実装になるかは元記事を参照してください。

まとめ

型レベルでやろうとすると消耗するのでソートは実行時で良い。

だいたいよくわからないブログ

ScalaでHListを使ったコンパイル時クイックソート〜 (後編)

目次

HList

HListの分割

Less Than Equals編

Greater Than 編

QuickSort

まとめ