Scalaのモノイドと半群

投稿日: 2022-10-11 2022-10-15
タグ: Functional Programming

1. 序章

関数型プログラミングコミュニティの優れた点の1つは、数学で明確に定義された合法的な表現を持つコードの抽象的なパターンを認識する傾向です。これらの抽象化は、代数的構造および代数法の観点から頻繁に説明されます。

このチュートリアルでは、関数型プログラミングのコンテキストでこれらの用語を定義します。次に、代数的構造、特にモノイドと半群の直感を構築します。ただし、最初にモノイドの平易な英語での簡潔な定義から始めることは価値があります。

モノイドは、2つの引数を取り、結合法則とアイデンティティの2つの法則に従う関数です。

2. 代数的構造

代数的構造とは、いくつかの操作とそれらが操作するsetを指します。 Scalaなどの関数型言語では、セットはデータ型ですが、操作は型クラスです。モノイドと半群は、そのような代数的構造の2つの例です。

ここでの一般的な概念は、動作をデータから分離することです。代数的構造は、データに適用される操作を通じて目的の動作を記述するためのコンテキストを提供します。

代数的構造のモノイドと半群を分析する前に、型と型クラスを簡単に確認することは価値があります。

2.1. 種類

タイプは値のコレクションです。 Int 、 Double 、およびStringはタイプの例です。タイプは静的であり、Scalaでのコンパイル時に解決されます。型システムは、プログラムのさまざまな部分の間の関連付けを定義し、すべての部分が論理的に一貫性があり、証明可能な正しい方法で組み合わされていることを確認します。

関数型プログラミングでは、データ型の基本的な構成要素は製品および副産物です。これらはまとめて代数的データ型（ ADT）—派手な名前ですが、非常に単純な意味を持つ関数型プログラミングの概念。これらは、「ands」と「ors」を使用してデータを表す慣用的な方法です。例えば：

形状は長方形または円です
長方形の幅は、高さはです。
円には半径があります

ADTの用語では、長方形や円などの「and」タイプは製品、であり、形状などの「or」タイプは余積です。 Scalaでは、通常、ケースクラスを使用して製品を表し、封印された特性を使用して副産物を表します。

sealed trait Shape
final case class Rectangle(width: Double, height: Double) extends Shape
final case class Circle(radius: Double) extends Shape

val rect: Shape = Rectangle(3.0, 4.0)
val circ: Shape = Circle(1.0)

次に、Scalaでの型クラスとその実装について簡単に説明します。

2.2. タイプクラス

型クラスは、メソッドと呼ばれる特定のオーバーロードされた操作をサポートする型システム構造です。これらは、一連の関数または定数名をそれぞれのタイプとともに指定することによって定義されます。たとえば、モノイドと半群はそのような型クラスの中にあります。型クラスには3つの重要なコンポーネントがあります。

型クラス自体
特定の型の型クラスインスタンス
型クラスを使用するメソッド

モノイド型と半群型のクラスを定義しましょう。

trait Semigroup[A] {
  def op(x: A, y: => A): A
}
trait Monoid[A] extends Semigroup[A] {
  def zero: A
}

これまでのところ、型、型クラス、および型クラスインスタンスの直感を構築することができました。次に、この直感を使用して、代数データ構造、具体的にはモノイドと半群を研究します。

3. モノイド

代数的構造semigroupは、セットと、セットの2つの要素を組み合わせる関連する二項演算子です。 モノイドは単位元が追加された半群です。モノイドについての直感を構築するために、これらの定義をScalaでエンコードしてみましょう。

まず、二項演算のScalaエンコーディングから始めます。二項演算は、 arity-2 の関数であり、2つの引数を取り、その関数を引数に適用した結果を返します。

def[A] |+| (left: A, right: A): A

モノイド二項演算の結合法則は、演算の順序が無関係であることを意味します。つまり、括弧を削除できます。 Scalaの用語では、次の式は同等です。

(x |+| y) |+|  z = x |+| (y |+| z)

最後に、モノイド代数的構造には、二項演算に関して「何もしない」要素である単位元があります。

e |+|  x = x |+|  e = x

そして、それがモノイドにあるすべてです！それらの良いところは、それらがいたるところにあるということです。それらを理解する最良の方法は、いくつかの例を見ることです。

整数は、合計と乗算の下でモノイドを形成します
リスト濃度

基本的に、モノイドの法則を守りながら一緒に粉砕できるものはすべて、モノイドであると見なされます。

