2026-09-02
RunUntil.hs
runUntil :: (s -> a -> Maybe s) -> s -> [a] -> (s, [a])
初めの状態から、リストの要素を先頭から1つずつ step で状態に反映していく runUntil を書いてください。step が Nothing を返したら、その要素で処理を打ち切り、打ち切る直前の状態と、まだ反映していない要素のリストを組にして返します。このリストには、打ち切りの原因になった要素も含めます。最後まで反映できたら、最後の状態と空リストを返します。リストが空なら、初めの状態と空リストです。
入力例 1
runUntil (\b x -> if b + x < 0 then Nothing else Just (b + x)) 10 [5, -20, 3]
出力例 1
(15,[-20,3])
入力例 2
runUntil (\b x -> if b + x < 0 then Nothing else Just (b + x)) 10 [1, 2]
出力例 2
(13,[])
入力例 3
runUntil (\b x -> if b + x < 0 then Nothing else Just (b + x)) 10 []
出力例 3
(10,[])
Reference
runUntil :: (s -> a -> Maybe s) -> s -> [a] -> (s, [a])
runUntil _ s [] = (s, [])
runUntil step s (x : xs) = case step s x of
Nothing -> (s, x : xs)
Just s' -> runUntil step s' xs
要素が残っていれば step を呼び、Nothing ならその場で止めて、今の状態 s と、x を含めた残り x : xs を返します。Just s' なら新しい状態で残りへ進みます。入力例1では、10に5を足して15になり、次の −20 を足すと負になるので打ち切って (15,[-20,3]) を返します。
foldl で書こうとすると、Nothing が返ったあとも要素を最後まで読み進めるので、どこで止まったかを別に持ち回る必要が出てきます。止まった時点で残りを xs だけにすると、原因になった −20 が消え、呼び出し側は直したあとで続きから再開できません。
Haskell の状態とリストは書き換えられない値なので、打ち切った処理の途中状態は、こうして返り値に入れない限りどこにも残りません。IORef に書き込みながら進む書き方では、例外で止まったあとに書きかけの状態が残りますが、この形なら呼び出し側が受け取るのは、打ち切る直前の状態と残りの要素だけです。
掲載したのは参考実装で、唯一の正解ではありません。case の代わりに maybe 関数で分岐しても同じです。