M.Hiroi's Home Page

Functional Programming

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

[ PrevPage | Haskell | NextPage ]

モノイド (Monoid)

今回は「モノイド (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] としてください。

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

Prelude Data.Monoid> [1,2,3] `mappend` [4,5,6]
[1,2,3,4,5,6]
Prelude Data.Monoid> mempty `mappend` [4,5,6]
[4,5,6]
Prelude Data.Monoid> [1,2,3] `mappend` mempty
[1,2,3]

●加法と乗法のモノイド

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

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

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

Prelude Data.Monoid> getSum $ Sum 10 `mappend` Sum 20
30
Prelude Data.Monoid> getSum $ Sum 10 `mappend` mempty
10
Prelude Data.Monoid> getProduct $ Product 10 `mappend` Product 20
200
Prelude Data.Monoid> getProduct $ mempty `mappend` Product 20
20

●真偽値のモノイド

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

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

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

Prelude Data.Monoid> getAll $ All True `mappend` All True
True
Prelude Data.Monoid> getAll $ All True `mappend` All False
False
Prelude Data.Monoid> getAll $ All True `mappend` mempty
True
Prelude Data.Monoid> getAll $ All True `mappend` All True
True
Prelude Data.Monoid> getAll $ All True `mappend` All False
False
Prelude Data.Monoid> getAll $ All True `mappend` mempty
True
Prelude Data.Monoid> getAny $ Any True `mappend` Any True
True
Prelude Data.Monoid> getAny $ Any True `mappend` Any False
True
Prelude Data.Monoid> getAny $ Any False `mappend` Any False
False
Prelude Data.Monoid> 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) になります。

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

Prelude Data.Monoid> mempty `mappend` Just [1,2,3]
Just [1,2,3]
Prelude Data.Monoid> Just [1,2,3] `mappend` mempty
Just [1,2,3]
Prelude Data.Monoid> 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 は論理和 (||) と同じく短絡演算子として機能します。

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

Prelude Data.Monoid> First (Just 1) `mappend` mempty
First {getFirst = Just 1}
Prelude Data.Monoid> mempty `mappend` First (Just 1)
First {getFirst = Just 1}
Prelude Data.Monoid> First (Just 2) `mappend` First (Just 1)
First {getFirst = Just 2}

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

●型クラス Foldable

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

Prelude> :i Foldable
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 [] -- Defined in ‘Data.Foldable’
instance Foldable Maybe -- Defined in ‘Data.Foldable’
instance Foldable (Either a) -- Defined in ‘Data.Foldable’
instance Foldable ((,) a) -- Defined in ‘Data.Foldable’

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

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

Prelude> foldl (+) 0 [1..10]
55
Prelude> foldr (+) 0 [1..10]
55
Prelude> foldr (+) 0 (Just 1)
1
Prelude> foldl (+) 0 (Just 1)
1
Prelude> 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 のデータ型は次のようになります。

Prelude> :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 で実現できます。

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

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

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

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

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


初版 2013 年 3 月 17 日
改訂 2021 年 1 月 24 日

整数の論理演算とビット操作

ML 系 (SML/NJ, OCaml), Haskell, Lisp / Scheme などの関数型言語では、データを表すのにリストがよく使われます。ところが、問題によってはリストよりもビットで表した方が、プログラムを作るのに都合がよい場合もあります。

Haskell の場合、整数の論理演算とビット操作はモジュール Data.Bits を使って行います。Data.Bits には型クラス Bits が定義されていて、Bits のインスタンスであれば Data.Bits で定義されている関数を使用することができます。Data.Bits をインポートすると Integer と Int は Bits のインスタンスになりますが、このほかにモジュール Data.Int と Data.Word をインポートすると、ビットサイズを限定した固定長整数を利用することができます。Data.Int は符号付き整数 (Int8, Int16, Int32, Int64)、Data.Word は無符号整数 (Word, Word8, Word16, Word32, Word64) になります。Word のビットサイズは Int と同じです。

