以下の内容はhttps://blog.3qe.us/entry/2022/05/29/224715より取得しました。

Shapelessの勉強（その3）

技術 scala shapeless

追記: Shapeless入門を記事にまとめました

www.3qe.us

今回はChapter 4を扱う。 Working with types and implicits と題したこの章では、依存型と呼ばれる便利な概念を導入し、これまで説明してきたHList等の概念にさらに柔軟性を与える。

前回はこれ。

blog.3qe.us

Chapter 4は、ちょっとしんどかった。

用語についての説明

定訳があるわけではないが頻出する用語について、ここで事前に説明をしておこうと思う。

  • summon
    • implicit searchを使って、ある型クラスのインスタンス（より厳密には、指定した値に対応する値）を自動的に取り出す（召喚する）こと。scala 3では、summonというそのものの名前の関数として登場する（ふるまいはだいたいimplicitlyと同じ）
  • summoner
    • summonを便利に行う手段になるような関数、オブジェクトのこと。

依存型

Shapelessは、その処理のうち色々な箇所で依存型を使っている。

たとえば前のchapter 3でも、GenericはADTsをHListに変換したが、toやfromを呼ぶときに返り値の型をわざわざ書かなくても良かった。

trait Generic[A] {
    type Repr
    def to(value: A): Repr
    def from(value: Repr): A
}

def getRepr[A](value: A)
  (implicit gen: Generic[A])/* : ??? */
  = gen.to(value)
case class Vec(x: Int, y: Int)

getRepr(Vec(10, 20)) // => 10 :: 20 :: HNil

ここで、返り値の型を明示していないことに注目してほしい。上掲した例の中でgetReprの返り値の型は、implicit resolutionによって解決されるGeneric[A]のインスタンスが内部的に持つRepr型に依存していることがわかるはずだ。

この過程は、型が（引数として渡ってくる）値に依存して決まるのでdependent typing（依存型付け？定訳不明。）と呼ばれる。dependent typingが不可能な場合、利用者側でGeneric[A]がAを変換した後の型を明示しなければならず、とても不便である。

依存型の有無による利便性の対比

不便な状況を意図的に生み出すことで理解しよう。試しに、trait内部にtype Reprとして型を置くのではなく、型パラメータとしてみる。何でもDoubleに変換してくれる型クラスDoublifyについて考えてみよう:

trait Doublify[A] {
    type Repr
    def to(value: A): Repr
}

これを、依存型を使って実装してみた後、依存型を使わずに実装してみる。

依存型を使った実装

object Doublify {
    type Aux[A, R] = Doublify[A] { type Repr = R }
    def apply[A](implicit d: Doublify[A]): Aux[A, d.Repr] = d
}

implicit val intDoublify: Doublify[Int] = new Doublify[Int] {
    type Repr = Double
    def to(value: Int): Double = value
}

val int = 100
Doublify[Int].to(int) // => 100.0

依存型を使った実装はスマートだ。とくに何もしなくても、Doublify[Int].to()と書くだけでよい。

依存型を使わない実装

依存型を使わずに型パラメータを使った型クラスDoublify2は以下のようになる:

// 返り値の型を型パラメータで指定する
trait Doublify2[A, Repr] {
    def to(value: A): Repr
}

object Doublify2 {
    // implicit 指定でReprを省略できないのでsummonerにもReprが露出する
    def apply[A, Repr](implicit d: Doublify2[A, Repr]): Doublify2[A, Repr] = d
}

implicit val intDoublify2: Doublify2[Int, Double] = new Doublify2[Int, Double] {
    def to(value: Int): Double = value
}

// 返り値の型が露出し、省略できなくなった。
// Doubleにする位なら簡単だが、より複雑なADTsを扱うような場合にはきわめて不便なことになる。
Doublify2[Int, Double].to(int) // => 100.0

返り値の型をどこでも明示しなければならず、Doublify2はきわめて使いづらいものになってしまった。

いったん依存型を使ったDoublifyに立ち返ろう:

trait Doublify[A] {
    type Repr
    def to(value: A): Repr
}

Aが入力として、Reprが出力用の型として使われている。Aは利用する側が指定しなければならない一方、ReprはDoublifyを実装するインスタンスが決めてよい。 型パラメータはなんらかの入力を、型メンバーはなんらかの出力を示す型として有用である、という示唆が読み取れる。

