HaskellのMap型、Set型

概要

多くのプログラミング言語でよく利用されMap型(ハッシュ型、キーバリュー型、辞書型、連想配列とも言われる)と、集合演算でよく使われるSet型をHaskellではどのように扱うかをいくつかのケースごとに紹介します。
Haskellでは標準関数としてMap型やSet型が実装されていないため、containersパッケージを事前にinstallする必要があります。

特徴

Map型、Set型は一般的にハッシュテーブルを用いて実装されている場合が多いがHaskellでは平衡二分木で実装されているため、データ構造の操作に関する計算量が異なる。

	ハッシュテーブル	平衡二分木
取得	O(1)	O(logN)
削除	O(1)	O(logN)
挿入	O(1)	O(logN)

計算量ではよく使われるハッシュテーブルに劣る反面、HaskellのMap型、Set型には数多くの強力な関数が用意されており、key-valueの順序関係も保持できるため、リストを扱うよう操作できる点がとても魅力的である。
HaskellのMapのベンチマーク結果はこちらを参照

参考資料

Data.Map-Hackage
Data.Set-Hackage

※本記事では上記の二つの記事の中から利用ケース別にいくつかピックアップして紹介するため、いくつか省いている機能(Map型における集合関数、本記事で載せている関数の類似関数など)が多数あります。より多くの関数や各種関数の計算量を知りたい方やは上記を参照してください。

version

containers >= 0.5.9

本記事では0.6.2.1を扱う。

準備

初めにそれぞれのパッケージをインポートします。

sample.hs

import qualified Data.Map.Strict as M
import qualified Data.Set as S

呼び出しの簡略化のため、ここではMap型をM、Set型をSとして利用します。
またimport qualified Data.Map もありますが、特別な理由がなければData.Map.Strictを使うことが推奨されているようです。

Data.Mapドキュメントの先頭行を抜粋

Note: You should use Data.Map.Strict instead of this module if:

• You will eventually need all the values stored.
• The stored values don't represent large virtual data structures to be lazily computed.

An efficient implementation of ordered maps from keys to values (dictionaries).

qualifiedはPreludeの標準の関数と名前の衝突を避けるために使用します。

Map型

import qualified Data.Map.Strict as M

以降、Map型がインポートされていることを前提に記述する。

使用するデータセット

fruits::[(String,Int)]
fruits = [("apple",1),("orange",2),("banana",3),("peach",4),("cherry",5),("orange",6),("apple",7),("peach",8)]
fruitsMap = M.fromList fruits

ghci環境での実行結果

Prelude M> fruits
[("apple",1),("orange",2),("banana",3),("peach",4),("cherry",5),("orange",6),("apple",7),("peach",8)]
Prelude M> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]

Haskellでは既存の型からMap型を生成する場合、タプル型のリストが用いられ、fstの値がkey,sndの値がvalueに対応してMap型が生成される。Map型の生成にはfromListが用いられる。

fromListの定義

fromList :: Ord k => [(k,a)] -> Map k a

定義より、fstが比較可能な型で、2つの値を持つタプル型であれば変換可能であることがわかる。
また、変換時にfstが重複する場合、最後に表れたfstをkey,その値をvalueとした要素のみが残る。
※例ではfruitsに存在していた、("apple",1)("apple",7)や("peach",4)("peach",8)のうち、後の("apple",7)や("peach",8)のみが残っていることを表している。
同じキーが複数回表れた場合、何らかの処理を適用して前に表れた値についても利用する方法については後述する。
変換時はkeyで昇順ソートされてMap型に変換される。
※fromListの他にも昇順リスト、降順リストなど変換前のリストの状態に応じたMap型への変換関数が用意されているので、詳細はこちらを参照してください。

空Mapの表現(empty)

Data.Mapより抜粋

empty :: Map k a

ghci環境での実行結果

Prelude M Main> M.fromList [] == M.empty
True
Prelude M> M.fromList [("orange",3)] == M.empty
False

単一要素を持ったMapの表現(singleton)

Data.Mapより抜粋

singleton :: k -> a -> Map k a

ghci環境での実行結果

Prelude M> M.singleton "peach" 4 == M.fromList[("peach",4)]
True
Prelude M> M.singleton "peach" 4 == M.fromList [("peach",4),("oraneg",3)]
False

データの参照(lookup,!?,!)

手続き型言語におけるMap.get(key)やMap[key]に相当する操作。

Data.Mapより抜粋

lookup :: Ord k => k -> Map k a -> Maybe a

ghci環境での実行結果

Prelude M Main> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]
Prelude M Main> M.lookup "orange" fruitsMap
Just 6
Prelude M Main> M.lookup "beef" fruitsMap
Nothing

Data.Mapより抜粋

(!?) :: Ord k => Map k a -> k -> Maybe a

ghci環境での実行結果

Prelude M Main> fruitsMap M.!? "orange"
Just 6
Prelude M Main> fruitsMap M.!? "beef"
Nothing

Data.Mapより抜粋

(!) :: Ord k => Map k a -> k -> a

ghci環境での実行結果

Prelude M Main> fruitsMap M.! "orange"
6
Prelude M Main> fruitsMap M.! "beef"
*** Exception: Map.!: given key is not an element in the map
CallStack (from HasCallStack):
  error, called at libraries/containers/containers/src/Data/Map/Internal.hs:627:17 in containers-0.6.2.1:Data.Map.Internal

lookupや!?はキーが存在しないことを考慮しているのに対し、!は直接の値を取得しているため、存在しないときはエラーとなる

データの追加(insert)

手続き型言語におけるMap.set(key,value)やMap[key]=valueに相当する操作。

Data.Mapより抜粋

insert :: Ord k => k -> a -> Map k a -> Map k a

ghci環境での実行結果

Prelude M> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]
Prelude M Main> M.insert "grape" 1 fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("grape",1),("orange",6),("peach",8)]
Prelude M Main> M.insert "orange" 1 fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",1),("peach",8)]
Prelude M Main> M.insert "kiwi" 10 empty
fromList [("kiwi",10)]

データの挿入はkeyの昇順ソート順で適切な位置に挿入される。すでに存在しているキーに対してinsertした場合は新しいkey,valueで上書きされる。

データの削除(delete)

Data.Mapより抜粋

delete :: Ord k => k -> Map k a -> Map k a

ghci環境での実行結果

Prelude M Main> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]
Prelude M Main> M.delete "orange" fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("peach",8)]
Prelude M Main> M.delete "beef" fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]

存在しないものを削除しようとした場合は、そのままのMapを返す。

データの存在チェック(member)

手続き型言語におけるMap.has(key)に相当する操作。

Data.Mapより抜粋

member :: Ord k => k -> Map k a -> Bool

ghci環境での実行結果

Prelude M Main> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]
Prelude M Main> M.member "orange" fruitsMap
True
Prelude M Main> M.member "beef" fruitsMap
False

memberはkeyが存在する場合はTrue,存在しない場合はFalseを返す。

データ値の更新(update)

Data.Mapより抜粋

update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a

ghci環境での実行結果

Prelude M> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]
Prelude M> M.update (\x -> Just (x+100)) "cherry" fruitsMap
fromList [("apple",7),("banana",3),("cherry",105),("orange",6),("peach",8)]
Prelude M> M.update (\x -> Just (x+100)) "beef" fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]

insertによる更新との違いは現在設定しているvalueを元に適用する操作を変えることができる。

keyリストの取得(keys)

Data.Mapより抜粋

keys  :: Map k a -> [k]

ghci環境での実行結果

Prelude M Main> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]
Prelude M Main> M.keys fruitsMap
["apple","banana","cherry","orange","peach"]

これはお馴染みの書き方。

valueリストの取得(elems)

Data.Mapより抜粋

elems :: Map k a -> [a]

ghci環境での実行結果

Prelude M Main> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]
Prelude M Main> M.elems fruitsMap
[7,3,5,6,8]

リストへの変換(toList)

Data.Mapより抜粋

toList :: Map k a -> [(k,a)]

ghci環境での実行結果

Prelude M> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]
Prelude M> toList fruitsMap
[("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]

toAscListやtoDescListを使えばソートも可能

キー、バリューリスト<`(k,[a])`型>(fromListWith)への変換

Data.Mapより抜粋

fromListWith :: Ord k => (a -> a -> a) -> [(k,a)] -> Map k a

ghci環境での実行結果

Prelude M> fruits
[("apple",1),("orange",2),("banana",3),("peach",4),("cherry",5),("orange",6),("apple",7),("peach",8)]
Prelude M> M.fromListWith (++) $ map (\(k,v) -> (k, [v])) fruits
fromList [("apple",[7,1]),("banana",[3]),("cherry",[5]),("orange",[6,2]),("peach",[8,4])

fromListWithではMap型生成時にlambdaを渡せるため、keyが重複した場合の挙動を記述できる

重複したキーの値の和を求めたい場合には以下のようにも書ける

Data.Mapより抜粋

Prelude M> M.fromListWith (+) fruits
fromList [("apple",8),("banana",3),("cherry",5),("orange",8),("peach",12)]

高階関数の適用(map,foldl,filter)

Data.Mapより抜粋

map :: (a -> b) -> Map k a -> Map k b
mapKeys :: Ord k2 => (k1->k2) -> Map k1 a -> Map k2 a
foldl :: (a -> b -> a) -> a -> Map k b -> a

ghci環境での実行結果

Prelude M> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]
Prelude M> M.map (+1) fruitsMap
fromList [("apple",8),("banana",4),("cherry",6),("orange",7),("peach",9)]
Prelude M> M.mapKeys ("F." ++ ) fruitsMap
fromList [("F.apple",7),("F.banana",3),("F.cherry",5),("F.orange",6),("F.peach",8)]
Prelude M> M.foldl (+) 0 fruitsMap
29
Prelude M>  M.foldlWithKey (\acc k v->acc ++ (k ++ "=" ++show v)) [] fruitsMap
"apple=7banana=3cherry=5orange=6peach=8"
Prelude M> M.filter (> 5) (fruitsMap)
fromList [("apple",7),("orange",6),("peach",8)]
Prelude M> M.filterWithKey (\x _-> length x > 5) fruitsMap
fromList [("banana",3),("cherry",5),("orange",6)]

リストで用意されているようなmap,foldl,foldr,filterがMap型にもそのまま適用できる。
key,value,またはその両方に適用できるような関数が各種に用意されている。

サイズを取得する（size)

Data.Mapより抜粋

size :: Map k a -> Int

ghci環境での実行結果

Prelude M> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]
Prelude M> M.size fruitsMap
5

keyの最小、最大を取得(lookupMax,lookupMin,findMax,findMin)

Data.Mapより抜粋

lookupMin :: Map k a -> Maybe (k,a)
lookupMax :: Map k a -> Maybe (k, a)
findMin :: Map k a -> (k,a)
findMax :: Map k a -> (k,a)

ghci環境での実行結果

Prelude M> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]
Prelude M> M.lookupMin fruitsMap
Just ("apple",7)
Prelude M> M.lookupMax fruitsMap
Just ("peach",8)
Prelude M> M.lookupMax M.empty
Nothing
Prelude M> M.findMin fruitsMap
("apple",7)
Prelude M> M.findMax fruitsMap
("peach",8)
Prelude M> M.findMax M.empty
*** Exception: Map.findMax: empty map has no maximal element
CallStack (from HasCallStack):
  error, called at libraries/containers/containers/src/Data/Map/Internal.hs:1672:17 in containers-0.6.2.1:Data.Map.Internal

