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
– Mateen Ulhaq, Commented Nov 3, 2018 at 5:57
For the recursion to be tail recursion, you need your cases to be similar to tailRecursiveFunction something = tailRecursiveFunction somethingElse. — n. m. could be an AI
– n. m. could be an AI, Commented Nov 3, 2018 at 6:27

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

1

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!

answered Nov 3, 2018 at 8:42

Will Ness

71.6k10 gold badges105 silver badges192 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Mateen Ulhaq Over a year ago

You can start with sum (x:xs) = g x xs immediately to avoid 0 + .... (Which only works because (+) 0 is essentially id for numeric types.)

Will Ness Over a year ago

but then I have to handle the [] case separately. With the explicit 0. It's unavoidable.

David Young Over a year ago

What do you mean by the last one (of the first code block) being in tail recursive form?

Will Ness Over a year ago

@DavidYoung in g x (y:xs) = g (x+y) xs, call to g is a tail call.

Collectives™ on Stack Overflow

Implementing tail recursion

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related