way to introduce programming to math majors. Functional
programming is a natural style of programming to students
who are already mathematically inclined, and discrete math
provides a context where programming can feel familiar and
relevant to math majors. We can see this as the other side of
programming providing computer science majors a familiar,
relevant context for math topics.
In the CS program where I teach, our DMFP course has no
programming prerequisites, only the expectation that students
have some level of mathematical maturity—say, about what one
would expect after pre-calculus. Our computer science majors
take DMFP anytime during the first three semesters—
concurrent with CS1 or CS2 or even after CS2. But in most semesters
at least half the students enrolled in DMFP are math majors,
with some students from other majors as well. Most of those
students have never programmed before.
One would expect that such a wide range of prior experience—including none—would put certain students at a disadvantage. But we have found that using the functional style helps
level the field. Moreover, the mixture of populations from CS,
math, and other majors means there also is a wide range of mathematical preparedness. Some students find the programming
focus easier, and others take more readily to the proof-writing
focus. It encourages collaboration across the majors.
Since our computer science majors take DMFP at different
stages, there is variation in how they perceive its integration
with computer science topics in the other introductory courses (which primarily use Java, with some C sprinkled into CS2).
One example is how students who take DMFP concurrently with
CS1—or even before CS1—find the coverage of recursion in CS1
to be no big deal. They have been writing recursive functions
in Standard ML for several weeks by that point. In a thorough
survey of research literature on teaching recursion, McCauley
et al. [ 13] find little evidence that would suggest an ideal order
in which to place recursion in relation to iteration in a student’s
experience—if anything, it seems that teaching recursion prior
to iteration simply makes it more difficult for students to learn
iteration. They do find, however, many voices saying that the way
we tend to introduce recursion—as a strange and difficult alternative to the more “natural” iterative approach—is itself the biggest obstacle to students’ mastery of it. Functional programming,
regardless of when it is taught relative to other styles, provides
a context where recursion is natural. It has many opportunities
for simple, intuitive examples and exercises. In our experience,
students introduced to iteration and recursion in courses taken
simultaneously find them equally natural.
On the other hand, students who take DMFP and CS2 at the
same time are better poised to make the connections between
functional programming and certain idioms in object-oriented
design, as mentioned earlier. Another point of contact between
DMFP and CS2 is the idea of a loop invariant. In DMFP students prove loop invariants as an application of mathematical
induction, while in CS2 they see both loop invariants and class
invariants as ways to reason more rigorously about their design
is important for a student to be well-rounded in the field. As a
specific example, many design patterns used in object-oriented
programming can be described as adaptations of idioms from
functional programming [ 5, 15, 20]. In my own experience, I have
enjoyed seeing students’ faces light up with sudden comprehension when they realize that strategy objects are just an adaptation of first-class functions to object-oriented programming.
Additionally, many modern programming languages that are not
thoroughly functional in their idioms still include functional features, such as lambda abstractions. Some ubiquitous strategies
such as map-reduce are also examples of functional thinking.
If exposure to functional programming is delayed until a
junior-level programming languages course, we are at a disadvantage for getting students to internalize it and apply it to
other things they study in the CS program. Placing functional
programming in the discrete math course puts it early enough
to allow students to see its connections to formal methods of
software verification, design patterns, and theory of computation, among other areas.
But there is yet another benefit of integrating discrete mathematics and functional programming into the same course: it
provides an excellent service course for populations other than
computer science majors. Although we find papers on how to
claim the discrete math course in the name of computer science, the better to serve our majors, to my knowledge there is
less discussion of how computer science programs can serve
math majors and other students. At large institutions a computer science department may have enough staffing to offer
programming courses designed specifically for the computing
needs of programs in math, engineering, or the sciences. Some
science programs may be able to offer their own introductions
to programming. But at smaller institutions, such as the liberal
arts college where I teach, introductory courses in the major
must also play the role of serving students from other majors
(and, I might add, the role of recruiting some of them to become computer science majors).
Considering this, I suggest that not only is a discrete math
and functional programming course a good way to teach discrete math to computer science majors, but it can be a good
I suggest that not only is a
discrete math and functional
programming course a
good way to teach discrete math to
majors, but it can be a good
way to introduce programming
to math majors.