多相な関数の定義から学ぶ、型クラスデザインパターン

201607.md

#多相な関数の定義から学ぶ、型クラスデザインパターン

　　　　　　　　　twitter: @OE_uia github: taisukeoe

##多相な関数

• 複数の異なる型に対して適用可能な関数
• どの型に対して定義されているか、静的に決定できる(定義されてない型の値を渡すとコンパイルエラーになる)

 Int => Int
 String => String
 Double => String
 Seq[Int] => Seq[Int]

##多相な関数のメリット

• 複数の異なる型に対する操作を一般化したまま変換,合成などを行える
• DSLの構築
• Heterogeneousなコレクションを簡便に操作できる

#一番単純な出発点としての、メソッドの引数オーバーロード

def overlap(i:Int):Int = i*i

def overlap(s:String):String = s.foldLeft(""){(l,r) => l + r + r}

overlap(2)
//4

overlap("hoge")
//hhooggee

#引数オーバーロードのデメリット

##(多相のままでは)eta-expansionできない

これにより関数合成、変換、など様々な操作ができなくなる

scala> overlap _
<console>:13: error: ambiguous reference to overloaded definition,
both method overlap of type (s: String)String
and  method overlap of type (i: Int)Int
match expected type ?
  overlap _
  ^

(注:@kmizuさんにご指摘いただき、一部修正しました)

多相を諦めればeta expansionできる

scala> overlap _: (String => String)
res1: String => String = <function1>

##型消去による衝突

def overlap(seq:Seq[Int]):Seq[Int] = ???

def overlap(seq:Seq[String]):Seq[String] = ???

<console>:20: error: double definition:
def overlap(seq: Seq[Int]): Seq[Int] at line 18 and
def overlap(seq: Seq[String]): Seq[String] at line 20
have same type after erasure: (seq: Seq)Seq
     def overlap(seq:Seq[String]):Seq[String] = ???
	       ^

#単純な型クラス Overlappable

• 型クラスは、共通の振る舞いを複数の既存の型に追加するための手法
• 共通の振る舞いのインターフェースを表す型を「型クラス」
• 共通の振る舞いを追加された型が、実際の振る舞いを定義したインスタンスを「型クラスインスタンス」
• Scalaの場合、implicit(暗黙)というキーワードにより型クラスインスタンスを参照する

ここでは、overlap可能という共通の振る舞いを示す型クラスOverlappableと、 IntとStringに対しOverlappableの型クラスインスタンスを定義している。

def overlap[A,B](a:A)(implicit O:Overlappable[A,B]):B = O overlap a

trait Overlappable[-A,+B]{
  def overlap(a:A):B
}

//型クラスのコンパニオンオブジェクトに型クラスインスタンスを定義すると、implicitの探索対象に含まれる
object Overlappable{
	  implicit lazy val intOverlap:Overlappable[Int,Int] = new Overlappable[Int,Int]{
		     def overlap(a:Int):Int = a * a
    }
	  implicit lazy val stringOverlap:Overlappable[String,String] = new Overlappable[String,String]{
   	     def overlap(s:String):String = s.foldLeft(""){(l,r) => l + r + r}
	  }
}

overlap(2)
overlap("hoge")

##型消去による衝突の回避

暗黙の解決は型消去の前のコンパイルフェイズに行われるため、衝突を回避できる。

implicit lazy val seqIntOverlap:Overlappable[Seq[Int],Seq[Int]] =
   	new Overlappable[Seq[Int],Seq[Int]]{
		   def overlap(a:Seq[Int]):Seq[Int] = a map Overlappable.intOverlap.overlap
	  }
implicit lazy val seqStringOverlap:Overlappable[Seq[String],Seq[String]] =
		new Overlappable[Seq[String],Seq[String]]{
		   def overlap(s:Seq[String]):Seq[String] = s map Overlappable.stringOverlap.overlap
		}

scala> overlap(Seq(2))
res4: Seq[Int] = List(4)

scala> overlap(Seq("hoge"))
res5: Seq[String] = List(hhooggee)

##eta-expansionは依然できない

