Skip to content

Instantly share code, notes, and snippets.

@chrisdone
Last active Jul 23, 2018
Embed
What would you like to do?
Origamic fold
-- | 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)
@rampion
Copy link

rampion commented Aug 11, 2017

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment