The Haskell Road to Logic, Maths and Programming

Sample from the book (table of contents plus first chapter):

compressed postscript

Addendum to Chapter 9 of the Book: Direct Computation of Polynomial Representations for Sequences:

Errata

A list of errata is here.

Software

Getting Started: GS.hs
Talking about Mathematical Objects: TAMO.hs
The Use of Logic: Proof: TUOLP.hs
Sets, Types and Lists: STAL.hs
Database used in `Sets, Types and Lists' Chapter: DB.hs
Module used in `Sets, Types and Lists' Chapter: Query.hs
Module used in `Sets, Types and Lists' Chapter: SetEq.hs
Module used in `Sets, Types and Lists' Chapter: Hierarchy.hs
Relations: REL.hs
Module used in `Relations' Chapter: SetOrd.hs
Functions: FCT.hs
Induction and Recursion: IAR.hs
Working with Numbers: WWN.hs
Module used in `Working with Numbers' Chapter: Nats.hs
Polynomials:
Corecursion: COR.hs
Module used in `Polynomials' and `Corecursion' Chapter: Polynomials.hs
Module used in `Corecursion' Chapter: Powerseries.hs
Finite and Infinite Sets: FAIS.hs

A Haskell interpreter to run these programs and modules is available from the Haskell homepage. Here is a gentle introduction to Haskell.

Home

Solutions

Please get in touch with Jan van Eijck.

Home

Courses using the book

Note: this is a very incomplete listing: this record was started only in Winter 2010.

Special Topics in Mathematics course, Oklahoma School of Science and Mathematics

Discrete Structures, University of Melbourne

Software testing, Master Programme Software Engineering, University of Amsterdam.

Please let us know if you are using the book for a course.

Home

Reviews

Ralf Laemmel, Book Review "The Haskell Road to Logic, Maths and Programming" (appeared in Jolli, in 2006): pdf.

David Sankel, Book Review in The Journal of Functional Programming, 16(2), 2006:

It should come as no surprise that a textbook has been written that attempts to teach foundational math and introduce programming. Indeed, several undergraduate Computer Science departments schedule both courses side by side. This book, unlike those programmes, attempts to teach the subjects as complementary, using one to learn about the other. Requiring only a secondary education in math, this textbook’s goal is to teach the reader Haskell programming and theorem proving.

The first chapter serves as a short crash-course in Haskell and the hugs interpreter. Subsequent chapters are each about a mathematical topic and use both text and Haskell code to illustrate these concepts. Chapters two through seven analyze foundational math constructs including sets, relations, functions, and induction. The final four chapters touch on more difficult concepts such as corecursion and infinite sets.

Throughout the book, programs are used to illustrate the text. This is one area where the book really excels. As well as illustrating the text, the programs incite further thinking, ensuring a deeper understanding of the mathematical concepts. For example, when teaching recursive proofs over the natural numbers, they solidify understanding by defining, in Haskell, the natural numbers in terms of successors of zero. This style of integrating programs within the text gave the math an applicable feel, absent from most pure math books.

The coverage of proofs, sets, relations, functions, and induction is gentle and effective. New notation is always accompanied by easily understood explanations. Those explanations are supplemented with common mistakes and a variety of examples. This methodology allows one to learn the math with very little background and external support.

In some instances, because the book focuses primarily on mathematical concepts, the reader is deprived of necessary and basic programming knowledge. An example of this is chapter one, where Haskell is introduced. Although someone familiar with programming could read through the chapter with ease, a beginner would likely stumble on some of the undefined words, like stack-overflow and floating point numbers. Furthermore, additional material about how Haskell relates to programming languages in general could have better set the stage.

The Haskell programs in the book are very concise and directly connected to the math they demonstrate. The high-level math constructs which are applied enhance the reader’s ability to write more compact and conceptually elegant programs. Moreover, the reader is forced to think about programming from a declarative point of view, which encourages using higher-level constructs for problem solving. By contrast, most introductory programming books concentrate mostly on successfully solving the problem.

Instead of locating exercises at the end of the each chapter, the authors mixed them within the text and examples. Designed to flow with the text, most of them are quick and have an easy to medium difficulty. The integration of exercises and text gives the book a enjoyable, hands-on feel. Some difficult proof problems, marked with a ‘*’, are scattered throughout the text. Although few in number, they provide excellent preparation for upper level math classes.

On the whole, I think this book would be very successful for use in an introductory college level math course or self learning. The integration of programming provides a unique and enjoyable way to learn math.

Maiz Lulkin, Book Review in goodreads, January 04, 2010:

The most hard core programming language ever - Haskell - presented in a really different and thought provoking way. For those interested in these topics - functional languages, logics and mathematical foundations - i think it's must have.

Home

Reader Feedback

Benjamin Geer, January 10, 2011:

I'm enjoying the book very much. I wish I had had a book like this when I first started learning programming.

Charles Turner, December 10, 2010:

I would like to express my gratitude, I've been struggling with the discrete maths strand of my CS course, but the book really has helped. It's given me confidence tackling proof problems in particular.

Shyamal Prasad, December 14, 2008:

Thanks very much for a wonderful little book - it's really one of the best texts I've read in computing in a long time!

For the following, see also Amazon Reader Reviews

B. Edds (Greenville, SC USA): We need more like it!, September 18, 2012:

Let me start by saying I am not a Haskell programmer. I program mostly with C# and F#, and study Haskell as a educational exercise. However, Haskell's ability to express formulae makes it the perfect 'pseudo-code' for presenting abstract mathematical concepts in a concrete way to modern programmers.

Us workaday programmers have a hard time picking up maths or remembering the maths we learned in school. This book gives us a great alternative to grinding through old textbooks to learn the math we need in our projects. Really, the concreteness of seeing mathematical concepts implemented in working code can make all the difference.

I love this book so much, I can only wish there were more in the same vein. What about a `Haskell Road to Linear Algebra', or a `Haskell Road to Calculus'? Wouldn't such a series be magnificent?!

