Namaran

Code daily. Without assist.

2026-10-04

Averages.hs

import qualified Data.Map.Strict as M

averages :: [(String, Double)] -> M.Map String Double

(キー, 値) の組のリストを受け取り、キーごとに値の平均を求めた表を返す averages を書いてください。空のリストなら空の表を返します。同じキーが何百万回現れても、表の中に未評価の足し算が溜まらないようにしてください。

入力例 1

averages [("a", 1), ("b", 4), ("a", 2)]

出力例 1

fromList [("a",1.5),("b",4.0)]

入力例 2

averages [("x", 3)]

出力例 2

fromList [("x",3.0)]

入力例 3

averages []

出力例 3

fromList []
Reference
import Data.List (foldl')
import qualified Data.Map.Strict as M

averages :: [(String, Double)] -> M.Map String Double
averages = M.map (uncurry (/)) . foldl' step M.empty
  where
    step m (k, x) = M.insertWith add k (x, 1) m
    add (s1, n1) (s2, n2) =
      let s = s1 + s2
          n = n1 + n2
       in s `seq` n `seq` (s, n)

参考実装は、キーごとに (合計, 個数) の組を foldl' で溜め、最後に M.map で合計を個数で割ります。

Data.Map.Strict の insertWith は、表に入れる値を弱頭部正規形まで評価します。組の弱頭部正規形は外側の (,) ができた状態のことで、中の s1 + s2 や n1 + n2 はまだ評価されません。add を (s1 + s2, n1 + n2) とだけ書くと、同じキーが現れるたびに組の中の足し算が1段ずつ積み重なり、最後に割り算をするまで残ります。手元で同じキーを200万回渡すと、この書き方では最大常駐メモリが約520MB、参考実装では約9MBでした。

参考実装の add は、seq で合計と個数を評価してから組を作ります。insertWith が組を弱頭部正規形まで評価するとき、この seq が先に走るので、表の中の組はいつも評価済みの数を2つ持っています。表そのものは foldl' が1歩ごとに評価するので、表、組、組の中身のどこにもサンクは残りません1。

掲載したのは参考実装で、唯一の正解ではありません。[(k, (x, 1)) | (k, x) <- xs] を M.fromListWith add に渡して表を作っても同じです。合計と個数を、data Acc = Acc !Double !Double のような正格なフィールドを持つ型にまとめる書き方もあります。

  1. foldl' は Haskell 2010 の Prelude には無いので、Data.List から読み込んでいます。GHC 9.10 以降の base では、Prelude からも使えます。