Zenn
Open17

それ、モノイド(Monoid)でできるよ

gakuzzzzgakuzzzz

この Scrap について

TODO

全てのサンプルコードには以下の import が存在している前提でお読みください。

import cats._
import cats.implicits.given
gakuzzzzgakuzzzz

件数をカウントする

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
gakuzzzzgakuzzzz

条件を満たす要素の数をカウントする

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
gakuzzzzgakuzzzz

各要素の数値を合計する

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
gakuzzzzgakuzzzz

グルーピングする

前提として以下のようなコードがあるとします

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]]
gakuzzzzgakuzzzz

ネストしたグルーピングをする

前提コード（この親トピックの最初の内容と同じです）
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]]]
gakuzzzzgakuzzzz

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]]
gakuzzzzgakuzzzz

最大値を見つける

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]
gakuzzzzgakuzzzz

最小値を見つける

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]
gakuzzzzgakuzzzz

全ての要素が条件を満たすか確認する（全称量化子）

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 になるわけです。

gakuzzzzgakuzzzz

条件を満たす要素が存在するか確認する (存在量化子)

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 になります。