CODEWITHSUNDEEP
stringhaskell
Anton Harald
Anton Harald

Reputation: 5924

Remove a Character Sequence From a String

Consider a function, which takes a string and returns a list of all possible cases in which three subsequent 'X's can be removed from the list.

Example:

"ABXXXDGTJXXXDGXF" should become

["ABDGTJXXXDGXF", "ABXXXDGTJDGXF"]

(The order does not matter)

here is a naive implementation:

f :: String -> [String]
f xs =  go [] xs [] where
  go left (a:b:c:right) acc =
    go (left ++ [a]) (b:c:right) y where        -- (1)
    y = if a == 'X' && b == 'X' && c == 'X'
      then (left ++ right) : acc
      else acc
  go _ _ acc = acc

I think the main problem here is the line marked with (1). I'm constructing the left side of the list by appending to it, which is generally expensive.

Usually something like this can be solved by this pattern:

f [] = []
f (x:xs) = x : f xs

Or more explicitly:

f [] = []
f (x:right) = x : left where
  left = f right

Now I'd have the lists right and left in each recursion. However, I need to accumulate them and I could not figure out how to do so here. Or am I on the wrong path?

A solution

Inspired by Gurkenglas' propose, here is a bit more generalized version of it:

import Data.Bool

removeOn :: (String -> Bool) -> Int -> String -> [String]
removeOn onF n xs = go xs where
  go xs | length xs >= n =
    bool id (right:) (onF mid) $
    map (head mid:) $
    go (tail xs)
    where
      (mid, right) = splitAt n xs
  go _ = []

removeOn (and . map (=='X')) 3 "ABXXXDGTJXXXDGXF"
--> ["ABDGTJXXXDGXF","ABXXXDGTJDGXF"]

The main idea seems to be the following: Traverse the list starting from its end. Make use of a 'look-ahead' mechanism which can examine the next n elements of the list (thus it must be checked, if the current list contains that many elements). By this recursive traversal an accumulating list of results is being enhanced in the cases the following elements pass a truth test. In any way those results must be added the current first element of the list because they stem from shorter lists. This can be done blindly, since adding characters to a result string won't change their property of being a match.

Upvotes: 1

Views: 1521

Answers (1)

Gurkenglas
Gurkenglas

Reputation: 2317

f :: String -> [String]
f (a:b:c:right)
  = (if a == 'X' && b == 'X' && c == 'X' then (right:) else id)
  $ map (a:) $ f (b:c:right)
f _ = []

Upvotes: 2

Related Questions