I am trying to learn Haskell and I read about tail recursions. For example I can write the sum function this way :
sum :: Num a => [a] -> a sum [] = 0 sum (x:xs) = x + summe xs But also this way
summe':: Num a => [a] -> a summe' x = iterate x 0 where iterate x y | null x = 0 + y | otherwise = iterate (tail x) (head x + y) Could someone tell me how to do it with this function? I am lost
f :: Integer -> Integer f 0 = 0 f n = n * f (n-1) + n In order to rewrite the following function using tail-recursion:
f :: Integer -> Integer f 0 = 0 f n = n * f (n-1) + n the same approach, which used in summe' can be used.
The idea is to start from zero and increment the value until n is reached:
f :: Integer -> Integer f n = iterate 0 0 where f' x sum = x * sum + x iterate x sum | x == n = f' n sum | otherwise = iterate (x + 1) (f' x sum) Thus, if n is reached, evaluate the function with n and the accumulated sum; otherwise, calculate the function with intermediate sum and value and pass it to the next iteration.
Well, flipping the "time direction" in f n = n * f (n-1) + n by letting n = k + 1, we have
f (k+1) = (k+1) * f k + (k+1) next fk k = (k+1) * fk + (k+1) and thus
f n = iterate 0 0 where iterate k fk | k==n = fk | otherwise = .... 
head,tailshould be avoided when possible, and here there is no reason to use them.