PureScript两种takeEnd实现的效率对比及尾递归优化疑问

我是PureScript新手，正在重写一些基础函数，想要实现从列表末尾提取指定数量元素的takeEnd函数。以下是我编写的实现：

takeEnd :: forall a. Int -> List a -> List a
takeEnd _ Nil = Nil
takeEnd n l = go n Nil $ reverse l where
    go _ new Nil = new
    go 0 new _ = new
    go n new  (x : xs) = go (n - 1) (x : new) xs

另外是我在书中找到的实现：

takeEnd :: forall a. Int -> List a -> List a
takeEnd _ Nil = Nil
takeEnd n  = go >>> snd where
    go Nil = Tuple 0 Nil
    go (x : xs) = go xs
        # \(Tuple c nl) -> Tuple (c + 1) $ if c < n then x : nl else nl

我想了解这两个版本哪个效率更高？同时我认为第二个版本未进行尾递归优化，这个判断是否正确？

效率对比 #

• 你的实现：首先调用reverse遍历整个列表（时间复杂度O(n)），随后go函数最多遍历指定数量的元素（时间复杂度O(k)，k为要提取的元素数），总时间复杂度为O(n + k)。但reverse会创建一个全新的列表，带来额外的O(n)内存开销。
• 书中的实现：仅需遍历列表一次（时间复杂度O(n)），遍历过程中同时完成计数和结果列表的构建，无需额外的反转操作，内存开销仅为O(k)（仅存储最终需要的k个元素）。

综上，书中的实现效率更高，尤其是处理大型列表时，能避免反转操作带来的内存和时间消耗。

尾递归判断 #

你的判断是正确的，书中的go函数无法被尾递归优化。

尾递归的核心是：递归调用必须是函数的最终执行操作，函数返回值直接等于递归调用的结果，不能在递归返回后再做额外计算。

看书中go函数的逻辑：

go (x : xs) = go xs # \(Tuple c nl) -> Tuple (c + 1) $ if c < n then x : nl else nl

#运算符的作用是将右侧函数应用到左侧表达式的结果上，等价于：

go (x : xs) = (\(Tuple c nl) -> Tuple (c + 1) $ if c < n then x : nl else nl) (go xs)

这里递归调用go xs的结果会被传入后续lambda函数进行处理（计数加1、判断是否将当前元素加入结果列表），递归调用并非函数的最终返回操作，因此PureScript编译器无法对其进行尾递归优化。

而你实现中的go函数是标准的尾递归：

go n new (x : xs) = go (n - 1) (x : new) xs

函数返回值直接是递归调用的结果，没有后续计算，会被编译器优化为循环，避免栈溢出风险。

内容的提问来源于stack exchange，提问作者Djordje Vuckovic