2026-08-31
Power.hs
power :: (a -> a -> a) -> a -> Int -> a
結合法則を満たす二項演算 op と値 x、1以上の整数 k を受け取り、x を k 個並べて op でつないだ値 x `op` x `op` ... `op` x を返す power を書いてください。結合法則とは、(a `op` b) `op` c と a `op` (b `op` c) がいつも等しいことで、つなぐ順番の区切り方を変えても結果は同じです。k が1なら x をそのまま返します。k が106 程度でも、op を呼ぶ回数が数十回で済むようにしてください。
入力例 1
power (++) "ab" 3
出力例 1
"ababab"
入力例 2
power (*) 2 10
出力例 2
1024
入力例 3
power max 7 1
出力例 3
7
Reference
Reference
power :: (a -> a -> a) -> a -> Int -> a
power op x k
| k == 1 = x
| even k = power op (op x x) (k `div` 2)
| otherwise = op x (power op (op x x) (k `div` 2))
x を k 個つないだものは、k が偶数なら、op x x を k / 2 個つないだものと同じです。結合法則があるので、2個ずつ区切ってから全体をつないでも値は変わりません。k が奇数なら、先頭の x を1つ外した残り k - 1 個が偶数なので、同じように op x x を k `div` 2 個つないだものに先頭の x をつなぎます。どちらの場合も k が半分になるので、106 でも20段ほどで1に着きます。これは参考実装で、唯一の正解ではありません。
見慣れた形は「k が0なら1を返す」から始めますが、ここでは0個つないだときに返す値、たとえば掛け算の1や連結の空文字列にあたるものが op と一緒に渡されていません。そのため0ではなく1を再帰の底にし、k `div` 2 が0になる呼び出しを作らないようにします。k が2以上なら k `div` 2 は1以上で、底の k == 1 に必ず届きます。入力例1は k が3で奇数なので、"ab" ++ power (++) "abab" 1 になり、"ababab" です。入力例3の k が1のときは、op を一度も呼ばずに x が返ります。