The Haskell Road to Logic, Maths and Programming

Kees Doets, Jan van Eijck, Jan Eijck

Mentioned 6

Long ago, when Alexander the Great asked the mathematician Menaechmus for a crash course in geometry, he got the famous reply There is no royal road to mathematics. Where there was no shortcut for Alexander, there is no shortcut for us. Still, the fact that we have access to computers and mature programming languages means that there are avenues for us that were denied to the kings and emperors of yore. The purpose of this book is to teach logic and mathematical reasoning in practice, and to connect logical reasoning with computer programming in Haskell. Haskell emerged in the 1990s as a standard for lazy functional programming, a programming style where arguments are evaluated only when the value is actually needed. Haskell is a marvelous demonstration tool for logic and maths because its functional character allows implementations to remain very close to the concepts that get implemented, while the laziness permits smooth handling of infinite data structures. This book does not assume the reader to have previous experience with either programming or construction of formal proofs, but acquaintance with mathematical notation, at the level of secondary school mathematics is presumed. Everything one needs to know about mathematical reasoning or programming is explained as we go along. After proper digestion of the material in this book, the reader will be able to write interesting programs, reason about their correctness, and document them in a clear fashion. The reader will also have learned how to set up mathematical proofs in a structured way, and how to read and digest mathematical proofs written by others. This is the updated, expanded, and corrected second edition of a much-acclaimed textbook. Praise for the first edition: Doets and van Eijck s The Haskell Road to Logic, Maths and Programming is an astonishingly extensive and accessible textbook on logic, maths, and Haskell. Ralf Laemmel, Professor of Computer Science, University of Koblenz-Landau

More on

Mentioned in questions and answers.

I am looking for a book that explains how a discrete math concept like, say, set theory, is used while doing programming. My preference is towards books that are easy to understand. For me, that means they use more English and less Mathematical notations and spend less time proving some theorems. I am quite comfortable with high-school mathematics and I have basic understanding of terms and concepts used in discrete mathematics (i.e. I know what a set is and how probability of two independent events occurring together is calculated, etc)

I can also understand languages like Haskell, Lisp, Ruby, Perl (and all C-based languages).

I really enjoyed reading Discrete Mathematics and Its Applications by Kenneth Rosenbook cover

The English is simple and easy to read, very well structured with lot of exercises.

You don't need advanced math to get it.

I think this one will be useful for you: It's using pseudocode for explaining basic concepts of programming which you can use in any programming language you'd like.

I highly recommend this book. I haven't finished it yet, but it has so far been a thoroughly enjoyable experience for learning both advanced mathematics and Haskell. It is a course-style text with unanswered questions and exercises, but I emailed the author and he quickly replied with the answers in pdf format.

P.S. It is heavy on the mathematical notation, but I only completed Calc I (10 years ago!) and am able to work through it without too much issue.

I know this question may sound silly, but I am learning (at least trying) Haskell for about 4 days. I've already finished to read, and now I am investing time in: The Haskell Road to Logic, Math and Programming, and things got really complicated for me. I don't have experience in functional programming, just some basic knowledge on Lisp.

Even though I understand the concepts, when I have to write a not so basic piece of code, there's a total darkness and I cannot build a plan in my head. It seems that there are a lot of ways to accomplish a certain task, but I cannot express myself.

After 4 days of python, I could've write complex scripts (not 'pythonic', but they did work). After 4 days in haskell, I am ... almost blank.

Any suggestions on how to improve my functional skills ? How long did it take for you to fully grasp Haskell ?

After about 2 years there are some parts of Haskell I know very well (Ptr stuff, vector libraries), some areas I know just enough to be dangerous (template haskell), and others I haven't touched (web frameworks, generics). Overall, though, I think I understand the language pretty well.

A large difficulty of learning Haskell is the (very steep IMO) learning curve. There are a lot of different inter-connected things you need to learn before you can be productive in the language, and because they're interconnected it's difficult to get a good sense of them without at least a few months of experience. My advice is to keep at it, and if you think you don't understand something, or that something deeper is happening, you're probably right. If you can't figure it out now, just move on and come back to it in a month or so. Eventually you'll make enough progress on multiple fronts that everything should become clear.

Like any language, the best way to make progress is to write code. It will take longer because Haskell is further away from the languages you already know, but it will be worth it.

I haven't taken any math classes above basic college calculus. However, in the course of my programming work, I've picked up a lot of math and comp sci from blogs and reading, and I genuinely believe I have a decent mathematical mind. I enjoy and have success doing Project Euler, for example.

