Scala 型パラメータによる関数の一般化例

Monoid, 型パラメータ, implicitを使った加算する関数の一般化

半年ぐらい前ですが、Scalaz の解説のプレゼンテーションである、 Scalaz Presentationというプレゼン動画を見ました。
Nick Partridgeさんというオーストラリアの方が、約1年半前に Scalazの説明をされているプレゼンなのですが
半年前に見たときは何をやっているのかさっぱり理解出来ませんでした。
今もう一度みると Scalaz に限らず型パラメータつかって関数を一般化するのに
段階をおって一般化されていくのですごくよくできたプレゼンの内容であるのがやっとわかるようになってきました。

まだよくわかってないところも多いのですが、
内容が良いと思ったのでビデオの Live Demoの部分のコードを書き出してみました。
どのようにScala の機能を使って Scalaz のライブラリが作られているかの説明なので、
この部分の実行には Scalaz のライブラリは必要ありません。

注意：この文書の中の説明は私なりの解釈で、ビデオの中の説明とは関係ありません。

書き出したのは最初の Live Demo の部分で sum メソッドの定義が
始めの

def sum(xs: List[Int]): Int ….

が一般化され

def sumM[_],A(...):A ...

となるまでの過程です。

型パラメータを使って一般化させる過程を考える上で非常に参考になりました。
Scalazのソースを追いかけるうえでも参考になります。

ビデオ見たこと無い方は見て損はないとおもいます。

間違いとかあればご指摘ください。

1. 初期状態

cord 1

    object Main {

        def sum(xs: List[Int]): Int = xs.foldLeft(0){ (a,b) => a + b}

        def p(a: Any) {println("###> " + a)}
        def main(args: Array[String]) {
            println
            p(sum(List(1,2,3,4)))
            println
        }
    }

ここで定義されている sum メソッドは普通の foldLeft を使ったListの中身を加算するごく普通の記述で、
sum の結果は初期値を0とし、そこにListの中身を加算していったものとなります。

2. Monoid を定義

このsumメソッドで使っている foldLeft には二つのパラメータが渡されています、

初期値の(0)

と

加算する関数部分の{(a,b) => a + b}

です。

ここでMonoidの登場です。
Monoid の説明はおこないませんが、
Monoid には単位元 mzero、加算 mappend をメソッドとして持っています。
上の foldLeft に渡している二つのパラメータにそれぞれが適合できそうです。

cord 2

    object IntMonoid {
      def mappend(a: Int, b: Int): Int = a + b
      def mzero: Int = 0
    }

    object Main {

        def sum(xs: List[Int]): Int = 
          xs.foldLeft(IntMonoid.mzero)(IntMonoid.mappend)

        def p(a: Any) {println("###> " + a)}
        def main(args: Array[String]) {
            println

            p(sum(List(1,2,3,4)))

            println
        }
    }

Monoid である IntMonoid オブジェクトを定義しています。
mappend は二つの値の加算、mzero には 0 を定義しています。

sum メソッドの定義はこのIntMonoid オプジェクトを使って初期値に Monoid の単位元である mzero、
実行する関数に mappend を渡すように変更しております。
初期値、と加算部分を IntMonoid で定義しているものを使用するようにできるようになりました。

3. Monoid の trait 定義

Monidは Int型に限った型ではないので、
Monoid型として定義します。Haskell の型クラスに相当するものでしょうか。
Scala の場合型クラスに相当するものは trait つかって定義することができます。

Monoid型として定義し、
抽象メソッドとして mappend, mzero を定義します。
2 で定義した IntMonoid はこの trait を extends し、使用します。

cord 3

    trait Monoid[A] {
      def mappend(a1: A, a2:A):A
      def mzero: A
    }

    object IntMonoid extends Monoid[Int]{
      def mappend(a: Int, b: Int): Int = a + b
      def mzero: Int = 0
    }

    object Main {

        def sum(xs: List[Int], m: Monoid[Int]): Int = 
          xs.foldLeft(m.mzero)(m.mappend)

        def p(a: Any) {println("###> " + a)}
        def main(args: Array[String]) {
            println

            p(sum(List(1,2,3,4),IntMonoid))

            println
        }
    }