依存型を用いた関数について考える

さて、Genericのほかにも、Shapelessはさまざまな箇所で依存型を使用している。ここではLast型クラスを題材に、依存型を用いた関数について考えてみよう。

Last型クラス

Lastが実装すべき唯一の操作は、HListの末尾の要素を返すことだけだ:

package shapeless.ops.hlist

trait Last[L <: HList] {
    type Out
    def apply(in: L): Out
}

ただし、引数の型LはHListのサブタイプであることが要求される。

この場合、さきほどの入出力のメタファを用いると、L <: HListが入力で、Outが出力だ。このことについてよく理解するために、さらに先へと進もう:

import shapeless.{HList, ::, HNil}
import shapeless.ops.hlist.Last

// summon
val last1 = Last[String :: Int :: HNil]
last1 // => shapeless.ops.hlist.Last[String :: Int :: shapeless.HNil]{type Out = Int}

// apply()
last1("foo" :: 42 :: HNil) // => 42

まずLastのコンパニオンオブジェクトに実装されているapply()によってLast[String :: Int :: HNil]のインスタンスがsummonされた。このimplicit resolutionが完了した時点でOut型がIntに確定し、last1.applyの返り値の型はIntで確定する。

しかも、型レベルでの計算がまず行われることから、無効な型に対してはLastのインスタンスを生成できなくなっており、実行時エラーが起こる余地を無くしている。

  • Last[HNil]のインスタンスはないので、これを使った計算はコンパイルできない
  • 型が合わないHListをlast1.applyに渡すこともできない

練習: Second型クラス

練習として、オリジナルのSecond型クラスを実装してみよう。可能な操作は、HListの2番目の値を取り出すことだけだ:

import shapeless.{HList, ::, HNil}

// available operation is just only "apply"
trait Second[L <: HList] {
    type Out
    def apply(l: L): Out
}

// summoner
object Second {
    // Outを型パラメータとして露出させ、implicit searchの手助けにする
    type Aux[L <: HList, O] = Second[L] { type Out = O }
    def apply[L <: HList](implicit inst: Second[L]): Aux[L, inst.Out] = inst

    // ところで ~> と中置記法的にも書けるな～
    type ~>[L <: HList, O] = Second[L] { type Out = O }
    def apply2[L <: HList](implicit inst: Second[L]): L ~> inst.Out = inst
}

コラム: implicitly vs. the

（割愛）

Secondつづき

さて、Secondのインスタンスは唯一定まる:

implicit def hlistSecond[A, B, Rest <: HList]: Second.Aux[A :: B :: Rest, B] =
new Second[A :: B :: Rest] {
    type Out = B
    def apply(value: A :: B :: Rest): B = value.tail.head
}

せやねという感じで、あまり難しくない。

とりあえず、当面必要な依存型についての知識は獲得できた。

依存型の連鎖

依存型を用いた型クラスのことを勉強したので、今度は依存型が連鎖するパターンについて学ぼう（おさらい: 依存型は型から型への計算手段を提供する）。

依存型が型から型への計算を提供するということは、これを連鎖させることも可能なはずだ。そこで、依存型を使った型クラスGenericとLastとを組み合わせて、case classの最後の要素を取り出す関数を作ってみよう:

  • Generic[A]は、AをHListに変換する
  • Last[HList]は、HListをその最後の要素の型に変換する
    • ヒント: HListであってもHNilである場合は動いてはいけない

よく知っているように（前章を見よう）、隣り合う引数の内部の型を参照することはできない:

def lastField[A](input: A):(
  implicit
  gen: Generic[A],
  last: Last[gen.Repr] // ダメ〜
): last.Out = ...

Auxによる持ち上げふたたび

そこで、おなじみのAuxを使って解決しよう:

import shapeless.{HList, ::, HNil, Generic}
import shapeless.ops.hlist.Last

def lastField[A, Repr <: HList](input: A)(
  implicit gen: Generic.Aux[A, Repr], // Reprを型パラメータに持ち上げる
  last: Last[Repr]
): last.Out = last.apply(gen.to(input))

case class Vec(x: Int, y: Int)

lastField(Vec(10, 20)) // => 20

いつものイディオムだ。

  • 中間的な型は、いつでも型パラメータに切り出そう
  • 関数の結果となる型は型パラメータに切り出すと使いにくいので切り出さない
    • これは自動的に推論できるから、切り出す必要はない

