Proposal: Better power for Rational

[Daniel Fischer]

Proposal: A better implementation of powers for Rational

Discussion period: Three weeks, until 16^th^ October 2010 (ICFP again)

Exponentiation by repeated squaring, as is used in (^) is bad for Rational 
since on each multiplication a gcd has to be calculated.

For well-formed Rationals, the numerator and denominator are known to be 
coprime, hence all powers of the numerator and denominator are also 
coprime.

To avoid superfluous work, I propose a special power function for Rationals 
and a rewrite rule to replace calls to (^) for Rational bases by the 
special function. It might also be beneficial to export the specialised 
function from Data.Ratio to be used if the rule doesn't fire.

Proposed function and rule:

ratPow :: Integral a => Rational -> a -> Rational
ratPow _ e
    | e < 0     = error "Negative exponent"
ratPow _ 0  = 1 :% 1
ratPow r 1  = r
ratPow (0:%y) _ = 0 :% 1
ratPow (x:%1) e = (x^e) :% 1
ratPow (x:%y) e = (x^e) :% (y^e)

{-# RULES
"power/Rational"    (^) = ratPow
  #-}

Like the elimination of `gcd` from recip (#4336), this would yield a great 
performance boost.

Cheers,
Daniel