I want to dive in and really start learning some cool math, particularly discrete mathematics, set theory, graph theory, number theory, combinatorics, category theory, lambda calculus, etc. My impression so far is that I'm well equipped to take these on at a conceptual level, but I'm having a really hard time with the mathematical language and symbols. I just don't "speak the language" and though I'm trying to learn it, I'm the going is extremely slow. It can take me hours to work through even one formula or terminology heavy paragraph. And yeah, I can look up terms and definitions, but it's a terribly onerous process that very much obscures the theoretical simplicity of what I'm trying to learn.

I'm really afraid I'm going to have to back up to where I left off, get a mid-level math textbook, and invest some serious time in exercises to train myself in that way of thought. This sounds amazingly boring, though, so I wondered if anyone else has any ideas or experience with this.

Sounds like you're in the same position I am. What I'm finding out about math education is that most of it is taught incorrectly. Whether a cause or result of this, I also find most math texts are written incorrectly. Exceptions are rare, but notable. For instance, anything written by Donald Knuth is a step in the right direction.

Here are a couple of articles that state the problem quite clearly:

And here's an article on a simple study technique that aims at retaining knowledge:

To this list I would now add The Haskel Road to Logic, Maths, and Programming, and Conceptual Mathematics: A First Introduction to Categories.

--- Nov 16 '09 answer for posterity--

Two books. Diestel's Graph Theory, and Knuth's Concrete Mathematics. Once you get the hang of those try CAGES.

I've heard it's better to read the first edition of "Introduction to Functional Programming" by Bird & Wadler than the second edition. The first edition uses Miranda, and the second edition uses Haskell.

Is this a common recommendation? My goal is to get serious about functional programming. Thoroughly knowing the concepts of functional programming is more important to me than knowing a language's syntax, so I'm fine with learning Miranda if the first edition is somehow better.

I know F# and Scala.

I strongly recommend the second edition, which is an extensively revised, extended and mostly improved revision of the first edition. I have read both editions. The first edition has an example on solving the 8 queens problem with backtracking, unfortunately this example was dropped in the second edition. The second edition is my favourite book on Haskell.

The examples are from mathematics, including proof by induction. The material on deriving programs from their specifications by Bird in the second edition is awesome, I love this book. If you can handle examples from maths, this book is superb.

I think this book is also a great introductory text on Haskell, however I found that as soon as I tried writing Haskell programs that I often had to read material from other tutorials, and kept having to refer to Real World Haskell.

Another great text on mathematics and logic, with examples using Haskell that helps to understand the maths, is the Haskell Road to Logic, Maths and Programming. Bird's text goes much deeper on Haskell programming.

I would like to hear from you folks that have achieved a high-level of proficiency in F# (and also in functional programming in general too) what should be my steps from now on to become a better/professional F# programmer?

I already know much of the F# syntax and have some years of experience with C++. My goal is, as an engineer and mathematician, to design better scientific libraries (linear algebra packages, partial differential solvers, etc.).

If you are interested in scientific libraries I suggest you to take a look at Jon Harrop's F# for Scientists.

Also to catter for your mathematician side I suggest you to read Doets-Van Eijck The Haskell Road to Logic, Maths and Programming, although written in Haskell, you will certainly be able to follow most of the text, and re-implementing the samples in F# could be a nice exercise.

I'm working my way through the book The Haskell Road to Logic, Maths and Programming. (I'm only mid-way through chapter 1, but I'm enjoying it so far and intend to continue.) I've read through the section 1.5 "Playing the Haskell Game" which "consists of a number of further examples to get you acquainted with [Haskell]". So far I've learned about functions, type declarations, guarded equations, a little about list pattern matching, and where & let.

I'm stuck on exercise 1.17, which asks us to write a function substring :: String -> String -> Bool where:

  1. if xs is a prefix of ys, xs is a substring of ys
  2. if ys equals y:ys' and xs is a substring of ys', xs is a substring of ys
  3. nothing else is a substring of ys

I used the prefix function provided in a previous example:

prefix :: String -> String -> Bool
prefix [] ys = True
prefix (x:xs) [] = False
prefix (x:xs) (y:ys) = (x==y) && prefix xs ys

And then tried:

substring :: String -> String -> Bool
subsstring xs [] = False
substring xs (y:ys) | prefix xs (y:ys) = True
                    | substring xs ys  = True
                    | otherwise        = False

...and may other permutations of this.

When I run substring "abc" "xxxabcyyy" I get True, but when I run substring "abc" "xxxabyyy" I get "* Exception: substring.hs:(3,0)-(5,45): Non-exhaustive patterns in function substring". I can't figure out why. I don't understand how there could be non-exhaustive patterns when I use "otherwise".

BTW, the book has not yet covered if-then-else. I'd prefer to keep that out of my solution, for now.

You have a typo in the function name:

subsstring xs [] = False

Because of the typo this declares a new function subsstring, not a case of the substring function.

The substring function itself then doesn't have any case that would match a second parameter of [].