What sort of programming assignments do you give in an FP course?

Question

I teach programming to a science/engineering students. Here is a typical sequence of assignments for a beginning programming class:

1. Arithmetic and conditionals: does x divide y
2. Looping: is a number prime
3. Functions: test prime-ness
4. Object-oriented: make a primegenerator class with a nextprime method.
5. All together: test the hypothesis that each prime is the average of two other primes.

Apart from side-effect-free coding, does FP offer anything in this sort of exercise set?

Bigger project: write a person class, and model diseases: the person has an infect method and a nextday method, and after a fixed number of days, they are healthy again. Now make a population class which contains a bunch of persons, and model disease propagation. Again a nextday method, where in each day people can infect each other with some probability, or they are vaccinated. Do parameter studies of herd immunity.

Is any of this more elegantly expressible in an FP manner? What are the sort of semi-realistic assignments you would give in an FP course? And what difference does FP make?

Answer 1

FP naturally lends itself to recursive problems, so anything with trees or lists is good. It also lends itself quite naturally towards more mathematical problems, so you could consider something like a sudoku solver or a credit card number validator.

Because of immutability, concurrency is far safer.

Your set of five questions would work very well in FP, though obviously step 4 would be modified.

In response to your request for clarification (though I am not a great FP expert), here is how I would approach that problem. I would not create an object. The first three methods would be essentially exactly as you described, though they would have to be recursive.

If I were in a lazy language like Haskell, I would define function 4 as an infinite series of numbers that passed the test in function 3. If I were in an eager language like the primary branch of Scheme, I would instead create a next-prime method that takes a prime number as an argument, and finds the next one.

For the final challenge (#5), I would create a method that tests the hypothesis up to a given number, passed in as an argument. As you can see, all of the functions I've described are stateless.

The sickness modeling problem is fine, though it would involve passing a fair amount of state information from one function call to the next.

It's also worth noting that some of the benefits feel less extreme than they did 20 years ago, since the major imperative languages have taken pains to bring many of the great FP tools into their own workspaces. (Lambdas, map/apply/reduce, etc) As a result, you can do a lot of FP or FP-adjacent coding in modern "imperative" languages, and you can gain the benefits as well.

Answer 2

My other answer was a kind of trailer of how FP as a teaching strategy can be used in various areas. Since OP showed an interest in combinatorics I've opened that up in greater detail below.

Combinatorics : Conspectus

To the lay-person combinatorics consists of some formula eg $n!$ $\binom{n}{r}$
_{I will write it in the older style as ${}^n\!C_r$ so that making a c function becomes straightforward map}

But where do these formulae come from??

Enumerative Processes

There are certain sets/lists/processes whose size/length/what-have-you are the context of these formulae

To be more concrete: Given set $S$ having $n$ elements the powerset of $S$ is $\wp(S)$

$\begin{aligned}\text{Where if} \quad \vert S\vert &= n\\ \text{Then }\quad \vert\wp(S)\vert &= 2^n \end{aligned}$

In short combinatorics straddles two worlds:

1. One where things like $S$, $\wp(S)$ etc live
2. One where things like $n$, $2^n$ live
3. Mappings like the $\vert \cdot \vert$ (size) function that steps from one to the other world

Now a strange phenomenon: Clearly the second world derives from the first, yet the second is formalized as the standard formulae of combinatorics the first remains more informal... pictures, descriptions, English text...

What would it take to formalize the first world also and from there the mapping to the second??

IMHO it would be a better presentation of the combinatorial identities

Notational Notes

1. If the numerical function is foo, I'll call the enumerative function fooE.
2. The function call foo.x.y can be written infix as
   x `foo` y : With this, we can read ${}^n\!C_r$ "en-see-aar"
3. ℒ.t is the type List-of-t (t is an arbitrary type). ℒ.ℕ etc are specific list types
4. Its de-ASCII-ized eg ∈ not <-, ℒ.t not [t] etc. If someone actually gets round to compiling it and trying out: please ask me! I can give literal running code if desired.

Some examples

1. Powerset of a set

If $S = \{a,b,c\}$ then
$\wp(S) = \{\emptyset, a, b, c, ab, ac, bc, abc\}$
_{Dropping brackets and commas for obvious reasons! ie read $ab$ as $\{a,b\}$}

For a finite set of $n$ elements, lets write pE ie powerset enumerator

pE :   ℒ.t → ℒ.(ℒ.t))
pE.     [] = [[]]
pE.(x::xs) = concat.[[s, x::s] | s ∈ pE.xs]

