I want to make this Function:
calling customPower 2 2 would give back 2^2 + 2^1 + 1
calling customPower 3 3 would give back 3^3 + 3^2 + 3^1 + 1
Here is my code:
customPower :: Int -> Int -> Int
customPower x y
| y == 0 = 1
| y > 0 = (x^(y)) + (customPower x y-1)
It gives me stack overflow exception and I can't find where is the error. Everything seems fine.
The operators have lower precedence than function calls, this means that your recursive call:
... + (customPower x y-1)
is interpreted as:
... + ((customPower x y)-1)
so you keep calling with the same parameters, therefore the recursion can never end.
We can fix this by adding brackets for y-1:
customPower :: Int -> Int -> Int
customPower x y
| y > 0 = x^y + customPower x (y-1)
| otherwise = 1With this modifications, we do not get stuck in an infinite loop:
Prelude> customPower 5 3
156
We can rewrite the above by making use of sum :: Num a => [a] -> a and map :: (a -> b) -> [a] -> [b] to implement this with a one-liner:
customPower :: (Num a, Integral b) => a -> b -> a
customPower x y = sum (map (x^) [0..y])
or we can use iterate :: (a -> a) -> a -> [a]:
customPower :: (Num a, Integral b) => a -> b -> a
customPower x y = sum (take (y+1) (iterate (x*) 1))
Due to Haskell's laziness, the above attempts will likely still result in a call stack that scales linear with the value of y: the functions are, like @dfeuer says, not tail recursive functions, we can however work with an accumulator here:
customPower :: Int -> Int -> Int
customPower x = go 1
where go a y | y > 1 = a
| otherwise = seq a (go (a+x^y) (y-1))
since the above sum is equal to a simple formula, we can even calculate the value in O(y log x):
y
.———— y+1
╲ i x - 1
╱ x = ————————
*———— x - 1
i=0
So we can calculate the value with:
customPower :: (Integral a, Integral b) => a -> b -> a
customPower x y = div (x^(y+1) - 1) (x - 1)
This will usually work faster, although in a rare case where the result times x -1 is larger than the maximum representable number of the type a, this will result in overflow and will return the wrong number.
customPower = go 1 where go acc x y | y > 0 = go (x^y + acc) x (y - 1) | otherwise = acc will fix the problem in optimized code. In unoptimized code, you'll need go !acc x y = ... or | y > 0 = acc `seq` .... The versions you give using sum will also build up thunks when not sufficiently optimized (and especially specialized).
(customPower x y) -1in the recursive case.customPower x y = iterate ((1+).(x*)) 1 !! y. If you want to get really cool, I bet this can be done as a variant of repeated squaring.customPower x yby summing up the bottom row of the matrix[[1,0],[1,x]]^y, and you can compute the latter with the usual repeated squaring algorithm.)foldr (\a r -> a + x*r) 0 [1 | i <- [0..y]].