Λ Takuya71 の日記 Λ

ここに記載の内容は個人的な見解で 勤務先、所属先には関連はございません。最近は scala に はまってます。認定スクラムマスター

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 ….

が 一般化され

となるまでの過程です。

型パラメータを使って 一般化 させる過程を考える上で 非常に参考になりました。
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でも公開