What are the differences and similarities of Scala and Haskell type systems?

How to explain Scala's type system to a Haskell expert? What examples show Scala's advantages?

How to explain Haskell's type system to an advanced Scala practitioner? What can be done in Haskell that can't be done in Scala?


Solution 1:

Scala To a Haskell programmer:

Scala is a strict and impure language with first-class modules. Data types are declared as "classes" or "traits" with subtle differences, and modules or "objects" are values of those types. Scala supports type constructors taking universally quantified type parameters. Objects/classes/traits have members which consist of values, mutable variables, and functions (called "methods", to which the module is implicitly passed as a variable called this). Modules may have type members which can also take parameters. Type members are existentially quantified and type parameters can be higher-kinded. Because types can be members of first-class values, Scala provides a flavour of dependent typing called path-dependent types.

First-class functions are also modules. A function is a module with a method named apply. A method is not first-class, but a syntax is provided to wrap a method in a first-class function. Unfortunately, a module requires all of its type parameters up front, hence a partially applied first-class function is not allowed to be universally quantified. More generally, Scala completely lacks a direct mechanism for types of rank higher than 1, but modules parameterized on higher-kinded types can be exploited to simulate rank-n types.

Instead of type classes with global scope, Scala lets you declare an implicit value of any given type. This includes function types, which provides implicit conversion, and therefore type extension. In addition to implicit conversions, type extension is provided by the "extends" mechanism which lets you declare a subtype/supertype relation among modules. This mechanism can be used to simulate algebraic datatypes where the supertype can be seen as the type on the left-hand side of a data declaration, and its subtypes as the value constructors on the right-hand side. Scala has extensive pattern-matching capabilities using a virtualized pattern matcher with first-class patterns.

Scala supports subtyping, and this limits type inference considerably. But type inference has improved over time. Inference of higher kinded types is supported. However, Scala lacks any meaningful kind system, and therefore has no kind inference and no kind unification. If a type variable is introduced, it is of kind * unless annotated otherwise. Certain types like Any (the supertype of all types) and Nothing (a subtype of every type) are technically of every kind although they cannot be applied to type arguments.

Haskell to a Scala programmer:

Haskell is a purely functional language. This means that functions are not allowed to have any side-effects at all. For example, a Haskell program doesn't print to the screen as such, but is a function that returns a value of the IO[_] datatype which describes a sequence of actions for the IO subsystem to perform.

Whereas Scala is strict by default and provides "by-name" annotation for nonstrict function arguments, Haskell is lazy by default using "by-need" semantics, and provides annotation for strict arguments.

Type inference in Haskell is more complete than in Scala, having full inference. This means that type annotation is almost never necessary.

Recent extensions to the GHC compiler allow advanced type system features that have no equivalent in Scala, such as rank-n types, type families, and kinds polymorphism.

In Haskell, a module is a collection of types and functions, but modules are not first-class entities. Implicits are provided by type classes, but these are globally scoped once declared, and they cannot be passed explicitly as in Scala. Multiple instances of a type class for a given type are resolved by wrapping with a newtype to disambiguate, whereas in Scala this would be solved simply by scoping or by passing instances explicitly.

Since Haskell isn't "object-oriented", there's no method/function dichotomy. Every function is first class and every function is curried by default (no Function1, Function2, etc).

Haskell has no subtype mechanism, but type classes can have a subclass relationship.

Solution 2:

I don't believe anyone has systematically compared Haskell (as exemplified by GHC's type system) with Scalas. The main points of difference are the degree of type inference, and support for higher-rank types. But a full treatment of the differences would be a publishable result.