Haskell traverse and filter through a list while lifting results

Question

Say I have code where I want to do the following:

1. Input: a list of strings [String]
2. Operation (checkSat and checkResult)
   • Obtains a boolean from an input string.
3. Output:
   • If everything in the input is parseable into a boolean, only return those that resulted in "unsat".
   • If at least one of them has an error, return an error.

data Err = Err String deriving (Show)

-- Detail omitted for this example
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

The code above doesn't quite work. What's the right way to write onlyUnsat with the correct typing?

Answer 1

Try this:

onlyUnsat :: [String] -> Either Err [String]
onlyUnsat = traverse checkSat >=> filterM (fmap not . checkResult)

  where

  filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a]
  filterM p = fmap (map fst . filter snd) . traverse (\x -> withFst x <$> p x)
    where withFst x = \y -> (x, y)

  (>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
  f >=> g = \x -> f x >>= g

Note that both filterM and >=> can be imported from Control.Monad. I've redefined them here for the sake of clarity :-)

The basic idea is to split the operation into two stages: (1) apply checkSat on every item in the list; and (2) filter every item in the list. The first stage is given by traverse checkSat, which has type [String] -> Either Err [String]. The second stage is given by filterM (fmap not . checkResult), which also has type [String] -> Either Err String. We then use >=> to chain these two computations together into one of the same type.