やや抽象的な質問で悪いが、こういう時みんなはどうしてる？

規模が比較的大きなデータ構造がある（大きなツリーとかリストとか配列とか）
データ構造の全ての要素ひとつひとつに対して処理を施す仕組み（fold 系とか）がある

このデータ構造に対して、全要素の平均値を求めたり {A1}、
ある条件を満たす要素だけを集めたり {A2}、
平坦にならしてリスト化したり {A3} といった様々な処理を施したい

しかし、データ構造の規模が大きく、また fold 系の処理も軽くはないため、
データ構造の全要素を何度も何度もたどることは好ましくない

こういう場合、今までは fold 系に渡す関数の中で {A1} と {A2} と {A3} を並行的に行い、
結果を３要素タプルにして返してた

こうすると、データ構造をたどるのは１回で済むから効率は良いんだけど、
fold 系に渡す関数の中がちょっと醜くなる
{Am} と {An} の処理の一部を共通化して効率よくするともっと酷くなる
が、仕方がないと思って諦め、可能な限り綺麗になるようにしてる

{A1} を施す fold 系、{A2} を施す fold 系などと別々に用意し、
何らかの方法でそれらを合成すれば一度の巡回で上記のと同じ結果が得られる
なんて方法はないかと、暇があれば考えてるんだけど・・・何かないかな
こういう条件に絞れば可能、とかいう話でも良いんだが
もしできれば、エッセンスを抽出して関数化したいと思ってる