Origamic fold

Origami.hs

-- | Fold over the input, folding left or right depending on the element.
origami :: (s -> l -> s) -> (r -> s -> s) -> s -> [Either l r] -> s
origami _ _ nil [] = nil
origami fl fr nil (x:xs) =
  case x of
    Left l -> origami fl fr (fl nil l) xs
    Right r -> fr r (origami fl fr nil xs)

How about this:

loop :: (sl -> l -> sl) -> (r -> sr -> sr) -> sl -> sr -> [Either l r] -> (sl, sr)
loop _ _ sl sr [] = (sl, sr)
loop fl fr sl sr (x : xs) = case x of
  Left l -> loop fl fr (fl sl l) sr xs
  Right r -> fr r <$> loop fl fr sl sr xs

Then your original function is equivalent to:

origami :: (s -> l -> s) -> (r -> s -> s) -> s -> [Either l r] -> s
origami fl fr s xs = let ~(s', s'') = loop fl fr s s' in s''

But we can just as easily tie the knot the other way

origami' :: (s -> l -> s) -> (r -> s -> s) -> s -> [Either l r] -> s
origami' fl fr s xs -> let ~(s'', s') = loop fl fr s' s xs in s''

Whereas origami is semantically equivalent to foldr fr (foldl fl s as) bs, origami' has the semantics of foldl fl (foldr fr s bs) as where (as, bs) = partitionEithers xs.