2026-11-10
GroupBy.hs
groupInOrder :: (Ord k) => [(k, v)] -> Map.Map k [v]
鍵と値の組のリストを受け取り、鍵ごとに、その鍵を持つ組の値を集めたリストを対応させた Map を返す groupInOrder を書いてください。Map は import qualified Data.Map as Map で読み込んであります。各リストの中の値は、受け取ったリストに現れた順に並べます。受け取ったリストが空なら空の Map を返します。
入力例 1
groupInOrder [("x", 1), ("y", 2), ("x", 3), ("x", 4)]
出力例 1
fromList [("x",[1,3,4]),("y",[2])]
入力例 2
groupInOrder [('b', "late"), ('a', "only"), ('b', "later")]
出力例 2
fromList [('a',["only"]),('b',["late","later"])]
入力例 3
groupInOrder []
出力例 3
fromList []
Reference
Reference
groupInOrder :: (Ord k) => [(k, v)] -> Map.Map k [v]
groupInOrder = foldr (\(k, v) -> Map.insertWith (++) k [v]) Map.empty
Map.insertWith f k new m は、k がまだ無ければ new をそのまま入れ、すでに old があれば f new old に置き換えます。組み合わせ関数が受け取るのは新しい値が先、古い値が後です。(++) を渡すと [v] ++ old になり、あとから挿入した値ほどリストの前に付きます。そこで foldr を使い、リストの右端の組から挿入します。あとから挿入されるのは元のリストで前にある組なので、前に付けていくと元の順に並びます。これは参考実装で、唯一の正解ではありません。
左から順に読む foldl に同じ insertWith (++) k [v] を組み合わせると、入力例1の "x" は [4,3,1] と逆順になります。foldl のまま直すなら insertWith (flip (++)) k [v] で古いリストの後ろに付けますが、++ は左のリストを毎回たどり直すので、同じ鍵の値が n 個あると手間は n の2乗に比例して増えます。foldr と前に付ける組み合わせなら、1回の挿入で付け足すのは要素1つ分です。入力例3の空リストでは foldr が初期値の Map.empty をそのまま返します。