Re: [Haskell-cafe] Using type-level programming to tag functions with time and space complexity

On Thu, 18 Oct 2007, Daniel McAllansmith wrote:

I was wondering if anyone had done work on tagging functions at the type level with their time or space complexity and, if it's even feasible, calculating the complexity of compound functions.

Any pointers?

I have done some work on this in the context of dependently typed languages. See "Lightweight Semiformal Time Complexity Analysis for Purely Functional Data Structures" (http://www.cs.chalmers.se/~nad/publications/danielsson-popl2008.html). The paper also lists some related work which may be useful to you. -- /NAD