2 Basic Types

Computers represent data internally as sequences of bits. Types give meaning to these sequences. At the same time, types restrict the range of possible values any piece of data can take. Type systems provide a set of primitive or built-in types and a set of rules for combining these types.

In this chapter we will look at some of the commonly available primitive types (empty, unit, Booleans, numbers, strings, arrays and references), their uses, and common pitfalls to be aware of. While we use primitive types every day, each comes with subtle nuances we should be aware of in order to use them effectively: for example, Boolean expressions can be short-circuited, and numerical expressions can overflow.

We’ll start with some of the simplest types which carry little or no information and move on to types which represent data via various encodings. Finally, we’ll look at arrays and references, which are building blocks for all other more complex data structures.

2.1       Designing Functions That Don’t Return Values

Viewing types as sets of possible values, you may wonder whether there is a type to represent the empty set. The empty set has no elements, so this would be a type for which we can never create an instance. Would such a type be useful?

2.1.1 The Empty Type

2.1.2 The Unit Type

2.1.3 Exercises

2.2       Boolean Logic and Short Circuits

2.2.1 Boolean Expressions

2.2.2 Short Circuit Evaluation

2.2.3 Exercise

2.3       Common Pitfalls of Numerical Types

2.3.1 Integer Types and Overflow

2.3.2 Floating-point Types and Rounding

2.3.3 Arbitrarily Large Numbers

2.3.4 Exercises

2.4       Encoding Text

2.4.1 Breaking Text

2.4.2 Encodings

2.4.3 Encoding Libraries

2.4.4 Exercises

2.5       Building Data Structures with Arrays and References

2.5.1 Fixed-Size Arrays

2.5.2 References

2.5.3 Efficient Lists

2.5.4 Binary Trees

2.5.5 Associative Arrays

2.5.6 Implementation Tradeoffs

2.5.7 Exercise

2.6       Summary

2.7       Answers to Exercises