如何使用foldr处理含#退格符的字符串 禁用reverse与++操作

你现有代码的核心问题在于对foldr的遍历方向理解有误：foldr是从右向左处理列表元素，你尝试遇到#就调用init删除结果末尾元素的逻辑是基于从左到右遍历的设计，和foldr的处理方向完全不匹配，自然无法得到正确结果，同时多次调用init也会带来额外的遍历开销，不符合单次遍历的要求。

我们可以让foldr的累积值同时存储两个信息：

• 当前需要跳过的普通字符数量（遇到#就累加这个计数）
• 已经处理完成的结果字符串

处理每个字符的逻辑如下：

• 如果当前字符是#：将跳过计数+1，结果字符串不变
• 如果当前字符是普通字符：
  • 若跳过计数大于0：说明当前字符需要被退格删除，将跳过计数-1，结果字符串不变
  • 若跳过计数等于0：直接将当前字符追加到结果字符串头部，跳过计数不变

最后只需要取出累积值中的结果字符串部分即可，整个过程只做单次遍历，没有使用reverse或者(++)操作，完全符合要求。

backspace :: String -> String
backspace = snd . foldr func (0, [])
  where
    func c (skip, res)
      | c == '#' = (skip + 1, res)
      | skip > 0 = (skip - 1, res)
      | otherwise = (skip, c : res)

ghci> backspace "abc#d##c"
"ac"
ghci> backspace "#####"
""

运行结果完全符合预期。

内容的提问来源于stack exchange，提问作者Bohdan Chornopolskyi