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

[Nils Anders Danielsson]

On Thu, 18 Oct 2007, Daniel McAllansmith <dm.maillists at gmail.com> 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