Haskell 用递归实现字符串子串替换 不可使用take和drop函数

实现思路 #

要实现多字符子串替换，我们需要两个递归实现的辅助函数，分别完成前缀匹配和指定长度字符跳过的能力，全程不依赖内置的take/drop函数。

完整实现代码 #

1. 前缀匹配辅助函数 #

用于判断当前字符串是否以目标子串为前缀：

startsWith :: String -> String -> Bool
startsWith "" _ = True
startsWith _ "" = False
startsWith (p:ps) (c:cs) = p == c && startsWith ps cs

2. 跳过指定长度字符辅助函数 #

用于匹配到子串后，跳过原字符串中对应旧子串长度的字符：

skipN :: Int -> String -> String
skipN 0 s = s
skipN _ "" = ""
skipN n (_:cs) = skipN (n-1) cs

3. 主替换函数 #

replaceSub :: String -> String -> String -> String
replaceSub "" _ s = s -- 空模式无需替换，避免无限递归
replaceSub _ _ "" = ""
replaceSub old new s@(c:cs)
  | startsWith old s = new ++ replaceSub old new (skipN (length old) s)
  | otherwise = c : replaceSub old new cs

效果测试 #

调用replaceSub "er" "ol" "qwer sder"即可得到预期结果"qwol sdol"。

内容的提问来源于stack exchange，提问作者Bohdan Chornopolskyi