Namaran

Code daily. Without assist.

2026-10-31

CountT.hs

data Trampoline a = Return a | Bounce (Trampoline a)

runT :: Trampoline a -> a
runT (Return x) = x
runT (Bounce t) = runT t

countT :: (a -> Bool) -> [a] -> Trampoline Int

リストの要素のうち p を満たすものの個数を数える countT を書いてください。countT は再帰呼び出しの結果を待たず、次にする呼び出しを Bounce に包んで返し、最後に個数を Return で返します。runT がそれを Return に着くまで1段ずつ進めます。空リストなら個数は0です。

入力例 1

runT (countT even [1 .. 10])

出力例 1

5

入力例 2

runT (countT even [])

出力例 2

0

入力例 3

runT (countT (> 0) [1 .. 1000000])

出力例 3

1000000
Reference
countT :: (a -> Bool) -> [a] -> Trampoline Int
countT p = go 0
 where
  go acc [] = Return acc
  go acc (x : xs)
    | p x = Bounce (go (acc + 1) xs)
    | otherwise = Bounce (go acc xs)

ふつうに書くと count p (x : xs) = (if p x then 1 else 0) + count p xs のように、再帰呼び出しの結果に数を足す形になります。この足し算は再帰呼び出しが返るのを待つので、呼び出しを Bounce に包んで先に返すことができません。

そこで、ここまでに数えた個数 acc を補助関数 go の引数で持ち回ります。要素を1つ調べるたびに、更新した acc を次の go に渡すので、go の再帰呼び出しのあとにする仕事は残りません。そのため呼び出しをそのまま Bounce に包んで返せます。リストが尽きたときの acc が答えなので、go acc [] はそれを Return で返し、countT は go 0 から始めます。

掲載したのは参考実装で、唯一の正解ではありません。ガードの代わりに if で次の acc を決めて、Bounce を1か所にまとめてもかまいません。