2026-09-01
First.hs
newtype First a = First {getFirst :: Maybe a}
instance Semigroup (First a) where
instance Monoid (First a) where
First a は Maybe a を包む型です。<> でつないだ値のうち、左から見て最初の Just が残るように、Semigroup と Monoid のインスタンスを書いてください。<> は左が Nothing なら右を、左が Just なら左を返します。mempty は、どの値と <> でつないでも相手を変えない値(単位元、identity element)にします。無限のリストを mconcat でつないでも、最初の Just が見つかった時点で答えが返るようにします。
入力例 1
getFirst (First Nothing <> First (Just 'b'))
出力例 1
Just 'b'
入力例 2
getFirst (mconcat (First Nothing : map (First . Just) [1 :: Int ..]))
出力例 2
Just 1
入力例 3
getFirst (mempty :: First Int)
出力例 3
Nothing
Reference
newtype First a = First {getFirst :: Maybe a}
instance Semigroup (First a) where
First Nothing <> b = b
a <> _ = a
instance Monoid (First a) where
mempty = First Nothing
mconcat の既定の定義は foldr (<>) mempty で、x : rest を x <> mconcat rest として計算します。mconcat rest が評価されるのは、<> が右側の値を必要としたときだけです。参考実装の <> は左が First Nothing かどうかだけを調べ、左が Just なら右を見ずに返すので、入力例 2 は2つ目の要素 First (Just 1) で答えが決まり、残りの無限の要素には触れません。mempty を First Nothing にすると、左に置けば1つ目の式で右がそのまま返り、右に置けば左が返るので、相手を変えません。
First が newtype であることも効いています。First a <> First b = ... のように右側にもコンストラクタの形を書いても、newtype の照合は値を評価しないので、右側の畳み込みはまだ動きません。First を data で宣言していたら、右側の First b との照合が mconcat rest を評価し、それがまた次の要素の <> を評価するので、無限のリストでは答えが返りません。参考実装の書き方なら、data でも答えが返ります。
掲載したのは参考実装で、唯一の正解ではありません。First a <> First b = First (maybe b Just a) と書いても、newtype なら同じように動きます1。
- GHC の標準ライブラリの
Data.Monoidにも、同じ働きのFirstがnewtypeで定義されています。Data.Monoidは Haskell 2010 の報告書のライブラリには含まれていません。