●Data.Bits の関数

Data.Bits に定義されている主な関数を表に示します。

表 : Data.Bits の主な関数
関数名機能
(.&.)Bits a => a -> a -> aビットごとの論理積を返す
(.|.)Bits a => a -> a -> aビットごとの論理和を返す
xorBits a => a -> a -> aビットごとの排他的論理和を返す
complementBits a => a -> aビットを反転する
shiftLBits a => a -> Int -> ashiftL x i は x を i ビット左シフトする
shiftRBits a => a -> Int -> ashiftR x i は x を i ビット右シフト (算術シフト) する
rotateLBits a => a -> Int -> arotateL x i は x を i ビット左回転する
rotateRBits a => a -> Int -> arotateR x i は x を i ビット右回転する
bitBits a => Int -> ai 番目のビットが 1 で、他のビットが 0 のデータを返す
setBitBits a => a -> Int -> ai 番目のビットを 1 にする
clearBitBits a => a -> Int -> ai 番目のビットを 0 にする
complementBitBits a => a -> Int -> acomplement x i は x の i 番目のビットを反転する
testBitBits a => a -> Booli 番目のビットが 1 であれば True を返す
bitSizeBits a => a -> Intビットサイズを返す
isSignedBits a => a -> Bool符号付き整数ならば True を返す
popCountBits a => a -> Intビットが 1 の個数を数える

(.&.) はビットごとの論理積を返します。

Prelude Data.Bits> 5 .&. 3
1
     0101
 AND 0011
---------
     0001

(.l.) はビットごとの論理和を返します。

Prelude Data.Bits> 5 .|. 3
7
    0101
 OR 0011
--------
    0111

xor はビットごとの排他的論理和を返します。

Prelude Data.Bits> 5 `xor` 3
6
     0101
 XOR 0011
---------
     0110

complement はビットごとの論理的な否定を返します。

Prelude Data.Bits> complement 1
-2
Prelude Data.Bits> complement 0
-1
Prelude Data.Bits> :m + Data.Word
Prelude Data.Bits Data.Word> complement (0xffffffff::Word32)
0
Prelude Data.Bits Data.Word> complement (0::Word32)
4294967295

shiftL, shiftR はビットをシフトする演算子で、rotateL, rotateR はビットを回転する演算子です。多倍長整数 (Integer) の場合、rotateL, rotateR は shiftL, shiftR と同じ動作になります。shiftR は算術シフトなので、負の数で i ビット右シフトしたあと、上位 i 個のビットは 1 になります。このほかに、shift, rotate という関数があります。shift x i は i が正の場合は shiftL, 負の場合は shiftR と同じ動作になります。rotate も同じです。

Prelude Data.Bits> shiftL 1 16
65536
Prelude Data.Bits> shiftL 1 32
4294967296
Prelude Data.Bits> shiftR (-65536) 8
-256
Prelude Data.Bits> shiftR (-65536) 15
-2
Prelude Data.Bits> shiftR (-65536) 16
-1
Prelude Data.Bits> rotateL (1::Int) 16
65536
Prelude Data.Bits> rotateL (1::Int) 64
1
Prelude Data.Bits> rotateR (0x80000000::Int) 16
32768
Prelude Data.Bits> rotateR (0x80000000::Int) 32
-9223372036854775808

bit i は i 番目のビットが 1 の整数を生成します。

Prelude Data.Bits> bit 0 :: Int
1
Prelude Data.Bits> bit 16 :: Int
65536
Prelude Data.Bits> bit 63 :: Int
-9223372036854775808

setBit, clearBit, complementBit は次の式と同じ動作になります。

setBit x i = x .|. bit i
clearBit x i = x .&. complement (bit i)
complementBit x i = x `xor` bit i

