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か所にまとめてもかまいません。