`[<<][compsci][>>][..]`
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)

Original question:

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.

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[1])

`[Reply][About]`
`[<<][compsci][>>][..]`