testBit x i は x の i 番目のビットが 1 ならば True を返します。 popCount はビットが 1 の個数を数えます。

Prelude Data.Bits> testBit (0xf0f0f0f0::Int) 31
True
Prelude Data.Bits> testBit (0xf0f0f0f0::Int) 0
False
Prelude Data.Bits> popCount 0xffff
16
Prelude Data.Bits> popCount 0xffffffff
32
Prelude Data.Bits> popCount (2^64 - 1)
64

●ビットが 1 の位置を求める

それでは簡単な例題として、ビットが 1 の位置をリストに格納して返す関数 bitIndices を作ってみましょう。なお、値が負の場合はビットが 0 の位置を求めることにします。次のリストを見てください。

リスト : ビットが 1 の位置を求める

bitIndices :: (Ord a, Bits a) => a -> [Int]
bitIndices n =
  if n >= 0 then iterP n 0 else iterN n 0
  where
    iterP 0 _ = []
    iterP n i = let xs = iterP (shiftR n 1) (i + 1)
                in if testBit n 0 then i : xs else xs
    iterN (-1) _ = []
    iterN n i = let xs = iterN (shiftR n 1) (i + 1)
                in if testBit n 0 then xs else i : xs

引数 n が 0 以上であれば局所関数 iterP を、そうでなければ iterN を呼び出します。iterP, iterN の引数 i が位置を表します。testBit で 0 番目のビットを調べます。1 の場合、iterP では位置 i をリストに加えます。0 の場合、iterN では i をリストに加えます。iterN, iterP を再帰呼び出しするとき、shiftR で n を 1 ビット右シフトします。shiftR は算術シフトなので、n が負の場合はすべてのビットが 1 となる -1 が再帰の停止条件となります。

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

*Main> bitIndices 0xff
[0,1,2,3,4,5,6,7]
*Main> bitIndices 0xffff
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
*Main> bitIndices (-1)
[]
*Main> bitIndices (-2)
[0]
*Main> bitIndices (-8)
[0,1,2]
*Main> bitIndices (-32)
[0,1,2,3,4]
*Main> bitIndices (-128)
[0,1,2,3,4,5,6]

●組み合わせの生成 (2)

組み合わせの生成は拙作のページ 順列と組み合わせ で説明しました。このほかに、n 個の中から m 個を選ぶ組み合わせは、ビットの 0, 1 で表すことができます。たとえば、5 個の数字 (0 - 4) から 3 個を選ぶ場合、数字を 0 番目 から 4 番目のビットに対応させます。すると、1, 3, 4 という組み合わせは 11010 と表すことができます。簡単な例題として、ビットを使って組み合わせを求めてみましょう。

●プログラムの作成

組み合わせを求めるプログラムは次のようになります。

リスト : 組み合わせの生成

-- ビットで表現する
combination :: Int -> Int -> [Integer]
combination n m = iter n m 0 [] where
  iter _ 0 a xs = a : xs
  iter 0 _ _ xs = xs
  iter n m a xs = 
    iter (n - 1) m a $ iter (n - 1) (m - 1) (setBit a (n - 1)) xs

-- 数値を 2 進数に変換する
toString2 :: Integer -> String
toString2 m = iter m [] where
  iter 0 xs = if null xs then "0" else xs
  iter m xs = iter (m `div` 2) (show (m `mod` 2) ++ xs)

関数 combination は n 個の中から m 個を選ぶ組み合わせを生成し、リストに格納して返します。実際の処理は局所関数 iter で行います。組み合わせは引数 a にセットします。m が 0 になったら、組み合わせがひとつできたので a をリスト xs に格納します。n が 0 になったら選ぶ要素がなくなったので xs をそのまま返します。

あとは iter を再帰呼び出しします。最初の呼び出しは n 番目の数字を選ばない場合です。n - 1 個の中から m 個を選びます。次の呼び出しが n 番目の数字を選ぶ場合で、a の n - 1 番目のビットを 1 にします。そして、n - 1 個の中から m - 1 個を選びます。関数 toString2 は整数値を 2 進数の文字列に変換します。

