5.2.1 Types and subtypes

Conceptually, a type is a set of values (i.e., possible states or objects) and a set of operations defined on the values in that set.

Similarly, a type S is (a behavioral) subtype of type T if the set of values of type S is a “subset” of the values in set T an set of operations of type S is a “superset” of the operations of type T. That is, we can safely substitute elements of subtype S for elements of type T because S’s operations behave the “same” as T’s operations.

This is known as the Liskov Substitution Principle [11,19].

Consider a type representing all furniture and a type representing all chairs. In general, we consider the set of chairs to be a subset of the set of furniture. A chair should have all the general characteristics of furniture, but it may have additional characteristics specific to chairs.

If we can perform an operation on furniture in general, we should be able to perform the same operation on a chair under the same circumstances and get the same result. Of course, there may be additional operations we can perform on chairs that are not applicable to furniture in general.

Thus the type of all chairs is a subtype of the type of all furniture according to the Liskov Substitution Principle.

5.2.2 Constants, variables, and expressions

Now consider the types of the basic program elements.

A constant has whatever types it is defined to have in the context in which it is used. For example, the constant symbol 1 might represent an integer, a real number, a complex number, a single bit, etc., depending upon the context.

A variable has whatever types its value has in a particular context and at a particular time during execution. The type may be constrained by a declaration of the variable.

An expression has whatever types its evaluation yields based on the types of the variables, constants, and operations from which it is constructed.

5.2.3 Static and dynamic

In a statically typed language, the types of a variable or expression can be determined from the program source code and checked at “compile time” (i.e., during the syntactic and semantic processing in the front-end of a language processor). Such languages may require at least some of the types of variables or expressions to be declared explicitly, while others may be inferred implicitly from the context.

Java, Scala, and Haskell are examples of statically typed languages.

In a dynamically typed language, the specific types of a variable or expression cannot be determined at “compile time” but can be checked at runtime.

Lisp, Python, JavaScript, and Lua are examples of dynamically typed languages.

Of course, most languages use a mixture of static and dynamic typing. For example, Java objects defined within an inheritance hierarchy must be bound dynamically to the appropriate operations at runtime. Also Java objects declared of type Object (the root class of all user-defined classes) often require explicit runtime checks or coercions.

5.2.4 Nominal and structural

In a language with nominal typing, the type of value is based on the type name assigned when the value is created. Two values have the same type if they have the same type name. A type S is a subtype of type T only if S is explicitly declared to be a subtype of T.

For example, Java is primarily a nominally typed language. It assigns types to an object based on the name of the class from which the object is instantiated and the superclasses extended and interfaces implemented by that class.

However, Java does not guarantee that subtypes satisfy the Liskov Substitution Principle. For example, a subclass might not implement an operation in a manner that is compatible with the superclass. (The behavior of subclass objects are this different from the behavior of superclass objects.) Ensuring that Java subclasses preserve the Substitution Principle is considered good programming practice in most circumstances.

In a language with structural typing, the type of a value is based on the structure of the value. Two values have the same type if they have the “same” structure; that is, they have the same public data attributes and operations and these are themselves of compatible types.

In structurally typed languages, a type S is a subtype of type T only if S has all the public data values and operations of type T and the data values and operations are themselves of compatible types. Subtype S may have additional data values and operations not in T.

Haskell is primarily a structurally typed language.

5.2.5 Polymorphic operations

Polymorphism refers to the property of having “many shapes”. In programming languages, we are primarily interested in how polymorphic function names (or operator symbols) are associated with implementations of the functions (or operations).

In general, two primary kinds of polymorphism exist in programming languages:

1. Ad hoc polymorphism, in which the same function name (or operator symbol) can denote different implementations depending upon how it is used in an expression. That is, the implementation invoked depends upon the types of function’s arguments and return value.

   There are two subkinds of ad hoc polymorphism.

   1. Overloading refers to ad hoc polymorphism in which the language’s compiler or interpreter determines the appropriate implementation to invoke using information from the context. In statically typed languages, overloaded names and symbols can usually be bound to the intended implementation at compile time based on the declared types of the entities. They exhibit early binding.

      Consider the language Java. It overloads a few operator symbols, such as using the + symbol for both addition of numbers and concatenation of strings. Java also overloads calls of functions defined with the same name but different signatures (patterns of parameter types and return value). Java does not support user-defined operator overloading; C++ does.

      Haskell’s type class mechanism, which we examine in a later chapter, implements overloading polymorphism in Haskell. There are similar mechanisms in other languages such as Scala and Rust.

   2. Subtyping (also known as subtype polymorphism or inclusion polymorphism) refers to ad hoc polymorphism in which the appropriate implementation is determined by searching a hierarchy of types. The function may be defined in a supertype and redefined (overridden) in subtypes. Beginning with the actual types of the data involved, the program searches up the type hierarchy to find the appropriate implementation to invoke. This usually occurs at runtime, so this exhibits late binding.

      The object-oriented programming community often refers to inheritance-based subtype polymorphism as simply polymorphism. This the polymorphism associated with the class structure in Java.

      Haskell does not support subtyping. Its type classes do support class extension, which enables one class to inherit the properties of another. However, Haskell’s classes are not types.

