Haskell遍历过滤列表并提升Either结果的正确实现方法

需求说明 #

需要实现的逻辑如下：

• 输入：字符串列表 [String]
• 处理流程：调用checkSat和checkResult两个函数，从每个输入字符串计算得到对应的布尔值结果
• 输出规则：
  • 所有输入都能成功解析为布尔值时，仅返回结果为"unsat"的条目
  • 只要有一个条目处理出错，直接返回错误

给定的基础代码如下，原onlyUnsat实现无法通过类型检查、运行不符合预期：

data Err = Err String deriving (Show)

-- 本示例省略具体实现细节
checkSat :: String -> Either Err String
checkSat = Right . id

checkResult :: String -> Either Err Bool
checkResult "sat"    = Right True
checkResult "unsat"  = Right False
checkResult err      = Left $ Err err

onlyUnsat :: [String] -> Either Err [String]
onlyUnsat xs = filter (traverse notSat xs) xs
  where notSat x  = fmap not $ checkSat x >>= checkResult
        onlyUnsat = filter (traverse notSat xs) xs

原代码问题 #

原实现存在三个核心错误：

1. filter仅接受返回纯Bool值的谓词，无法直接处理返回Either Err Bool的带错误上下文的判断逻辑，类型不匹配
2. where子句中重复定义了同名onlyUnsat，会触发无限递归
3. traverse notSat xs的返回值是Either Err [Bool]，不能直接作为filter的谓词参数

正确实现 #

核心思路是先通过traverse完成全量错误检查——只要任意一个条目处理失败就提前返回错误，全部检查通过后再做筛选：

onlyUnsat :: [String] -> Either Err [String]
onlyUnsat xs = map fst . filter snd <$> traverse tagAndCheck xs
  where
    tagAndCheck x = do
      isSat <- checkSat x >>= checkResult
      -- 元组第一个元素存原字符串，第二个元素标记是否为需要保留的unsat条目
      pure (x, not isSat)

逻辑说明 #

• traverse tagAndCheck xs会按顺序处理所有输入：遇到错误时直接返回Left Err，全部处理成功则得到Right [(String, Bool)]类型的标记列表
• 用<$>在Either上下文内执行后续筛选：filter snd保留标记为需要保留的条目，map fst取出原字符串即可得到最终结果

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