I need to process a string using foldr where '#' means deleting the previous character. For example:

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

>backspace "#####"
""

It needs to be done using foldr through one pass of the list, without using reverse and/or ( ).

Here what I have got so far:

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

But it just filter the '#' from the string. I thought about deleting the last element of current answer every time c == '#' and got something like that

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

but it is not working properly,

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

CodePudding user response：

You can use (Int, String) as state for your foldr where the first Int is the number of backspaces, and the String is the current string constructed.

This thus means that you can work with:

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

In case we have a character that is not a #, but n > 0 it means we need to remove that character, and thus ignore c and decrement n. In case n == 0 we can add c to the String.

I leave filling in the … parts as an exercise.