Compiling Rust is NP-hard

Re:Compiling Rust is NP-hard by trissylegs on Thursday July 08, 2021 @06:55AM (#27770375)

I think in Haskell you need to add:

    {-# LANGUAGE UndecidableInstances #-}

to get an Undecidable type system.

[ Parent | on HN ]

Re:Compiling Rust is NP-hard by arianvanp on Thursday July 08, 2021 @07:14AM (#27770492)

There are other language extensions to make the haskell type system undecidable. The classic example is `RankNTypes`

E.g. you can proof that type systems of rank n >= 3 are undecidable. [0]

I think that's why haskell has both Rank2Types and RankNTypes as a language extension. So you can still use higher rank types without running into decidability problems up to rank 2.

[0] https://dl.acm.org/doi/10.1145/182409.182456

[ Parent | on HN ]