This textbook is about systematic problem solving and systematic
reasoning using type-driven design. There are two problem solving
techniques that are emphasized throughout the book: divide and conquer
and iterative refinement. Divide and conquer is the process by which a
large problem is broken into two or more smaller problems that are
easier to solve and then the solutions for the smaller pieces are
combined to create an answer to the problem. Iterative refinement is the
process by which a solution to a problem is gradually made better-like
the drafts of an essay. Mastering these techniques are essential to
becoming a good problem solver and programmer.
The book is divided in five parts. Part I focuses on the basics. It
starts with how to write expressions and subsequently leads to decision
making and functions as the basis for problem solving. Part II then
introduces compound data of finite size, while Part III covers compound
data of arbitrary size like e.g. lists, intervals, natural numbers, and
binary trees. It also introduces structural recursion, a powerful
data-processing strategy that uses divide and conquer to process data
whose size is not fixed. Next, Part IV delves into abstraction and shows
how to eliminate repetitions in solutions to problems. It also
introduces generic programming which is abstraction over the type of
data processed. This leads to the realization that functions are data
and, perhaps more surprising, that data are functions, which in turn
naturally leads to object-oriented programming. Part V introduces
distributed programming, i.e., using multiple computers to solve a
problem.
This book promises that by the end of it readers will have designed and
implemented a multiplayer video game that they can play with their
friends over the internet. To achieve this, however, there is a lot
about problem solving and programming that must be learned first. The
game is developed using iterative refinement. The reader learns
step-by-step about programming and how to apply new knowledge to develop
increasingly better versions of the video game. This way, readers
practice modern trends that are likely to be common throughout a
professional career and beyond.