If I could ask for anything more from the authors, I would ask for more books like this! I can't praise the work enough!

Andrey Smorodin (USA): This is a great book, May 31, 2012:

I am really happy to have this item which is great book for learning math with real applications in Haskell. Author demonstrate elegant of math theory and pure functional language. This pair together can be used for solving and modeling math concepts.

I really recommend this book to math hobbits and/or Haskell newcomers. And thank you again Kees Doets and Jan van Eijck for several happy weeks and good time with reading and solving problems. That was really fun.

John J. Rood (Holbrook, MA USA): The Haskell Road to Discrete Math, April 9, 2006:

Want to learn discrete math as in the non-calculus version of Math 101? Willing to work hard to learn it? Then this is the book for you! It is written in a user friendly style. The book has a chatty tone when explaining serious topics. The chat is the talk of experts, however, so it should never be underestimated. The book will teach you the functional programming language Haskell. This language is the most modern version of the Lisp family to have received any significant attention. It features advanced type features and lazy evaluation. The book covers all the "classic" topics of a discrete math course, to a considerable depth. Best of all, they are all implemented in Haskell. All except for the predicate calculus, that is. It would be a major piece of work indeed to have any implementation of this topic in a work at this level! The book teaches logic by example. One is taught the meaning, the rules and the insider's "recipes" of mathematical proofs. The book then covers the standard topics of sets, relations, functions, and induction / recursion with impressive computer implementations. The book goes on to a quick overview of the construction of the number systems of mathematics. It proceeds to a substantial treatment of combinatorics in a short space which includes implementation of polynomial solutions to recursion relations. Then it is on to corecursion, power series, and a hint of domain theory. The book ends with a modern chapter on the elements of set theory. All in all an excellent book! IMHO it is the best book out there on the topics in a discrete math course. It is amazing that all of this (except the serious parts of logic) could be implemented in Haskell so successfully. The one caveat about the book is that if you want to benefit fully from it, you are going to have to do some hard work.

Code Monkey, The math book all programmers should read, December 2, 2009:

