Namaran

Code daily. Without assist.

2026-11-13

Sync.hs

sync :: [(String, Int)] -> [(String, Int)] -> ([String], [String], [String])

名前と版の組を並べた古い一覧 old と新しい一覧 new を照合し、新しい一覧にだけある名前、古い一覧にだけある名前、両方にあって版が違う名前の3つのリストを組にして返す sync を書いてください。各リストは名前の昇順に並べ、同じ名前は1度だけ入れます。1つの一覧に同じ名前が複数あるときは、後ろにある組の版を使います。どちらの一覧も空なら、3つとも空リストです。

入力例 1

sync [("a",1),("b",1),("c",2)] [("b",2),("c",2),("d",1)]

出力例 1

(["d"],["a"],["b"])

入力例 2

sync [] []

出力例 2

([],[],[])

入力例 3

sync [("x",1),("x",2)] [("x",2)]

出力例 3

([],[],[])
Reference

Reference

import qualified Data.Map as Map

sync :: [(String, Int)] -> [(String, Int)] -> ([String], [String], [String])
sync old new =
  ( Map.keys (Map.difference n o)
  , Map.keys (Map.difference o n)
  , Map.keys (Map.filter id (Map.intersectionWith (/=) o n))
  )
 where
  o = Map.fromList old
  n = Map.fromList new

照合の単位は組ではなく名前です。そこで2つの一覧を、名前をキー、版を値とする Map に変えます。Map.fromList は同じキーが複数あると後ろの値を残すので、「後ろにある組の版を使う」はこれだけで満たされます。Map.difference a b は、a のキーのうち b に無いものを、値は見ずに残します。n から o を引けば新しい一覧にだけある名前、o から n を引けば古い一覧にだけある名前になります。Map.intersectionWith (/=) o n は両方にあるキーだけを残し、2つの版を (/=) で比べた Bool を値にするので、Map.filter id で版が違うものだけが残ります。Map.keys はキーを昇順に返し、Map のキーは重複しないので、並び順と「1度だけ」の条件も満たされます。これは参考実装で、唯一の正解ではありません。

Data.List の \\ や intersect で組のリストを直接比べると、("b",1) と ("b",2) は別の要素なので、入力例1の b が「新しい一覧にだけある」と「古い一覧にだけある」の両方に入ります。入力例3でも、古い一覧の ("x",1) が消えた組として残ります。名前で突き合わせ、版は両方にある名前どうしでだけ比べることで、入力例1は (["d"],["a"],["b"]) に、入力例3は版が同じなので ([],[],[]) になります。空の一覧からは空の Map ができるので、入力例2も3つとも空です。