Difference between revisions of "Power function"
(formatted my post to HaskellCafe) 

(11 intermediate revisions by 3 users not shown)  
Line 3:  Line 3:  
Why are there several notions of power in Haskell, namely <hask>(^)</hask>, <hask>(^^)</hask>, <hask>(**)</hask>? 
Why are there several notions of power in Haskell, namely <hask>(^)</hask>, <hask>(^^)</hask>, <hask>(**)</hask>? 

+  <haskell> 

+   typically for integers 

+  (^) :: (Num a, Integral b) => a > b > a 

+  
+   typically for rationals 

+  (^^) :: (Fractional a, Integral b) => a > b > a 

+  
+   typically for floatingpoint numbers 

+  (**) :: Floating a => a > a > a 

+  </haskell> 

== Answer == 
== Answer == 

−  The reason is that there is no 
+  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 [https://stackoverflow.com/q/6400568 StackOverflow question] for details. 

−  +  
−  +  === Type inference reasons === 

−  +  
−  In the 
+  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 [https://stackoverflow.com/a/6402880 this approach does not work for Haskell's numeric type classes]. 
−  +  
−  +  === 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 1<sup>''x''</sup>, where ''x'' is irrational, is dense in the complex unit circle. 

−  +  
−  +  But even for real numbers there are problems: to calculate <hask>(1)**(1/3::Double)</hask> the power implementation would have to decide whether 

+  <hask>(1/3::Double)</hask> is close enough to ⅓. 

+  If it does so it returns <hask>(1)</hask>, otherwise it fails. However, why shall <hask>0.333333333333333</hask> represent ⅓? It may be really meant as <hask>333333333333333/10^15</hask>, and a real 10<sup>15</sup>th 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: 

+  <haskell> 

+  Prelude> (1)**2 :: Double 

+  1.0 

+  Prelude> (1)**(2 + 1e15  1e15) :: Double 

+  NaN 

+  </haskell> 

+  While both expressions should be evaluated to <hask>1.0</hask>, a reliable check for integers is not possible with floatingpoint numbers. 

+  
+  ==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  <hask>(*)</hask>  <hask>(^)</hask>  cardinal  repeated multiplication  <math>a^b = \prod_{i=1}^b a </math> 

+   

+   any field  <hask>(/)</hask>  <hask>(^)</hask>  integer  multiplication and division  <math>a^b = \begin{cases} a^b & b\ge 0 \\ \frac{1}{a^{b}} & b<0 \end{cases} </math> 

+   

+   an algebraic field  <hask>root</hask>  <hask>(^/)</hask>  rational  list of polynomial zeros (length = denominator of the exponent)  <math> a^{\frac{p}{q}} = \{ x : a^p = x^q \} </math> 

+   

+   positive real  <hask>log</hask>  <hask>(^?)</hask>  any ring of characteristic zero with inverses for integers and a notion of limit  exponential series and logarithm  <math>a^b = \exp(b \log a) = \sum_{k \geq 0} \frac{(b \log a)^k}{k!}</math> 

+  } 

−  But also for real numbers there are problems: 

+  * examples for rings are: Polynomials, Matrices, Residue classes 

−  For computing <hask>(1)**(1/3::Double)</hask> the power implementation has to decide whether 

+  * 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 

−  <hask>(1/3::Double)</hask> is close enough to <math>\frac{1}{3}</math>. 

−  If it does so it returns <hask>(1)</hask>, otherwise it fails. 

−  However, why shall <hask>0.333333333333333</hask> represent <math>\frac{1}{3}</math>? 

−  It may be really meant as <hask>333333333333333/10^15</hask>, 

−  and a real <math>10^{15}</math>th root of <math>1</math> does not exist. 

−  So I propose some balancing: The more general the basis the less general the exponent and vice versa. 

−  I also think the following symbols are more systematic and intuitive. 

−  They are used in NumericPrelude. 

−  <code> 

−  any ring (provides *) ^ cardinal 

−  any field (provides /) ^ integer 

−  an algebraic field (provides 'root') 

−  ^/ rational (computing a list of powers 

−  depending on the denominator 

−  of the rational) 

−  positive real 

−  (including transcendent) ^? anything (unqiue via exponential series) 

−  </code> 

−  That is <hask>(^)</hask> replaces <hask>(^^)</hask>, 
+  That is, <hask>(^)</hask> replaces <hask>(^^)</hask>, 
<hask>(^?)</hask> replaces <hask>(**)</hask>, 
<hask>(^?)</hask> replaces <hask>(**)</hask>, 

<hask>(^)</hask> remains and <hask>(^/)</hask> is new. 
<hask>(^)</hask> remains and <hask>(^/)</hask> is new. 
Latest revision as of 21:34, 10 March 2016
Contents
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 floatingpoint numbers
(**) :: Floating a => a > a > a
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.
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.
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 1^{x}, where x is irrational, is dense in the complex unit circle.
But even for real numbers there are problems: to calculate (1)**(1/3::Double)
the power implementation would have to decide whether
(1/3::Double)
is close enough to ⅓.
If it does so it returns (1)
, otherwise it fails. However, why shall 0.333333333333333
represent ⅓? It may be really meant as 333333333333333/10^15
, and a real 10^{15}th 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
1.0
Prelude> (1)**(2 + 1e15  1e15) :: Double
NaN
While both expressions should be evaluated to 1.0
, a reliable check for integers is not possible with floatingpoint numbers.
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  
any field  (/) 
(^) 
integer  multiplication and division  
an algebraic field  root 
(^/) 
rational  list of polynomial zeros (length = denominator of the exponent)  
positive real  log 
(^?) 
any ring of characteristic zero with inverses for integers and a notion of limit  exponential series and logarithm 
 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, (^)
replaces (^^)
,
(^?)
replaces (**)
,
(^)
remains and (^/)
is new.
See also
 HaskellCafe: Proposal for restructuring Number classes