Sat Apr 7 16:53:35 CEST 2012
foldr from traverse + monad
Defining foldl is simple using the State monad:
foldl f s b = s' where
(_, s') = runState (traverse f' b) s
f' b = modify (flip f b)
Instead of "updating" state we could build a nested computation with
a hole in it. Is this somehow dual?
Indeed, and the approach is quite straightforward.
foldr f s b = k' s where
(_, k') = runState (traverse f' b) (\s -> s)
f' b = modify (\k -> (\s -> k $ f b s))
Instead of getting a new state value by applying a function to it, it
works the other way around. It takes the hole in which the final
value of the computating is inserted and replaces it with a different
hole, observes what is put in that hole, modifies it and puts the
result in the original hole.
Both approaches are dual: one updates values, the other updates holes.
Once duality pops up you find it everywhere of course:
- foldl / foldr are dual in the order they traverse and "cons" a list
- the above also works with State and RState (reverse State)
- in Data.Foldable the dual of a monoid is used to implement
foldr/foldl in terms of foldMap (library/base/Data/Foldable.hs)