valueに対して最小、最大を取ってくるものは残念ながら存在しないため、事前にimport Data.turple (swap)を用いて、key-valueを入れ替えておく必要がありそう。これはおそらく、Map型の定義より、valueには順序付きの制約(Ord)がないためだと思われる。

keyからIndexを取得(lookupIndex,findIndex)

Data.Mapより抜粋

lookupIndex :: Ord k => k -> Map k a -> Maybe Int
findIndex :: Ord k => k -> Map k a -> Int

ghci環境での実行結果

Prelude M> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]
Prelude M> M.lookupIndex "cherry" fruitsMap
Just 2
Prelude M> M.lookupIndex "beef" fruitsMap
Nothing
Prelude M> M.findIndex "cherry" fruitsMap
2
Prelude M> M.findIndex "beef" fruitsMap
*** Exception: Map.findIndex: element is not in the map
CallStack (from HasCallStack):
  error, called at libraries/containers/containers/src/Data/Map/Internal.hs:1457:23 in containers-0.6.2.1:Data.Map.Internal

keyを指定することで、その要素のindexを取得する。ハッシュテーブルで実装されたMapには順序関係は存在しないため、HaskellにおけるMap型ならでは機能である。

indexから要素(key-value)を取得(elemAt)

Data.Mapより抜粋

elemAt :: Int -> Map k a -> (k,a)

ghci環境での実行結果

Prelude M> fruitsMap
fromList [("apple",7),("banana",3),("cherry",5),("orange",6),("peach",8)]
Prelude M> M.elemAt 0 fruitsMap
("apple",7)
Prelude M> M.elemAt 3 fruitsMap
("orange",6)
Prelude M> M.elemAt 5 fruitsMap
*** Exception: Map.elemAt: index out of range
CallStack (from HasCallStack):
  error, called at libraries/containers/containers/src/Data/Map/Internal.hs:1498:17 in containers-0.6.2.1:Data.Map.Internal

指定したindexに対応する要素をMapから取得する。ハッシュテーブルで実装されたMapには順序関係は存在しないため、HaskellにおけるMap型ならでは機能である。

Set型

import Data.Set as S

以降、Set型がインポートされていることを前提に記述する

使用するデータセット

universeOne = ["comet","earth","jupiter","mars","venus","mars","venus"]
universeTwo = ["star","jupiter","meteor","comet","planet"]
universeOneSet = S.fromList universeOne
universeTwoSet = S.fromList universeTwo

Map型と同様、fromListを用いることでSet型に変換でき、変換時に昇順ソートされる。

Prelude S> universeOne
["comet","earth","jupiter","mars","venus","mars","venus"]
Prelude S> universeOneSet
fromList ["comet","earth","jupiter","mars","venus"]

基本的な操作に対する関数名はMap型とほとんど同じものであるが、Set型についてもケース別に記載する

空Setの表現(empty)

Data.Setより抜粋

empty  :: Set a

ghci環境での実行結果

Prelude S> S.empty == S.fromList []
True

単一要素を持ったSetの表現(singleton)

Data.Setより抜粋

singleton :: a -> Set a

ghci環境での実行結果

Prelude S> S.singleton "comet" == S.fromList ["comet"]
True

データの追加(insert)

Data.Setより抜粋

insert :: Ord a => a -> Set a -> Set a

ghci環境での実行結果

Prelude S> universeOneSet
fromList ["comet","earth","jupiter","mars","venus"]
Prelude S> S.insert "cosmos" universeOneSet
fromList ["comet","cosmos","earth","jupiter","mars","venus"]

データの削除(delete)

Data.Setより抜粋

delete :: Ord a => a -> Set a -> Set a

ghci環境での実行結果

Prelude S> universeOneSet
fromList ["comet","earth","jupiter","mars","venus"]
Prelude S> S.delete "mars" universeOneSet
fromList ["comet","earth","jupiter","venus"]

データの存在チェック(member)

Data.Setより抜粋

member :: Ord k => k -> Map k a -> Bool

