Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I was talking to a friend about the differences between the type systems of Haskell and Java. He asked me what Haskell's could do that Java's couldn't, and I realized that I didn't know.

After thinking for a while, I came up with a very short list of minor differences. Not being heavy into type theory, I'm left wondering whether they're formally equivalent.

To try and keep this from becoming a subjective question, I'm asking: what are the major, non-syntactical differences between their type systems? I realize some things are easier/harder in one than in the other, and I'm not interested in talking about those.

And to make it more specific, let's ignore Haskell type extensions since there's so many out there that do all kinds of crazy/cool stuff.

share|improve this question
3  
I too am curious to hear the long winded category theorists answer to this question; though I doubt I will particularly understand it, I am still interested in a detailing of this. My inclination from things I've read is that the HM type system allows the compiler to know a ton about what your code does which is why it is capable of inferring types so much as well as giving so many guarantees about the behavior. But that's just my gut instinct and I'm sure there are other things to it which I'm utterly unaware of. –  Jimmy Hoffa Oct 8 '12 at 16:07
1  
This is a great question - time to tweet it out to followers for the great Haskell/JVM debate! –  Martijn Verburg Oct 8 '12 at 16:17
1  
@Matt Fenwick Being a functional language Haskell has built in support for higher-order functions; you can easily apply map or reduce over a list in Haskell for example. Of course the same functionality can be provided with Java also, but not directly. –  m3th0dman Oct 8 '12 at 16:36
5  
@m3th0dman: Scala has the exact same support for higher-order functions as Java has. In Scala, first-class functions are simply represented as instances of abstract classes with a single abstract method, just like Java. Sure, Scala has syntactic sugar for defining these functions, and it has a rich standard library of both pre-defined function types and methods that accept functions, but from a type system perspective, which is what this question is about, there is no difference. So, if Scala can do it, then Java can, too, and in fact there are Haskell-inspired FP libraries for Java. –  Jörg W Mittag Oct 8 '12 at 16:41
5  
@m3th0dman They're perfectly ordinary types. There's nothing special about lists except some synactic niceties. You can easily define your own algebraic data type that's equivalent to the built-in list type except for the literal syntax and the names of the constructors. –  sepp2k Oct 8 '12 at 18:38

5 Answers 5

up vote 50 down vote accepted

("Java", as used here, is defined as standard Java SE 7; "Haskell", as used here, is defined as standard Haskell 2010.)

Things that Java's type system has but that Haskell's doesn't:

  • nominal subtype polymorphism
  • partial runtime type information

Things that Haskell's type system has but that Java's doesn't:

  • bounded ad-hoc polymorphism
    • gives rise to "constraint-based" subtype polymorphism
  • higher-kinded parametric polymorphism
  • principal typing

EDIT:

Examples of each of the points listed above:

Unique to Java (as compared to Haskell)

Nominal subtype polymorphism

/* declare explicit subtypes (limited multiple inheritance is allowed) */
abstract class MyList extends AbstractList<String> implements RandomAccess {

    /* specify a type's additional initialization requirements */
    public MyList(elem1: String) {
        super() /* explicit call to a supertype's implementation */
        this.add(elem1) /* might be overridden in a subtype of this type */
    }

}

/* use a type as one of its supertypes (implicit upcasting) */
List<String> l = new ArrayList<>() /* some inference is available for generics */

Partial runtime type information

/* find the outermost actual type of a value at runtime */
Class<?> c = l.getClass // will be 'java.util.ArrayList'

/* query the relationship between runtime and compile-time types */
Boolean b = l instanceOf MyList // will be 'false'

Unique to Haskell (as compared to Java)

Bounded ad-hoc polymorphism

-- declare a parametrized bound
class A t where
  -- provide a function via this bound
  tInt :: t Int
  -- require other bounds within the functions provided by this bound
  mtInt :: Monad m => m (t Int)
  mtInt = return tInt -- define bound-provided functions via other bound-provided functions

-- fullfill a bound
instance A Maybe where
  tInt = Just 5
  mtInt = return Nothing -- override defaults