2. Parametric polymorphism, in which the same implementation can be used for many different types. In most cases, the function (or class) implementation is stated in terms of one or more type parameters. In statically typed languages, this binding can usually be done at compile time (i.e., exhibiting early binding).

   The object-oriented programming (e.g., Java) community often calls this type of polymorphism generics or generic programming.

   The functional programming (e.g., Haskell) community often calls this simply polymorphism.

5.2.6 Polymorphic variables

A polymorphic variable is a variable that can “hold” values of different types during program execution.

For example, a variable in a dynamically typed language (e.g., Python) is polymorphic. It can potentially “hold” any value. The variable takes on the type of whatever value it “holds” at a particular point during execution.

Also, a variable in a nominally and statically typed, object-oriented language (e.g., Java) is polymorphic. It can “hold” a value its declared type or of any of the subtypes of that type. The variable is declared with a static type; its value has a dynamic type.

A variable that is a parameter of a (parametrically) polymorphic function is polymorphic. It may be bound to different types on different calls of the function.

5.3.1 Integers: Int and Integer

The Int data type is usually an integer data type supported directly by the host processor (e.g., 32- or 64-bits on most current processors), but it is guaranteed to have the range of at least a 30-bit, two’s complement integer.

The type Integer is an unbounded precision integer type. Unlike Int, host processors usually do not support this type directly. The Haskell library or runtime system typically supports this type in software.

Haskell integers support the usual literal formats (i.e., constants) and typical operations:

• Infix binary operators such as + (addition), - (subtraction), * (multiplication), and ^ (exponentiation)

• Infix binary comparison operators such as == (equality of values), /= (inequality of values), <, <=, >, and >=

• Unary operator - (negation)

For integer division, Haskell provides two-argument functions:

• div such that div m n returns the integral quotient truncated toward negative infinity from dividing m by n

• quot such that quot m n returns the integral quotient truncated toward 0 from dividing m bem n

• mod (i.e., modulo) and rem (i.e., remainder) such that

      (div m n) * n + mod m n == m
      (quot m n)* n + rem m n == m 

To make these definitions more concrete, consider the following examples. Note that the result of mod has the same sign as the divisor and rem has the same sign as the dividend.

    div  7 3  == 2 
    quot 7 3  == 2 
    mod  7 3  == 1          -- same sign as divisor
    rem  7 3  == 1          -- same sign as dividend

    div  (-7) (-3) == 2 
    quot (-7) (-3) == 2
    mod  (-7) (-3) == (-1)  -- same sign as divisor
    rem  (-7) (-3) == (-1)  -- same sign as dividend

    div  (-7) 3 == (-3) 
    quot (-7) 3 == (-2)
    mod  (-7) 3 == 2        -- same sign as divisor
    rem  (-7) 3 == (-1)     -- same sign as dividend

    div  7 (-3) == (-3) 
    quot 7 (-3) == (-2) 
    mod  7 (-3) == (-2)     -- same sign as divisor
    rem  7 (-3) == 1        -- same sign as dividend

Haskell also provides the useful two-argument functions min and max, which return the minimum and maximum of the two arguments, respectively.

Two-arguments functions such as div, rem, min, and max can be applied in infix form by including the function name between backticks as shown below:

    5 `div` 3   -- yields 1 
    5 `rem` 3   -- yields 2
    5 `min` 3   -- yields 3 
    5 `max` 3   -- yields 5

5.3.2 Floating point numbers: Float and Double

The Float and Double data types are usually the single and double precision floating point numbers supported directly by the host processor.

Haskell floating point literals must include a decimal point; they may be signed or in scientific notation: 3.14159, 2.0, -2.0, 1.0e4, 5.0e-2, -5.0e-2.

Haskell supports the usual operations on floating point numbers. Division is denoted by / as usual.

In addition, Haskell supports the following for converting floating point numbers to and from integers:

• floor returns the largest integer less than its floating point argument.

• ceiling returns the smallest integer greater than its floating point argument

• truncate returns its argumentas an integer truncated toward 0.

• round returns it argument as an integer rounded away from 0.

• fromIntegral returns its integer argument as a floating point number in a context where Double or Float is required. It can also return its Integer argument as an Int or vice versa.

5.3.3 Booleans: Bool

The Bool (i.e., Boolean) data type is usually supported directly by the host processor as one or more contiguous bits.

The Bool literals are True and False. Note that these begin with capital letters.

Haskell supports Boolean operations such as && (and), || (or), and not (logical negation).

