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.

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

[1] http://www.haskell.org/ghc/dist/7.0.4/ghc-7.0.4-src.tar.bz2