-- require exactly the bounds you need (ideally)
tString :: (Functor t, A t) => t String
tString = fmap show tInt -- use bounds that are implied by a concrete type (e.g., "Show Int")

"Constraint-based" subtype polymorphism (based on bounded ad-hoc polymorphism)

-- declare that a bound implies other bounds (introduce a subbound)
class (A t, Applicative t) => B t where -- bounds don't have to provide functions

-- use multiple bounds (intersection types in the context, union types in the full type)
mtString :: (Monad m, B t) => m (t String)
mtString = return mtInt -- use a bound that is implied by another bound (implicit upcasting)

optString :: Maybe String
optString = join mtString -- full types are contravariant in their contexts

Higher-kinded parametric polymorphism

-- parametrize types over type variables that are themselves parametrized
data OneOrTwoTs t x = OneVariableT (t x) | TwoFixedTs (t Int) (t String)

-- bounds can be higher-kinded, too
class MonadStrip s where
  -- use arbitrarily nested higher-kinded type variables
  strip :: (Monad m, MonadTrans t) => s t m a -> t m a -> m a

Principal typing

This one is difficult to give a direct example of, but it means that every expression has exactly one maximally general type (called its principal type), which is considered the canonical type of that expression. In terms of "constraint-based" subtype polymorphism (see above), the principal type of an expression is the unique subtype of every possible type that that expression can be used as. The presence of principal typing in (unextended) Haskell is what allows complete type inference (that is, successful type inference for every expression, without any type annotations needed). Extensions that break principal typing (of which there are many) also break the completeness of type inference.

share|improve this answer
6  
Don't use l as a single letter variable, it is VERY difficult to distinguish from 1! –  awashburn Sep 29 '13 at 19:32
5  
It may be worth noting, that while you are absolutely right that Java has some runtime type information and Haskell does not, you can use the Typeable type-class in Haskell to provide something which behaves like runtime type information for many types (with newer PolyKinded classes on the way, it will be all types iirc), although I think it depends on the situation whether it actually passes any type information at runtime or not. –  DarkOtter Sep 30 '13 at 14:25
2  
@DarkOtter I'm aware of Typeable, but Haskell 2010 does not have it (maybe Haskell 2014 will?). –  Ptharien's Flame Sep 30 '13 at 15:13
3  
What about (closed) sum types? They're one of the more important mechanisms for encoding constraints. –  tibbe Sep 30 '13 at 20:12
2  
Nullability? Soundness (no covariance sillinses)? Closed sum types/pattern matches? This answer is way too narrow –  Peaker Sep 30 '13 at 20:55

Java's type system lacks higher kinded polymorphism; Haskell's type system has it.

In other words: in Java, type constructors can abstract over types, but not over type constructors, whereas in Haskell, type constructors can abstract over type constructors as well as types.

In English: in Java a generic can't take in another generic type and parameterize it,

public void <Foo> nonsense(Foo<Integer> i, Foo<String> j)

while in Haskell this is quite easy

higherKinded :: Functor f => f Int -> f String
higherKinded = fmap show
share|improve this answer
21  
Mind running that by us again, in English this time? :P –  Mason Wheeler Oct 8 '12 at 16:33
7  
@Matt: As an example I can't write this in Java, but I can write the equivalent in Haskell: <T<_> extends Collection> T<Integer> convertStringsToInts(T<string> strings). The idea here would be that if someone called it as convertStringsToInts<ArrayList> it would take an arraylist of strings and return an arraylist of integers. And if they instead used convertStringsToInts<LinkedList>, it'd be the same with linked lists instead. –  sepp2k Oct 8 '12 at 18:32
6  
Isn't this higher-kinded polymorphism, rather than rank 1 vs n? –  Adam Oct 8 '12 at 19:05
6  
@JörgWMittag: My understanding is that higher-rank polymorphism concerns where you can put the forall in your types. In Haskell, a type a -> b is implicitly forall a. forall b. a -> b. With an extension, you can make these foralls explicit and move them around. –  Tikhon Jelvis Oct 9 '12 at 3:51
6  
@Adam is rigtht: higher rank and higher kinded are totally different. GHC can also do higher ranked types (i.e. forall types) with some language extension. Java knows neither higher kinded nor higher ranked types. –  Ingo Oct 11 '12 at 12:57

