string - MissingHのような外部ライブラリを使用せずに、Haskellで文字列の部分文字列を別の文字列に置き換えるにはどうすればよいですか?

Question

外部ライブラリを使用せずに、Haskell で部分文字列を文字列に置き換え、可能であればパフォーマンスを向上させたいと考えています。

置換関数を使用することを考えましたが、プログラム全体を移植して の代わりに型Data.Textを使用したくありません。を値にパックしてから、必要なものを置き換えてから、その Text 値をアンパックして多くの場合に遅くなりますか?TextStringsStringTextStringStrings

Answer 1

これを試してください（テストされていません）：

replace :: Eq a => [a] -> [a] -> [a] -> [a]
replace needle replacement haystack
  = case begins haystack needle of
      Just remains -> replacement ++ remains
      Nothing      -> case haystack of
                        []     -> []
                        x : xs -> x : replace needle replacement xs

begins :: Eq a => [a] -> [a] -> Maybe [a]
begins haystack []                = Just haystack
begins (x : xs) (y : ys) | x == y = begins xs ys
begins _        _                 = Nothing

Textただし、一般に、sの代わりにsを使用するようにプログラムを切り替えると、パフォーマンスが向上しますString。