Take the 2-minute tour ×

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?
share|improve this question
add comment

4 Answers

up vote 33 down vote accepted

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)
share|improve this answer
Those advanced features aren't inherently limited to functional languages though. –  sepp2k Jul 1 '10 at 20:51
@sepp2k true - can you think of a type system feature that is inherently limited to functional languages? –  Simon Marlow Jul 1 '10 at 21:17
No. That's why I wouldn't say that there is much of a relation between the "functional level of a language" and the type system. –  sepp2k Jul 1 '10 at 21:22
It would be possible to make a functional language without the use of lambda calculus. In fact, a language with the two-ary boolean function NAND as its only only operation is turing complete. NAND looks pretty referentially transparent to me. –  Zorf Jul 7 '10 at 21:46
@Lajla: Depends upon your definition of "functional". –  Jon Harrop Aug 14 '10 at 11:39
show 1 more comment

What role does the type system play in a functional language?

To Simon Marlow's excellent answer, I would add that a type system, especially one that includes algebraic data types, makes it easier to write programs:

  • Software designs, which in object-oriented languages are sometimes expressed using UML diagrams, are very clearly expressed using types. This clarity manifests especially when not only values have types, but also modules have types, as in Objective Caml or Standard ML.

  • When a person is writing code, a couple of simple heuristics make it very, very easy to write pure functions based on the types:

    • A value of function type can always be created with a lambda.
    • A value of function type can always be consumed by applying it.
    • A value of an algebraic data type can be created by applying any of the type's constructors.
    • A value of an algebraic data type can be consumed by scrutinizing it with a case expression.

    Based on these observations, and on the simple rule that unless there's a good reason, a function should consume each of its arguments, it's pretty easy to cut down the space of possible code you could write to a very small number of candidates. For example, there just aren't that many sensible functions of type (using Haskell notation)

    forall a . (a -> Bool) -> [a] -> Bool

    The art of using types to create code is called type-directed programming. When it works well, you hear functional programmers say things like "once we got the types right, the code practically wrote itself." Since the types are usually much smaller than the code, this is a big win.

share|improve this answer
add comment
  1. Same as in any programming language: it helps you to avoid/find errors in your code. In case of static typing a good type system prevents programs with certain types of errors from compiling.
  2. No. The untyped lambda calculus is what you could call the prototype of functional programming languages and it is, as the name suggests, entirely untyped.
  3. In a functional language (as well as any other language where a function can be used as a value) the type system needs to know what the type of a function is. Other than that there is nothing special about type systems for functional languages.

    In a purely functional language you need to abstract side-effects, so you'd want the type system to somehow be able to support that. For example if you want to have a world type like in Clean, you'd want the type system to support uniqueness types to ensure proper usage.

    If you want to have an IO monad like in haskell, you'd need an IO type (though a monad typeclass like in haskell is not required to have an IO monad, so you don't need a type system, which supports that).

share|improve this answer
Do you mean that there is no difference between the "functional" level of a language by it being statically or dynamically typed? –  Abhinav Sarkar Jul 1 '10 at 20:33
@abhin4v: I'm note sure what you mean by "functional level" –  sepp2k Jul 1 '10 at 20:52
add comment

1: Same as any other, it stops you from doing operations that are either ill-defined, or whose result would be 'nonsensical' to humans. Like float addition on integers.
2: Nope, the oldest programming language in the world, the (untyped) lambda calculus, is both functional and untyped.
3: Hardly, functional just means no side effects, no mutations, referential transparency et cetera.

Just remember that the oldest functional language, the untyped lambda calculus has no type system.

share|improve this answer
add comment

Your Answer


