Monad Transformers

Question

I've run into the same scenario involving Monad Transformers a few times now, and I'm looking for some "best-practice" advice.

Bear with the introduction, the issue itself is really simple:

---

Say you're given a list of inputs, and you want to convert them into some aggregated form while handling the possibility of invalid inputs. In code, we could have something like:

type Input = String
type ProcessedInput = String
type Output = S.Set ProcessedInput
data Error = InvalidFormat Input
           | DuplicateInput ProcessedInput

processInput :: Input -> Maybe ProcessedInput

-- Useful later, not vital to the problem
ifM :: Monad m => m Bool -> m a -> m a -> m a
ifM cond t f = cond >>= \c -> if c then t else f

and we want something like:

buildInputs :: [Input] -> Either Error Output

I've found that it's normally nicer to compute this inside a little isolated monad transformer stack (StateT around an Except, so we can build up our result and handle errors when needed) instead of doing a bunch of maps and any checks and aggregations.

So the question: Is it "better" to express this computation as acting on single inputs, or acting on the entire input? Bearing in mind that this is an entirely self-contained computation, it won't need to be used as a subcomputation anywhere else.

---

Using a "single-input" action requires some slightly unintuitive wrapping in buildInputs:

buildInputs :: [Input] -> Either Error Output
buildInputs is = runExcept $ execStateT builder S.empty
        where builder = sequence (map buildInputs' is)

buildInputs' :: Input -> StateT Output (Except Error) ()
buildInputs' i = case processInput i of
                    Nothing -> throwError (InvalidFormat i)
                    Just p  -> ifM (gets $ S.member p)
                                       (throwError $ DuplicateInput p)
                                       (modify $ S.insert p)

---

Using a "whole-input" action gives a cleaner wrapper at the cost of a messier body:

buildInputs :: [Input] -> Either Error Output
buildInputs is = runExcept $ execStateT (buildInputs2' is) S.empty

buildInputs' :: [Input] -> StateT Output (Except Error) ()
buildInputs' [] = return ()
buildInputs' (i:is) = case processInput i of
                        Nothing -> throwError (InvalidFormat i)
                        Just p  -> do
                                    ifM (gets $ S.member p)
                                            (throwError $ DuplicateInput p)
                                            (modify $ S.insert p)
                                    buildInputs' is

---

Is there a best-practice convention for this sort of thing? Is there an entirely better way of doing this that I've missed?

^{Complete code here}

Answer 1

The loop in the second one is precisely what combinators like sequence and map are meant to capture and factor away. Thus, I find the first version is more idiomatic.

It's always possible to turn a program on single inputs to one on whole inputs by wrapping it in a loop like your second snippet does, but not the other way around in general, because a program on lists might make non-trivial use of the remaining tail (is). In that sense, your first version contains more information, that is lost when transforming it into the second one, and keeping it may thus improve readability: we know more about what the function cannot do.

---

On a smaller scale, sequence and map together are also called traverse, and since in this case we are collecting the results in a separate structure we only need a fold (traverse_) rather than a traversal, which puts the individual () outputs in a list. Here again, by using a more general function, we signal that the "regular output" of the computation (that would be [()]) is irrelevant.

When the loop body (buildInputs') is small and called only at one location, it may be worth inlining it, and for_ is sometimes nicer than traverse_ for that (for_ = flip traverse_) and makes the code look nicely imperative when it is meant to be.

The pattern-match on the result of process could also be refactored to be quieter.

buildInputs :: [Input] -> Either Error Output
buildInputs is = runExcept (execStateT go S.empty) where
  go = for_ is $ \i -> do
    p <- processInput i `ifFail` throwError (InvalidFormat i)
    collides <- gets $ S.member p  -- The variable name tells what this is checking
    when collides $ throwError (DuplicateInput p)
    modify $ S.insert p

ifFail :: Applicative m => Maybe a -> m a -> m a
ifFail (Just a) _ = pure a
ifFail Nothing oops = oops