The 'Haskell Road to Logic' is a wonderful introduction to the mathematics that lie behind functional programming and computer science. Readers should however be aware that this book is not, and does not pretend to be, a book about programming in Haskell. It is really a text book about topics in mathematics that are of particular interest to computer scientists. What distinguishes the book from many others is its use of Haskell to implement mathematical structures that are usually taught as abstract concepts. This approach makes the mathematics far more approachable for computer programmers than many other text books. Presumably it should also make for an excellent introduction to computer programming for the mathematically inclined.

While the book is easy to read and has a friendly writing style, it not particularly well suited to casual reading. To really understand the subject being discussed the reader will probably need to solve most of the exercises in the text. The good news is this requires minimal prior mathematical training (the authors expect familiarity with "secondary school mathematics"). Solving the exercises will also train the reader in writing, and proving the correctness of, short functional programs.

The book has a minor few faults. One is a relatively large number of minor errors (many of which are noted in the errata available on the book's website). Another is that some major topics are introduced in exercises without much discussion, particularly in the later chapters. But these are but quibbles in a review of a fantastic math book for programmers.

Herbert C. Meyer (Shelbyville, KY, USA), modern approach to Mathematics foundations , June 7, 2009:

When I was a Math undergrad back in the 70's, we had a 5 hr course called Foundations of Mathematics. This was an intro to symbolic logic, propositional calculus, and methods of proof. Deadly boring, dry material that we either knew, grasped by intuition, or ignored.

This textbook covers this material in a constructive fashion by using the Haskell programming language. Haskell is a modern form of lisp, one of the original programming languages, from the '50's, the language used for most Artificial Intelligence work. The breadth of Haskell allows it to be used for logic and proof, as well as the usual numerical and string processing. Pattern matching and list processing is built into the basic structure of the Haskell language.

This text's exercises are mostly Haskell programming assignments. Turning the abstract ideas of the math into the concrete statements of Haskell (if statements in a program can be considered concrete) will make the ideas familiar and real. Free, useful versions of Haskell (Hugs) are available for readers or students to use, even on Windows systems. Any familiarity with any programming system and a text editor should be enough to get started.

What is the difference between proving a theorem and debugging a program? The way I do it, not much. That has much to do with me, I am a programmer first, and a Math second. This statement is the Curry-Howard correspondence, connecting computability and proof or truth. This text is a step on that road to truth.

Malcolm Gorman(Melbourne, Australia), Pascal's logic calculator machine incarnate!, January 18, 2009:

This book is breathtaking in its clarity and depth. I'm into the chapter on using Haskell to prove logical theorems.

One of my all-time favourite subjects in undergraduate study was Logic. That you could translate English language arguments into logical symbolism and test their validity and soundness by following a set of rules was, to me, a revelation. By following a number of logical inference rules, one could build an argument that proves the validity of a conclusion. The use of truth tables was intriguing and so simple in concept.

Blaise Pascal (French philosopher, and whose name was given to the Pascal programming language) speculated about the possibility of a logic calculating machine. Well, this book shows how you can do it with Haskell.

The Haskell Road To Logic, Maths and Programming provides Haskell source code that you can run to demonstrate the validity of all the traditional logical inference rules that I learned in Logic.

It's a pleasure to read.

Alexey Romanov (Moscow, Russia), A perfect fit, August 20, 2009:

As a mathematician, I find that of all current programming languages Haskell is the best for describing mathematical notions in thanks to such features as newtypes, type classes, list comprehensions, purity, etc. It is also much better suited to reasoning about programs than the imperative languages are.

Therefore, it makes perfect sense to write a book which covers the basic notions of discrete math and implements them in Haskell, which is just what this book does. Along the way the reader will see many examples of strict and rigorous logical proofs, and learn how to approach them.

Luby Liao (University of San Diego, San Diego, CA), I recommend every university library to have this book, March 16, 2006:

In March 2006, there are only three or four books that boast Haskell in their titles. They are all excellent books. But the world can benefit from more Haskell books. In fact, we are in need of such books, especially CS1 texts. This book is a pleasure to read. I suspect that even math haters will not find it hostile. Anyone learning Haskell will find the book and its companion web site a valuable resouce. On the web site, you will find the source code from the book, such as Powerseries.hs. You can quickly play and experiment with it; read and learn from it. I wish more books are as pleasant and affordable ($25).

Qual Highety (Austin, Texas), Enlightening, September 17, 2010

As a professional programmer who dropped out of college too early to get a good grounding in mathematics, this book has been a wonder to me. I've been trying to learn more advanced mathematics in the last year or so, and struggled because I didn't know how to do proofs. Haskell is prominent in the title, but is secondary in the book. The vast majority of my time has been spent reading and performing proofs with with pencil and paper. The mathematics portions are all fairly rigorous. Once proofs are fully introduced, nearly all the exercises are proving theorems given in the book, or providing counter examples. There isn't much in the way of computational type exercises I've seen in some other discrete math texts, stuff like "what's the transitive closure of this relation". Instead, a theorem will be given and the author will ask you to prove it.

The Haskell exercises typically follow pure math introductions and exercises, and are used to help develop a stronger, more intuitive understating of the subjects. I can now write enough Haskell to take on the exercises, but to this point, the Haskell has all be very compact - 10 lines of code to answer a question at the max, usually more like 3. There's no way I could go and do something 'practical' with Haskell at this point, but I can grok some of it and am starting to appreciate functional programming.

This is easily the most challenging self study book I've taken on, but also the most rewarding. Not only have I gained proof writing knowledge, and a solid understanding of the fundamentals of modern mathematics, but it's helped me develop a measure of discipline in thought. I've noticed improvements in the clarity of my day to day software development - in design, development, and verification. The methodical approach to breaking down a proof into cases and sub-cases has been most helpful in that regard.

I recommend this to anyone, especially developers who haven't had the benefit of a thorough mathematical education.

J. Burton, First class introduction to Haskell, 4 April 2007:

This is a great book which I enjoyed reading and found more useful than other introductory Haskell texts with the exception of Bird, although it may not be the best choice if you are most interested in the practical aspects of the Haskell. The emphasis is on foundations and language features (which are all Haskell 98) are introduced as they occur naturally in the discussion of a number of Number Theory and Logic problems. This book is well named -- it aims to teach the three disciplines of its title in equal measure and learning Haskell is presented as the channel for that, rather than being a goal in itself.

Le Serf, Lovely, 23 April 2009:

The Haskell Road is a truly enjoyable little book.

What it is not: HR is not one of those vast towers of paper that introductory computer science books seem to have become. The kind of book that's called "Discrete Mathematics" and essentially contains all the stuff that nobody wants to teach but everyone wants you to know. Those books and the courses they support are often a student's first introduction to thinking about computing, and it's shameful. They are a patchwork of misaligned topics - and the students' thinking begins to resemble them, unsurprisingly.

Rather, the Haskell road is elegant - clean, concise, yet informal and approachable. Like the title says, it is an introduction to Logic, Maths and Programming. The book takes the enlightened viewpoint that these are unified concepts. The book begins by introducing basic Haskell syntax, and all of a sudden, we are implementing a prime number test. Simple; yes, but we also learn how to _prove_ that a procedure is a prime number test.

This approach continues throughout the book. The ideas of formal logic and deductive reasoning are made approachable by the fact that we implement the rules in Haskell. Sometimes, the exercise is in Haskell, and the answer is in logic. The point is that the reader is made from the first instant to see the equivalence, the shared foundations between these different means of expressing thought.

This is also one of the few books that teaches, explicitly, the means of proof. It does not do so abstractly, but quite straightforwardly, using the tools of formal logic. A few somewhat difficult chapters are the result (2-4); but they are greatly enlightened by enjoyable exercises. This treatment of proof was a first for me - though I am currently a graduate student, it made clear much that had been opaque to me. I read the chapters and did the exercises in a sitting; the following day (literally) I was finding my quantum computing proofs easier than I had the day before. Few books are able to have such a direct, jolting impact - indeed, that experience compelled me to write this review.

The exercises are not too difficult nor too easy; they are not all gathered at the end but rather placed in exactly the right place. Five minutes attempting an exercise is usually enough to see the trick of it. Some of them take seconds, however, and some take quite a long time. Those are marked as such. The exercises are the glue that sticks the book's ideas into the reader's mind, and it works.

The basic ideas of programming, like lists and functions are brilliantly intertwined with the equivalent ideas in mathematics, namely set theory. Haskell's lazy evaluation enables us to start puzzling about infinite sets early on. Throughout, one learns a reasoned, careful, elegant approach to programming. Too many students learn to program by throwing Java API calls at the problem until most of the output is correct. A more thorough, more disciplined mind can go much further, and the Haskell Road seeks to develop this.

I can't say enough good things about this book, so I will stop now. If you have been doing computer science for 30 years, or if it's your first day, or (especially!) if you're a programmer that wants to learn to do "real math" - this is the book for you.

Submitted by metaperl on Fri, 10/07/2005: Someone help me. The Haskell Road is Calling...:

For some reason, I keep picking up "The Haskell Road to Logic, Maths and Programming"

All my life I have avoided proofs and mathematics, but perhaps now is the moment to meet my Maker. I keep going back to this book.

For some reason, it is infectious. A beginner introduction to how thought is structured. A beginner introduction to what math is all about.

I had been wondering what I was going to do with Haskell once I finished learning it. I am a Perl professional by trade and even though some interplay has been going on, I never really knew why I was learning Haskell. I just liked the conciseness and elegance of the language and the mathematical purity.

The most important thing is to have passion behind what you do. If I want to go deeper into math for math's sake, then so be it... no need to artificially create projects for myself. Just enjoy haskell and math. It is a very very good fit.

Metaperl again (Sat, 11/05/2005):

I am grateful to be studying Haskell. It has done wonders for my corporate-level Perl development. The book to read is "The Haskell Road to Logic, Maths and Computer Programming." This book will force you to think clearly. It does not cover monads, but monads can wait until you can specify and solve problems. But my improved thought processes are one thing. Delivering projects on a deadline is another and Perl continues to deliver through a cooperative community based around CPAN. The Haskell community is based around the reason of masterminds doing the intelligent things. The Perl community is based around the needs of people doing practical things in the best way that they can.

Maiz, Jan 4, 2010:

The most hard core programming language ever - Haskell - presented in a really different and thought provoking way. For those interested in this topics - functional languages, logics and mathematical foundations - i think it's must have. GoodReads Review

Darrin Thompson on www.randomhacks.net, March 7, 2007:

I’m getting better with producing proofs because I found the Haskell Road to Logic Maths and Programming. It’s a good remedial course for those of us familiar with programming but weak in abstract math chops.

Darrin Thompson in an Answer to a Blog about Computing Education (October 1, 2010):

I finished my 2 year degree with distance courses 10 years ago. I remember the feeling of isolation both from the professor and the other students. Were there any other students? I don’t even know. I did finish my courses though.

I can add two observations from own experience.

1. I desperately wanted to socialize with the other students. Even though the work had some challenge to it, I was bored. Half the fun of the class is doing it together and the together was completely missing for me.

However...

2. When I’m interested in a subject on my own, and select a text on my own, I feel completely different about it. I email the author of the book to get answer keys, I do problem sets. I work alone at reading and understanding the text. If I get stuck on something I email the author for answers.

Does anyone else spot the irony? The situation is exactly the same, worse even, yet I’m having fun. I don’t necessarily “finish” because I usually have a particular goal which usually doesn’t involve a comprehensive understanding of my text.

For instance, I wanted to understand a little linear algebra and realized that what little knowledge I ever had about constructing proofs was completely rusted away.

I got the Haskell Road to Logic Maths and Programming. I did the first 3 chapters and part of chapter 4, just to learn how to do a proof the right way. I did every stinking exercise up to the point I felt I had reached my goal.

The professor/author was responsive to my occasional questions and provided me an answer key. (And a little admonition not to peek. Still makes me smile to this day.)

My wonderful experience was exactly the same as my dreadful experience in many ways.

Maybe distance education needs to be more self-directed to succeed?

Greg Restall, May 10, 2004, on Haskell and Logic:

This looks very nice indeed: The Haskell Road is a textbook on elementary logic, mathematics and programming, based around my favourite programming language Haskell.

I’m glad that this wasn’t the textbook in my introductory computer science course, long ago in 1986. If it were, I may have fallen in love with computing and never become a philosopher.

Impression from metaperl's blog:

The Haskell Road To Logic, Maths And Programming has a very seductive intro and table of contents... I am starting to realize that I am going nowhere in Haskell unless I learn to think and know functions well... humbling after 5 years as a well-paid Perl programmer.

Herbert Carl Meyer wrote (June 1, 2009):

I find the book fascinating and instructive. I am afraid I am a programmer first and mathematician second. It is hard for me to read the book and think abstractly, and easy to fire up the laptop and write and run haskell code.

I had a similar problem when I was an undergrad, my instructor in a Linear Algebra course used an APL (Iverson) system as part of the course. I think at least part of it was to automate the drudgery of marking homework. I learned more about APL than linear algebra.

But I will continue. I plan on picking up the other texts in the series. Thank you for writing the book.

Chris Kimm wrote (November 4, 2008):

I'm about 2/3 though the book and I've found it to be excellent in all ways! Though I have no formal math or computer science training, I've found the book to be accessible and perfectly paced. Also, though I was initially doubtful that Haskell could be a learn-as-you-go language, (ala Scheme in SICP), there haven't been any sections so far where I've needed to consult external sources to get through your material.

My initial hope was to use the material in this book to prepare me for "Concrete Mathematics" by Graham, Knuth, and Patashnik. Even if I need another stepping stone before approaching that book, "The Haskell Road" has offered an enormous amount of clarity for me in math reasoning and also in functional programming.

Iain Barnett wrote (October 3, 2008):

I'm finding the book challenging but very interesting. I like the pace, the simple presentation, and that the only challenge is the subject matter -- not anything to do with the writing (unlike the other Haskell book I've got -- or a lot of computing books).