ghci環境での実行結果

Prelude S> universeOneSet
fromList ["comet","earth","jupiter","mars","venus"]
Prelude S> S.member "jupiter" universeOneSet
True
Prelude S> S.member "cosmos" universeOneSet
False

リストへの変換(toList)

Data.Setより抜粋

toList :: Set a -> [a]

ghci環境での実行結果

Prelude S> universeOneSet
fromList ["comet","earth","jupiter","mars","venus"]
Prelude S> S.toList universeOneSet
["comet","earth","jupiter","mars","venus"]

サイズを取得する(size)

Data.Setより抜粋

size :: Set a -> Int

ghci環境での実行結果

Prelude S> universeOneSet
fromList ["comet","earth","jupiter","mars","venus"]
Prelude S> S.size universeOneSet
5

高階関数(map,filter,foldl)

Data.Setより抜粋

map :: Ord b => (a->b) -> Set a -> Set b
filter :: (a -> Bool) -> Set a -> Set a
foldl :: (a -> b -> a) -> a -> Set b -> a

ghci環境での実行結果

Prelude S> S.map (\x -> "U." ++ x) universeOneSet
fromList ["U.comet","U.earth","U.jupiter","U.mars","U.venus"]
Prelude S> S.filter (\x -> length x == 5) universeOneSet
fromList ["comet","earth","venus"]
Prelude S> S.foldl (++) [] universeOneSet
"cometearthjupitermarsvenus"

Map型と同様にリストのように高階関数が取り扱える。

集合演算(union,difference,intersection)

Data.Setより抜粋

union :: Ord a => Set a -> Set a -> Set a
difference :: Ord a => Set a -> Set a -> Set a
intersection :: Ord a => Set a -> Set a -> Set a

ghci環境での実行結果

Prelude S> universeOneSet
fromList ["comet","earth","jupiter","mars","venus"]
Prelude S> universeTwoSet
fromList ["comet","jupiter","meteor","planet","star"]
Prelude S> S.union universeOneSet universeTwoSet
fromList ["comet","earth","jupiter","mars","meteor","planet","star","venus"]
Prelude S> S.difference universeOneSet universeTwoSet
fromList ["earth","mars","venus"]
Prelude S> S.intersection universeOneSet universeTwoSet
fromList ["comet","jupiter"]

union、difference、intersectionはそれぞれ二つの集合の和集合、差集合、積集合した結果を返す。

部分集合かどうかチェック(isSubsetOf)

Data.Setより抜粋

isSubsetOf :: Ord a => Set a -> Set a -> Bool

ghci環境での実行結果

Prelude S> universeOneSet
fromList ["comet","earth","jupiter","mars","venus"]
Prelude S> S.isSubsetOf (S.fromList ["mars","earth"]) universeOneSet
True
Prelude S> S.isSubsetOf (S.fromList ["mars","cosmos"]) universeOneSet
False
Prelude S> S.isSubsetOf S.empty universeOneSet
True
Prelude S> S.isSubsetOf S.empty S.empty
True
Prelude S> S.isSubsetOf universeOneSet universeOneSet
True

isSubsetOfはisSubsetOf A Bに対してAがBの部分集合である場合はTrue,そうでない場合はFalseを返す。

終わりに

本記事ではHaskellにおけるMap型、Set型で用意されている操作関数の中で、手続き型言語でもお馴染みの操作パターンを例にいくつか紹介しました。HaskellではMap型を用いるような操作はTurple型リストで解決できる場合が多いので、出番があるかどうかは作り手次第によると思いますが、Map型を利用する場合の名前確認表に本記事をご利用頂ければと思います。Map型を利用する場合は基本操作に対する計算量がO(1)ではなくO(logN)であること(操作によってはO(N)やO(NlogN)のものもあります)を十分考慮して設計してください。
また、公式ドキュメントには本記事で載せなかった亜種が多数存在しますので、よりニッチな利用ケースには参考資料の公式ページをご利用ください。