Converting a list of Eithers to an Either containing a list

user_1411129 0
Viewed 138

I have a function which returns a list of Either items. If it only contains Right items I want to return a single Right containing a list of the values in the original Right items, but if it contains any Left items I want a single Left containing a list of the values in the original Left items. So if I have: [Right "a", Right "b", Right "c"] it should become: Right ["a", "b", "c"] but if I have: [Right "a", Left "b", Right "c", Left "d"] it should become: Left ["b", "d"]

Note: The sequence function from Control.Monad isn't suitable because it only keeps the first Left item.

I have come up with this:

eitherList :: [Either a1 a2] -> Either [a1] [a2]
eitherList l = if null lefts
               then Right rights
               else Left lefts
  where f1 (Left a) (al, ar) = (a : al, ar)
        f1 (Right a) (al, ar) = (al, a : ar)
        (lefts, rights) = foldr f1 ([], []) l

but it seems clumsy. Is there a simpler or better way of doing this? I'm just starting to learn about functors and monads and I'm wondering if these are relevant?

haskell
2 Answers

The sequence function from Control.Monad isn't suitable because it only keeps the first Left item.

You had the right idea, just missing a few details. There is a package, validation, that offers a type called Validation, which is shaped just like Either:

data Validation err a
  = Failure err
  | Success a

But notably, its Applicative instance works as you want, appending the “error” values together:

instance (Semigroup err) => Applicative (Validation err) where

  pure = Success

  Failure e1 <*> Failure e2 = Failure (e1 <> e2)
  Failure e1 <*> Success _  = Failure e1
  Success _  <*> Failure e2 = Failure e2
  Success f  <*> Success a  = Success (f a)

Unlike Either, Validation can’t have a Monad instance, so you need to use the more general sequenceA (or traverse) instead of sequence (or mapM):

sequence  :: (Traversable t, Monad m)       => t (m a) -> m (t a)
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

mapM      :: (Traversable t, Monad m)       => (a -> m b) -> t a -> m (t b)
traverse  :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

The Data.Validation module exports various functions for converting to and from Either. For your purpose, a good choice is liftError:

liftError :: (b -> e) -> Either b a -> Validation e a

singleton :: a -> [a]
singleton = pure

liftError singleton :: Either e a -> Validation [e] a

Here it is all together:

import qualified Data.Validation as Validation

eitherList :: [Either e a] -> Either [e] [a]
eitherList = Validation.toEither . traverse (Validation.liftError pure)
-- Note: ‘traverse f’ = ‘sequenceA . fmap f’

And your examples work as expected:

> example1 = [Right "a", Right "b", Right "c"]

> example2 = [Right "a", Left "b", Right "c", Left "d"]

> eitherList example1
Right ["a","b","c"]

> eitherList example2
Left ["b","d"]
user_2468860

Most of the heavy lifting can be done by Data.Either.partitionEithers:

eitherList :: [Either a1 a2] -> Either [a1] [a2]
eitherList l = case (partitionEithers l) of
                  ([], rs) -> Right rs
                  (ls, _) -> Left ls

(The implementation of partitionEithers is very similar to what you wrote for the fold.)

user_11268410
Related