Implementing tail recursion

Question

I've written a simple function in haskell that is non tail recursive that sums up the values inside a list where:

nonTailRecursiveSum :: [Integer] -> Integer
nonTailRecursiveSum [] = 0 --base case
nonTailRecursiveSum (x:xs) = x + sum xs

But what I'm trying to do now is to implement the same function but using tail recursion. For what i know, tail recursion performs the recursive call at the final step so i tried something like:

tailRecursiveSum :: [Integer] -> Integer
tailRecursiveSum [] = 0
tailRecursiveSum (x:xs) = aux_f(x) + tailRecursiveSum xs
.
.

But i got lost in the midway as I'm not familiar with tail recursion in Haskell. Could anyone assist me on the continuation of the tail recursive version of the code?

sum (x:xs) = aux xs x where aux (x:xs) total = aux xs (x + total) — Mateen Ulhaq
For the recursion to be tail recursion, you need your cases to be similar to tailRecursiveFunction something = tailRecursiveFunction somethingElse. — n. 1.8e9-where's-my-share m.

Will Ness Will Ness · Accepted Answer · 2018-11-03T08:42:24

Playing with it for a bit,

sum (x:y:xs) = x + sum (y:xs)
             = x + (y + sum xs)
             = (x + y) + sum xs

g a b = a + sum b

sum (x:y:xs) = g x (y:xs)
             = x + g y xs
             = g (x+y) xs   -- !!!

the last one is in tail recursive form! We thus just define

sum xs = g 0 xs
  where
  g acc [] = ...
  g acc (x:xs) = g (acc + ...) ...

Fill in the blanks!

Implementing tail recursion

1 Answers