それでは 5 個の中から 3 個を選ぶ combination 5 3 の実行例を示します。

*Main> combination 5 3
[7,11,13,14,19,21,22,25,26,28]
*Main> map toString2 $ combination 5 3
["111","1011","1101","1110","10011","10101","10110","11001","11010","11100"]

この場合、最小値は 7 (111) で最大値は 28 (11100) になります。このように、combination は組み合わせを表す数を昇順で出力します。

●組み合わせに番号を付ける方法

次は、N 通りある組み合わせに 0 から N - 1 までの番号を付ける方法を紹介しましょう。たとえば、6 個の中から 3 個を選ぶ組み合わせは 20 通りありますが、この組み合わせに 0 から 19 までの番号を付けることができます。1 1 1 0 0 0 を例題に考えてみましょう。次の図を見てください。


    図 : 6C3 の組み合わせ

最初に 5 をチェックします。5 を選ばない場合は 53 = 10 通りありますね。この組み合わせに 0 から 9 までの番号を割り当てることにすると、5 を選ぶ組み合わせの番号は 10 から 19 までとなります。

次に、4 をチェックします。4 を選ばない場合は、42 = 6 通りあります。したがって、5 を選んで 4 を選ばない組み合わせに 10 から 15 までの番号を割り当てることにすると、5 と 4 を選ぶ組み合わせには 16 から 19 までの番号となります。

最後に、3 をチェックします。同様に 3 を選ばない場合は 3 通りあるので、これに 16 から 18 までの番号を割り当て、5, 4, 3 を選ぶ組み合わせには 19 を割り当てます。これで組み合わせ 1 1 1 0 0 0 の番号を求めることができました。

では、0 0 0 1 1 1 はどうなるのでしょうか。左から順番にチェックしていくと、最初の 1 が見つかった時点で、その数字を選ばない組み合わせは存在しません。つまり、残りの数字をすべて選ぶしかないわけです。したがって、これが 0 番目となります。

このように、数字を選ぶときに、数字を選ばない場合の組み合わせの数を足し算していけば、その組み合わせの番号を求めることができるのです。

●組み合わせを番号に変換

組み合わせを番号に変換するプログラムは次のようになります。

リスト : 組み合わせを番号に変換

-- 組み合わせの数を求める
comb :: Int -> Int -> Integer
comb n r = iter (toInteger n) (toInteger r) where
  iter n r
    | n == r || r == 0 = 1
    | otherwise = iter n (r - 1) * (n - r + 1) `div` r

-- 組み合わせを番号に変換する
comb2num :: Int -> Int -> Integer -> Integer
comb2num n r c = iter n r 0 where
  iter n r v
    | r == 0 || n == r  = v
    | testBit c (n - 1) = iter (n - 1) (r - 1) (v + comb (n - 1) r)
    | otherwise         = iter (n - 1) r v

関数 comb2num の引数 c はビットで表した組み合わせ、引数 n と r は nr の n と r を表しています。実際の処理は局所関数 iter で行います。引数 v は求める番号を表します。n と r の値が同じになるか、もしくは r が 0 になれば、組み合わせの番号を計算できたので v を返します。

そうでない場合、c の n - 1 ビットの値を調べます。ビットが 1 であれば、v に comb (n - 1) r の値を足し算し、r を -1 して iter を再帰呼び出しします。そうでなければ、v と r の値はそのままで iter を再帰呼び出しします。

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

*Main> map (comb2num 5 3) $ combination 5 3
[0,1,2,3,4,5,6,7,8,9]
*Main> map (comb2num 6 3) $ combination 6 3
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]
*Main> map (comb2num 6 4) $ combination 6 4
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]

●番号を組み合わせに変換

