I'm a fan of Data.Foldable, and I wonder if it could be extended to function types by way of Bananas in Space: Extending Fold and Unfold to Exponential Types (mirror) or Boxes Go Bananas: Encoding Higher-Order Abstract Syntax with Parametric Polymorphism (mirror).
Finally, I'm not even so sure that we can't give all of the bananas, lenses, envelopes and barbed wire generic (but more strongly typed than SYB) interfaces for even non-regular datatypes with initial algebra semantics (code here).
I think the first and second questions above are worth bothering the Haskell libaries mailing list about, so I did: Paramorphisms / Data.Scanable? (mirror), Catamorphisms for arrows? (mirror). As before, I expect I'll have to push harder (by actually writing some code) if I want any changes made.