To complement the other answers, Haskell's type system doesn't have subtyping, while typed object oriented languages as Java do.

In programming language theory, subtyping (also subtype polymorphism or inclusion polymorphism) is a form of type polymorphism in which a subtype is a datatype that is related to another datatype (the supertype) by some notion of substitutability, meaning that program elements, typically subroutines or functions, written to operate on elements of the supertype can also operate on elements of the subtype. If S is a subtype of T, the subtyping relation is often written S <: T, to mean that any term of type S can be safely used in a context where a term of type T is expected. The precise semantics of subtyping crucially depends on the particulars of what "safely used in a context where" means in a given programming language. The type system of a programming language essentially defines its own subtyping relation, which may well be trivial.

Due to the subtyping relation, a term may belong to more than one type. Subtyping is therefore a form of type polymorphism. In object-oriented programming the term 'polymorphism' is commonly used to refer solely to this subtype polymorphism, while the techniques of parametric polymorphism would be considered generic programming...

share|improve this answer
3  
Though that does not mean you don't get ad-hoc polymorphism. You do, just in a different form (type classes instead of subtype polymorphism). –  delnan Oct 9 '12 at 6:30
2  
Subclassing is not subtyping! –  Frank Shearar Oct 1 '13 at 17:47

One thing nobody's mentioned so far is type inference: a Haskell compiler can usually infer the type of expressions but you have to tell the Java compiler your types in detail. Strictly, this is a feature of the compiler but the design of the language and type system determines whether type inference is feasible. In particular, type inference interacts badly with Java's subtype polymorphism and ad hoc overloading. In contrast, the designers of Haskell try hard not to introduce features that impact type inference.

Another thing people don't seem to have mentioned so far is algebraic data types. That is, the ability to construct types from sums ('or') and products ('and') of other types. Java classes do products (field a and field b, say) fine. But they don't really do sums (field a OR field b, say). Scala has to encode this as multiple case classes, which isn't quite the same. And while it works for Scala it's a bit of a stretch to say Java has it.

Haskell can also construct function types using the function constructor, ->. While Java's methods do have type signatures, you can't combine them.

Java's type system does enable a type of modularity that Haskell hasn't got. It will be a while before there's an OSGi for Haskell.

share|improve this answer
1  
@MattFenwick, I modified the 3rd paragraph based on your feedback. The two type systems do treat functions very differently. –  GarethR Oct 1 '13 at 21:55

Some minor differences:

  1. Haskell has infinite data types. [1..] Lazy evaluation required.
  2. Haskell has pattern matching
  3. Haskell has checking of side effects
  4. Type inference
  5. Type classes
share|improve this answer
5  
Yep, some of these were on my short list of minor differences ... I decided not to include them because 1,2,3 aren't really about the type system, 4 is orthogonal to the expressive power or formal properties of the type system, and I'm not sure about 5. –  Matt Fenwick Oct 8 '12 at 17:49
3  
Yes, especially lazy evaluation is not a property of a type system. You can have lazy-evaluated languages with no type system at all and vice versa. Points 2. and 3. are syntactical differences. –  Petr Pudlák Oct 8 '12 at 21:17
2  
Haskell doesn't have infinite types either. –  Wes Feb 18 '13 at 4:16
2  
@KristopherMicinski an infinite type is something like (a -> a -> ...) not a lazily evaluated value. –  Wes Sep 30 '13 at 17:39
3  
To clarify: The OP is confusing the type language and the value language. You can have recursive types like data List a = Cons a | Nil but that is a finite type, not an infinite one, although it can be used to construct "infinite" data structures. –  Wes Sep 30 '13 at 17:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.