Bernardo Szpilman wrote (May 24, 2008):

I'm learning Haskell and extinguishing my Linear Algebra hate thanks to your book. I love programming and have always done, but mine was a bad relationship with math, especially proofs. Thanks so much for bringing the two together, thus bringing me much closer to the math I'll need throughout my whole Computer Engineering career (I'm in college). It's a splendid idea, and for that your work is completely unique.

I must say that I was really pleased to find your book, because I have been trying to find a way of studying logic using a computer for some time and this was the first time it all seems to come together.

I am currently going through your excellent book, "The Haskell Road to Logic, Maths and Programming". Many thanks for taking the time to write such a fine book, utilizing such a fine language as Haskell, and teaching both programming, logic, and the fundamentals of math.

I'd like to thank you for writing such an informative book on Haskell. I'm a senior in high school from New Jersey. I've been trying to wrap my mind around functional programming and formal mathematics to get a headstart on my college studies and your text has proved to be a formidable companion thus far.

I'm enjoying your book a lot, this combination of Haskell plus mathematics and logic is just awsome :-)

John O'Keeffe wrote (August 8, 2007):

I'd just like to say what a fabulous book it is. It exactly targets the maths I'm working through as well as opening up the delightful world of Haskell programming. So thank you very much indeed!

Musing from programing musings (March 28, 2006):

One of the nicest things about writing Haskell code is that it’s the closest one can probably get to writing pure maths while programming. Thus, learning Haskell is an excellent way to learn more about maths and logic. If that sounds to you like doubling the fun (and you’re not yet a math wizard), The Haskell Road to Logic, Maths and Programming by Jan van Eijck and Kees Doets is definitely the book for you. Its purpose is to teach logic and mathematical reasoning in practice, and to connect logical reasoning with Haskell programming. And, in my opinion, it does a pretty good job at that. Although it begins with the very basics, it includes chapters on far from trivial (i.e., fun!) stuff like, for instace, corecursion or Cantor sets. And i found amazing how natural it was to express logical and mathematical ideas in Haskell.

Ask Hacker News: Recommendation for (re)learning Math Skills:

I'd recommend this one: The Haskell Road to Logic, Maths and Programming -- would fit best if you'd also have an interest in Haskell/FP, but it's also a good introduction to formal proofs -- might be a bit too basic if you're interested in higher maths, tho, but a good starting point for math education.

Home