Analysing the Complexity of Functional Programs: Higher-Order Meets First-Order (Long Version)

Martin Avanzini, Ugo Dal Lago, Georg Moser

We show how the complexity of higher-order functional programs can be analysed automatically by applying program transformations to a defunctionalized versions of them, and feeding…