haskell power function

how to write a power function which makes use of the following facts: To raise x to a power n (where n is a positive whole number), if n is even, you can find the nth power of x by squaring half that power. For example, x^12 is x^6 * x^6. For odd powers, just subtract one from the power, and multiply the result for the smaller power by x. for example, x^13 is x * x^12, which is x * x^6 * x^6. Recursively, any power can be found with less work than m开发者_如何学运维ultiplying x by itself the number of times indicated. I came up with this

power x n
    | n == 0  =  1
    | x == 0  =  0
    | even n = ( power x (n / 2) ) * ( power x (n / 2) )
    | odd n = x * ( power x ((n - 1) / 2)) * ( power x ((n - 1) / 2) )

but I get an error saying ERROR - Unresolved overloading * Type : (Integral a, Fractional a) => Integer * Expression : power 2 2

---

What's happened here is a common type mismatch. First, take a look at the type signature for even: even :: (Integral a) => a -> Bool. odd has a similar signature. So you can see that even and odd take any type of the Integral typeclass and evaluate it. Then look at the signature for /: (/) :: (Fractional a) => a -> a -> a. / takes only Fractional types, not Integral ones. It's impossible for one type to be evaluated by both those functions. In this case, there's an easy fix: use div instead of /. Note that if you use div as an infix function (place it between the arguments) you'll need to put backticks around div.

---

Look at the type of even and compare that to the type of /.

---

Just a remark now that your code is running: Haskell doesn't automatically memoize functions, so you're calculating the recursive calls to power twice in the last two lines. I would recommend to introduce a simple function sqr k = k * k and to use it. There are several ways: a separate function; a where clause; and let.

I would prefer let:

power _ 0 = 1
power 0 _ = 0
power x n  = let sqr k = k * k
                 half_n = n `div` 2  
                 sqrHalfPower = sqr ( power x half_n )
             in if even n then sqrHalfPower else x * sqrHalfPower 

As you can see pattern matching deals with the first two cases. Then let defines some useful expressions, which can be used later in in. Note that for odd numbers, (n-1) `div` 2 gives the same result as n `div` 2, so we can unify both cases.

---

I think, the fastest way to calculate power:

     pow:: Integer->Integer->Integer
     pow x n  |(n==1) = x
              |even n = (pow x ( div n 2))*(pow x ( div n 2)) 
              |odd n  = x * (pow x (n-1))

you can also use "Int" instead "Integer"(replace Integer on Int in the signature!).