Реализация хвостовой рекурсии

Question

Я написал простую функцию в haskell, которая не является хвостовой рекурсией и суммирует значения в списке, где:

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

Но сейчас я пытаюсь реализовать ту же функцию, но с использованием хвостовой рекурсии. Насколько я знаю, хвостовая рекурсия выполняет рекурсивный вызов на последнем этапе, поэтому я попробовал что-то вроде:

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

Но я потерялся на полпути, потому что я не знаком с хвостовой рекурсией в Хаскеле. Может ли кто-нибудь помочь мне в продолжении хвостовой рекурсивной версии кода?

Answer 1

Немного поиграем,

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   -- !!!

последний находится в хвостовой рекурсивной форме! Таким образом, мы просто определяем

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

Заполните пробелы!