Namaran

Code daily. Without assist.

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 をそのまま返します。