Namaran

Code daily. Without assist.

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。

  1. GHC の標準ライブラリの Data.Monoid にも、同じ働きの First が newtype で定義されています。Data.Monoid は Haskell 2010 の報告書のライブラリには含まれていません。