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

Question

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?

Bolshevist

Answer 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.

Deci

Can you provide some examples? – Zoo

Can you please explain Haskell from a Scala developer's perspective? – Cirsoid

@Apocalisp: Higher-order unification is undecidable and even when a unifier can be found, the MGU is not uniquely defined. At best this seems to leave a deeply embedded non-determinism in Haskell. What use is made of higher-order unification in Haskell and how are its tractability and non-uniqueness issues handled? – Nahshunn

Randall: It's entirely possible that I'm conflating HOU with whatever mechanism of unifying partially applied type constructors is available in GHC Haskell. Changing the answer to reflect this. – Deci

I wish that these kind of comparisons were available for all permutations of programming languages. – Sassanid

@RandallSchulz Are you sure about that? To my knowledge, higher-order unification is decidable, but rank-k unification is not for k > 2. This wouldn't normally be an issue for Haskell (since it only has rank-2 types), but the algorithms for deciding rank-2 unification are so pathological that Haskell simply goes the undecidable route. In other words, Haskell does not have full type reconstruction (by choice). In other news, even if Haskell did full type reconstruction on rank-2 types, it wouldn't be a Hindley-Milner type system. – Grafton

(continued) "Hindley-Milner" refers to a class of type systems, of which Haskell is not a member. "Damas-Milner" refers to a constraint unification-based algorithm for deciding full type reconstruction. Haskell's type checker is a very distant derivation of this algorithm. – Grafton

@Deci First-class functions cannot be universally quantified in Scala because it lacks a direct mechanism for higher-rank types. This has nothing to do with first-class modules. Well, actually that's not really true. First-class modules introduce a very strange type form which is easily munged into either an existential or a rank-2 type, allowing universally-quantified first-class functions. Either way, your statement isn't really true. Awesome answer, otherwise! – Grafton

@Daniel: The oracle agrees with me: en.wikipedia.org/wiki/… (for what that's worth). That article discusses several related algorithms that are decidable. – Nahshunn

@RandallSchulz In that article, "higher-order unification" refers to unification-based reconstruction of higher-rank types. I thought "higher-order" was referring to unification of a system with type constructor polymorphism. – Grafton

There's an overloading of "higher-order" here. I was originally using "higher-order unification" to mean unification of higher-order type variables (not higher rank, which introduces ambiguity). Any algorithm that is decidable at the type level is certainly decidable at the kind level as well, or at any level in the tower of universes. – Deci

@Deci There are subtle interactions between a universe and the level above which makes your statement a little hard to prove. In practice though, I suspect your claim holds for anything non-pathological. – Grafton

Answer 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.

Jp

Do you know whether such a treatment has been published in the six years since this post? I'd be interested to read that paper. – Frothy