Discussion:
Hindley-Milner Algorithm Time Complexity
(too old to reply)
Homayoon
2010-04-11 12:50:38 UTC
Permalink
Does anyone know of a resource with a time analysis on the Hindley-
Milner algorithm?

I hope this is not too off topic. I've seen discussions about the HM
algorithm and also time complexity on this group so I thought this
might be (at least a little bit) relevant.

Thanks,
Homayoon
Dirk Thierbach
2010-04-11 15:51:22 UTC
Permalink
Post by Homayoon
Does anyone know of a resource with a time analysis on the Hindley-
Milner algorithm?
HM is worst-time exponential. A simple Haskell example is

let dup x = (x,x)

Then

dup . dup . dup . ... . dup

has a type that is exponential in size wrt. to the size of the term,
so the time needed for the typing itself must also be (at least)
exponential.

Experience shows, however, that for "real-world" examples it's usually
runs in polynomial time.

- Dirk
Homayoon
2010-04-11 16:04:15 UTC
Permalink
Post by Dirk Thierbach
Post by Homayoon
Does anyone know of a resource with a time analysis on the Hindley-
Milner algorithm?
HM is worst-time exponential. A simple Haskell example is
  let dup x = (x,x)
Then  
  dup . dup . dup . ... . dup  
has a type that is exponential in size wrt. to the size of the term,
so the time needed for the typing itself must also be (at least)
exponential.
Experience shows, however, that for "real-world" examples it's usually
runs in polynomial time.
- Dirk
Thanks for your answer. Is there a source that I can reference about
the real world performance you are referring to. I'm going to do a
presentation about this at class, so I need to cite a reference to
make a claim. Also, isn't there a way to make an average time
analysis, instead of worst case?
Christian Maeder
2010-04-12 08:38:57 UTC
Permalink
Post by Homayoon
Thanks for your answer. Is there a source that I can reference about
the real world performance you are referring to. I'm going to do a
presentation about this at class, so I need to cite a reference to
Michael I. Schwartzbach
Polymorphic Type Inference
1995
http://www.brics.dk/LS/95/3/BRICS-LS-95-3.ps.gz

HTH Christian
Post by Homayoon
make a claim. Also, isn't there a way to make an average time
analysis, instead of worst case?
Loading...