Proposal: Better power for Rational

Daniel Fischer at
Fri Sep 24 20:34:16 EDT 2010

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 

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)

"power/Rational"    (^) = ratPow

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


More information about the Libraries mailing list