Namaran

Code daily. Without assist.

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 が返ります。