使用 foldr 处理字符串，其中“#”表示删除前一个字符

Question

我需要使用 foldr 处理字符串，其中 '#' 表示删除前一个字符。例如：

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

>backspace "#####"
""

需要使用foldr遍历列表，而不使用reverse and/or (++).

到目前为止我得到的是：

backspace :: String -> String
backspace xs = foldr func [] xs where
  func c cs | c /= '#' = c:cs
            | otherwise = cs

但它只是从字符串中过滤掉 '#'。我想每次 c == '#' 删除当前答案的最后一个元素并得到类似的东西

backspace :: String -> String
backspace xs = foldr func [] xs where
  func c cs | c /= '#' = c:cs
            | cs /= [] = init cs
            | otherwise = cs

但它不能正常工作，

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

Answer 1

您可以使用 (Int, String) 作为 foldr 的状态，其中第一个 Int 是退格的数量，String 是当前构造的字符串。

这意味着您可以使用：

backspace :: String -> String
backspace = snd . foldr func (0, [])
  where func '#' (n, cs) = (<b>n+1</b>, cs)
        func c (n, cs)
                 | n > 0 = …      -- (1)
                 | otherwise = …  -- (2)

如果我们有一个字符不是 #，而是 n > 0，这意味着我们需要删除该字符，因此忽略 c 并递减 n.如果 n == 0 我们可以将 c 添加到 String.

我将填写 … 部分作为练习。

使用 foldr 处理字符串，其中“#”表示删除前一个字符

Process a string using foldr where '#' means deleting the previous character

haskell

list

fold