2026-10-11
Powers.hs
-- sum of the powers of two that do not exceed the limit
powerSum :: Integer -> Integer
powerSum limit = sum (filter (<= limit) (iterate (* 2) 1))
main :: IO ()
main = print (powerSum 1000)
powerSum は、limit を超えない2の累乗 1, 2, 4, ... の和を返すつもりの関数です。powerSum 1000 は 1 + 2 + ... + 512 の 1023 を出力するはずですが、いまは何も出力せず、いつまでも終わりません。
Answer
Wrong
powerSum limit = sum (filter (<= limit) (iterate (* 2) 1))
iterate (* 2) 1 は終わりのない無限リストです。filter は条件を満たさない要素を捨てて次の要素を調べ続ける関数で、リストが昇順に並んでいることを知りません。1024 から先はどの要素も条件を満たしませんが、filter はリストの終わりに着くまで探し続け、その終わりは来ません。sum は最後の要素を待ったまま返らず、Integer の値は上限なく大きくなり続けます。
Right
powerSum limit = sum (takeWhile (<= limit) (iterate (* 2) 1))
takeWhile は、条件を満たさない最初の要素 1024 を見た時点でリストを終わらせます。iterate の残りは誰にも要求されないので計算されず、sum は 1 から 512 までの10個を足した 1023 を返します。