sum メソッドの変更は第二引数をついかし、ここに Monoid[Int]型をとるようにします。
これで IntMonoid.mzero, IntMonoid.mappend と指定していた箇所を
引数として渡した Monoid[Int]型変数 m を使って、
m.mzero, m.mappend とすることができるようになりました。

実際の sum の呼び出し部分は
sum(List(1,2,3,4),IntMonoid)
のようになりました。

4. sum メソッドに型パラメータをつける

3 の sumメソッドの定義では List[Int] と型が指定されているので、
これを型パラメータを使用するように定義します。

def sum(xs:List[Int], m: Monoid[Int]): Int
が
def sum[T](xs: List[T], m: Monoid[T]): T

これで Int型という決まった型ではなく型パラメータをとる形に変わりました。

cord 4

trait Monoid[A] {
    def mappend(a1: A, a2:A):A
    def mzero: A
}

object IntMonoid extends Monoid[Int]{
    def mappend(a: Int, b: Int): Int = a + b
  def mzero: Int = 0
}

object Main {


    def sum[T](xs: List[T], m: Monoid[T]): T = 
      xs.foldLeft(m.mzero)(m.mappend) // 型パラメータを使用する

    def p(a: Any) {println("###> " + a)}
    def main(args: Array[String]) {
        println

        p(sum(List(1,2,3,4),IntMonoid)) //こちらは変化無し

        println
    }
}

sumメソッドの呼び出し部分には変化はありません。

5. 暗黙的パラメータを定義します

sumメソッドの呼び出し時ですが sum(List(1,2,3,4),IntMonoid) となり、
よく考えると当初の sumメソッドの呼び出し時よりも IntMonoidの指定する必要が増えています。
また sumメソッドの第二引数に渡している IntMonoid は今の時点ではいつも同じ値なので、
暗黙的パラメータ(implicit parameter)をつかってパラメータを指定しない場合、
暗黙的に IntMonoid が引き渡されるようにし、省略可能にします。

sum[T](xs:List[T], m: Monoid[T]):T

から

sum[T](xs:List[T])(implicit m: Monoid[T]):T

とカーリー化を行い、第二引数に implicit パラメータをつけます。

cord 5

trait Monoid[A] {
  def mappend(a1: A, a2:A):A
  def mzero: A
}

object IntMonoid extends Monoid[Int]{
  def mappend(a: Int, b: Int): Int = a + b
  def mzero: Int = 0
}

object Main {

  implicit val intMonoid = IntMonoid // implicit val を定義

    def sum[T](xs: List[T])(implicit m: Monoid[T]): T = 
      xs.foldLeft(m.mzero)(m.mappend) // implicit parameter化

    def p(a: Any) {println("###> " + a)}
    def main(args: Array[String]) {
        println

        p(sum(List(1,2,3,4))) // intMonoid の指定を省略可能になりました。

        println
    }
}

この上で implicit val intMonoid = IntMonoid と定義しているので、
第二パラメータを省略した場合にはこの intMonoid が暗黙的に引き渡されます。
このおかげで 4では p(sum(List(1,2,3,4),IntMonoid)) と指定した部分が
p(sum(List(1,2,3,4))) とIntMonoid の指定を省略可能となりました。
これで初期状態の sum メソッドの呼び出しと同じようにすることができるようになりました。

6. List[String]型も扱えるようにする

Listの中身は Int型だけではありません String型も扱えるようにしてみましょう。
ここでは object Monoid を定義し、その中に implicit object として IntMonoid, StringMonoid を定義します

object Monoid {
  // Int をとる Monoid
  implicit object IntMonodid extends Monoid[Int]{
        def mappend(a: Int, b: Int): Int = a + b
    def mzero: Int = 0
    }
  // String をとる Monoid
  implicit object StringMonoid extends Monoid[String] {
        def mappend(a: String, b: String): String = a + b
        def mzero: String = ""      
  }
}

こうすると

  implicit val intMonoid = IntMonoid

