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

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?

• Are you asking for input for a "first course" that uses FP or for the situation where the students have already studied computing in another paradigm? Feb 1, 2022 at 15:28
• @Buffy Either. I've outlined a sequence of exercises in my "from zero" class. What would a corresponding sequence be in FP and would it make any difference. My second scenario is one of the suggested end-of-semester coding projects, so feel free to suggest the sort of project that would be doable better in FP for a student with a semester of coding behind them. Feb 1, 2022 at 16:06
• Actually, I think he answers would be very different. Learning a first paradigm is much easier than changing paradigms. Feb 1, 2022 at 16:11
• The 'infection' assignment sounds interesting, have you seen the old Atari game Agent USA? Feb 1, 2022 at 23:06
• It was a teaching game, one of the few video games I thought was worth playing. It has a metaphor of an infection that the player is trying to defeat, so I thought of it from your assignment idea. I have never heard of anyone else using that example in an assignment, but perhaps I am ignorant. Feb 1, 2022 at 23:39

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.

• Please clarify: those five introductory steps, would they be handled differently in an OO paradigm, or would it be a case of same-approach-different-syntax? And yes, I realize that step 4 is "stateful". How would you approach that in FP? Feb 1, 2022 at 16:17
• @VictorEijkhout I hope I clarified!
– Ben I.
Feb 2, 2022 at 4:40
• At the level that my students code, having a nextprime function that takes an int and gives an int would be fine. However, conceivable, a stateful primegenerator object could retain history to be more efficient than that. Is there an FP way out of that? Feb 2, 2022 at 17:16
• @VictorEijkhout Yes, absolutely. Pass your state (such as your list of primes) as a parameter to your next function call. This is why stateful calculation is not FPs strongest suit. Passing state like this will also prevent some compiler optimizations such as automatic memoization (a big advantage that stateless languages can provide). In general, the reason that compiled Haskell code is most comparable to C is because they take really excellent advantage of presuppositions that are only safe because of statelessness.
– Ben I.
Feb 2, 2022 at 20:28
• @VictorEijkhout That said, if your compiler does do automatic memoization, you might find that passing state the way I describe actually provides no benefit at all, since your prior results will already not need to be recalculated. I'm sure Rusi would know more about this part than me.
– Ben I.
Feb 2, 2022 at 20:31

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
• (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.
• I really wish you would define your syntax. "pE : [a] → [[a]]" means "for a given element a, the list with single element a is mapped into the list with as element the list of a". Yes? You're being about 200% too metaphorical in your notation. I can sort of imagine what it means, but not really. Or maybe this is standard notation, but in an area that I don't know about. Feb 4, 2022 at 20:05
• Yeah, I could never be a mathematician. Parents wanted me to go in to EE, but the mathness was a little bit too much. I just watched an old music video where they showed a coffee pot as surfaces of revolution and I burst in to tears: so beautiful! So the FP stuff is also ravishing, and not for me. Feb 4, 2022 at 22:52
• Comments at chat : chat.stackexchange.com/rooms/59174/the-classroom
– Rusi
Feb 5, 2022 at 9:28
• @VictorEijkhout: pE : [a] → [[a]] is just standard typing syntax in almost any arbitrary functional programming language. It would be legal (or almost legal) in Gofer, Haskell, ML, Standard ML, OCaml, F#, Elm, Idris, and many others and immediately recognizable to a Scala programmer as well. It means "pE is a function from list-of-as to list-of-lists-of-as", where a is a type parameter, IOW pE is a parametrically polymorphic function. It is really the standard way to write a function type. Apr 10, 2022 at 11:05
• @JörgWMittag (Since you're a couple of months late to the party😄). Here's the link to the longer chat ensuing from here chat.stackexchange.com/transcript/59174/2022/2/5
– Rusi
Apr 11, 2022 at 15:14

# 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??

• 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 xl-part and each yr-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
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(), interm([1,2]), interm([1,2,3]) etc
4. Finally try c(), 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.(Mul.e1.e2) = eval.e1 * eval.e2

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

compile: Exp        → ℒ.Instr

compile.(L.x)       = [Opd.x]
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))


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))).[]
 : ℒ.ℤ


# 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 😇)

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 ]

• Thanks for writing this much. Now, overlooking ridiculous statements that some page of Lisp would "cover the field of language implementation" (wish I'd know that before I took a 2 semester compiler writing course!), can you explain that Catelan example? What is c.[1,2]? Catelan numbers have one index, not 2 or 3. And why doesn't it output a number? Your syntax is far from self-explanatory to me. Feb 1, 2022 at 18:14
• I'm afraid I still don't get it. I figured out that c.[1,2] was like c(1,2), but why are there 2 or 3 parameters to begin with? Where is the code that says c.4 => 75 or whatever it is? And why splitting the list? I don't see any lists in the math, let alone split lists. And what does the : [Tree.Int] notation do? Maybe you can use some pseudo notation that gets the idea across without bogging me down in counter intuitive syntax. Feb 2, 2022 at 2:49
• @VictorEijkhout Check now Heres equivalent python code; shud run in python (3)
– Rusi
Feb 2, 2022 at 3:17
• @VictorEijkhout «Why are there 2 or 3 parameters?» Theres exactly one list parameter. Sorry I missed the type of c. Type inference is a pleasant luxury; but disconcerting to the onlooker😎 Inserted type of c now. More logical reordering now
– Rusi
Feb 2, 2022 at 3:36
• @victoreijkhout Towards reducing the outlandish feel to "cover the field of language implementation" to "be a HelloWorld to the field of language implementation" would it convey something without the feeling of absurdity?
– Rusi
Feb 2, 2022 at 19:50