Namaran

Code daily. Without assist.

2026-10-07

Signup.hs

import qualified Data.Map as Map

register :: (String, Int) -> Map.Map String Int -> Map.Map String Int
register (email, uid) db
  | Map.member email db = db
  | otherwise = Map.insert email uid db

main :: IO ()
main = print (Map.toList (foldr register Map.empty signups))
  where signups = [("bob", 1), ("ann", 2), ("bob", 3), ("ann", 4)]

これは何を出力するでしょうか?

Answer

[("ann",4),("bob",3)] です。

register は、同じアドレスがすでに db にあれば db をそのまま返し、なければ登録します。どのアドレスについても、先に register された申し込みが残り、あとから来たものは断られます。

どの申し込みが先に register されるかは、foldr の展開で決まります。foldr register Map.empty signups を展開すると register ("bob",1) (register ("ann",2) (register ("bob",3) (register ("ann",4) Map.empty))) になります。空の Map に最初に適用されるのは、一番内側にあるリストの最後の ("ann",4) で、そのあと ("bob",3) が登録されます。("ann",2) と ("bob",1) が来た時点では、どちらのアドレスも登録済みなので断られます。リストを左から読んで、1 と 2 が残ると考えると間違えます。

最後に Map.toList は、登録した順ではなくキーの昇順に並べるので、"ann" が "bob" より前に来ます。リストの先頭から順に登録したいなら、foldl (flip register) Map.empty signups のように左から畳み込みます。こうすると [("ann",2),("bob",1)] になります1。

  1. 実際に畳み込むなら、Data.List の foldl' を使います。foldl は途中の Map を作る計算を評価せずに積み上げるので、長いリストではメモリを無駄に使います。