Haskell has infinite and recursive types but its type system is perfectly decidable, mainly because Haskell's type system is nominal, so cycles are easily detected and dealt with.