main に記述していたこちらの行も不要となり、sumメソッドが呼び出し時に引き渡されたListの中身によって、
Int型、String型の Monoidが暗黙的に割り当てられれます。

cord 6

trait Monoid[A] {
    def mappend(a1: A, a2:A):A
    def mzero: A
}

object Monoid {
  // Int をとる Monoid
  implicit object IntMonoid extends Monoid[Int]{
        def mappend(a: Int, b: Int): Int = a + b
    def mzero: Int = 0
    }
  // String をとる Monoid
  implicit object StringMonoid extends Monoid[String] {
        def mappend(a: String, b: String): String = a + b
        def mzero: String = ""      
  }
}

object Main {

    import Monoid._

    def sum[T](xs: List[T])(implicit m: Monoid[T]): T = 
      xs.foldLeft(m.mzero)(m.mappend)


    def p(a: Any) {println("###> " + a)}
    def main(args: Array[String]) {
        println

        p(sum(List(1,2,3,4)))
        p(sum(List("a","b","c","d")))

        println
    }
}

これで、今までは List[Int]型のリストしか扱えませんでしたが、
List[String]型のデータでも同じようにあつかえるようになりました。
sum(List("a","b","c","d")) を実行すると abcd という文字列が返ってきます。

7. 暗黙的パラメータにパラメータを渡してもいいよ

sum メソッド sum[T](xs: List[T])(implicit m: Monoid[T]): Tの
(implicit m: Monoid[T]) の部分は暗黙的パラメータですが、
パラメータはパラメータなのであえてパラメータを明示的に渡すことももちろん可能です。

この 7 では multMonoid という mappend で二つの引数値をかけ算するMonoid型の値を定義し、
sum(List(1,2,3,4))(multMonoid) のように sum のimpliict parameter部分に multMonoid を渡しています。
これにより sum(List(1,2,3,4))(multMonoid)はListの各要素を掛け合わせたものが結果として返ります。

cord 7

trait Monoid[A] {
    def mappend(a1: A, a2:A):A
    def mzero: A
}

object Monoid {
  implicit object IntMonoid extends Monoid[Int]{
        def mappend(a: Int, b: Int): Int = a + b
    def mzero: Int = 0
    }

  implicit object StringMonoid extends Monoid[String] {
        def mappend(a: String, b: String): String = a + b
        def mzero: String = ""      
  }
}

object Main {

    import Monoid._

    // 引数をかけ算する
    val multMonoid = new Monoid[Int] {
        def mappend(a:Int, b: Int): Int = a * b
        def mzero: Int = 1  // 単位元は 1 
    }


    def sum[T](xs: List[T])(implicit m: Monoid[T]): T = 
      xs.foldLeft(m.mzero)(m.mappend)


    def p(a: Any) {println("###> " + a)}
    def main(args: Array[String]) {
        println

        p(sum(List(1,2,3,4)))
        p(sum(List("a","b","c","d")))
        p(sum(List(1,2,3,4))(multMonoid))

        println
    }
}

8. ListをfoldLeftするobject作成

sum メソッドですが def sum[T](xs: List[T])(implicit m: Monoid[T]): T = xs.foldLeft(m.mzero)(m.mappend)
引数 xs のメソッドに引数 m の m.mzero, m.mappend を渡す形式になっていますが、これらを渡して処理してくれるメソッドをもつオブジェクトを定義して、
そのメソッドで処理されるように変更します。

object FoldLeftList {
    def foldLeft[A, B](xs: List[A], b: B, f: (B,A) => B) = xs.foldLeft(b)(f)
}

という object を定義します。このobjectは foldLeft というメソッドを持っていて、そのメソッドは[A,B]の型パラメータをとり、引数として List[A],B型,(B,A) => Bの関数の三つの引数をとるメソッドで中身はリストの内容をfoldLeftしています。

この object を使うことで sum は

def sum[T](xs: List[T])(implicit m: Monoid[T]): T = 
        FoldLeftList.foldLeft(xs, m.mzero, m.mappend)

のように定義することができるようになりました。

cord 8

