Defining a tail recursive function equivalent to this Haskell function

Question

I am struggling with a problem from a previous exam regarding tail recursion. The problem is to define a tail recursive function duh, that is equivalent to the function below.

dup [] = ([], [])
dup (x:xs) = let (as, bs) = dup xs in (x:as, x:bs)

Does anyone have any tips on how to approach this problem? I am only semi familiar with the concept of tail recursion, so any further explanations would be very welcome

Answer 1

Typically, you use an accumulator to build up your result as you go. In this case, you want to accumulate each element of the input into a pair of lists. This pair of lists gets passed from one call to the other. Once you reach your base case, the accumulator is (more or less) your final answer: you may need to do some final processing on it first, though.

In this case, you want to build up a pair of lists, and the starting point for building any list is an empty list.

dup :: [a] -> ([a], [a])
dup xs = dup' xs ([], [])
    where dup' :: [a] -> ([a], [a]) -> ([a], [a])
          dup' [] acc = ...
          dup' (x:xs) acc = ...

Think about what you want to do to a pair of lists in each case before you make the recursive call to dup'.

Note that the accumulator doesn't have to have the same type as the final return value, or even be a single argument. You could also define the tail-recursive version like

dup' :: [a] -> [a] -> [a] -> ([a], [a])
dup' [] accA accB = ...
dup' (x:xs) accA accB = ...