キーの型に合わせて最適化できるMapを作る

　containersパッケージは今のところ，この2回で説明した汎用的なMap型とInt型のキーに特化したIntMap型しか提供していません。実際のプログラミングでは，効率よく処理を行うために，キーの型に特化したMapが必要になることもあります。

　例えば，長い文字列をキーとして使う場合，汎用的なMap型ではなく，文字列の検索に適したトライ木などのデータ構造のほうがよいでしょう（参考リンク1，参考リンク2）。さらに，性能を向上させるために文字列としてStringではなくByteStringを使う場合には，ByteStringに特化した実装のほうが適しています（参考リンク）。

　特定の型に対して最適なデータ構造を選ぶというやり方は，単純な型であれば問題ありません。しかし，実際のプログラミングでは，(Int,ByteString)のように複数の型を組み合わせたり，ユーザーが新しい型を定義したりすることも少なくはありません。このような場合，汎用的なMapしか選択肢がないのは望ましくありません。「キーが(Int,ByteString)型であれば，Int型とByteString型に特化する」というように，型が保持するすべての情報を生かすMapがほしくなります。

　キーの型に特化したMapを定義するには，第28回のコラムで触れた型族を利用できます。型族は，型を引数に取って型を返す「型関数」を定義する機能です。型族を使えば，型が持っているデータを基に，その型をキーとして使う場合に最適な実装を持つMapを作れます（参考リンク1，参考リンク2）。

　例を見ましょう。HaskellWikiにあるGMap（Generic Map）の実装を少し改良したコードを以下に示します。

