お気楽 Haskell プログラミング入門

はじめに

今回は「モノイド (Monoid)」という型クラスについて説明します。

●モノイドとは？

モノイドは主に数学で使われている用語です。モノイド - Wikipedia によると、『数学、とくに抽象代数学における単系（たんけい、英: monoid; モノイド）はひとつの二項演算と単位元をもつ代数的構造である』 とのことです。たとえば、加法と乗法を考えてみましょう。

                結合則                      単位元
加法 : (a + b) + c = a + (b + c) : 0  (a + 0 = a, 0 + a = a)
乗法 : (a * b) * c = a * (b * c) : 1  (a * 1 = a, 1 * a = a)

加法の二項演算子は + で単位元が 0、乗法の二項演算子は * で単位元は 1 です。そして、加法と乗法が結合則を満たしているのは明らかです。このように、二項演算子が結合則を満たし、かつ単位元が存在するような構造を「モノイド (Monoid)」といいます。

モノイドはいろいろな所で現れる構造です。たとえば、真偽値やリストもモノイドの条件を満たします。

                結合律                      単位元
リスト : (a ++ b) ++ c = a ++ (b ++ c) : []    (a ++ [] = a, [] ++ a = a)
真偽値 : (a || b) || c = a || (b || c) : False (a || False = a, False || a = a)
         (a && b) && c = a && (b && c) : True  (a && True = a, True && a = a)

リストの場合、二項演算子を ++ とし、単位元を空リスト [ ] とするとモノイドの条件を満たします。真偽値の場合は 2 通りあって、二項演算子 を || (OR) にする方法と && (AND) にする方法があります。|| の場合は単位元を False とし、&& の場合は単位元を True とするとモノイドの条件を満たします。

●型クラス Monoid の定義

Haskell の場合、モノイドは型クラスのひとつで、モジュール Data.Monoid に定義されています。

リスト : 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 が動作します。なお、Functor や Applicative と同様に、モノイドの条件を満たしていることは、プログラマがチェックしないといけません。

●リストのモノイド

リストの場合、モノイドの定義は次のようになります。

リスト : リストのモノイド

instance Monoid [a] where
  mempty  = []
  mappend = (++)

Monoid のクラス定義で使用されている型変数は型構築子ではないので、instance 宣言では具体的に [a] としてください。

それでは実行してみましょう。

ghci> :m + Data.Monoid
ghci> [1,2,3] `mappend` [4,5,6]
[1,2,3,4,5,6]
ghci> mempty `mappend` [4,5,6]
[4,5,6]
ghci> [1,2,3] `mappend` mempty
[1,2,3]

●加法と乗法のモノイド

Data.Monoid には加法と乗法のモノイドを表すデータ型 Sum と Product が定義されています。

newtype Sum a = Sum { getSum :: a }
newtype Product a = Product { getProduct :: a }

簡単な実行例を示します。

ghci> getSum $ Sum 10 `mappend` Sum 20
30
ghci> getSum $ Sum 10 `mappend` mempty
10
ghci> getProduct $ Product 10 `mappend` Product 20
200
ghci> getProduct $ mempty `mappend` Product 20
20

●真偽値のモノイド

Data.Monoid には真偽値のモノイドを表すデータ型 All と Any も定義されています。

newtype All = All { getAll :: Bool }
newtype Any = Any { getAny :: Bool }

簡単な実行例を示します。

ghci> getAll $ All True `mappend` All True
True
ghci> getAll $ All True `mappend` All False
False
ghci> getAll $ All True `mappend` mempty
True
ghci> getAll $ All True `mappend` All True
True
ghci> getAll $ All True `mappend` All False
False
ghci> getAll $ All True `mappend` mempty
True
ghci> getAny $ Any True `mappend` Any True
True
ghci> getAny $ Any True `mappend` Any False
True
ghci> getAny $ Any False `mappend` Any False
False
ghci> getAny $ Any True `mappend` mempty
True

●Maybe のモノイド

Maybe のモノイドは 2 通りの方法を考えることができます。最初に、Maybe に格納しているデータ型がモノイドの場合を説明します。

リスト : Maybe のモノイド (1)

instance Monoid a => Monoid (Maybe a) where
  mempty = Nothing
  Nothing `mappend` m = m
  m `mappend` Nothing = m
  Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

Maybe a の型変数 a はモノイドなので、型クラス制約で Monoid a を指定します。mempty は Nothing になります。2, 3 番目の節は、引数 m と mempty を mappend で連結すると結果は m になる、というモノイドの規則を表しています。最後の節で、Just m1 と Just m2 の mappend は Just (m1 `mappend` m2) になります。

簡単な実行例を示します。

ghci> mempty `mappend` Just [1,2,3]
Just [1,2,3]
ghci> Just [1,2,3] `mappend` mempty
Just [1,2,3]
ghci> Just [1,2,3] `mappend` Just [4,5,6]
Just [1,2,3,4,5,6]

もう一つは真偽値と同じ方法です。次のリストを見てください。

リスト : Maybe のモノイド (2)

newtype First a = First { getFirst :: Maybe a }
  deriving (Eq, Ord, Read, Show)

instance Monoid (First a) where
  mempty = First Nothing
  r@(First (Just _)) `mappend` _ = r
  First Nothing `mappend` r = r

