Определение хвостовой рекурсивной функции, эквивалентной этой Haskell функции

Question

Я борюсь с проблемой предыдущего экзамена по поводу рекурсии хвоста. Задача состоит в том, чтобы определить хвостовую рекурсивную функцию duh, которая эквивалентна функции ниже.

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

У кого-нибудь есть какие-нибудь советы о том, как решить эту проблему? Я только частично знаком с концепцией рекурсии хвоста, поэтому любые дальнейшие объяснения были бы очень желательны

Answer 1

Как правило, вы используете аккумулятор для увеличения результата, как вы go. В этом случае вы хотите накапливать каждый элемент ввода в пару списков. Эта пара списков передается от одного вызова к другому. Как только вы дойдете до своего базового случая, аккумулятор является (более или менее) вашим окончательным ответом: вам, возможно, потребуется сначала выполнить некоторую окончательную обработку для него, однако.

В этом случае вы хотите создать пару списков, и отправной точкой для создания любого списка является пустой список.

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

Подумайте, что вы хотите сделать с парой списков в каждом случае, прежде чем создавать рекурсивный вызов dup'.

Обратите внимание, что аккумулятор не должен иметь тот же тип, что и конечное возвращаемое значение, или даже быть единственным аргументом. Вы также можете определить хвостовую рекурсивную версию, например

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

Answer 2

duh xs = (,) xs xs является одним из таких определений, в нем отсутствуют какие-либо не-хвостовые вызовы.

duh = dup - это другое, потому что dup уже является хвостовой рекурсией, по модулю cons.

Answer 3

Рекурсивная функция архетипического хвоста - foldl. Напишите dup в терминах foldl, и оно будет хвостовым рекурсивным, по крайней мере, после включения определения foldl.