You mention no run-time type erasure, but avoiding indirection can be crucial for some applications of compositions. For example, if composition is nested (n-1)-times, e.g. for n=4:
auto f_4 = compose(f_3, compose(f_2, compose(f_1, f_0)));
then if I am not mistaken you will have 3 levels of...