CODEWITHSUNDEEP
haskell
Łukasz Karczewski
Łukasz Karczewski

Reputation: 1208

`sequence` seems to work incorrectly with `Either`

When I use sequence on Maybe, everything seems to work fine:

sequence [Just 2, Just 3] == Just [2, 3]
sequence [Just 2, Just 3, Nothing] == Nothing

The result type is as per the sequence type: (Traversable t, Monad m) => t (m a) -> m (t a), the m (t a) becomes Maybe [Int] and it is correct for Nothing too.

However, if I do something like this:

sequence [Right 2, Right 3] == Right [2, 3]
sequence [Right 2, Right 3, Left 4] == Left 4

How is Left 4 of type m (t a)? If Right [2, 3] is Either [Int] then Left 4 should also by of that type, but obviously (to me) it isn't. What am I missing?

Upvotes: 1

Views: 31

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477210

Let is first do the type analysis. The m is not Either, the m is m ~ Either b. Indeed, since m takes a single type parameter.

So if we set m ~ Either b, then we get:

(Traversable t) => t (Either b a) -> Either b (t a)

and with t ~ [], we thus get:

[Either b a] -> Either b [a]

You can see Either b as a more sophisticated version of Maybe where Left e is used to show an error (computation that failed) with e the error object (this can for example be a string, or some other type), and Right x, a computation that succeeded with x the result. In that case sequence will thus check if the list of computations succeeded, and if it did it will return a Right [x1, x2, …, xn], and if one of the computations failed, it will return the first "error object".

This is based on the instance of Monad (Either b), indeed [src]:

-- | @since 4.4.0.0
instance Monad (Either e) where
    Left  l >>= _ = Left l
    Right r >>= k = k r

For a Left l, it will thus return a Left l, whereas for a Right, it will apply k to the result r.

Upvotes: 2

Related Questions