型パラメーターがNothing型に推論される

scala> overlap _
<console>:13: error: could not find implicit value for parameter O: Overlappable[Nothing,Nothing]
     overlap _
     ^

#Magnet Pattern

• sprayチームが名づけたデザインパターン 参考:spray | Blog » The Magnet Pattern

• 基本的な考え方は先のOverlappable型クラスと同じ

• ただしMagnet Patternでは、暗黙の型変換を利用して暗黙のパラメータリストを除いている

trait OverlapMagnet{
  type Result
  def value:Result
}

object OverlapMagnet{
	 implicit class IntOverlapMagnet(i:Int) extends OverlapMagnet{
     type Result = Int
	   def value = i * i
	 }
	 implicit class StringOverlapMagnet(s:String) extends OverlapMagnet{
	   type Result = String
	   def value = s.foldLeft(""){(l,r) => l + r + r}
	 }
}

def overlap(magnet:OverlapMagnet):magnet.Result = magnet.value

##型消去による衝突の回避

暗黙の解決は型消去の前のコンパイルフェイズに行われるため、衝突を回避できる。

(ほぼ例がOverlappableと一緒なので省略)

##eta-expansion Dependent Method Typeがあるとeta-expansionできない

scala> overlap _

<console>:21: error: method with dependent type (magnet: OverlapMagnet)magnet.Result cannot be converted to function value
   overlap _
   ^

ただし、オーバーロードされているメソッドの戻り値の型が常に同じであれば、eta-expansion可能

scala> def overlapAndToString(magnet:OverlapMagnet):String = magnet.value.toString
overlapAndToString: (magnet: OverlapMagnet)String

scala> overlapAndToString _
res10: OverlapMagnet => String = <function1>

##(余談)暗黙の引数リストを除くと何が嬉しいのか？

Result型がapplyメソッドを持っていると、impicitな引数リストと衝突する。 applyを多用するDSLには不向き。

def overlap[A,B](a:A)(implicit O:Overlappable[A,B]):B = O overlap a

trait Overlappable[-A,+B]{
  def overlap(a:A):B
}
class IntResult(i:Int){
  def apply():Int = i
}
object Overlappable{
  implicit lazy val intOverlap:Overlappable[Int,IntResult] = new Overlappable[Int,IntResult]{
     def overlap(a:Int):IntResult = new IntResult(a * a)
  }
}

scala> overlap(2)()
<console>:13: error: not enough arguments for method overlap: (implicit O: Overlappable[Int,B])B.
Unspecified value parameter O.
       overlap(2)()
                 ^

##Poly

• 型でインデックスされた関数のリスト
  • Poly自身は型クラスではなく、内部クラスであるPoly#Caseが型クラス。多重定義したい個々の関数に相当する.
  • Poly#applyを通じて関数を適用する
  • Shapelessで実装されている

trait Poly{
  final def at[A] = new {
     def apply[B](f:A => B):Case[A,B] = new Case[A,B]{
      def apply(a:A) = f(a)
     }
  }
  sealed trait Case[A,B]{ def apply(a:A):B }

  def apply[A,B](a:A)(implicit C:this.Case[A,B]):B = C(a)
}

object overlap extends Poly{
    implicit val intOv = at[Int]{_ * 2}
    implicit val stringOv = at[String]{_.foldLeft(""){(l,r) => l + r + r}}
}

overlap(2)
overlap("hoge")

※ Shapelessの実装ではなく、単純化した @djspiewak さんの Roll your own Shapelessの例を引用

###Poly.applyにおける暗黙の値の探索hack

trait Poly{
 //...
 def apply[A,B](a:A)(implicit C:this.Case[A,B]):B = C(a)
 //...
}

• クラスのコンパニオンオブジェクトのメンバーに型クラスインスタンスを定義すると、そのクラスにおけるimplicitの探索対象に含まれる

• オブジェクトのクラスの、コンパニオンオブジェクトはそのオブジェクト自身(!)

• Polyを継承したオブジェクトを定義すると、そのオブジェクト(overlap)のメンバもimpilicitの探索対象に含まれる

