それ、モノイド(Monoid)でできるよ
この Scrap について
TODO
全てのサンプルコードには以下の import が存在している前提でお読みください。
import cats._
import cats.implicits.given
モノイド(Monoid)とは
TODO
モノイド(Monoid) を使うメリット
TODO
件数をカウントする
val list = List(1, 2, 3, 4, 5)
list.size // 5: Int
size
メソッドをモノイド使って書き換えると以下のようになります
val list = List(1, 2, 3, 4, 5)
list.foldMap(_ => 1) // 5: Int
条件を満たす要素の数をカウントする
val list = List(1, 2, 3, 4, 5)
list.count(_ % 2 == 0) // 2: Int
count
メソッドをモノイド使って書き換えると以下のようになります
val list = List(1, 2, 3, 4, 5)
list.foldMap(v => if (v % 2 == 0) 1 else 0) // 2: Int
各要素の数値を合計する
val lists = List(
List(1, 2),
List(3),
List(4, 5, 6),
)
lists.map(_.size).sum // 6: Int
lists.view.map(_.size).sum // リストの件数が多い時に2重ループを避けるため view を使う
リストの各要素の何らかの数値を得てその全体合計を計算する、といった場合、map
+ sum
で表現できます。
これもモノイドを使うことで単純な1重ループにすることができます。
val lists = List(
List(1, 2),
List(3),
List(4, 5, 6),
)
lists.foldMap(_.size) // 6: Int
WordCount
MapReduce のサンプルコードと言えば WordCount
TODO
グルーピングする
前提として以下のようなコードがあるとします
opaque type CharacterId = Int
opaque type GuildId = Int
enum Job {
case ナイト, 忍者, 黒魔道士, 白魔道士
}
import Job.*
case class Character(id: CharacterId, guildId: GuildId, job: Job, level: Int)
val characters = List(
Character(1, 1, ナイト, 99),
Character(2, 1, 忍者, 15),
Character(3, 1, 黒魔道士, 30),
Character(4, 1, 白魔道士, 60),
Character(5, 1, 忍者, 99),
Character(6, 2, 黒魔道士, 20),
Character(7, 2, 黒魔道士, 25),
Character(8, 2, 白魔道士, 10),
Character(9, 3, ナイト, 99),
)
GuildId
でグルーピングしたい時、groupBy
が使えます。
characters.groupBy(_.guildId)
// HashMap(
// 1 -> List(
// Character(1,1,ナイト,99),
// Character(2,1,忍者,15),
// Character(3,1,黒魔道士,30),
// Character(4,1,白魔道士,60),
// Character(5,1,忍者,99)),
// 2 -> List(
// Character(6,2,黒魔道士,20),
// Character(7,2,黒魔道士,25),
// Character(8,2,白魔道士,10)),
// 3 -> List(
// Character(9,3,ナイト,99))
// ): Map[GuildId, List[Character]]
これをモノイド使って書き換えると以下のようになります
characters.foldMap(chara => Map(chara.guildId -> List(chara)))
// HashMap(
// 1 -> List(
// Character(1,1,ナイト,99),
// Character(2,1,忍者,15),
// Character(3,1,黒魔道士,30),
// Character(4,1,白魔道士,60),
// Character(5,1,忍者,99)),
// 2 -> List(
// Character(6,2,黒魔道士,20),
// Character(7,2,黒魔道士,25),
// Character(8,2,白魔道士,10)),
// 3 -> List(
// Character(9,3,ナイト,99))
// ): Map[GuildId, List[Character]]
ネストしたグルーピングをする
前提コード(この親トピックの最初の内容と同じです)
opaque type CharacterId = Int
opaque type GuildId = Int
enum Job {
case ナイト, 忍者, 黒魔道士, 白魔道士
}
import Job.*
case class Character(id: CharacterId, guildId: GuildId, job: Job, level: Int)
val characters = List(
Character(1, 1, ナイト, 99),
Character(2, 1, 忍者, 15),
Character(3, 1, 黒魔道士, 30),
Character(4, 1, 白魔道士, 60),
Character(5, 1, 忍者, 99),
Character(6, 2, 黒魔道士, 20),
Character(7, 2, 黒魔道士, 25),
Character(8, 2, 白魔道士, 10),
Character(9, 3, ナイト, 99),
)
単純なグルーピングであれば groupBy
を使う方が望ましいケースが多いですが、ネストしたグルーピングをしたい場合はモノイドを使った方が簡単かつ計算量も減らせる可能性があります。
例として GuildId
でグルーピングした中でさらに Job
でもグルーピングしたい場合、標準APIでは以下のようになります。
characters.groupBy(_.guildId)
.view
.mapValues(_.groupBy(_.job))
.toMap
// HashMap(
// 1 -> HashMap(
// 忍者 -> List(
// Character(2,1,忍者,15),
// Character(5,1,忍者,99)),
// 黒魔道士 -> List(
// Character(3,1,黒魔道士,30)),
// 白魔道士 -> List(
// Character(4,1,白魔道士,60)),
// ナイト -> List(
// Character(1,1,ナイト,99))),
// 2 -> HashMap(
// 白魔道士 -> List(
// Character(8,2,白魔道士,10)),
// 黒魔道士 -> List(
// Character(6,2,黒魔道士,20),
// Character(7,2,黒魔道士,25))),
// 3 -> HashMap(
// ナイト -> List(
// Character(9,3,ナイト,99)))
//): Map[GuildId, Map[Job, List[Character]]]
これをモノイドを使って書き換えると以下のようになります
characters.foldMap { chara =>
Map(chara.guildId -> Map(chara.job -> List(chara)))
}
// HashMap(
// 1 -> HashMap(
// 忍者 -> List(
// Character(2,1,忍者,15),
// Character(5,1,忍者,99)),
// 黒魔道士 -> List(
// Character(3,1,黒魔道士,30)),
// 白魔道士 -> List(
// Character(4,1,白魔道士,60)),
// ナイト -> List(
// Character(1,1,ナイト,99))),
// 2 -> HashMap(
// 白魔道士 -> List(
// Character(8,2,白魔道士,10)),
// 黒魔道士 -> List(
// Character(6,2,黒魔道士,20),
// Character(7,2,黒魔道士,25))),
// 3 -> HashMap(
// ナイト -> List(
// Character(9,3,ナイト,99)))
//): Map[GuildId, Map[Job, List[Character]]]
group by した中であるカラムが最大値の別のカラムを得る
前提コード(この親トピックの最初の内容と同じです)
opaque type CharacterId = Int
opaque type GuildId = Int
enum Job {
case ナイト, 忍者, 黒魔道士, 白魔道士
}
import Job.*
case class Character(id: CharacterId, guildId: GuildId, job: Job, level: Int)
val characters = List(
Character(1, 1, ナイト, 99),
Character(2, 1, 忍者, 15),
Character(3, 1, 黒魔道士, 30),
Character(4, 1, 白魔道士, 60),
Character(5, 1, 忍者, 99),
Character(6, 2, 黒魔道士, 20),
Character(7, 2, 黒魔道士, 25),
Character(8, 2, 白魔道士, 10),
Character(9, 3, ナイト, 99),
)
例えば characters
を Job でグルーピングした中でレベルが最大のキャラのIDを取得したい、というケースを考えます。
これは仮にSQLでやろうとすると、単純な group by だけではできず、group by した結果を自己結合したりする必要があります。
-- 仮に SQL でやるとサブクエリ等が必要になる
SELECT
C.*
FROM
characters C
WHERE
(job, level) IN (
SELECT
job, max(level)
FROM
characters
GROUP BY
job
)
しかしモノイドを使うとこれが簡単にできます。
今回はレベルが最大のキャラを取得したいので、 最大値を見つける から Max
を借りてきましょう。すると以下のように書くことができます。
import org.typelevel.semigroups.Max
given Ordering[Character] = Ordering.by(_.level)
characters.foldMap(char => Map(char.job -> Max(char)))
// Map(
// 黒魔道士 -> Character(3,1,黒魔道士,30),
// ナイト -> Character(1,1,ナイト,99),
// 忍者 -> Character(5,1,忍者,99),
// 白魔道士 -> Character(4,1,白魔道士,60)
// ): Map[Job, Max[Character]]
フラットな集合からツリー構造を作る
TODO
最大値を見つける
val list = List(1, 2, 3, 4, 5)
list.maxOption // Some(5): Option[Int]
maxOption
をモノイド使って書き換えたいんですが、Max の定義が cats 標準とは 別のリポジトリ で定義されています。 そのため依存ライブラリにこちらを追加しましょう。
すると maxOption
を以下のように書き換えることができます。
import org.typelevel.semigroups.Max
val list = List(1, 2, 3, 4, 5)
list.foldMap(v => Option(Max(v))) // Some(5): Option[Max[Int]]
リストが空でない事が保証されているのであれば、Option
でくるむ必要も無くなります。
import cats.data.NonEmptyList
import org.typelevel.semigroups.Max
val list = NonEmptyList.of(1, 2, 3, 4, 5)
list.reduceMap(v => Max(v)) // 5: Max[Int]
最小値を見つける
val list = List(1, 2, 3, 4, 5)
list.minOption // Some(1): Option[Int]
Min も Max と同様に こちら を依存ライブラリに追加すると同様に書き換えることができます。
import org.typelevel.semigroups.Min
val list = List(1, 2, 3, 4, 5)
list.foldMap(v => Option(Min(v))) // Some(1): Option[Min[Int]]
リストが空でない事が保証されているのであれば、Option
でくるむ必要も無くなります。
import cats.data.NonEmptyList
import org.typelevel.semigroups.Min
val list = NonEmptyList.of(1, 2, 3, 4, 5)
list.reduceMap(v => Min(v)) // 1: Min[Int]
全ての要素が条件を満たすか確認する(全称量化子)
val list = List(1, 2, 3, 4, 5)
val emptyList = List()
list.forall(_ < 10) // true: Boolean
list.forall(_ == 3) // false: Boolean
emptyList.forall(_ == 3) // true: Boolean
全ての要素が条件を満たすか確認する foeall
メソッドですが、空リストでは true
になることに驚いた方もいるのではないでしょうか?
実はこれもモノイドで表現できることがわかると自然に思えてくるようになります。
Boolean がモノイドになる演算は複数ありますが、ここでは全ての要素が条件を満たしているかを表現したいので、&&
(論理積) を2項演算とします。
他の Boolean のモノイドと区別できるように cats の monoid リポジトリ では All
という別の型が定義されています。
All
を使うことで forall
を書き換えることができます。
import org.typelevel.monoids.All
val list = List(1, 2, 3, 4, 5)
val emptyList = List()
list.foldMap(v => All(v < 10)) // true: All
list.foldMap(v => All(v == 3)) // false: All
emptyList.foldMap(v => All(v == 3)) // true: All
2項演算を &&
とした場合、単位元は true
になるため、空リストの際は結果が true
になるわけです。
条件を満たす要素が存在するか確認する (存在量化子)
val list = List(1, 2, 3, 4, 5)
val emptyList = List()
list.exists(_ > 10) // false: Boolean
list.exists(_ == 3) // true: Boolean
emptyList.exists(_ == 3) // false: Boolean
exists
も forall
と同様にモノイドを使って表現することができます。
要素のいずれかが条件を満たしていれば良いので ||
(論理和) を2項演算とします。
All
と同様に cats の monoid リポジトリ では Any
という別の型が定義されています。
Any
を使うことで exists
を書き換えることができます。
import org.typelevel.monoids.Any
val list = List(1, 2, 3, 4, 5)
val emptyList = List()
list.foldMap(v => Any(v > 10)) // false: Any
list.foldMap(v => Any(v == 3)) // true: Any
emptyList.foldMap(v => Any(v == 3)) // false: Any
2項演算を ||
とした場合、単位元は false
になるため、空リストの際は結果が false
になります。