search
LoginSignup
2

More than 1 year has passed since last update.

posted at

updated at

Organization

Haskellのためモノイドを学ぶ

はじめに

  • こんにちは ! KDDI アジャイル開発センターの小板橋です。
  • この記事は、KDDI Engineer Advent Calendar 2020の10日目の記事となります。
  • Haskell初心者の備忘録としてこの記事を残します。

半群とは

抽象代数学であるモノイドを学ぶ前に半群について学びます。
次の条件を満たす集合を半群と呼びます。

  • 結合法則を満たす下記のような演算が定義されている。なお、この時のa, b, cはある集合Gの要素として含む。
( a · b ) · c = a · ( b · c )

モノイドとは

モノイドとは、ひとつの二項演算と単位元をもつ代数的構造です。
例えば、整数の集合は加算演算子と単位元0に対してモノイドを形成します。
もう少し詳しく説明すると、
結合法則を満たす下記のような演算が定義されている。なお、この時のa, b, cはある集合Gの要素として含む。

( a · b ) · c = a · ( b · c )

且、下記のような単位元がある構造を指します。なお、この時のaはある集合Gの要素として含み、eもある集合Gの要素として含む。

e · a = a = a · e

つまり、??
下記のような構造になるということです。

半群 + 単位元e

e <> x = x = x <> e

例: Integer同士の足し算を考えたときに、0をどちらかに足し合でも変化がないことが分かると思います。

0 + 3 = 3 = 3 + 0
0 + 5 = 5 = 5 + 0
0 + 7 = 7 = 7 + 0

型クラスMonoidの定義

class Monoid a where
  mempty  :: a
  mappend :: a -> a -> a
  mconcat :: [a] -> a
  mconcat = foldr mappend mempty
  • memptyは、単位元を表しています。
  • mappendは、二項演算子を表しています。
  • mconcatは、リストに格納されているモノイドを結合する関数です。
  • mconcatは、デフォルト実装が定義されている為、インスタンスを利用する場合、memptyとmappendを定義するだけでMonoidになります。

型クラスMonoidを使用する

例えば、リスト[x,y,z]にmconcatを適用すると以下のようになります。

x `mappend` (y `mappend` (z `mappend` mempty))

Monoidクラスの2つのメソッドは、単位元と結合に関する則を満たす必要があります。

mempty `mappend` x          = x
x `mappend` mempty          = x
x `mappend` (y `mappend` z) = (x `mappend` y) `mappend` z

これらの則を用いると、例えばmconcat[x,y,z]の結果は、下記のように直せます。
→ 理由 : モノイド則によって、結果に影響を与えないことが保証されているためです。

x `mappend` y `mappend` z

実際に試してみる

example.hs
[1,2,3] `mappend` [4,5,6]
GHCi, version 8.6.5
=> [1,2,3,4,5,6]

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
2