ここで、この新しい抽象化を利用して、MapReduceのような方法で単語のカウントを行います。ドキュメントのコレクションで単語の頻度を数えることは、 Hadoop 、 Spark 、 Flink などのツールの「HelloWorld」であり、それには十分な理由があります。これはあまり工夫されていないタスクであり、その基礎となる構造は分散コンピューティングに自然に適合します。

自明ではないモノイドインスタンスを実装して、いくつかの単語を数えましょう。

4. MapReduceを実装するためのモノイド

このセクションでは、モノイドを使用してMapReduce関数を開発します。まず、関数のシグネチャを定義します。つまり、Scalaで関数の入力/出力をコード化します。このアプローチは、私たちのモノイドがサポートしなければならないタイプも明らかにします。

def wordCount(string: String): Map[String, Int] = ???
def mapMonoid[V:Numeric](map1: Map[K, V], map2[K, V]) : Map[K, V] = ???
def frequency(wordCounts: Map[String, Int]*)(implicit monoid: Monoid[Map[String, Int]]): Map[String, Int]=???

最初の関数wordCountは、単語頻度カウンターです。この関数は、多くの計算ノードに分散されます。この関数は、不変マップを使用することにより、本質的にスレッドセーフです。

2番目の関数mapMonoidは、引数を組み合わせて結果を返す2項演算arity-2です。これは私たちですモノイド型クラスインスタンスデータ型の場合マップ[K、V]。関数シグネチャの型注釈、 [V：数値] 、は型制約です。これは、クライアントにNumericsをMapの値部分として使用するように強制するメカニズムです。この制約は、monoidインスタンスがその引数を安全に組み合わせることができるようにするために必要です。

最後に、可変個引数関数 frequency は、モノイドインスタンスを利用するラッパーです。この関数は、MapReduceのreduceフェーズです。すべてのノードから計算された単語数を任意の順序で取得し、それらを最終的な回答に減らします。関数型シグネチャには、 Monoid [Map [String、Int]]。型の暗黙パラメーターが必要です。

ここでの重要な観察の1つは、の削減と集約の順序は、最終的な結果とは無関係であるということです。その保証は、私たちのモノイドインスタンスが連想的であるという事実から来ています。このような無秩序でステートレスな計算は、並行プログラミングの理想的なターゲットです。

次に、各関数の実装を開始します。

4.1. 単語を数える

上記の定義に基づいて、wordCount関数を実装しましょう。

object WordCount {
  case class WordCount(word: String, count: Int)
  def wordCount(s: String): Map[String, Int] =
    s.split("\\s+")
      .map(x => WordCount(x, 1))
      .groupBy(w => w.word)
      .map(x => (x._1 -> x._2.foldLeft(0)((a, c) => c.count + a)))
      .toMap

4.2. モノイドの実装

次に、データ型 Map [K、V] 、に対して、パラメーター[ X155X]Vのタイプは数値です。

object MapMonoidInstance {
  implicit def mapMonoid[K, V: Numeric]: Monoid[Map[K, V]] = 
    new Monoid[Map[K, V]] {
      override def zero: Map[K, V] = Map()
      override def op(l: Map[K, V], r: => Map[K, V]): Map[K, V] = 
        l.keySet.union(r.keySet)
          .map(k =>(k -> implicitly[Numeric[V]].plus(
                      l.getOrElse(k, implicitly[Numeric[V]].zero),
                      r.getOrElse(k, implicitly[Numeric[V]].zero)))).toMap
    }
}

4.3. モノイドの使用

最後に、 reduce 操作は、モノイド準同型を使用して、要素を1つのレポートに結合します。この関数には、暗黙のパラメーターとしてモノイドインスタンスが必要です。これは、モノイド機能を利用して構造体をフォールドし、すべての要素を組み合わせて Map [String、Int]の結果を減らします。

def frequency(wordCounts: Map[String, Int] *)(implicit monoid: Monoid[Map[String, Int]]): Map[String, Int] =
   wordCounts.foldLeft(monoid.zero)(monoid.op(_, _))

5. 結論

この記事では、モノイドと半群の代数的構造について説明しました。

まず、型クラスと型クラスのインスタンスを確認しました。次に、モノイドと半群の両方に対して独自の型クラスを開発しました。最後に、モノイドを使用してスレッドセーフなMapReduceプログラムを開発しました。

いつものように、コードはGitHubのにあります。

getdocs

13036