You should be a bit more precise about what traditional complexity analysis
can/cannot do. It is not so much that a typical analysis must be first
order as that such analyses are first order. In other words, this is an
observation about analysis as it is usually done, not how it must be done.
Accordingly, a typical analysis either implicitly assumes the function
argument of map is unit cost, or really computes the cost of map f. But
typical analyses don't develop a notion of recurrence for map that takes into
account the complexity of using f.
You should be a bit more precise about what traditional complexity analysis can/cannot do. It is not so much that a typical analysis must be first order as that such analyses are first order. In other words, this is an observation about analysis as it is usually done, not how it must be done. Accordingly, a typical analysis either implicitly assumes the function argument of map is unit cost, or really computes the cost of map f. But typical analyses don't develop a notion of recurrence for map that takes into account the complexity of using f.