gistfile1.hs

combine :: [Either a b] -> ((a,b) -> c) -> [c]
combine xs f = combine' (Nothing, Nothing) xs 
  where
  combine' (_, Just y) (Left l:xs) =
    f (l,y) : combine' (Just l, Just y) xs
  combine' (Just x, _) (Right l:xs) =
    f (x,l) : combine' (Just x, Just l) xs
  combine' (_, y) (Left l : xs)  =
    combine' (Just l, y) xs
  combine' (x, _) (Right l : xs) =
    combine' (x, Just l) xs
  combine' _ [] = []

eithers = [Left 3, Right 10, Right 20, Right 30, Left 1]

-- *Main> combine eithers (uncurry (+))
-- [13,23,33,31]

You may want to check out the Arrow Transformers library, particularly Control.Arrow.Transformer.ArrowState:

https://hackage.haskell.org/package/arrows-0.4.1.2/docs/Control-Arrow-Transformer-State.html

However it is possible to do implement your combine function using ordinary State monads, with (Maybe Int, Maybe Int) as the state value, and using Control.Monad.mapM to update the state with each item in the list. In the following example, the Arrow operators ||| and *** are used to unwrap the Left or Right input and apply it to the first or second element of the stateful tuple.

import Control.Arrow
import Control.Monad
import Control.Monad.State
import Data.Maybe

combine :: [Either a b] -> ((a,b) -> c) -> [c]
combine xs f = combine' (Nothing, Nothing) xs
  where
  combine' (_, Just y) (Left l:xs) =
    f (l,y) : combine' (Just l, Just y) xs
  combine' (Just x, _) (Right l:xs) =
    f (x,l) : combine' (Just x, Just l) xs
  combine' (_, y) (Left l : xs)  =
    combine' (Just l, y) xs
  combine' (x, _) (Right l : xs) =
    combine' (x, Just l) xs
  combine' _ [] = []

eithers :: [Either Int Int]
eithers = [Left 3, Right 10, Right 20, Right 30, Left 1]

monadStateCombine :: [Either a b] -> (a -> b -> c) -> [c]
monadStateCombine xs f = concat $ evalState (mapM combine' xs) (Nothing, Nothing) where
  combine' x = do
    modify $ (*** id) . const . Just ||| (id ***) . const . Just $ x
    liftM (maybeToList . uncurry (liftM2 f)) get

main :: IO ()
main = do
  print $ combine eithers $ uncurry (+)
  print $ monadStateCombine eithers (+)