In my project I ended up using the following unfold function in several places.
unfold :: (a -> Either b a) -> a -> b
unfold f x = either id (unfold f) $ f x
It feels like a very general recursion pattern (simply apply a function on values of type a until you get a Right b), but I'm failing to find such a function somewhere with Hoogle.
Is it really not defined anywhere?
This function is implemented in the extra package as Control.Monad.Extra.loop.
loop :: (a -> Either a b) -> a -> bA looping operation, where the predicate returns Left as a seed for the next loop or Right to abort the loop.
loop (\x -> if x < 10 then Left $ x * 2 else Right $ show x) 1 == "16"
The extra package also provides a monadic version loopM.
As a future note, in addition to searching Hoogle for a function by name, you can simply plug in a type signature and Hoogle will look for functions matching this signature. I found the above function by entering (a -> Either a b) -> a -> b into Hoogle as such.
If you want a version with the type arguments flipped from the extra version, there's also iterateM_ from the monad-loops package.
iterateM_ :: Monad m => (a -> m a) -> a -> m b
This doesn't solve your problem in one step, but it's capturing the underlying pattern of recursion more accurately.
Note that there's nothing specific to Either going on in there, which does make it a bit trickier to find. I found it via hoogle by name. I didn't know if it existed, but I knew that if something by that name did exist, it would solve your problem. I derived that starting from iterate in base. It repeatedly applies a function to the output from the previous step, with an initial seed value, like you wanted. But you wanted to be able to short circuit at any time, which Either's monad instance does for you, so a name like iterateM would make more sense. Except you don't care about all the intermediate results, so iterateM_ would be the name that makes sense.
(Also, it turns out everything that does produce the intermediate results requires a streaming system to do it. Which makes sense in retrospect, but explains why hoogle changed what packages it was showing results from entirely when I added the "_" at the end.)
Now, as far as this not actually being exactly the type you want: yes, a bit was lost when it became more generic. But that can be recovered in a bit of an interesting way. Look back at the type of iterateM_, and notice that the return value is m b, and b wasn't mentioned anywhere previously in the type. This is subtle but significant information. Since there's no way a function can just make up a value of a polymorphic type it knows nothing about, it means that it can never produce such a value at all. Let's inline Either in the type and see what happens: iterateM_ :: (a -> Either r a) -> a -> Either r b. How can we safely convert Either r b to r? Well, we know we can choose anything at all for b, because it can't exist. And fortunately, there are tools to handle this.
base contains a module, Data.Void, that helps here. It has a type Void that has no constructors. You can think of it as a type-level signifier that something can't happen. And since it can't happen, there's an adapter to make things fit together on the value level as needed: absurd :: Void -> a. The name comes from logic, based on the idea that once the impossible happens once you're in a silly case and might as well allow anything else to happen. At an operational level, you can have values of type Void in Haskell because undefined :: Void will type-check. But absurd is perfectly safe regardless - it forces its argument to be evaluated. Since any time it actually is evaluated the argument must be a bottom value of some sort, this remains type-safe.
So how does this fit in with iterateM_? Well, things have worked out so there's an Either r b value that we know must be the Left constructor, but using fromLeft feels dirty. But what's interesting here is that while r is constrained by context, b is still completely polymorphic. We can choose whatever type we want for it, because we know it'll never happen. So choose Void, giving either id absurd :: Either r Void -> r
unfold :: (a -> Either b a) -> a -> b
unfold f x = either id absurd $ iterateM_ f x
Maybe that's not even an improvement on your original. Maybe it is - the recursion is captured in a combinator instead of explicit. And for what it's worth, that combinator captures a more general pattern of recursion than something specific to Either. But that has the cost of introducing an extra conversion step to realign the types afterwards, and that step ends up involving a new idea that wasn't necessary before. On the plus side, it makes a nice illustration for how to use the type system to communicate things clearly.