定义等价于此 Haskell 函数的尾递归函数

Question

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

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

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

Answer 1

原型尾递归函数是foldl。根据 foldl 编写 dup，它将是尾递归的，至少在内联 foldl 的定义之后。

Answer 2

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

在这种情况下，您想要构建一对列表，构建any列表的起点是一个空列表。

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

在对 dup'.

进行递归调用之前，请考虑在每种情况下要对一对列表执行的操作

请注意，累加器不必与最终 return 值具有相同的类型，甚至不必是单个参数。您还可以定义尾递归版本，例如

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

Answer 3

duh xs = (,) xs xs 就是这样一种定义，其中缺少任何非尾调用。

duh = dup是另一个，因为dup已经是尾递归了，modulo cons.

定义等价于此 Haskell 函数的尾递归函数

Defining a tail recursive function equivalent to this Haskell function

haskell

recursion

tail-recursion