Haskell中如何使用foldr定义recr？

核心问题拆解 #

你现在有两个关键问题：

• recrWithFoldr里的xs是初始传入的完整列表，不会随foldr递归更新，导致tail xs永远取原列表的尾部，完全不符合预期。
• 没搞懂题目里“返回包含原列表的元组”的提示——这正是用foldr实现recr的核心技巧：foldr本身只能拿到当前元素和递归子结果，没法直接获取当前元素对应的剩余列表（也就是recr里的xs参数），所以得用元组把“计算结果”和“当前剩余列表”打包在一起返回。

修正recrWithFoldr实现 #

我们让foldr返回(b, [a])类型的元组：第一个元素是recr要输出的结果，第二个元素是当前节点对应的剩余列表。具体代码如下：

recrWithFoldr :: (a -> [a] -> b -> b) -> b -> [a] -> b
recrWithFoldr f z xs = fst $ foldr g (z, []) xs
    where
        g x (r, rest) = let newRest = x : rest
                        in (f x newRest r, newRest)

逻辑解释 #

• 初始状态元组是(z, [])，对应空列表的处理结果
• 每处理一个元素x，把x拼到之前的剩余列表rest前面，得到当前节点的剩余列表newRest（也就是recr中x:xs里的xs）
• 调用f x newRest r算出当前节点的结果，再和newRest打包成新元组返回
• 最后取元组的第一个元素，就是recr的最终结果

修正trim函数 #

你当前的trim逻辑错误：直接用x : xs会把原剩余列表拼上去，没用到递归结果r。正确的开头去空格逻辑应该是：如果当前字符是空格，就返回递归处理剩余列表的结果；如果不是空格，就把当前字符和递归结果拼接（保留当前字符及后面所有内容）。

修正后的代码：

trim :: [Char] -> [Char]
trim = recr (\x _ r -> if x == ' ' then r else x : r) []

测试示例：

• trim " hello world" → "hello world"
• trim "hello world" → "hello world"（仅删除开头空格，保留中间和结尾空格）

关于foldrWithRecr的验证 #

你的foldrWithRecr实现是正确的，因为recr的第二个参数xs对实现foldr没有作用，直接忽略即可。

内容的提问来源于stack exchange，提问作者Santiago Roussineau