如何使用带守卫的尾递归将列表拆分为奇偶元素子列表？

嘿，我来帮你搞定这个问题！首先得明确：尾递归的核心是用累加器保存中间结果，这样递归调用就是函数的最后一步，不需要在递归返回后再做额外计算。你的现有代码问题在于没有使用累加器，而且类型逻辑也不对——直接把元素拼接到子列表后，没办法正确组合成二元组返回。

正确的尾递归实现方案 #

我们可以写一个主函数，调用一个带累加器的辅助尾递归函数。辅助函数会携带两个累加器：一个存奇数元素，一个存偶数元素，每次递归根据当前元素的奇偶性更新对应的累加器。

sumt :: [Int] -> ([Int], [Int])
sumt xs = sumtHelper xs ([], [])
  where
    -- 辅助尾递归函数：参数是剩余列表、当前奇数累加器、当前偶数累加器
    sumtHelper :: [Int] -> ([Int], [Int]) -> ([Int], [Int])
    sumtHelper [] (odds, evens) = (reverse odds, reverse evens)
    sumtHelper (x:xs) (odds, evens)
      | x `mod` 2 == 1 = sumtHelper xs (x : odds, evens)  -- 奇数加到累加器头部
      | otherwise = sumtHelper xs (odds, x : evens)        -- 偶数加到累加器头部

代码解释 #

1. 尾递归逻辑：sumtHelper的最后一步总是调用自身，没有后续的列表拼接操作，符合尾递归的要求，编译器可以把它优化成循环，避免栈溢出。
2. 守卫判断：通过x mod 2 == 1判断奇数，否则判定为偶数，分别更新对应的累加器列表。
3. 累加器与反转：我们选择把元素加到累加器的头部（这是O(1)的高效操作），所以最后需要反转两个累加器，才能得到和原列表顺序一致的子列表。比如处理[1,2,3,4]时：
   • 处理1后：odds = [1]，evens = []
   • 处理2后：odds = [1]，evens = [2]
   • 处理3后：odds = [3,1]，evens = [2]
   • 处理4后：odds = [3,1]，evens = [4,2]
   • 最后反转得到([1,3], [2,4])，完美符合要求！

为什么你的原有代码行不通？ #

你的代码尝试直接从递归结果中取子列表拼接，但这样会导致类型错误：x : (fst $ tupl xs)返回的是一个列表，而函数需要返回二元组，逻辑完全不对。而且这种写法不是尾递归，因为递归调用后还要做列表拼接操作，编译器没办法优化，大数据量下容易出现栈溢出。

内容的提问来源于stack exchange，提问作者Bercovici Adrian