Haskell/Type basics II

From Wikibooks, open books for an open world
Jump to navigation Jump to search

In this chapter, we will show how numerical types are handled in Haskell and introduce some important features of the type system. Before diving into the text, though, pause for a moment and consider the following question: what should be the type of the function (+)?[1]

The Num class[edit | edit source]

Mathematics puts few restrictions on the kinds of numbers we can add together. Consider, for instance, (two natural numbers), (a negative integer and a rational number), or (a rational and an irrational). All of these are valid. In fact, any two real numbers can be added together. In order to capture such generality in the simplest way possible we need a general Number type in Haskell, so that the signature of (+) would be simply

(+) :: Number -> Number -> Number

However, that design fits poorly with the way computers perform arithmetic. While computers can handle integers as a sequence of binary digits in memory, that approach does not work for real numbers,[2] thus making a more complicated encoding necessary for dealing with them: floating point numbers. While floating point provides a reasonable way to deal with real numbers in general, it has some inconveniences (most notably, loss of precision) which makes using the simpler encoding worthwhile for integer values. So, we have at least two different ways of storing numbers: one for integers and another for general real numbers. Each approach should correspond to different Haskell types. Furthermore, computers are only able to perform operations like (+) on a pair of numbers if they are in the same format.

So much for having a universal Number type – it seems that we can't even have (+) mix integers and floating-point numbers. However, Haskell can at least use the same (+) function with either integers or floating point numbers. Check this yourself in GHCi:

Prelude> 3 + 4
7
Prelude> 4.34 + 3.12
7.46

When discussing lists and tuples, we saw that functions can accept arguments of different types if they are made polymorphic. In that spirit, here's a possible type signature for (+) that would account for the facts above:

(+) :: a -> a -> a

With that type signature, (+) would take two arguments of the same type a (which could be integers or floating-point numbers) and evaluate to a result of type a (as long as both arguments are the same type). But this type signature indicates any type at all, and we know that we can't use (+) with two Bool values, or two Char values. What would adding two letters or two truth-values mean? So, the actual type signature of (+) uses a language feature that allows us to express the semantic restriction that a can be any type as long as it is a number type:

(+) :: (Num a) => a -> a -> a

Num is a typeclass — a group of types — which includes all types which are regarded as numbers.[3] The (Num a) => part of the signature restricts a to number types – or, in Haskell terminology, instances of Num.

Numeric types[edit | edit source]

So, which are the actual number types (that is, the instances of Num that the a in the signature may stand for)? The most important numeric types are Int, Integer and Double:

  • Int corresponds to the plain integer type found in most languages. It has fixed maximum and minimum values that depend on a computer's processor. (In 32-bit machines the range goes from -2147483648 to 2147483647).
  • Integer also is used for integer numbers, but it supports arbitrarily large values – at the cost of some efficiency.
  • Double is the double-precision floating point type, a good choice for real numbers in the vast majority of cases. (Haskell also has Float, the single-precision counterpart of Double, which is usually less attractive due to further loss of precision.)

Several other number types are available, but these cover most in everyday tasks.

Polymorphic guesswork[edit | edit source]

If you've read carefully this far, you know that we don't need to specify types always because the compiler can infer types. You also know that we cannot mix types when functions require matched types. Combine this with our new understanding of numbers to understand how Haskell handles basic arithmetic like this:

Prelude> (-7) + 5.12
-1.88

This may seem to add two numbers of different types – an integer and a non-integer. Let's see what the types of the numbers we entered actually are:

Prelude> :t (-7)
(-7) :: (Num a) => a

So, (-7) is neither Int nor Integer! Rather, it is a polymorphic value, which can "morph" into any number type. Now, let's look at the other number:

Prelude> :t 5.12
5.12 :: (Fractional t) => t

5.12 is also a polymorphic value, but one of the Fractional class, which is a subset of Num (every Fractional is a Num, but not every Num is a Fractional; for instance, Ints and Integers are not Fractional).

When a Haskell program evaluates (-7) + 5.12, it must settle for an actual matching type for the numbers. The type inference accounts for the class specifications: (-7) can be any Num, but there are extra restrictions for 5.12, so that's the limiting factor. With no other restrictions, 5.12 will assume the default Fractional type of Double, so (-7) will become a Double as well. Addition then proceeds normally and returns a Double.[4]

