Lazyness and the duality between Sums and Products

Eithers.hs

{-# LANGUAGE NoImplicitPrelude #-}
import Data.Foldable
import Control.Applicative

data Either a b = Left a | Right b

data Eithers t a b
  = Eithers
  { lefts :: t a
  , rights :: t b
  }

consEither :: Either a b -> Eithers [] a b -> Eithers [] a b
consEither e (Eithers xs ys) = case e of
  Left x -> Eithers (x:xs) ys
  Right y -> Eithers xs (y:ys)

eithers :: Foldable t => t (Either a b) -> Eithers [] a b
eithers = foldr consEither (Eithers [] [])

genericEithers :: (Foldable t, Alternative s) => t (Either a b) -> Eithers s a b
genericEithers = foldr f' (Eithers empty empty)
  where
    f' e (Eithers xs ys) = case e of
      Left x -> Eithers (pure x <|> xs) ys
      Right y -> Eithers xs (pure y <|> ys)