逆に、番号から組み合わせを求めるプログラムも簡単に作ることができます。次のリストを見てください。

リスト : 番号を組み合わせに変換

num2comb :: Int -> Int -> Integer -> Integer
num2comb n r v = iter v n r 0 where
  iter v n r c
    | r == 0   = c
    | n == r   = c .|. ((shift 1 n) - 1)
    | otherwise = 
        if v >= k
        then iter (v - k) (n - 1) (r - 1) (setBit c (n - 1))
        else iter v (n - 1) r c
        where k = comb (n - 1) r

引数 v が番号で、引数 n と r は nr の n と r を表しています。実際の処理は局所関数 iter で行います。引数 c が求める組み合わせです。たとえば、n = 5, r = 3 の場合、ビットが 1 になるのは 4C2 = 6 通りあり、0 になるのは 4C3 = 4 通りあります。したがって、数値が 0 - 3 の場合はビットを 0 にし、4 - 9 の場合はビットを 1 にすればいいわけです。

ビットを 0 にした場合、残りは 4C3 = 4 通りになるので、同様に次のビットを決定します。ビットを 1 にした場合、残りは 4C2 = 6 通りになるので、v から 4 を引いて iter を再帰呼び出しして次のビットを決定します。

r が 0 の場合は、組み合わせが完成したので c を返します。n と r が等しい場合は、残りのビットをすべて 1 にセットしてから c を返します。それ以外の場合は、n-1Cr の値を comb (n - 1) r で求めて変数 k にセットします。v が k 以上であれば変数 c のビットを 1 にセットし、v から k を引き算して iter を再帰呼び出しします。そうでなければ、iter を再帰呼び出しするだけです。

それでは、n = 5, r = 3 の場合の実行例を示します。

*Main> combination 5 3
[7,11,13,14,19,21,22,25,26,28]
*Main> map (comb2num 5 3) $ combination 5 3
[0,1,2,3,4,5,6,7,8,9]
*Main> map (num2comb 5 3) $ map (comb2num 5 3) $ combination 5 3
[7,11,13,14,19,21,22,25,26,28]

正常に動作していますね。この方法を使うと、n 個ある組み合わせの中の i 番目 (0 <= i < n) の組み合わせを簡単に求めることができます。

●ちょっと便利なビット操作

setBit や clearBit は操作するビットの位置を指定しないといけませんが、最も右側 (LSB) にある 1 を 0 にクリアする、逆に最も右側にある 0 を 1 にセットすることは簡単にできます。

(1) 右側にある 1 をクリア => x .&. (- x)

x     : 1 1 1 1
x - 1 : 1 1 1 0
----------------
 AND  : 1 1 1 0

x     : 1 0 0 0
x - 1 : 0 1 1 1
----------------
 AND  : 0 0 0 0

(2) 右側にある 0 を 1 にセット => x .|. (x + 1)

x     : 0 0 0 0
x + 1 : 0 0 0 1
----------------
  OR  : 0 0 0 1

x     : 0 1 1 1
x - 1 : 1 0 0 0
----------------
  OR  : 1 1 1 1

上図 (1) を見てください。x から 1 を引くと、右側から連続している 0 は桁借りにより 1 になり、最初に出現する 1 が 0 になります。したがって、x .&. (x - 1) を計算すると、最も右側にある 1 を 0 にクリアすることができます。(2) の場合、x に 1 を足すと、右側から連続している 1 は桁上がりにより 0 になり、最初に出現する 0 が 1 になります。x .|. (x + 1) を計算すれば、最も右側にある 0 を 1 にセットすることができます。

