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

Nils Anders Danielsson nad at cs.chalmers.se
Tue Nov 13 04:57:45 EST 2007

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"
The paper also lists some related work which may be useful to you.


More information about the Haskell-Cafe mailing list