object FoldLeftList {
    def foldLeft[A, B](xs: List[A], b: B, f: (B,A) => B) = 
      xs.foldLeft(b)(f)
}

trait Monoid[A] {
    def mappend(a1: A, a2:A):A
    def mzero: A
}
object Monoid {
  implicit object IntMonoid extends Monoid[Int]{
        def mappend(a: Int, b: Int): Int = a + b
    def mzero: Int = 0
    }

  implicit object StringMonoid extends Monoid[String] {
        def mappend(a: String, b: String): String = a + b
        def mzero: String = ""      
  }
}
object Main {

    import Monoid._

    val multMonoid = new Monoid[Int] {
        def mappend(a:Int, b: Int): Int = a * b
        def mzero: Int = 1
    }


    def sum[T](xs: List[T])(implicit m: Monoid[T]): T = 
        FoldLeftList.foldLeft(xs, m.mzero, m.mappend)


    def p(a: Any) {println("###> " + a)}
    def main(args: Array[String]) {
        println

        p(sum(List(1,2,3,4)))
        p(sum(List("a","b","c","d")))
        p(sum(List(1,2,3,4))(multMonoid))

        println
    }
}

9. sum をもっと一般化

9でsumは

def sum[T](xs: List[T])(implicit m: Monoid[T]): T = 
        FoldLeftList.foldLeft(xs, m.mzero, m.mappend)

となりましたが、もっと sum を一般化するにはこのメソッドの第一引数 xs の型が List になっていますのでこの部分に型パラメータを適用するともっと一般化ができそうです。

trait FoldLeft[F[_]] {
    def foldLeft[A, B](xs: F[A], b: B, f: (B,A) => B): B
}

object FoldLeft {
  implicit object FoldLeftList extends FoldLeft[List]{
    def foldLeft[A, B](xs: List[A], b: B, f: (B,A) => B):B = 
      xs.foldLeft(b)(f)
  }
}

FoldLeft trait を定義します。
この trait は F[_]型パラメータを取ります。
List[Int]が入ると F には Listが適用されることになります。
そして implicit object として FoldLeft[List]をextends した FoldLeftListを定義します。

これを使うことで sum メソッドは

始めの sum メソッド

    def sum(xs: List[Int]): Int = xs.foldLeft(0){ (a,b) => a + b}

から

    def sum[M[_],T](xs: M[T])(implicit m: Monoid[T], fl: FoldLeft[M]): T = 
        fl.foldLeft(xs, m.mzero, m.mappend)

のように型パラメータを使用するものに変更が出来ました。引数に List 型は明示されていません。
この sum メソッドには implicit parameter として新たに fl: FoldLeft[M] が追加されました。
この暗黙的パラメータ部分には List の場合 implicit object FoldLeftList が暗黙的に引き渡されることが期待されます。
例としてこの sumメソッドに List(1,2,3,4) が渡されると

xs <- List(1,2,3,4)
M[T] <- List[Int]
m <- Monoid[Int]
fl <- FoldLeft[List]

が入ることになります。
さらにMonoid[Int],FoldLeft[List]の部分は暗黙的パラメータとして定義されているので、
implicit object で定義されているものから適合するものが暗黙的に引き渡されますので
この例の場合にはそれぞれに IntMonoid, FoldLeftListが引き渡されることになります。

cord 9

trait FoldLeft[F[_]] {
    def foldLeft[A, B](xs: F[A], b: B, f: (B,A) => B): B
}

object FoldLeft {
  implicit object FoldLeftList extends FoldLeft[List]{
    def foldLeft[A, B](xs: List[A], b: B, f: (B,A) => B):B = 
      xs.foldLeft(b)(f)
  }
}

trait Monoid[A] {
    def mappend(a1: A, a2:A):A
    def mzero: A
}

object Monoid {
  implicit object IntMonoid extends Monoid[Int]{
        def mappend(a: Int, b: Int): Int = a + b
    def mzero: Int = 0
    }

  implicit object StringMonoid extends Monoid[String] {
        def mappend(a: String, b: String): String = a + b
        def mzero: String = ""      
  }
}
object Main {
    import Monoid._,FoldLeft._

