문자열에서 문자 시퀀스 제거

Question

문자열을 사용하여 세 개의 'X'가 목록에서 제거 될 수있는 모든 가능한 경우 목록을 반환하는 함수를 생각해보십시오.

예 :

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 

내가 가장 큰 문제는 여기 생각 :

"ABXXXDGTJXXXDGXF" 여기

는 순진 구현

["ABDGTJXXXDGXF", "ABXXXDGTJDGXF"] 

가 (순서는 중요하지 않습니다)가되어야 (1)로 표시된 선입니다. 나는 그것을 추가함으로써 목록의 왼쪽면을 만들고 있는데, 이것은 일반적으로 비싸다. 이 같은

일반적으로 무언가가이 패턴에 의해 해결 될 수 있습니다

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

지금 내가 바로 각 재귀에 남아있는 목록이있을 것이다 :

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

또는 더 명시 적으로. 그러나, 나는 그것들을 축적 할 필요가있다. 그리고 나는 그렇게 여기에서하는 방법을 이해할 수 없었다. 아니면 잘못된 길에 있습니까? 트래버스 :

이

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"] 

주요 아이디어는 다음과 같은 것 같다 :

---

해결책

여기 제안 'Gurkenglas에서 영감 그것의 좀 더 일반화 된 버전입니다 목록이 끝에서부터 시작됩니다. 목록의 다음 n 요소를 검사 할 수있는 'look-ahead'메커니즘을 사용하십시오 (따라서 현재 목록에 많은 요소가 포함되어 있으면 확인해야합니다). 이 재귀 탐색에 의해 다음 요소가 진실 테스트를 통과하는 경우 누적 된 결과 목록이 향상됩니다. 어떤 식 으로든 그 결과는 목록의 현재 첫 번째 요소에 더해진다. 결과 문자열에 문자를 추가해도 성냥의 속성이 변경되지 않으므로 이는 맹목적으로 수행 할 수 있습니다.

Answer 1

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 _ = []