Option
The Option type is
the first polymorphic type that has
been described so far. The definition of Option
is as follows:
The definition introduces a type Option, which
is parameterized by a type variable arbitrarily named
a. It defines two data constructors,
Some and None,
the first of which takes a value of type a. The
type encodes the concept of an optional value:
The programmer is required to pattern match on values of type
Option to determine whether or not a value is
present.
Typically, most programs represent the above as a nullable reference type. This
leads to endless bugs involving accidentally dereferencing null references.
Programs written using Option types are
immune to this class of bugs, as it's statically impossible to get access
to a nonexistent value.
Note that as Option is polymorphic, it may
be instantiated with any other type, including other Option
types:
Choice
The Choice type is a logical continuation
of the Option type. It represents a choice
between values of two types:
As with Option, it may be instantiated with any
other types:
Types isomorphic to the Choice type are often
used to represent computations that may succeed or fail: On success, a value
of type b is returned, and on failure, a value of
of type a is returned (usually some sort of error
code value) .
Pairs
Where the Choice type represents a choice between
two possible values, the Pair type represents
a structure where values of two (possibly different) types will be present
simultaneously. The Pair type is equivalent
to the tuple type in other languages:
Naturally, Pair types can be nested, forming
arbitrarily complex structures:
Most languages have shorthand syntax for constructing values of some standard library
pair type: "(x, y)".
Naturals (inductive)
Many functional languages (particularly those that act as proof assistants)
use the following definition for natural numbers:
This definition is taken directly from axioms 1 and 6 of the
Peano axioms,
and is probably the first type encountered by programmers upon being
introduced to most proof assistants. The type is the first recursive type
described so far; that is, a type that refers to itself in its own
definition.
It's also possible to copy the definition of, for example,
plus, almost directly:
Lists
The List type is a recursive type found in
just about every functional language in existence.
A List is either empty or an
element of some type prepended to another list of elements of that type.
By this definition, lists may contain elements of any type, but each
element of the list has the same type.
Constructing values of type List works
as expected:
Typically, the programmer writes recursive functions to manipulate
values of recursive types. Using pattern matching, it's
possible to write a function such as length
in a couple of lines:
As with the Pair type, Most languages have shorthand
syntax for constructing and matching on lists:
"[x, y, ...]".
Trees
The definition of a binary tree type is similarly simple (and is both polymorphic
and recursive):
Manipulating values of these types should be unsurprising by this point:
Note that, as demonstrated, it's obviously possible to build binary trees
that are unbalanced. In order to preserve invariants such as "the tree must
be balanced", it's often necessary to hide the data constructors of the
given type and then use the module system of the language in question to
expose functions that manipulate values of the tree types internally
. As an example, the Haskell standard library offers high performance
maps and sets based on red-black trees. The programmer is not exposed to the
internal construction of the trees that back the Map and
Set types, but internally they are composed of
nothing more than the algebraic data types described so far.
The
BinaryTree type, as with all the types
discussed so far, is an example of a
persistent
data structure. Persistent data structures offer rather
large benefits with regards to both simplification of and confidence in the
correctness of the code that deals with them compared to their mutable counterparts
(particularly in heavily concurrent/parallel programs).
See
Purely functional data structures by Chris Okasaki,
Cambridge University Press, 1998,
ISBN 0-521-66350-4.
Hiding
As mentioned in the previous section, there may sometimes be additional
restrictions on the creation of values. For example, if the programmer wants
to define a type representing the set of integers greater than or equal to
0, it can't be achieved directly. Most
languages have multiple ways of dealing with this problem. In Haskell, the
simplest way to achieve this is to hide the data constructors of the declared
type, and provide one or more functions that enforce the desired invariants:
The module declaration exports the Natural type,
but does not export its constructor, MakeNatural.
This effectively means that it's not possible for the programmer to construct
values of type Natural directly! However, the module also
exports a function make_natural which takes
an integer and returns an optional value based on whether the integer falls
within the desired range. It also exports a convenient function,
from_natural, which "unwraps" a
Natural value and returns the Integer
contained within .
Essentially, this is a technique to make a given type
abstract. That is, the structure of the type
essentially becomes private. Languages such as
OCaml allow types
to be made abstract using
module signatures.
Java and Ada have the
private keyword for controlling
visibility of (various parts of) types.