    val multMonoid = new Monoid[Int] {
        def mappend(a:Int, b: Int): Int = a * b
        def mzero: Int = 1
    }


    def sum[M[_],T](xs: M[T])(implicit m: Monoid[T], fl: FoldLeft[M]): T = 
        fl.foldLeft(xs, m.mzero, m.mappend)


    def p(a: Any) {println("###> " + a)}
    def main(args: Array[String]) {
        println

        p(sum(List(1,2,3,4)))
        p(sum(List("a","b","c","d")))
    //  p(sum(List(1,2,3,4))(multMonoid))  // 今はエラーになるのでコメントアウト

        println
    }
}

10. 再度パラメータを明示的に渡してみる

9 でコメントアウトしていた sum(List(1,2,3,4))(multMonoid) を正しく動作させるには
暗黙的に解決できない部分を指定してあげることで正常に実行可能です。
sum(List(1,2,3,4))(multMonoid, implicitly[FoldLeft[List]])
と暗黙的パラメータ部分を明示的に記述しておきます。

trait FoldLeft[F[_]] {
  def foldLeft[A, B](xs: F[A], b: B, f: (B,A) => B): B
}

object FoldLeft {
  implicit object FoldLeftList extends FoldLeft[List]{
    def foldLeft[A, B](xs: List[A], b: B, f: (B,A) => B):B = xs.foldLeft(b)(f)
  }
}

trait Monoid[A] {
  def mappend(a1: A, a2:A):A
  def mzero: A
}

object Monoid {
  implicit object IntMonoid extends Monoid[Int]{
    def mappend(a: Int, b: Int): Int = a + b
    def mzero: Int = 0
  }

  implicit object StringMonoid extends Monoid[String] {
    def mappend(a: String, b: String): String = a + b
    def mzero: String = ""    
  }
}
object Main {

  // def implicitly[T](implicit t: T): T = t
  import Monoid._, FoldLeft._

  val multMonoid = new Monoid[Int] {
    def mappend(a:Int, b: Int): Int = a * b
    def mzero: Int = 1
  }


  def sum[M[_],T](xs: M[T])(implicit m: Monoid[T], fl: FoldLeft[M]): T = 
    fl.foldLeft(xs, m.mzero, m.mappend)


  def p(a: Any) {println("###> " + a)}
  def main(args: Array[String]) {
    println

    p(sum(List(1,2,3,4)))
    p(sum(List("a","b","c","d")))
    p(sum(List(1,2,3,4))(multMonoid, implicitly[FoldLeft[List]]))

    println
  }
}

gist

gistでも公開

Takuya71 のぶろぐ

外資系ソフトウェア会社で働いてます、認定スクラムマスター

Scala 型パラメータによる関数の一般化例

Monoid, 型パラメータ, implicitを使った加算する関数の一般化

1. 初期状態

cord 1

2. Monoid を定義

cord 2

3. Monoid の trait 定義

cord 3

4. sum メソッドに型パラメータをつける

cord 4

5. 暗黙的パラメータを定義します

cord 5

6. List[String]型も扱えるようにする

cord 6

7. 暗黙的パラメータにパラメータを渡してもいいよ

cord 7

8. ListをfoldLeftするobject作成

cord 8

9. sum をもっと一般化

cord 9

10. 再度パラメータを明示的に渡してみる

gist

Monoid, 型パラメータ, implicitを使った加算する関数の一般化

1. 初期状態

cord 1

2. Monoid を定義

cord 2

3. Monoid の trait 定義

cord 3

4. sum メソッドに 型パラメータをつける

cord 4

5. 暗黙的パラメータ を定義します

cord 5

6. List[String]型も扱えるようにする

cord 6

7. 暗黙的パラメータにパラメータを渡してもいいよ

cord 7

8. ListをfoldLeftするobject作成

cord 8

9. sum をもっと一般化

cord 9

10. 再度 パラメータを明示的に渡してみる

gist

4. sum メソッドに型パラメータをつける

5. 暗黙的パラメータを定義します

10. 再度パラメータを明示的に渡してみる