I don't understand one thing about implementation of ^
in haskell
:
(^) :: (Num a, Integral b) => a -> b -> a
x0 ^ y0 | y0 < 0 = errorWithoutStackTrace "Negative exponent"
| y0 == 0 = 1
| otherwise = f x0 y0
where -- f : x0 ^ y0 = x ^ y
f x y | even y = f (x * x) (y `quot` 2)
| y == 1 = x
| otherwise = g (x * x) (y `quot` 2) x -- See Note [Half of y - 1]
-- g : x0 ^ y0 = (x ^ y) * z
g x y z | even y = g (x * x) (y `quot` 2) z
| y == 1 = x * z
| otherwise = g (x * x) (y `quot` 2) (x * z) -- See Note [Half of y - 1]
Why do we need f
? isn't f x y
is just g x y 1
?
Is it some optimization or I missing something?
If I change code in a following way will it work?
(^) :: (Num a, Integral b) => a -> b -> a
x0 ^ y0 | y0 < 0 = errorWithoutStackTrace "Negative exponent"
| y0 == 0 = 1
| otherwise = g x0 y0 1
where
g x y z | even y = g (x * x) (y `quot` 2) z
| y == 1 = x * z
| otherwise = g (x * x) (y `quot` 2) (x * z)
No, f x y
is not just g x y 1
: g x 3 1
calls g (x*x) 1 (x*1)
, but f x 3
calls g (x*x) 1 x
. In particular, the last argument is x*1
in the former but x
in the latter. It would be surprising to find an instance for which this makes a semantic difference or a noticeable performance difference, but they are at the very least not the exact same thing.