1. RunEagler

    Posted

    RunEagler
Changes in title
+HaskellにおけるMap型、Set型
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,565 @@
+## 概要
+
+多くのプログラミング言語でよく利用されMap型(ハッシュ型、キーバリュー型、辞書型、連想配列とも言われる)と、集合演算でよく使われるSet型をHaskellではどのように扱うかをいくつかのケースごとに紹介します。
+Haskellでは標準関数としてMap型やSet型が実装されていないため、[containers](http://hackage.haskell.org/package/containers)パッケージを事前にinstallする必要があります。
+
+## 特徴
+
+Map型、Set型は一般的にハッシュテーブルを用いて実装されている場合が多いがHaskellでは平衡二分木で実装されているため、データ構造の操作に関する計算量が異なる。
+
+| | ハッシュテーブル | 平衡二分木 |
+|:----------------:|:-----------------:|:------------------:|
+| 取得 | O(1)| O(logN) |
+| 削除   | O(1) | O(logN) |
+| 挿入 | O(1) | O(logN) |
+
+計算量ではよく使われるハッシュテーブルに劣る反面、HaskellのMap型、Set型には数多くの強力な関数が用意されており、key-valueの順序関係も保持できるため、リストを扱うよう操作できる点がとても魅力的である。
+HaskellのMapのベンチマーク結果は[こちら](https://github.com/haskell-perf/dictionaries)を参照
+
+## 参考資料
+[Data.Map-Hackage](https://hackage.haskell.org/package/containers-0.6.2.1/docs/Data-Map.html)
+[Data.Set-Hackage](http://hackage.haskell.org/package/containers-0.6.2.1/docs/Data-Set.html)
+
+※本記事では上記の二つの記事の中から利用ケース別にいくつかピックアップして紹介するため、いくつか省いている機能(Map型における集合関数、本記事で載せている関数の類似関数など)が多数あります。より多くの関数や各種関数の計算量を知りたい方やは上記を参照してください。
+
+## version
+
+```
+containers >= 0.5.9
+```
+本記事では`0.6.2.1`を扱う。
+## 準備
+初めにそれぞれのパッケージをインポートします。
+
+```haskell: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型
+
+```haskell
+import qualified Data.Map.Strict as M
+```
+以降、Map型がインポートされていることを前提に記述する。
+
+## 使用するデータセット
+
+```haskell
+fruits::[(String,Int)]
+fruits = [("apple",1),("orange",2),("banana",3),("peach",4),("cherry",5),("orange",6),("apple",7),("peach",8)]
+fruitsMap = M.fromList fruits
+```
+```haskell: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```が用いられる。
+
+```haskell: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型への変換関数が用意されているので、詳細は[こちら](https://hackage.haskell.org/package/containers-0.6.2.1/docs/Data-Map.html)を参照してください。
+
+## 空Mapの表現(empty)
+
+```haskell:Data.Mapより抜粋
+empty :: Map k a
+```
+```haskell:ghci環境での実行結果
+Prelude M Main> M.fromList [] == M.empty
+True
+Prelude M> M.fromList [("orange",3)] == M.empty
+False
+```
+
+## 単一要素を持ったMapの表現(singleton)
+
+```haskell:Data.Mapより抜粋
+singleton :: k -> a -> Map k a
+```
+```haskell: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]`に相当する操作。
+
+```haskell:Data.Mapより抜粋
+lookup :: Ord k => k -> Map k a -> Maybe a
+```
+```haskell: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
+```
+
+```haskell:Data.Mapより抜粋
+(!?) :: Ord k => Map k a -> k -> Maybe a
+```
+```haskell:ghci環境での実行結果
+Prelude M Main> fruitsMap M.!? "orange"
+Just 6
+Prelude M Main> fruitsMap M.!? "beef"
+Nothing
+```
+
+```haskell:Data.Mapより抜粋
+(!) :: Ord k => Map k a -> k -> a
+```
+```haskell: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`に相当する操作。
+
+```haskell:Data.Mapより抜粋
+insert :: Ord k => k -> a -> Map k a -> Map k a
+```
+```haskell: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)
+
+```haskell:Data.Mapより抜粋
+delete :: Ord k => k -> Map k a -> Map k a
+```
+```haskell: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)に相当する操作。
+
+```haskell:Data.Mapより抜粋
+member :: Ord k => k -> Map k a -> Bool
+```
+
+```haskell: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)
+```haskell:Data.Mapより抜粋
+update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
+```
+```haskell: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)
+
+```haskell:Data.Mapより抜粋
+keys :: Map k a -> [k]
+```
+```haskell: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)
+
+```haskell:Data.Mapより抜粋
+elems :: Map k a -> [a]
+```
+```haskell: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)
+
+```haskell:Data.Mapより抜粋
+toList :: Map k a -> [(k,a)]
+```
+```haskell: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)への変換
+
+```haskell:Data.Mapより抜粋
+fromListWith :: Ord k => (a -> a -> a) -> [(k,a)] -> Map k a
+```
+```haskell: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が重複した場合の挙動を記述できる
+
+重複したキーの値の和を求めたい場合には以下のようにも書ける
+
+```haskell:Data.Mapより抜粋
+Prelude M> M.fromListWith (+) fruits
+fromList [("apple",8),("banana",3),("cherry",5),("orange",8),("peach",12)]
+```
+
+## 高階関数の適用(map,foldl,filter)
+
+```haskell: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
+```
+```haskell: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)
+
+```haskell:Data.Mapより抜粋
+size :: Map k a -> Int
+```
+```haskell: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)
+
+```haskell: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)
+```
+```haskell: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)
+```haskell:Data.Mapより抜粋
+lookupIndex :: Ord k => k -> Map k a -> Maybe Int
+findIndex :: Ord k => k -> Map k a -> Int
+```
+```haskell: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)
+
+```haskell:Data.Mapより抜粋
+elemAt :: Int -> Map k a -> (k,a)
+```
+
+```haskell: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型
+
+```haskell
+import Data.Set as S
+```
+以降、Set型がインポートされていることを前提に記述する
+
+## 使用するデータセット
+
+```haskell
+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型に変換でき、変換時に昇順ソートされる。
+
+```haskell
+Prelude S> universeOne
+["comet","earth","jupiter","mars","venus","mars","venus"]
+Prelude S> universeOneSet
+fromList ["comet","earth","jupiter","mars","venus"]
+```
+
+基本的な操作に対する関数名はMap型とほとんど同じものであるが、Set型についてもケース別に記載する
+
+## 空Setの表現(empty)
+
+```haskell:Data.Setより抜粋
+empty :: Set a
+```
+
+```haskell:ghci環境での実行結果
+Prelude S> S.empty == S.fromList []
+True
+```
+
+## 単一要素を持ったSetの表現(singleton)
+
+```haskell:Data.Setより抜粋
+singleton :: a -> Set a
+```
+
+```haskell:ghci環境での実行結果
+Prelude S> S.singleton "comet" == S.fromList ["comet"]
+True
+```
+
+## データの追加(insert)
+
+```haskell:Data.Setより抜粋
+insert :: Ord a => a -> Set a -> Set a
+```
+
+```haskell:ghci環境での実行結果
+Prelude S> universeOneSet
+fromList ["comet","earth","jupiter","mars","venus"]
+Prelude S> S.insert "cosmos" universeOneSet
+fromList ["comet","cosmos","earth","jupiter","mars","venus"]
+```
+
+## データの削除(delete)
+
+```haskell:Data.Setより抜粋
+delete :: Ord a => a -> Set a -> Set a
+```
+```haskell:ghci環境での実行結果
+Prelude S> universeOneSet
+fromList ["comet","earth","jupiter","mars","venus"]
+Prelude S> S.delete "mars" universeOneSet
+fromList ["comet","earth","jupiter","venus"]
+```
+
+## データの存在チェック(member)
+
+```haskell:Data.Setより抜粋
+member :: Ord k => k -> Map k a -> Bool
+```
+
+```haskell: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)
+
+```haskell:Data.Setより抜粋
+toList :: Set a -> [a]
+```
+
+```haskell:ghci環境での実行結果
+Prelude S> universeOneSet
+fromList ["comet","earth","jupiter","mars","venus"]
+Prelude S> S.toList universeOneSet
+["comet","earth","jupiter","mars","venus"]
+```
+
+## サイズを取得する(size)
+
+```haskell:Data.Setより抜粋
+size :: Set a -> Int
+```
+
+```haskell:ghci環境での実行結果
+Prelude S> universeOneSet
+fromList ["comet","earth","jupiter","mars","venus"]
+Prelude S> S.size universeOneSet
+5
+```
+### 高階関数(map,filter,foldl)
+
+```haskell: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
+```
+
+```haskell: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)
+
+```haskell: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
+```
+
+```haskell: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)
+
+```haskell:Data.Setより抜粋
+isSubsetOf :: Ord a => Set a -> Set a -> Bool
+```
+
+```haskell: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)のものもあります)を十分考慮して設計してください。
+また、公式ドキュメントには本記事で載せなかった亜種が多数存在しますので、よりニッチな利用ケースには参考資料の公式ページをご利用ください。
+
+
+
+