It should be clear that pE starts with a singleton list And at every stage its size doubles

So that there is the clear correlation between $\wp(S)$ construction and $\wp(S)$ size

We can formalize this by actually writing p

p :  ℕ  → ℕ   -- p is good ol power of 2
p.   0  = 1
p.(n+1) = 2*p.n

Usage

? pE."abc"
[[], "a", "b", "ab", "c", "ac", "bc", "abc"] : ℒ.(ℒ.Char))

And defining identity: length.(pE.l) $=$ p.(length.l)

2. Combinations

Also known as the binomial coefficient ${}^n\!C_r$

But what exactly does it count??

If $S$ is an $n$-set ${}^n\!C_r$ is the number of all $r$ length subsets of $S$

But what are those (sub)sets themselves? Lets make that explicit

So here's the Pascal triangle — classic version.

1
1 1
1 2 1
1 3 3 1

Pascal triangle showing the universal set from which the combinations are made for each row

1               ∅
1 1             a
1 2 1           ab
1 3 3 1         abc

Above with the specific sets at each level made explicit

counts	base set S	all combs
1	∅	«∅»
1 1	a	«∅,{a}»
1 2 1	ab	«∅, {a, b} {ab}»
1 3 3 1	abc	«∅, {a, b, c} {ab, bc, ac} {abc}»

The parallel between first and third column should be patent enough.
Lets anyhow capture that in a pair of functions: cE and c

cE : ℒ.t → ℕ → ℒ.(ℒ.t)
[]      `cE` (r+1) = []
xs      `cE` 0     = [[]]
(x::xs) `cE` r     = xs `cE` r ++ [x::y | y ∈ xs `cE` (r-1)]


c : ℕ → ℕ → ℕ
0     `c` (r+1) = 0
n     `c` 0     = 1
(n+1) `c` r     = n `c` r + n `c` (r-1)

Note that the $c$ def is just the classic Pascal identity: ${}^{n+1}\!C_r = {}^n\!C_r + {}^n\!C_{r-1}$. And cE explains why that

Usage:

? 5 `c` 2
10 : ℕ
? [5 `c` i | i ∈ [0...5]]
[1, 5, 10, 10, 5, 1] : ℒ.ℕ

? "abcde" `cE` 2
["de", "ce", "cd", "be", "bd", "bc", "ae", "ad", "ac", "ab"] : ℒ.(ℒ.Char)

So as for the relation between p and pE likewise between c and cE

And the defining identity between c and cE: length.(l `cE` r) $=$ (length.l) `c` r

Note the types:

• c takes 2 numbers (ℕ) n and r and returns an ℕ
• cE takes a list (ℒ.t) and an ℕ and returns a ℒ.(ℒ.t) type list

Philosophical Slant

The above is a foray into basic combinatorics.
And combinatorics is math!

So there's a definite slant:

• Math is the primary topic of this
• That it runs on a computer is secondary
• You could call it executable math but note that...
• ... we need to stop thinking of programs as executing and start thinking of them as calculators evaluating over sophisticated data structures
  vide other answer
• (With nod to @ScottRowe) It's all about data; only peripherally about computation!
  And function-al programming is a particularly inept description of it...
  But we seem stuck with that term for now.

Answer 3

Why FP?

One overarching reason for FP is to get conspective views on a given subject in a couple of lines. Ideally a couple of lines but as far as possible within a page.

