Oops, this email got stuck in the pipe (flaky internet):
 
  foldMap _ Tip = mempty
  foldMap f (Bin _ _ v l r) = Foldable.foldMap f l `mappend` f v `mappend` Foldable.foldMap f r

Btw, from my perspective, one problem with relying on foldMap is that it treats the whole structure uniformly, whereas the split approach would let one, for example, bottom out to a sequential implementation at a certain granularity.  Perhaps that is the "boilerplate for controlling recursion" that you referred to... but isn't it sometimes necessary?

   -Ryan