また、最も右側にある 1 を取り出すことも簡単にできます。簡単な例として 4 ビットの整数値を考えてみます。負の整数を 2 の補数で表した場合、4 ビットで表される整数は -8 から 7 になります。次の図を見てください。

 0 : 0000
 1 : 0001    -1 : 1111    1 .&. (-1) => 0001
 2 : 0010    -2 : 1110    2 .&. (-2) => 0010
 3 : 0011    -3 : 1101    3 .&. (-3) => 0001
 4 : 0100    -4 : 1100    4 .&. (-4) => 0100
 5 : 0101    -5 : 1011    5 .&. (-5) => 0001
 6 : 0110    -6 : 1010    6 .&. (-6) => 0010
 7 : 0111    -7 : 1001    7 .&. (-7) => 0001
             -8 : 1000


        図 : 最も右側にある 1 を取り出す方法

2 の補数はビットを反転した値 (1 の補数) に 1 を加算することで求めることができます。したがって、x と -x の論理積 (x .&. (-x)) は、最も右側にある 1 だけが残り、あとのビットはすべて 0 になります。

1 の位置が必要な場合は次のように求めることができます。

popCount (m - 1)

m の値を -1 する場合、そのビットは 0 になり、それ以下のビットは 1 になります。あとは、1 になったビットの個数を popCount で求めればよいわけです。

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

Prelude Data.Bits> popCount ((0x1::Int) - 1)
0
Prelude Data.Bits> popCount ((0x80::Int) - 1)
7
Prelude Data.Bits> popCount ((0x800::Int) - 1)
11
Prelude Data.Bits> popCount ((0x8000::Int) - 1)
15

●ビットが 1 の個数を求める

最後に、ビットが 1 の個数を数える処理を作ってみましょう。Data.Bits には popCount がありますが、私たちでも簡単に作ることができます。データ型を Int とすると、プログラムは次のようになります。

リスト : ビットカウント

bitCount :: Int -> Int
bitCount 0 = 0
bitCount n = 1 + bitCount (n .&. (n - 1))

整数 n の右側から順番に 1 をクリアしていき、0 になるまでの回数を求めます。とても簡単ですね。32 個のビットを順番に調べるよりも高速です。

Int を 32 bit とする場合、次の方法で 1 の個数をもっと高速に求めることができます。

リスト : ビットカウント (2)

bitCount' :: Int -> Int
bitCount' n =  (d .&. 0xffff) + shiftR d 16 where
  a = (n .&. 0x55555555) + ((shiftR n 1) .&. 0x55555555)
  b = (a .&. 0x33333333) + ((shiftR a 2) .&. 0x33333333)
  c = (b .&. 0x0f0f0f0f) + ((shiftR b 4) .&. 0x0f0f0f0f)
  d = (c .&. 0x00ff00ff) + ((shiftR c 8) .&. 0x00ff00ff)

最初に、整数を 2 bit ずつに分割して、1 の個数を求めます。たとえば、整数 n を 4 bit で考えてみましょう。5 を 2 進数で表すと 0101 になり、n と論理積を計算すると 0, 2 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。同様に n を 1 ビット右シフトして論理積を計算すると、1, 3 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。あとは、それを足し算すれば 2 bit の中にある 1 の個数を求めることができます。

変数 a には 2 ビットの中の 1 の個数が格納されています。左隣の 2 ビットの値を足し算すれば、4 ビットの中の 1 の個数を求めることができます。次に、左隣の 4 ビットの値を足し算して 8 ビットの中の 1 の個数を求め、左隣の 8 ビットの値を足し算して、というように順番に値を加算していくと 32 ビットの中にある 1 の個数を求めることができます。

bitCount は 1 の個数が多くなると遅くなりますが、bitCount は 1 の個数に関係なく高速に動作します。興味のある方は試してみてください。

●参考 URL

ビットが 1 の個数を数える方法は フィンローダさん初級C言語Q&A(15) を参考にさせていただきました。フィンローダさんに感謝いたします。


初版 2013 年 3 月 17 日
改訂 2021 年 1 月 24 日

Copyright (C) 2013-2021 Makoto Hiroi
All rights reserved.

[ PrevPage | Haskell | NextPage ]