Functional Programming and Type Systems

Question

I have been learning about various functional languages for some time now including Haskell, Scala and Clojure. Haskell has a very strict and well-defined static type system. Scala is also statically typed. Clojure on the other hand, is dynamically typed.

So my questions are

1. What role does the type system play in a functional language?
2. Is it necessary for a language to have a type system for it to be functional?
3. How is the "functional" level of a language related to the kind of the type system of the language?

Answer 1

A language does not need to be typed to be functional - at the heart of functional programming is the lambda calculus, which comes in untyped and typed variants.

The type system plays two roles:

• it provides a guarantee at compile time that a class of errors cannot occur at run-time. The class of errors usually includes things like trying to add two strings together, or trying to apply an integer as a function.
• it has some efficiency benefits, in that objects at runtime do not need to carry their types around, because the types have already been established at compile-time. This is known as type erasure.

In advanced type systems like Haskell's, the type system can provide more benefits:

• overloading: using one identifier to refer to operations on different types
• it allows a library to automatically choose an optimised implementation based on what type it is used at (using Type Families)
• it allows powerful invariants to be proven at compile time, such as the invariant in a red-black tree (using Generalised Algebraic Datatypes)