Generic.AuxがReprを型パラメータとして露出させてくれているおかげで、2つめのimplicit引数はLast[Repr]と書けるようになった。

Repr自体は関数の中では使われておらず、2つの型クラスを結び付けるための自由変数にすぎない。こうした型間の自由変数は型パラメータとして持ち上げることで、正しくコンパイラが推論できるようにしているのだ。

自由変数を型パラメータに持ち上げない場合

ところで自由変数を型パラメータに持ち上げなかったらどうなるだろう？

def getWrappedValue[A, H](input: A)
(implicit gen: Generic.Aux[A, H :: HNil]): H = gen.to(input).head

case class Box[A](x: A)

getWrappedValue(Box(100))

ここでは、genの型にGenericとHListとが入れ子になっている。 なんとこれではgetWrappedValue自体のコンパイルには成功するのに、呼び出す側ではimplicit resolutionに失敗してコンパイルが通らない！（原文では、陰湿 insidious ！と表現されている。わかる）

その理由は、依存型を使った変換は1つずつ行われるため、Reprに対応する型を見付けるのと同時にその長さを判定することができないためだ。このトラブルは、implicit resolutionを段階に分けて行うことで動くようになる。コンパイラの気持ちになろう:

  • まずAに対応するReprを提供してくれるようなGenericを探す
  • 次に、Repr型をHead :: HNilの形にマッチさせられるかどうかを検証する

これは、implicit制約を分割することで対応できる:

def getWrappedValue[A, Repr <: HList, Head, Tail <: HList](input: A)
    (implicit gen: Generic.Aux[A, Repr], ev: (Head :: Tail) =:= Repr): Head = gen.to(input).head

さらに、ReprがHead :: Tail の形に分解できることを示すためにIsHCons型クラスを導入する（headメソッドはIsHConsに定義されていて、evの定義では足りないのだ）:

def getWrappedValue[A, Repr <: HList, Head](input: A)
    (implicit gen: Generic.Aux[A, Repr], ev: IsHCons.Aux[Repr, Head, HNil]): Head = gen.to(input).head

これでgetWrappedValueが動作するようになった。ちなみにIsHCons.Auxを使っているのはHeadという名前を割り当てるためだけなので、Auxを使わなくてもgetWrappedValueを定義できる:

def getWrappedValue2[A, Repr <: HList](input: A)
    (implicit gen: Generic.Aux[A, Repr], ev: IsHCons[Repr]): ev.H = gen.to(input).head

まとめ

  • Shapelessを使ったコーディングにおいて、しばしば返り値の型はコード中の値の型によって決定されることがある。そのような関係を依存型付けと呼ぶ。
  • この問題はimplicit searchを使い、コンパイラに型を探させることでうまく表現できる。
  • 依存型を使って型を導出する場合、しばしば数段階に分けて計算する必要がある。このときは次のようなルールに従う必要があるだろう。
    • 中間的な型（文中では自由変数と表現している）を型パラメータとして切り出すこと。結果として使わなくとも、型のユニフィケーションで必要となるため
    • コンパイラは定義した順にimplicit searchを行うので、必要な順序でimplicit引数を定義する必要がある コンパイラは一度に1つの制約しか解決できないので、1回のimplicit制約で制約を加えすぎてはいけない
    • すべての型パラメータに加えて、他の場所で使われうる型メンバを（Auxで持ち上げて）指定することで、返り値の型が明白になるようにしなければならない
      • たいてい型メンバも重要なので、Auxパターンを用いて型パラメータに持ち上げることで、型が消えないようにする
      • 型パラメータとして明示されなかったものは、それ以降のimplicit searchで使えない
      • Auxパターンがコードを読みやすくする: Auxがあると、だいたい依存型だなという検討がつきそう
  • 依存型を連鎖（e.g. GenericとLastでやったように）させて使う便利な操作があるとき、たいていこれを1つの型クラスとして統合できる。Shapelessにおいて、これは数学用語からの借用でLemma（補題）パターンと呼んでいる。これはSection 6.2で扱う。

疑問点

  • dependent typingの定訳が分からなかった。
    • dependent typeは依存型なので、依存型付けと訳出するのが良いのかな？

とにかく、次回はChapter 5だ！！



以上の内容はhttps://blog.3qe.us/entry/2022/05/29/224715より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14