Personal tools

Power function

From HaskellWiki

Revision as of 21:34, 10 March 2016 by Fylwind (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


1 Question

Why are there several notions of power in Haskell, namely
-- typically for integers
(^) :: (Num a, Integral b) => a -> b -> a
-- typically for rationals
(^^) :: (Fractional a, Integral b) => a -> b -> a
-- typically for floating-point numbers
(**) :: Floating a => a -> a -> a

2 Answer

The reason is that there is no implementation of the power function that can cover all exotic choices for basis and exponent while being both efficient and accurate.

See this StackOverflow question for details.

2.1 Type inference reasons

In mathematical notation, the human reader is clever enough to to tell which definition of the power function is applicable in a given context. In Haskell, doing so would drastically complicate type inference. In some other languages such as C++, operator overloading is used to work around this problem, but this approach does not work for Haskell's numeric type classes.

2.2 Mathematical reasons

If we assume the most general types for both basis and exponent, namely complex numbers, the result of the power is no longer unique. In particular, all possible solutions of say 1x, where x is irrational, is dense in the complex unit circle.

But even for real numbers there are problems: to calculate
the power implementation would have to decide whether
is close enough to ⅓. If it does so it returns
, otherwise it fails. However, why shall
represent ⅓? It may be really meant as
, and a real 1015th root of −1 does not exist. Fortunately, the Haskell implementation does not try to be too clever here. But it does so at another point:
Prelude> (-1)**2 :: Double
Prelude> (-1)**(2 + 1e-15 - 1e-15) :: Double
While both expressions should be evaluated to
, a reliable check for integers is not possible with floating-point numbers.

3 Power function in Numeric Prelude

One can refine the set of power functions further as it is done in the Numeric Prelude. In this library, the more general the basis the less general the exponent and vice versa:

basis type provides symbol exponent type definition
any ring
cardinal repeated multiplication a^b = \prod_{i=1}^b a
any field
integer multiplication and division a^b = \begin{cases} a^b & b\ge 0 \\ \frac{1}{a^{-b}} & b<0 \end{cases}
an algebraic field
rational list of polynomial zeros (length = denominator of the exponent)  a^{\frac{p}{q}} = \{ x : a^p = x^q \}
positive real
any ring of characteristic zero with inverses for integers and a notion of limit exponential series and logarithm a^b = \exp(b \log a) = \sum_{k \geq 0} \frac{(b \log a)^k}{k!}
  • examples for rings are: Polynomials, Matrices, Residue classes
  • examples for fields: Fractions of polynomials (rational functions), Residue classes with respect to irreducible divisors, in fact we do not need fields, we only need the division and associativity, thus invertible Matrices are fine

That is,
remains and
is new.

4 See also