Namaran

Code daily. Without assist.

2026-11-17

ApplyUntil.hs

applyUntil
  :: (a -> Bool) -> (a -> a) -> a -> (Int, a)

値 x に関数 f を繰り返し適用し、述語 p を満たす値になったところで止めて、f を適用した回数と、そのときの値の組を返す applyUntil を書いてください。x がはじめから p を満たすなら、f は一度も適用せず (0, x) を返します。適用を繰り返せば、いつかは必ず p を満たす値になるものとします。

入力例 1

applyUntil (> 100) (* 2) 3

出力例 1

(6,192)

入力例 2

applyUntil even (+ 1) 4

出力例 2

(0,4)

入力例 3

applyUntil ((< 3) . length) (drop 1) "abcde"

出力例 3

(3,"de")
Reference

Reference

applyUntil
  :: (a -> Bool) -> (a -> a) -> a -> (Int, a)
applyUntil p f x
  | p x = (0, x)
  | otherwise = (n + 1, y)
 where
  (n, y) = applyUntil p f (f x)

p x を、f を適用する前に調べます。満たしていればそこで止まり、回数 0 と x をそのまま返します。入力例 2 の 4 ははじめから偶数なので (0,4) です。先に f を適用してから調べる形で書くと、4 は 5 になり、さらに 6 になって (2,6) を返してしまいます。掲載したのは参考実装で、唯一の正解ではありません。

満たしていなければ、f x から先の残りを同じ applyUntil に任せます。戻ってくるのは「f x から数えた回数」と「最後の値」の組なので、where のパターン (n, y) で組をほどき、回数にはいま適用した1回を足し、値は y のまま返します。入力例 1 では 3 から 6、12、24、48、96、192 と6回適用したところで 100 を超え、内側の呼び出しから順に 0、1、…、6 と数えながら組が戻ってきます。where の束縛は使われたときに初めて評価されるので、p x が真の場合には再帰呼び出しは起きません。

値の型は型変数 a で決めていないので、入力例 3 のように文字列にも使えます。"abcde" から先頭を1文字ずつ落とし、長さが3未満になる "de" まで3回適用します。回数を数えなくてよければ、標準の until p f x が最後の値だけを返します。