Namaran

Code daily. Without assist.

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 関数で分岐しても同じです。