{-# LANGUAGE TypeFamilies, KindSignatures #-}
{-# LANGUAGE FlexibleInstances, UndecidableInstances, OverlappingInstances #-}
module Gmap where
import Prelude hiding (lookup, null)
import Data.Char (ord)
import qualified Data.Map
import qualified Data.IntMap

-- Generic maps as ATs
-- -------------------

-- data family GMap k :: * -> *
class GMapKey k where
  data GMap k :: * -> *
  empty       :: GMap k v
  singleton   :: k -> v -> GMap k v
  lookup      :: k -> GMap k v -> Maybe v
  insert      :: k -> v -> GMap k v -> GMap k v
  delete      :: k -> GMap k v -> GMap k v
  -- null gm = size gm == 0
  null        :: GMap k v -> Bool

-- data instance GMap Int v = GMapInt (Data.IntMap.IntMap v)
instance GMapKey Int where
  data GMap Int v        = GMapInt (Data.IntMap.IntMap v)
  empty                  = GMapInt Data.IntMap.empty
  singleton k v          = GMapInt (Data.IntMap.singleton k v)
  lookup k   (GMapInt m) = Data.IntMap.lookup k m
  insert k v (GMapInt m) = GMapInt (Data.IntMap.insert k v m)
  delete k   (GMapInt m) = GMapInt (Data.IntMap.delete k m)
  null       (GMapInt m) = Data.IntMap.null m

　型族を利用するには，LANGUAGE指示文や-XオプションでTypeFamiliesを指定する必要があります。この例ではLANGUAGE指示文を使ってTypeFamiliesを指定しています。

　「GMap」が型族を使って書かれた型関数です。型族の記述には，型クラスに所属させる関連型形式と，型クラスから独立した場所に記述する形式の2種類があります。同じ型関数は，すべて同一の形式で記述する必要があります。ここでは関連型形式を採用し，GMapKeyクラスやGMapKeyクラスのインスタンスの外に，型関数のGMapを独立させる場合の記述をコメントとして載せておきました。

　GMapKeyクラスのGMapの定義を見てみましょう。型族では，種を指定しない場合は*という種だと見なされるため，「data GMap k :: * -> *」と「GMap k」の種を示しています。種を記述していないkには「*」という種が与えられるため，GMap全体の種は「* -> * -> *」になります。このような種注釈は，LANGUAGE指示文または-XオプションでKindSignaturesを指定することで利用できます（GHC 6.10.4ではKindSignaturesなしで型族に対して種注釈を記述できますが，KnidSignaturesを指定しておけば，種をソースコード内に記述していることを明確に示せます）。

　GMapの定義は，第28回で示した例とは異なり，「type (family) GMap ...」ではなく「data (family) GMap ...」になっています。これは，GMapを適用したときに結果となる型からGMapを取り除くのではなく，GMapを適用した結果としてGMapIntデータ構成子などを持つGMap型が新しく作成されて残ることを意味しています。

　GMapKeyクラスのインスタンスでは，個々のインスタンスである型に対するGMapの定義を書いています。GMapKeyクラスのInt型に対するインスタンスにある「data GMap Int v = GMapInt (Data.IntMap.IntMap v)」という式は，キーとしてInt型を使用すると，GMapをInt型に適用し，GMapIntデータ構成子にData.IntMapモジュールのIntMap型を保持した結果をGMap型として返す，という意味です。この結果，Int型をキーとする処理では，IntMapが実際の実装として使われます。

　GMapの内容を取り出すunGMap関数を作成して，動作を確認してみましょう。

*Gmap> let t = insert (4::Int) "d" $ empty
*Gmap> :t t
t :: GMap Int [Char]
*Gmap> let unGMap (GMapInt x) = x
*Gmap> :t unGMap t
unGMap t :: Data.IntMap.IntMap [Char]

　unGMap tの型である「Data.IntMap.IntMap [Char]」から，Int型をキーとして利用した場合には，GMapIntデータ構成子にIntMap型を保持したものをGMap型として利用していることがわかります。

　同様に，空の状態を意味する( )型に対してGMapKeyクラスのインスタンスとGMapを記述することで，( )に特化したMapとしてMaybe型を利用できます。

-- data instance GMap () v = GMapUnit (Maybe v)
instance GMapKey () where
  data GMap () v           = GMapUnit (Maybe v)
  empty                    = GMapUnit Nothing
  singleton () v           = GMapUnit $ Just v
  lookup ()   (GMapUnit v) = v
  insert () v (GMapUnit _) = GMapUnit $ Just v
  delete ()   (GMapUnit _) = GMapUnit Nothing
  null   (GMapUnit Nothing) = True
  null   (GMapUnit _)       = False

*Gmap> let t' = insert () False $ empty
*Gmap> :t t'
t' :: GMap () Bool
*Gmap> let unGMap' (GMapUnit x) = x
*Gmap> :t unGMap' t'
unGMap' t' :: Maybe Bool

　( )型は無引数のデータ構成子である( )だけを値として持つため，( )をキーとして使う場合には，Mapから値を引き出すときに比較すべきものがありません。そこでMaybe型を利用して，Mapが「値を保持するか」「値を保持しないか」だけを表現しているのです。

　また，ある型に特化したMapが存在しない場合には，Ordクラスを使って汎用的なData.MapモジュールのMap型を利用するように定義することもできます。Ordクラスのインスタンスをキーとして利用するには，FlexibleInstances，UndecidableInstances，OverlappingInstancesの三つの拡張機能が必要になります。これらの拡張機能について詳しく知りたい方は，GHCのマニュアルを参照してください（参考リンク）。

{-# LANGUAGE FlexibleInstances, UndecidableInstances, OverlappingInstances #-}
～　略　～
-- data instance (Ord k) => GMap k v = GMapOrd (Data.Map.Map k v)
instance (Ord k) => GMapKey k where
  data (Ord) => GMap k v  = GMapOrd (Data.Map.Map k v)
  empty                  = GMapOrd Data.Map.empty
  singleton k v          = GMapOrd (Data.Map.singleton k v)
  lookup k   (GMapOrd m) = Data.Map.lookup k m
  insert k v (GMapOrd m) = GMapOrd (Data.Map.insert k v m)
  delete k   (GMapOrd m) = GMapOrd (Data.Map.delete k m)
  null       (GMapOrd m) = Data.Map.null m

　ここまでの説明で，最適なMap実装を型族が自動的に選択してくれることはわかりました。では，(Int,a)のようなデータ型に特化したMapを作成するにはどうすればよいでしょうか？

　(Int,a)の場合，Int型の値とa型の値を比較することで全体的な比較結果を得られます。したがって，Int型をキーとしてMapを取り出し，取り出したMapからa型のキーで結果を取り出す入れ子のMapを定義することで，Int型とa型に特化したMapを作成できます。

-- data instance GMap (a, b) v = GMapPair (GMap a (GMap b v))
instance (GMapKey a, GMapKey b) => GMapKey (a, b) where
  data GMap (a, b) v            = GMapPair (GMap a (GMap b v))
  empty                         = GMapPair empty
  singleton (a, b) v            = GMapPair $ singleton a (singleton b v)
  lookup (a, b)   (GMapPair gm) = lookup a gm >>= lookup b 
  insert (a, b) v (GMapPair gm) = GMapPair $ case lookup a gm of
                                    Nothing  -> insert a (insert b v empty) gm
                                    Just gm2 -> insert a (insert b v gm2  ) gm
  delete (a, b)   (GMapPair gm) = GMapPair $ case lookup a gm of
                                    Nothing  -> delete a gm
                                    Just gm2 -> if null gm2
                                                  then delete a gm
                                                  else insert a (delete b gm2) gm
  null   (GMapPair gm)          = null gm

　GMap (a,b)の定義で「GMap a (GMap b v)」という入れ子のMapを作成しています。また，GMapの定義にGMap自身が出てくることからわかるように，GMapは再帰的に適用されます。aまたはbがIntや( )などに特化したMapを持つものであれば，GMapが再帰的に適用される中でこうしたMapの実装が使われます。GMapを再帰的に適用した結果，aとbの両方に最適化された入れ子のMapが最終的に作成されるのです。

*Gmap> let t'' = insert (4::Int,()) "d" $ empty
*Gmap> :t t''
t'' :: GMap (Int, ()) [Char]
*Gmap> let unGMap'' (GMapPair x) = x
*Gmap> :t unGMap'' t''
unGMap'' t'' :: GMap Int (GMap () [Char])
*Gmap> :t unGMap $ unGMap'' t''
unGMap $ unGMap'' t'' :: Data.IntMap.IntMap (GMap () [Char])
*Gmap> let t''' = insert ((),4::Int) "d" $ empty
*Gmap> :t t'''
t''' :: GMap ((), Int) [Char]
*Gmap> :t unGMap'' t'''
unGMap'' t''' :: GMap () (GMap Int [Char])
*Gmap> :t unGMap' $ unGMap'' t'''
unGMap' $ unGMap'' t''' :: Maybe (GMap Int [Char])

　(a,b)からunGMap*を使って取り出した結果が，aとbそれぞれの型に特化したMapになっているのがわかります。

　一方，Eitherのような複数のデータ構成子を持つデータ型では，まずデータ構成子を比較し，データ構成子が持つフィールドを比較することで結果を得ます。したがって，データ構成子と同じ数だけMapを持たせ，データ構成子ごとに再帰的にGMapを適用するように定義することで，各データ構成子に特化した実装を持つMapを実現できます。

-- data instance GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)
instance (GMapKey a, GMapKey b) => GMapKey (Either a b) where
  data GMap (Either a b) v                = GMapEither (GMap a v) (GMap b v)
  empty                                   = GMapEither empty empty
  singleton (Left  a) v                   = GMapEither (singleton a v) empty
  singleton (Right b) v                   = GMapEither empty (singleton b v)
  lookup (Left  a) (GMapEither gm1 _   )  = lookup a gm1
  lookup (Right b) (GMapEither _   gm2 )  = lookup b gm2
  insert (Left  a) v (GMapEither gm1 gm2) = GMapEither (insert a v gm1) gm2
  insert (Right b) v (GMapEither gm1 gm2) = GMapEither gm1 (insert b v gm2)
  delete (Left  a)   (GMapEither gm1 gm2) = GMapEither (delete a gm1) gm2
  delete (Right b)   (GMapEither gm1 gm2) = GMapEither gm1 (delete b gm2)
  null             (GMapEither gm1  gm2)  = null gm1 || null gm2

*Gmap> let t'''' = insert (Left 4::Either Int ()) "d" $ empty
*Gmap> :t t''''
t'''' :: GMap (Either Int ()) [Char]
*Gmap> let unGMap''' (GMapEither x _) = x
*Gmap> :t unGMap''' t''''
unGMap''' t'''' :: GMap Int [Char]
*Gmap> :t unGMap $ unGMap''' t''''
unGMap $ unGMap''' t'''' :: Data.IntMap.IntMap [Char]
*Gmap> let unGMap'''' (GMapEither _ y) = y
*Gmap> :t unGMap'''' t''''
unGMap'''' t'''' :: GMap () [Char]
*Gmap> :t unGMap' $ unGMap'''' t''''
unGMap' $ unGMap'''' t'''' :: Maybe [Char]

　「Either a b」からunGMap*を使って取り出した結果が，それぞれのデータ構成子のフィールドに特化したMapになっているのがわかります。

　なお，無引数のデータ構成子の場合にはフィールドが存在しないため，( )型がフィールドの代わりに使われます。

　(a,b)のフィールドごとにMapを入れ子にする方法と，「Either a b」のデータ構成子ごとにMapを用意する方法の二つを組み合わせることで，どんなデータ型のキーに特化したMapでも定義できます。

　今回紹介したGMapを使う方法の欠点は，ユーザーが型クラスのインスタンスをいちいち書かなければならないことです。現在，第5回で説明したように，ユーザー定義の型クラスに対して自動的にインスタンスを導出しようとする試みがいくつか行われています。しかし，コードの記述量や性能面の問題から，決定的な方法はまだありません。GMapの目的はプログラムの効率化なので，現状ではユーザーがインスタンスを書かざるを得ません。将来的にこの問題が解決することを願っています（参考リンク1，参考リンク2）。


著者紹介 shelarcy

　今回はトライ木の概要しか説明しませんでした。「Purely Functional Data Structures」や「Algorithms: A Functional Programming Approach」といった書籍には，Haskellを使って実装した例が載っています。また，HackageDBでは様々なトライ木を実装したライブラリが提供されています。興味がある方は，これらの解説書やライブラリでのトライ木の実装を見てみるとよいでしょう。