Haskell apply函数优化：正确应用规则并避免字符重复

问题背景 #

需要实现规则替换函数 apply :: State -> [Rule] -> State，类型定义如下：

type State = String
data Rule = Rule Char State deriving Show

预期调用 apply "FXRYF" [Rule 'X' "XRYF", Rule 'Y' "FXLY"] 返回 "FXRYFRFXLYF"，但当前实现代码返回错误结果 "FFXRYFXRRYFXLYFF"。

错误代码 #

type State = String
data Rule = Rule Char State deriving Show 

apply :: State -> [Rule] -> State
apply state rules = concat [if char == c then s else [char] | char <- state, Rule c s <- rules]

错误原因 #

当前列表推导式会同时遍历输入字符串的每个字符和所有规则：

• 对每个字符，每一条规则都会执行一次判断
• 不匹配时就输出原字符，导致原字符被重复输出（比如字符F会被两条规则各输出一次，最终结果里出现多个F）
• 正确逻辑应为：对每个字符，查找匹配的规则，找到则替换，找不到则保留原字符，且仅处理一次

修复方案 #

方案一：利用键值对查找 #

通过将Rule转换为键值对，使用lookup快速找到匹配规则：

type State = String
data Rule = Rule Char State deriving Show 

apply :: State -> [Rule] -> State
apply state rules = concatMap replaceChar state
  where
    replaceChar :: Char -> State
    replaceChar c = case lookup c (map ruleToPair rules) of
                      Just s -> s
                      Nothing -> [c]
    ruleToPair :: Rule -> (Char, State)
    ruleToPair (Rule char str) = (char, str)

方案二：递归查找匹配规则 #

手动递归遍历规则列表，找到第一个匹配项：

type State = String
data Rule = Rule Char State deriving Show 

apply :: State -> [Rule] -> State
apply state rules = concat [maybe [char] id $ findMatch char rules | char <- state]
  where
    findMatch :: Char -> [Rule] -> Maybe State
    findMatch _ [] = Nothing
    findMatch c (Rule rc s:rs)
      | c == rc = Just s
      | otherwise = findMatch c rs

方案说明 #

• 两个方案均对输入字符串的每个字符单独处理：
  1. 查找第一个匹配当前字符的规则
  2. 找到则用规则对应的字符串替换原字符
  3. 未找到则保留原字符
• 测试调用 apply "FXRYF" [Rule 'X' "XRYF", Rule 'Y' "FXLY"]，会返回预期结果 "FXRYFRFXLYF"

内容的提问来源于stack exchange，提问作者Karim Jakobsen