いいものをつくろう

CTOの日記

Scala

scala の monoidを理解する

投稿日:

scala はmonadとか出てきて哲学的な要素がちらほら見られる言語なんではなかろうか。ほら、また今日、monoidという概念があるらしいこと知った。今日はそれを理解することでscalaの実装のレベルを少し 上がれば嬉しい

これを知らなくても当然、プログラミングができる。でも知っていた方がよりエレガントなコードを書くことができる。エレガントなコードとはよりソースコードの量が少なく言語が持つ技を駆使した(実行時間においても効率的)なコードである。同僚はそのようなソースコードを書いている。なので私も知りたいのである。

この記事はscalazこの解説を理解するための私のメモである。直接このサイトが理解できる人はこの記事に書いてあることは新しくないでしょう。monoidは聞いたことない方や聞いたことはあるけどそれ以上ではない方を対象に書いています。

scalaではmonidという考えが投影(実装)されている。

monoidとは
関数が閉じていて
結合性があり
単位元が存在する
という三つの特徴を持ち合わせた関数のことを言う

閉じているとは=>入力と出力の型が同じ
結合性とは=>入力の計算順の組み合わを変えても結果が同じ
単位元とは=>足しても、元の数と変わらない数( 例えばInt型だと0+1は1 String型だと"miso" +""は"miso"なので""空文字といった具合だ。)

でこのmonoidという
考え方が役に立つらしい。見ていこう。

1st Step、まずはInt型のリストの合計を出すsumという関数を考える。普通に書くと以下のようになりますね。

[scala] def sum(xs: List[Int]): Int = xs.foldLeft(0){ _ + _ }[/scala]

これのIntの部分をモノイド風に書くと

[scala]
def sum(xs: List[Int]): Int = xs.foldLeft(0){ _ + _ }
object IntMonoid{
def mappend(a: Int, b: Int): Int = a + b
def mzero: Int = 0
}
def sum(xs: List[Int]): Int = xs.foldLeft(IntMonoid.mzero)(IntMonoid.mappend)
sum(List(1, 2, 3, 4))
[/scala]

IntMonoidというオブジェクトを定義して同じ型の二つの引数が足された時(append)
の処理と単位元であるIntの0を定義してInt型のMonoidを表現しています
そのInt型のMonoidを、ListのfoldLeftをパラメターとして使っています。
なんとなくMonoid風(チック)になりました。
こうすると何が嬉しいんだ?
なんだかList[Int]の部分を色んか型に変更できそうな気がしてきました。
すると
def sum[A](xs: List[A]): A = xs.sum
でいいじゃん
って考えるのですが、

[scala]
def sum[A](xs: List[A]): A = xs.sum
cmd27.sc:1: could not find implicit value for parameter num: Numeric[A]
def sum[A](xs: List[A]): A = xs.sum
^
Compilation Failed
[/scala]

とNumeric[A]が見つかりませんとコンパイルエラーが出ます。
sumのfull signitureをみると

[scala]def sum[B <: A](implicit num: Numeric[B]): B[/scala]

というシグニチャで
Numeric[B]を実装しないといけないことがわかります。
ちょっと脱線するのですが
[B >: A]の意味もしっかり抑えておきましょう
Bというクラスを型パラメータとする、と書いてありして、さらにBには>:Aいう
条件がついていそうです。これは下限境地というものです。
例えばAnimal -> Mamoo -> Human -> Japaneseというような継承された
クラスを考えた時
[A <: Animal]なると上限境地でAnimal含むすべての派生クラスという意味だけど

[A >: Human]となっているとJapaneseというHumanの派生クラスはダメでそれ以上の基底クラスに限ります、という意味です。

本家の説明も慣れてくるとわかりやすいので抜粋しておきます。

def sum[B <: A](implicit num: Numeric[B]): B

型パラメータの上限境界について見てきました。T <: U のような型パラメータ宣言では、型パラメータ T は型 U のサブタイプの範囲に制限されます。これと対照的なのが Scala における下限境界です。型パラメータ宣言 T >: S において、型パラメータ T は型 S の スーパータイプ の範囲に制限されます (上限境界と下限境界を組み合わせることもできます。T >: S <: U のように)。

少し複雑だが、この記事も参考にしてほしい

ということで本トピックに戻りまして
def sum[B <: A](implicit num: Numeric[B]): B

ですが、Aという基底クラス以前のクラスBでちゃんとNumeric[B]が定義されているものだけがsumという関数呼び出しを許されるようです。ではNumeric[B]とはどんなクラスなのでしょうか?

Numericの公式apiドキュメントにあるようにいかにも俺は数だぜ〜

というような,minとかmaxとか比較演算とか他の型への変換(toInt, toLong)のような関数が書かれており、IntIsIntegralとかFractionalというようなTraitがKnownSubclassesとして挙げられている。

IntegralとかFractionalは馴染みがないのですんなり理解はできない。むしろNumericな感じのするInt, Doubleとかがあるのかと思いきや、彼らは普通にInt extends AnyValの子供だ。

直感的に書いたこれはdef sum[A <: Numeric](xs: List[A]): A = xs.sum

以下のようなコンパイルエラーが出ちゃう

[scala]
cmd27.sc:1: type Numeric takes type parameters
def sum[A <: Numeric](xs: List[A]): A = xs.sum
^
cmd27.sc:1: could not find implicit value for parameter num: Numeric[A]
def sum[A <: Numeric](xs: List[A]): A = xs.sum
^
Compilation Failed
[/scala]

正解はこうらしい

[scala]def sum[T](x: List[T])(implicit num: Numeric[T]): T = x.foldLeft(num.zero)(num.plus)
[/scala]