Why does Doug McIlroy describe McCarthy's first Lisp lecture as the The Most Significant Computer Science talk he ever attended??

What was done is (to me) less important than the last line:

One could go home and build it oneself without any instruction book

This is what I mean by conspective

Alan Kay says that studying Lisp's eval-apply pair increased his understanding of CS by a factor of hundred.

So to take Alan Kay's example:

The Lisp interpreter in Lisp is hardly a pageful

Which means that that page, presumably coverable in one lecture, could be said to cover the field of language implementation.

Now can McCarthy's one page lisp in lisp be compared with gcc's 15 million lines??

Some answers may be

• Lisp-in-lisp is a toy gcc is real
• Apples-n-oranges comparison
• Oh gcc is many languages, many machines...

I think all such answers miss the point.

Sure there's "more" happening in all-of-gcc than in a pageful-of-lisp. But if all those 15 million lines cannot be squeezed into a sumary of "all thats here" something crucial is lacking in our communication and ultimately in our understanding.

This is after all Einstein in a different guise: You do not understand something unless you can explain it to your grandmother (or a 6-year old or a barmaid)

Of course people do dig into gcc starting zero and there are intros to the field as there are intros to all fields egs

• the chapters of a compiler book
• a block diagram of main parts of toolchain
• a UML diagram
• etc

But in FP there is a a very special extra possibility: Show that conspectus as executable code

Compared to that all the above have a quality of hand-waving

Let me (for now) put down a few files from my laptop taught at various times. Depending the nature of your appetite I can flesh out/further explain/add different.

Notes on non-standard notation

1. function-call notation

c.[1,2] would look like c([1,2]) in conventional C-family language style.
ie

• C family :f(x)
• Haskell family f x
• Dijkstra functional notation: f.x

ie f.x is the Dijkstra form of the more usual f(x) ie function call. I could give justifications/explanations for the Dijkstra notation (if desired).

2. Algebraic Datatypes

Things like L, I are constructors of algebraic data types. The small notational wrinkle carrying a large semantic load here is tiny fact of "initial letter capital implies data constructor not normal function". For this Fortranism — identical in my notation to Haskell — my embarrassed apologies 😜.

3. Interactions

One interacts with the system by typing something at the ? prompt.
The system responds with a result (as any interpreter does). And its type
Pedagogically this is a big deal: Types serve as a beginner cyclist's guide wheels

• The user almost never gives a type
• The system invariably responds with a type as if to say: Your answer is this, and its type according to me is this.

If you (Victor) have some (standard) FPL preference, I can try moving to that... For now the Catalan example is shown also in Python

Combinatorics

Catalan Numbers

 -- Implements the 3rd (or 2nd) interpretation from here
 -- https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics
  
 ctype Tree a where
     I : Tree.t → Tree.t → Tree.t  -- I:  "Internal node"
     L : t → Tree.t                -- L:  "Leaf node"
  
 c: ℒ.t → ℒ.(Tree.t)

 c.[x]  = [L.x]
 c.ls   = [I.x.y | i ∈ [1...length.ls -1], (l,r) = splitAt.i.ls, x ∈ c.l, y ∈ c.r]

Example usage:

? c.[1,2]
[I.(L.1).(L.2)] : ℒ.(Tree.ℤ)
? c.[1,2,3]
[I.(L.1).(I.(L.2).(L.3)), I.(I.(L.1).(L.2)).(L.3)] : ℒ.(Tree.ℤ)

Now if you see those 2 lines defining the Catalan enumerator c. And now see the definition from wikipedia, you can see the closeness of the parallel $$\begin{aligned}C_0 &= 1\\ C_{n+1} &= \sum_{i=0}^{n}C_iC_{n-i}\quad\text{for }n\ge 0\end{aligned}$$

Catalan explanation

So the verbalization of catalan enumeration would go like this:

Trivial case

c for a singleton list is a singleton answer: just a L(eaf) node

Recursive case

For a list of greater than 1 element (called ls)