• 具体的には object overlap がPolyを継承すると this.Case = overlap.type.Case

• overlap.type.Case 型の暗黙のパラメーターの探索対象には、 overlap.typeのコンパニオンオブジェクトが含まれる

• overlap.type のコンパニオンオブジェクトは、object overlapである

• ゆえにobject overlapのメンバーとして定義した暗黙の値Case[A,B]は、Poly#applyの探索対象となる。

##eta expansion overlapはobjectなので当然eta expansionできない。

overap.applyも型パラメータがNothingに推論されるため、eta expansionできない。

scala> overlap _
<console>:14: error: _ must follow method; cannot follow overlap.type
     overlap _
		 ^

scala> overlap.apply _
<console>:14: error: could not find implicit value for parameter C: overlap.Case[Nothing,Nothing]
     overlap.apply _
		         ^

##eta expansionできないけど…？

本家ShapelessのPolyは合成可能

以下抜粋

trait Poly extends PolyApply with Serializable {
	  import poly._
    def compose(f: Poly) = new Compose[this.type, f.type](this, f)
    def andThen(f: Poly) = new Compose[f.type, this.type](f, this)
		//...
}

class Compose[F, G](f : F, g : G) extends Poly
object Compose {
		implicit def composeCase[C, F <: Poly, G <: Poly, T, U, V]
				(implicit unpack: Unpack2[C, Compose, F, G], cG : Case1.Aux[G, T, U], cF : Case1.Aux[F, U, V]) = new Case[C, T :: HNil] {
		 	  	type Result = V
		  		val value = (t : T :: HNil) => cF(cG.value(t))
		}
}

//以下自動生成されたコード
type Case1[Fn, A] = Case[Fn, A :: HNil]
object Case1 {
	type Aux[Fn, A, Result0] = Case[Fn, A :: HNil] { type Result = Result0 }

	def apply[Fn, A, Result0](fn : (A) => Result0): Aux[Fn, A, Result0] =
		new Case[Fn, A :: HNil] {
			 type Result = Result0
	  	 val value = (l : A :: HNil) => l match { case a :: HNil => fn(a) }
	  }
}

trait Unpack2[-P, F[_, _], T, U]

object Unpack2 {
	  implicit def unpack2[F[_, _], T, U]: Unpack2[F[T, U], F, T, U] = new Unpack2[F[T, U], F, T, U] {}
}

#Auxパターン

• 補助、という意味の「Auxiliary」から来ているパターン
• 型メンバーを型パラメーターにマッピングする
• Shapelessで重度に使われている

trait Overlap[A]{
	 type Result
	 def value(a:A):Result
}
object Overlap{
	 type Aux[A0,B0] = Overlap[A0]{type Result = B0} //型メンバーを型パラメータにマップする型エイリアス
	 implicit def intOverlap:Overlap.Aux[Int,Int] = new OverlapMagnet[Int]{
	   type Result = Int
	   def value(i:Int):Int = i + i
	 }
}

trait Semigroup[A]{
	 def append(a:A,a2:A):A
}
object Semigroup{
   implicit val int:Semigroup[Int] = new Semigroup[Int]{
     def append(a:Int,a2:Int):Int = a + a2
   }
}

##Scalaの同一引数リスト内の値について：

• 他方の型パラメーターには依存可能
• 他方の型メンバー（Dependent Method Type)には依存不可能(subsequent argument listのみ)

これを活用して、型クラスから他方の型クラスへ依存する（処理を渡す)ことができる。

def overlap[A,B](a:A)(implicit O:Overlap.Aux[A,B], S:Semigroup[B]):B = S.append(O.value(a),O.value(a))

#まとめ

• 型クラスを利用して多相な関数を様々な方法で実装できるが、それぞれ一長一短ある
• 型クラス + 型メンバー + Dependency Method Typeにより色々と面白いことができる
• Shapelessは型クラスのテクニックの宝庫なので、ソース読んでみるととても勉強になります。 (ただソースの自動生成やマクロなどにもあふれていて、読みやすいわけでは…)。