Take first Rights from list in Haskell

Question

Firstly, I have a (infinite) list of Eithers, which is produced like this:

x :: A
...

f :: A -> Either B A
...

xs :: [Either B A]
xs = iterate (>>=f) (Right x)

The list will contain several Rights (always a finite number) and then the same Left value repeated. What I need is to take all the Rights and one Left after them. In this particular case it can be done also by changing the function for example, but I'm also interested in best general method.

Answer 1

Let me suggest a more invasive change. Instead of

x :: A
f :: A -> Either B A
xs :: [Either B A]

consider

x :: A
f :: A -> Writer [A] B

and forget xs entirely. Where before f was a single step of the iteration, it is now recursive; where before it would return Right a, you now tell [a] >> f a; where before it would return Left b, you now return b.

If it's really necessary, you can still access the individual pieces of the Writer, namely the [A] and B, via execWriter and evalWriter (or by using runWriter to access them both at once):

xs :: [A]
b :: B
(xs, b) = runWriter (f x)

Answer 2

You could use span to split the list between the Right elements and the Left ones, then pattern match to grab the first Left.

(rights, firstLeft : _) = span isRight xs
    where isRight (Right _) = True
          isRight _         = False

Answer 3

I'd do it like this, if you need to keep them all in the same list:

answer = map fst . takeWhile snd $ zip xs (True : map isRight xs)
  where isRight (Right _) = True
        isRight _         = False

(Why aren't isRight and isLeft defined in Data.Either?)