1. Generate all is from [1... length.ls -1] More usually the length.ls - 1 may look length(ls) - 1

2. For each such i split the list ls at i Call the two halves l and r
   1,2 Basically generate all non-trivial ie non-empty splits of the input

3. Generate all Catalan enumerations for l (the c.l recursive call) Likewise r Note these are LISTS of catalan enumerations internal-to-the-recursion generated For each x ∈ l-part and each y ∈ r-part...

4. Collect the node (at the head of the list comprehension) I.x.y (I stands for internal node like L stands for Leaf)

   The telegraphic names like L I are for a reason: we make tree values with them; that value making becomes clunky with "readable" so-called constructors. ie we want to decide at which point to optimize readability. The point of interaction called interaction-with-the-REPL is by and large simply not available with a compiled language like C++/Java.

Python equivalent of Catalan

def c(ls):
    if len(ls)==1:
        x = ls[0]
        return [('L',x)]
    else: 
        r = range(1,len(ls))
        return [('I',x,y) for i in r for x in c(ls[i:]) for y in c(ls[:i])]

def interm(ls):
    r = range(1,len(ls))
    return [(ls[:i], ls[i:]) for i in r]

1. Just load this up into python
2. Try out interm first to get the sense of all non trivial splits
3. ie try first interm([1]), interm([1,2]), interm([1,2,3]) etc
4. Finally try c([1]), c([1,2]), c([1,2,3])

Interpreter-n-Compiler

ctype Exp where
   L :Int → Exp
   Add, Mul: Exp → Exp →Exp

eval:Exp         → Int

eval.(L.x)       = x 
eval.(Add.e1.e2) = eval.e1 + eval.e2 
eval.(Mul.e1.e2) = eval.e1 * eval.e2 


ctype Instr where
   Opd: Int → Instr    -- Opd = OPeranD; it loads its arg onto the stack
   AddI, MulI: Instr

compile: Exp        → ℒ.Instr

compile.(L.x)       = [Opd.x]                            
compile.(Add.e1.e2) = compile.e1 ++ compile.e2 ++ [AddI]  
compile.(Mul.e1.e2) = compile.e1 ++ compile.e2 ++ [MulI]  

 
mac: ℒ.Instr → ℒ.ℤ → ℒ.ℤ

mac. [].        stk    = stk                      
mac. ((Opd.x) :: is).stk      = mac.is.(x :: stk) 
mac. (AddI :: is).(r::l::stk) = mac.is.(l+r::stk) 
mac. (MulI :: is).(r::l::stk) = mac.is.(l*r::stk) 

Showing the interpreter run:

? eval.(Add.(L.3).(L.4))
7 : ℤ

Then the compiler

? compile.(Add.(L.3).(L.4))
[Opd.3, Opd.4, AddI] : ℒ.Instr
? compile.(Add.(L.3).(L.4))
[Opd.3, Opd.4, AddI] : ℒ.Instr

Finally showing the output of the compiler given to the machine results in the top of the stack having same result as the interpreter

? mac.(compile.(Add.(L.3).(L.4))).[]
[7] : ℒ.ℤ

Summary

The two lines definition of c capture the essence of catalan numbers. The 4 lines eval + 4 lines compile + 5 lines machine capture a semester's worth of compiler construction.

One can of course keep fleshing out the details to one's taste.

But the summary is a lynchpin to understanding
(in my understanding 😇)

---

Added Later

Since you're making some efforts into understanding this (combinatorics part) I made another more detailed explanatory answer (hopefully!)

It strongly distinguishes between

• counting which must invariably be something from ℕ
• enumerating which actually creates the entities being counted
• with the convention that if the first is foo the second is fooE

What I've called c here should (in this new convention) be cE

And that cE returns a list whose length is the catalan number known in standard combinatorics accounts eg wikipedia

After you get that I'll uniformly change the convention and remove this "Added later"
[It'd be rude to change a text notations while someone is reading!!
For now I've changed the confusing type [a] to ℒ.t ]