文字列から文字シーケンスを削除する

Question

文字列を受け取り、後続の3つの 'X'をリストから削除する可能性のあるすべてのケースのリストを返す関数を考えてみましょう。

例：

"ABXXXDGTJXXXDGXF"がここ

["ABDGTJXXXDGXF", "ABXXXDGTJDGXF"] 

（順番は関係ありません）

になるべきではナイーブな実装である：

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 

私はここでの主な問題を考えます（1）でマークされた行です。私はそれを追加することによってリストの左側を構築していますが、これは一般的に高価です。

通常、このようなものは、このパターンによって解決することができます。

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

以上の明示：

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

今、私はリストが右と各再帰に残さなければならないと思います。しかし、私はそれらを蓄積する必要があり、私はここでそれを行う方法を理解できませんでした。または私は間違った道にいるのですか？トラバース ：

は

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