定义与此 Haskell 函数等效的尾递归函数

Question

我正在努力解决之前考试中关于尾递归的问题。问题是定义一个尾递归函数duh，相当于下面的函数。

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

有没有人有任何关于如何解决这个问题的提示？我对尾递归的概念只是半熟悉，所以任何进一步的解释都会非常受欢迎

Answer 1

通常，您可以使用累加器来累积结果。在这种情况下，您希望将输入的每个元素累积到一对列表中。这对列表从一个调用传递到另一个调用。一旦您达到基本情况，累加器（或多或少）就是您的最终答案：不过，您可能需要先对其进行一些最终处理。

在这种情况下，您要构建一对列表，而构建任何列表的起点都是一个空列表。

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 = ...