The following test will give you a better feel of this process. In a source file, define

x = 2

Then load the file in GHCi and check the type of x. Then, change the file to add a y variable,

x = 2
y = x + 3

reload it and check the types of x and y. Finally, modify y to

x = 2
y = x + 3.1

and see what happens with the types of both variables.

Monomorphic trouble[edit | edit source]

The sophistication of the numerical types and classes occasionally leads to some complications. Consider, for instance, the common division operator (/). It has the following type signature:

(/) :: (Fractional a) => a -> a -> a

Restricting a to fractional types is a must because the division of two integer numbers will often result in a non-integer. Nevertheless, we can still write something like

Prelude> 4 / 3
1.3333333333333333

because the literals 4 and 3 are polymorphic values and therefore assume the type Double at the behest of (/). Suppose, however, we want to divide a number by the number of elements in a list.[5] The obvious thing to do would be using the length function, which takes a list and gives the number of elements in it:

Prelude> length [1,2,3]
3
Prelude> 4 / length [1,2,3]

Unfortunately, that blows up:

<interactive>:1:0:
    No instance for (Fractional Int)
      arising from a use of `/' at <interactive>:1:0-17
    Possible fix: add an instance declaration for (Fractional Int)
    In the expression: 4 / length [1, 2, 3]
    In the definition of `it': it = 4 / length [1, 2, 3]

As usual, the problem can be understood by looking at the type signature of length:

length :: (Foldable t) => t a -> Int

For now, let's focus on the type of the result of length. It is Int; the result is not polymorphic. As an Int is not a Fractional, Haskell won't let us use it with (/).

To escape this problem, we have a special function. Before following on with the text, try to guess what this does only from the name and signature:

fromIntegral :: (Integral a, Num b) => a -> b

fromIntegral takes an argument of some Integral type (like Int or Integer) and makes it a polymorphic value. By combining it with length, we can make the length of the list fit into the signature of (/):

Prelude> 4 / fromIntegral (length [1,2,3])
1.3333333333333333

In some ways, this issue is annoying and tedious, but it is an inevitable side-effect of having a rigorous approach to manipulating numbers. In Haskell, if you define a function with an Int argument, it will never be converted to an Integer or Double, unless you explicitly use a function like fromIntegral. As a direct consequence of its refined type system, Haskell has a surprising diversity of classes and functions dealing with numbers.

Classes beyond numbers[edit | edit source]

Haskell has typeclasses beyond arithmetic. For example, the type signature of (==) is:

(==) :: (Eq a) => a -> a -> Bool

Like (+) or (/), (==) is a polymorphic function. It compares two values of the same type, which must belong to the class Eq and returns a Bool. Eq is simply the class for types of values which can be compared for equality, and it includes all of the basic non-functional types.[6]

A quite different example of a typeclass that we have glossed over has appeared in the type of length. Given that length takes a list and gives back an Int, we might have expected its type to be:

length :: [a] -> Int

The actual type, however, is a little trickier:

length :: (Foldable t) => t a -> Int

Beyond lists, there are other kinds of structures that can be used to group values in different ways. Many of these structures (together with lists themselves) belong to a typeclass called Foldable. The type signature of length tells us that it works not only with lists, but also with all those other Foldable structures. Later in the book, we will see examples of such structures, and discuss Foldable in detail. Until then, whenever you see something like Foldable t => t a in a type signature, feel free to mentally replace that with [a].

Typeclasses add a lot to the power of the type system. We will return to this topic later to see how to use them in custom ways.

Notes

  1. If you followed our recommendations in "Type basics", chances are you have already seen the rather exotic answer by testing with :t... if that is the case, consider the following analysis as a path to understanding the meaning of that signature.
  2. Among other issues, between any two real numbers there are uncountably many real numbers – and that fact can't be directly mapped into a representation in memory no matter what we do.
  3. This is a loose definition, but will suffice until we discuss typeclasses in more detail.
  4. For seasoned programmers: This appears to have the same effect that programs in C (and many other languages) manage with an implicit cast (where an integer literal is silently converted to a double). In C, however, the conversion is done behind your back, while in Haskell it only occurs if the variable/literal is a polymorphic value. This distinction will become clearer shortly, when we show a counter-example.
  5. A reasonable scenario – think of computing an average of the values in a list.
  6. Comparing two functions for equality is considered intractable