PR

連想リストとの相互変換を行う

　最後に，Map型と他の辞書を相互変換する処理を見ていきましょう。Data.Mapは，連想リストをMap型に変換するfromList関数と，Map型を連想リストに変換するtoList関数を提供しています。

-- > fromList [] == empty
-- > fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
-- > fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
fromList :: Ord k => [(k,a)] -> Map k a 
fromList xs       
  = foldlStrict ins empty xs
  where
    ins t (k,x) = insert k x t

～ 略 ～

foldlStrict :: (a -> b -> a) -> a -> [b] -> a
foldlStrict f z xs
  = case xs of
      []     -> z
      (x:xx) -> let z' = f z x in seq z' (foldlStrict f z' xx)

-- > toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
-- > toList empty == []
toList :: Map k a -> [(k,a)]
toList t      = toAscList t
-- | /O(n)/. Convert to an ascending list.
--
-- > toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
toAscList :: Map k a -> [(k,a)]
toAscList t   = foldr (\k x xs -> (k,x):xs) [] t

-- | /O(n)/. Post-order fold.
foldr :: (k -> a -> b -> b) -> b -> Map k a -> b
foldr _ z Tip              = z
foldr f z (Bin _ kx x l r) = foldr f (f kx x (foldr f z r)) l

　どちらの関数も「変換元のデータ構造に対して定義されたfold*関数を使い，データ構造を再帰的にたどりながら，新しく作成するデータ構造に対してキーと値を追加していく」という定義になっています。

　なお，第34回で説明したData.FoldableモジュールのtoList関数では連想リストに変換できないので注意してください。

　Map型にもFoldableクラスのインスタンスは提供されていますが，キーに対する情報を切り落とすように定義されています。

instance Foldable (Map k) where
  foldMap _f Tip = mempty
  foldMap f (Bin _s _k v l r)
    = foldMap f l `mappend` f v `mappend` foldMap f r

　この結果，Data.FoldableモジュールのtoList関数を使うと，連想リストではなく，Map型の中の要素だけを保持するリストに変換されてしまいます。

Prelude Data.Map> fromList [("foo",10),("bar",24)]
fromList [("bar",24),("foo",10)]
Prelude Data.Map> Data.Foldable.toList $ fromList [("foo",10),("bar",24)]
[24,10]

著者紹介 shelarcy

　2009年10月24日，「Real World Haskell」の翻訳である「Real World Haskell―実戦で学ぶ関数型言語プログラミング」がついに出版されました。また，11月11日には，「Programming in Haskell」の翻訳である「プログラミングHaskell」が発売される予定です。

　さらに，ここ1～2カ月の間にリリースされる予定のGHC6.12.1では，ワイド文字列（wchar_t）に対応していない一般のライブラリでも，ライブラリ内の文字を引数として取る関数に日本語文字を渡すことが可能になります（参考リンク）。

　Haskellを本格的に学んだり使ったりするための状況がいよいよ整ってきました。