newtype で新しいデータ型 First を定義します。型変数 a に型クラス制約は必要ありません。mempty は First Nothing になります。次の節で右辺の値が Just であれば、それをそのまま返します。左辺が Nothing であれば、右辺の値をそのまま返します。つまり、mappend は論理和 (||) と同じく短絡演算子として機能します。

簡単な実行例を示します。

ghci> First (Just 1) `mappend` mempty
First {getFirst = Just 1}
ghci> mempty `mappend` First (Just 1)
First {getFirst = Just 1}
ghci> First (Just 2) `mappend` First (Just 1)
First {getFirst = Just 2}

このほかにも Ordering などいろいろなデータ型がモノイドになります。興味のある方は Data.Monoid のマニュアルを参照してください。

●型クラス Foldable

Functor の fmap は汎用のマップ関数ですが、同じように型クラス Foldable には汎用の畳み込み関数が定義されています。

ghci> :i Foldable
type Foldable :: (* -> *) -> Constraint
class Foldable t where
  Data.Foldable.fold :: Monoid m => t m -> m
  foldMap :: Monoid m => (a -> m) -> t a -> m
  Data.Foldable.foldMap' :: Monoid m => (a -> m) -> t a -> m
  foldr :: (a -> b -> b) -> b -> t a -> b
  Data.Foldable.foldr' :: (a -> b -> b) -> b -> t a -> b
  foldl :: (b -> a -> b) -> b -> t a -> b
  Data.Foldable.foldl' :: (b -> a -> b) -> b -> t a -> b
  foldr1 :: (a -> a -> a) -> t a -> a
  foldl1 :: (a -> a -> a) -> t a -> a
  Data.Foldable.toList :: t a -> [a]
  null :: t a -> Bool
  length :: t a -> Int
  elem :: Eq a => a -> t a -> Bool
  maximum :: Ord a => t a -> a
  minimum :: Ord a => t a -> a
  sum :: Num a => t a -> a
  product :: Num a => t a -> a
  {-# MINIMAL foldMap | foldr #-}
        -- Defined in ‘Data.Foldable’
instance Foldable ((,) a) -- Defined in ‘Data.Foldable’
instance Foldable (Either a) -- Defined in ‘Data.Foldable’
instance Foldable [] -- Defined in ‘Data.Foldable’
instance Foldable Maybe -- Defined in ‘Data.Foldable’
instance Foldable Solo -- Defined in ‘Data.Foldable’

foldl と foldr はリストだけではなく、Foldable のインスタンスであれば何でも畳み込むことができます。

簡単な例を示しましょう。

ghci> foldl (+) 0 [1..10]
55
ghci> foldr (+) 0 [1..10]
55
ghci> foldr (+) 0 (Just 1)
1
ghci> foldl (+) 0 (Just 1)
1
ghci> foldl (+) 0 Nothing
0

リストの場合は今までの foldl, foldr と同じ動作になります。Maybe の場合、引数 (初期値) と Just に格納されている値を二項演算子に渡して計算し、その結果を返します。

●二分木の畳み込み

それでは簡単な例題として、「二分探索木」で作成した Tree を Foldable のインスタンスにしてみましょう。foldmap を実装すると、あとの関数はデフォルト実装で動作します。プログラムは次のようになります。

リスト : 二分木の畳み込み

import Data.Monoid

-- データ型の定義
data Tree a = Nil | Node a (Tree a) (Tree a) deriving Show

instance Foldable Tree where
  foldMap f Nil = mempty
  foldMap f (Node x l r) =
    foldMap f l `mappend` f x `mappend` foldMap f r

-- 畳み込み
fold_left :: (a -> b -> a) -> a -> Tree b -> a
fold_left = foldl

fold_right :: (a -> b -> b) -> b -> Tree a -> b
fold_right = foldr

foldMap のデータ型は次のようになります。

ghci> :t foldMap
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

最初の引数は要素 a をモノイドに変換する関数です。そして、第 2 引数 t a から要素 a を取り出して、それに関数 a -> m を適用した結果 (モノイド) を返します。Tree の場合、空リストであれば mempty を返します。そうでなければ、二分木を通りがけ順で巡回し、その結果を mappend で連結します。このとき、二分木の要素 x を関数 f でモノイドに変換します。これで、畳み込み fold_left は foldl で、fold_right は foldr で実現できます。

簡単な実行例を示します。

ghci> a = fromList [4,2,1,3,6,5,7]
ghci> a
Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) 
(Node 7 Nil Nil))

ghci> getAny $ foldMap (\x -> Any $ x == 5) a
True
ghci> getAny $ foldMap (\x -> Any $ x > 7) a
False
ghci> foldMap (\x -> [x]) a
[1,2,3,4,5,6,7]
ghci> foldMap (\x -> if x > 3 then [x] else []) a
[4,5,6,7]

ghci> fold_right (:) [] a
[1,2,3,4,5,6,7]
ghci> fold_left (flip (:)) [] a
[7,6,5,4,3,2,1]
ghci> fold_right (+) 0 a
28
ghci> fold_left (*) 1 a
5040
ghci> fold_left (\a x -> a || x == 5) False a
True
ghci> fold_left (\a x -> a || x > 7) False a
False

foldMap は要素をモノイドに変換する関数を渡せば動作します。fold_left, fold_right も正しく動作していますね。