これもいけた

[scala]def sum[T : Numeric](xs: List[T]): T = xs.sum[/scala]

う〜ん、これの辺の理解が足りないので、すんなり何故上の式が通るのか
わからない。わかるのはIntは暗黙的にNumericとして扱われることができる
ということか。

とにかく、ここでもMonoid風にsumをジェネリックにしようぜ、ってことで
本題に戻る。 2nd Stepとして、上でのはIntMonoidを直接、書きましたが、traitを
作っていろんな型でも作りやすくします。mappend, mzeroは慣例でmonoidのmを先頭文字につけた名前にしているだけです。モノイドの特徴である引数と戻り値が同じ型でA, A : Aの関数と単位元であるmzeroを表す関数を持つ、とします

[scala]
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
}
def sum(xs: List[Int], m: Monoid[Int]): Int = xs.foldLeft(m.mzero)(m.mappend)
sum(List(1, 2, 3, 4), IntMonoid)
[/scala]

 

3rd Stepとして、先ほどはMonoid[Int]としてましたがMonoid[A]として

コンパイル通りますね〜

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

sum[Int](List(1, 2, 3, 4), IntMonoid)
[/scala]

 

4th Stepとして、Doubleも書いてみましょうか

[scala]
object DoubleMonoid extends Monoid[Double]{
def mappend(a: Double, b: Double): Double = a + b
def mzero: Double = 0.0
}
sum[Double](List(1.0, 2.0, 3.0, 4.0), DoubleMonoid)
[/scala]

 

5th Stepとして、先ほどのMonoidを暗黙的 (implicit)にしてみましょう。

scalaでimplictにする慣例はどうなっているんでしょうね。今は使えることろは使っている気がします。個人的にはある程度、直感的にソースを追えればimplicitでもいいんじゃないとかと思います。まだ慣れてないので、implicitない方が安心はしますが、implicitと使いこなしは中・上級者への通る道かなとも思います

動画の例ではimplicit valなしでimplicit reference ルールでobject 名と同じであれば、そこをルックアップしてくるようです。ここではammのREPLでやったせいか、そうはならなかったのでimplicit val云々をちゃんと書いています。

[scala]
def sum[A](xs: List[A])(implicit m: Monoid[A]): A = xs.foldLeft(m.mzero)(m.mappend)
sum(List(1, 2, 3, 4))(IntMonoid)

implicit val intMonoid = IntMonoid
implicit val doubleMonoid = DoubleMonoid
sum(List(1, 2, 3, 4))
sum(List(1.0, 2.0, 3.0, 4.0))
[/scala]

6th Step (package implicit set up 😀 ) ということで見やすく、使いやすく

パッケージ化していきます。先ほども言ったように
because of scala implicit resolution rule
objectで名前が同じなら、今回はMonoidという名前だと探してくれる

[scala]
object Monoid {
implicit object IntMonoid extends Monoid[Int]{
def mappend(a: Int, b: Int): Int = a + b
def mzero: Int = 0
}
implicit object DoubleMonoid extends Monoid[Double]{
def mappend(a: Double, b: Double): Double = a + b
def mzero: Double = 0.0
}
}
def sum[A](xs: List[A])(implicit m: Monoid[A]): A = xs.foldLeft(m.mzero)(m.mappend)

sum(List(1, 2, 3, 4))
sum(List(1.0, 2.0, 3.0, 4.0))
[/scala]

 

以下のような形でMonoidを別実装して、plugin もできちゃう

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

sum(List(1, 2, 3, 4)) // res12: Int = 10
sum(List(1, 2, 3, 4))(multMonoid) // res13: Int = 24
[/scala]

 

ここからはさらにハッキーでListを抽象化してfoldable的なもにする。
するとfoldableでMonoidな型であれば何でもsumできる関数となる

[scala]
def sum[T](xs: List[T])(m: Monoid[T]): T = ???

こんな感じに変えたい
def sum[M[_], T](xs: M[T])(m: Monoid[T]): T = ???
[/scala]

M[_]のアンダースコアは、これはMを使うにはタイプを指定しないといけないことを表していて、List[String]やOption[Int]のような物であるということを指す

一般化していこう

[scala]
//traitは以下のようなイメージだが、traitなしでまずはやってから解説する
//trait FolderLeft[F[_]] {
// def folderLeft[A, B](f: F[])
//}

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

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

sum(List(1, 2, 3, 4))
[/scala]

ここまでくると
def sumをもっと一般化できる

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

というようなことをやりたい
しかし、FoldLeftList.foldLeftは xs: List[A]とListであることを期待しているので、そうではない
traitを作る

[scala]
trait FoldLeft[M[_]] {
def foldLeft[A ,B](xs: M[A], b: B, f1: (B, A) =&amp;amp;amp;amp;amp;amp;amp;amp;gt; B): B
}
object FoldLeft {
implicit object FoldLeftList extends FoldLeft[List] {
def foldLeft[A, B](xs: List[A], b: B, f: (B, A) =&amp;amp;amp;amp;amp;amp;amp;amp;gt; B) = xs.foldLeft(b)(f)
}
}

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

implicit val foldLeftList = FoldLeft.FoldLeftList

sum(List(1, 2, 3, 4))
[/scala]

以上で一通りの解説を終わります。
Monoidというものが理解できること
そして、多少脱線して、scalaのわかりにく文法,下限境界などにも触れた内容でした。

最後までお読みいただき、
ありがとうございました。

 

 

参考

video: https://vimeo.com/10482466
doc: http://eed3si9n.com/learning-scalaz/ja/polymorphism.html

-Scala

Copyright© CTOの日記 , 2020 All Rights Reserved.