Functions can match against patterns using the Boolean constants. For example, we could define a function myAnd as follows:

    myAnd :: Bool -> Bool -> Bool
    myAnd True  b = b
    myAnd False _ = False

Above the pattern _ is a wildcard that matches any value but does not bind a value that can be used on the right-hand-side of the definition.

The expressions in Haskell if conditions and guards on function definitions must be Bool-valued expressions. They can include calls to functions that return Bool values.

5.3.4 Characters: Char

The Char data type is usually supported directly by the host processor by one or more contiguous bytes.

Haskell uses Unicode for its character data type. Haskell supports character literals enclosed in single quotes—including both the graphic characters (e.g., ’a’, ’0’, and ’Z’) and special codes entered following the escape character backslash \ (e.g., '\n' for newline, '\t' for horizontal tab, and '\\' for backslash itself).

In addition, a backslash character \ followed by a number generates the corresponding Unicode character code. If the first character following the backslash is o, then the number is in octal representation; if followed by x, then in hexadecimal notation; and otherwise in decimal notation.

For example, the exclamation point character can be represented in any of the following ways: ’!’, '\33', '\o41', '\x21'

5.3.5 Functions: t1 -> t2

If t1 and t2 are types then t1 -> t2 is the type of a function that takes an argument of type t1 and returns a result of type t2.

Function and variable names begin with lowercase letters optionally followed by a sequences of characters each of which is a letter, a digit, an apostrophe (') (sometimes pronounced “prime”), or an underscore (_).

Haskell functions are first-class objects. They can be arguments or results of other functions or be components of data structures. Multi-argument functions are curried-–that is, treated as if they take their arguments one at a time.

For example, consider the integer addition operation (+). (Surrounding the binary operator symbol with parentheses refers to the corresponding function.) In mathematics, we normally consider addition as an operation that takes a pair of integers and yields an integer result, which would have the type signature

    (+) :: (Int,Int) -> Int

In Haskell, we give the addition operation the type

    (+) :: Int -> (Int -> Int) 

or just

    (+) :: Int -> Int -> Int

since Haskell binds -> from the right.

Thus (+) is a one argument function that takes some Int argument and returns a function of type Int -> Int. Hence, the expression ((+) 5) denotes a function that takes one argument and returns that argument plus 5.

We sometimes speak of this (+) operation as being partially applied (i.e., to one argument instead of two).

This process of replacing a structured argument by a sequence of simpler ones is called currying, named after American logician Haskell B. Curry who first described it.

The Haskell library, called the standard prelude (or just Prelude), contains a wide range of predefined functions including the usual arithmetic, relational, and Boolean operations. Some of these operations are predefined as infix operations.

5.3.6 Tuples: (t1,t2,...,tn)

If t1, t2, $\cdots$, tn are types, where n is finite and n >= 2, then is a type consisting of n-tuples where the various components have the type given for that position.

Each element in a tuple may have different types. The number of elements in a tuple is fixed.

Examples of tuple values with their types include the following:

    ('a',1) :: (Char,Int)
    (0.0,0.0,0.0) :: (Double,Double,Double) 
    (('a',False),(3,4)) :: ((Char, Bool), (Int, Int))

We can also define a type synonym using the type declaration and the use the synonym in further declarations as follows:

    type Complex = (Float,Float)
    makeComplex :: Float -> Float -> Complex
    makeComplex r i = (r,i)`

A type synonym does not define a new type, but it introduces an alias for an existing type. We can use Complex in declarations, but it has the same effect as using (Float,Float) expect that Complex provides better documentation of the intent.

5.3.7 Lists: [t]

The primary built-in data structure in Haskell is the list, a sequence of values. All the elements in a list must have the same type. Thus we declare lists with notation such as [t] to denote a list of zero or more elements of type t.

A list literal is a comma-separated sequence of values enclosed between [ and ]. For example, [] is an empty list and [1,2,3] is a list of the first three positive integers in increasing order.

We will look at programming with lists in a later chapter.

5.3.8 Strings: String

In Haskell, a string is just a list of characters. Thus Haskell defines the data type String as a type synonym :

    type String = [Char]

We examine lists and strings in a later chapter, but, because we use strings in a few examples in this subsection, let’s consider them briefly.

A String literal is a sequence of zero or more characters enclosed in double quotes, for example, "Haskell programming".

Strings can contain any graphic character or any special character given as escape code sequence (using backslash). The special escape code \& is used to separate any character sequences that are otherwise ambiguous.

For example, the string literal "Hotty\nToddy!\n" is a string that has two newline characters embedded.

Also the string literal "\12\&3" represents the two-element list ['\12','3'].

The function show returns its argument converted to a String.

Because strings are represented as lists, all of the Prelude functions for manipulating lists also apply to strings. We look at manipulating lists and strings in later chapters of this textbook.

5.3.9 Advanced Types

In later chapters, we examine other important Haskell type concepts such as user-defined algebraic data types and type classes.