<h1>Why FP?</h1>
<p>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.</p>
<p>Why does Doug McIlroy describe McCarthy's first Lisp lecture as the The Most Significant <a href="http://www.paulgraham.com/mcilroy.html" rel="nofollow noreferrer">Computer Science talk</a> he ever attended??</p>
<p>What was done is (to me) less important than the last line:</p>
<blockquote>
<p>One could go home and build it oneself without any instruction book</p>
</blockquote>
<p>This is what I mean by <strong>conspective</strong></p>
<p>Alan Kay says that studying Lisp's eval-apply pair <a href="https://stackoverflow.com/questions/34888245/alan-kays-eval-apply-einstein-moment">increased his understanding of CS</a> by a factor of hundred.</p>
<p>So to take Alan Kay's example:</p>
<p>The Lisp interpreter in Lisp is hardly a pageful</p>
<p>Which means that that page, presumably coverable in one lecture, could be said <strong>to cover the field of language implementation.</strong></p>
<p>Now can McCarthy's one page lisp in lisp be compared with gcc's <a href="https://en.wikipedia.org/wiki/GNU_Compiler_Collection" rel="nofollow noreferrer">15 million lines</a>??</p>
<p>Some answers may be</p>
<ul>
<li>Lisp-in-lisp is a toy gcc is real</li>
<li>Apples-n-oranges comparison</li>
<li>Oh gcc is many languages, many machines...</li>
</ul>
<p>I think all such answers miss the point.</p>
<p>Sure there's &quot;more&quot; 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 &quot;all thats here&quot; something crucial is lacking in our communication and ultimately <strong>in our understanding.</strong></p>
<p>This is after all Einstein in a different guise: <em>You do not understand something unless you can explain it to your grandmother</em> (<a href="https://skeptics.stackexchange.com/questions/8742/did-einstein-say-if-you-cant-explain-it-simply-you-dont-understand-it-well-en">or a 6-year old or a barmaid</a>)</p>
<p>Of course people do dig into gcc starting zero and there are intros to the field as there are intros to all fields egs</p>
<ul>
<li>the chapters of a compiler book</li>
<li>a block diagram of main parts of toolchain</li>
<li>a UML diagram</li>
<li>etc</li>
</ul>
<p>But in FP there is a a very special extra possibility: <strong>Show that conspectus as executable code</strong></p>
<p>Compared to that all the above have a quality of hand-waving</p>
<p>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.</p>
<h2>Notes on non-standard notation</h2>
<h3>1. function-call notation</h3>
<p><code>c.[1,2]</code> would look like <code>c([1,2])</code> in conventional C-family language style.<br />
ie</p>
<ul>
<li>C family :<code>f(x)</code></li>
<li>Haskell family <code>f x</code></li>
<li>Dijkstra functional notation: <code>f.x</code></li>
</ul>
<p>ie <code>f.x</code> is the Dijkstra form of the more usual <code>f(x)</code> ie function call.
I could give justifications/explanations for the Dijkstra notation (if desired).</p>
<h3>2. Algebraic Datatypes</h3>
<p>Things like <code>L</code>, <code>I</code> are constructors of <a href="https://en.wikipedia.org/wiki/Algebraic_data_type" rel="nofollow noreferrer">algebraic data types</a>. The small notational wrinkle carrying a large semantic load here is tiny fact of &quot;initial letter capital implies data constructor not normal function&quot;.  For this Fortranism  — identical in my notation to Haskell — my embarrassed apologies .</p>
<h3>3. Interactions</h3>
<p>One interacts with the system by typing something at the <code>? </code> prompt.<br />
The system responds with a result (as any interpreter does). <strong>And its type</strong><br />
Pedagogically this is a big deal: Types serve as a beginner cyclist's guide wheels</p>
<ul>
<li>The user almost never gives a type</li>
<li>The system invariably responds with a type as if to say: <em>Your answer is this, and its type according to me is this.</em></li>
</ul>
<p>If you (Victor) have some (standard) FPL preference, I can try moving to that... For now the Catalan example is shown also in Python</p>
<h1>Combinatorics</h1>
<h2>Catalan Numbers</h2>
<pre><code> -- 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:  &quot;Internal node&quot;
     L : t → Tree.t                -- L:  &quot;Leaf node&quot;
  
 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]
</code></pre>
<p>Example usage:</p>
<pre><code>? 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.ℤ)
</code></pre>
<p>Now if you see those 2 lines defining the Catalan enumerator <code>c</code>.
And now see the definition from <a href="https://en.wikipedia.org/wiki/Catalan_number#Properties" rel="nofollow noreferrer">wikipedia</a>, you can see the closeness of the parallel
<span class="math-container">$$\begin{aligned}C_0 &amp;= 1\\
C_{n+1} &amp;= \sum_{i=0}^{n}C_iC_{n-i}\quad\text{for }n\ge 0\end{aligned}$$</span></p>
<h3>Catalan explanation</h3>
<p>So the verbalization of catalan enumeration would go like this:</p>
<h3>Trivial case</h3>
<p><code>c</code> for a singleton list is a singleton answer: just a L(eaf) node</p>
<h3>Recursive case</h3>
<p>For a list of greater than 1 element (called <code>ls</code>)</p>
<ol>
<li><p>Generate all <code>i</code>s from <code>[1... length.ls -1]</code>
More usually the <code>length.ls - 1</code> may look <code>length(ls) - 1</code></p>
</li>
<li><p>For each such <code>i</code> split the list <code>ls</code> at <code>i</code>
Call the two halves <code>l</code> and <code>r</code><br />
1,2 Basically generate all <em>non-trivial ie non-empty splits of the input</em></p>
</li>
<li><p>Generate all Catalan enumerations for <code>l</code> (the <code>c.l</code> recursive call) Likewise <code>r</code>
Note these are LISTS of catalan enumerations internal-to-the-recursion generated
For each <code>x</code> ∈ <code>l</code>-part and each <code>y</code> ∈ <code>r</code>-part...</p>
</li>
<li><p>Collect the node (at the head of the list comprehension) <code>I.x.y</code>
(<code>I</code> stands for internal node like  <code>L</code> stands for Leaf)</p>
<p>The telegraphic names like <code>L</code> <code>I</code> are for a reason: we make tree <strong>values</strong> with them; that value making becomes clunky with &quot;readable&quot; so-called constructors. ie we want to decide <em>at which point</em> to optimize readability.  The point of interaction called <em>interaction-with-the-REPL</em> is by and large simply not available with a compiled language like C++/Java.</p>
</li>
</ol>
<h3>Python equivalent of Catalan</h3>
<pre><code>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]
</code></pre>
<ol>
<li>Just load this up into python</li>
<li>Try out <code>interm</code> first to get the sense of <em>all non trivial splits</em></li>
<li>ie try first <code>interm([1])</code>, <code>interm([1,2])</code>, <code>interm([1,2,3])</code> etc</li>
<li>Finally try <code>c([1])</code>, <code>c([1,2])</code>, <code>c([1,2,3])</code></li>
</ol>
<h1>Interpreter-n-Compiler</h1>
<pre><code>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) 
</code></pre>
<p>Showing the interpreter run:</p>
<pre><code>? eval.(Add.(L.3).(L.4))
7 : ℤ
</code></pre>
<p>Then the compiler</p>
<pre><code>? compile.(Add.(L.3).(L.4))
[Opd.3, Opd.4, AddI] : ℒ.Instr
? compile.(Add.(L.3).(L.4))
[Opd.3, Opd.4, AddI] : ℒ.Instr
</code></pre>
<p>Finally showing the output of the compiler given to the machine results in the top of the stack having same result as the interpreter</p>
<pre><code>? mac.(compile.(Add.(L.3).(L.4))).[]
[7] : ℒ.ℤ
</code></pre>
<h1>Summary</h1>
<p>The two lines definition of <code>c</code> capture the essence of catalan numbers.
The 4 lines eval + 4 lines compile + 5 lines machine capture a semester's worth of compiler construction.</p>
<p>One can of course keep fleshing out the details to one's taste.</p>
<p>But the summary is a lynchpin to understanding<br />
(in my understanding )</p>
<hr />
<h2>Added Later</h2>
<p>Since you're making some efforts into understanding this (combinatorics part) I made another more detailed explanatory <a href="https://cseducators.stackexchange.com/a/7280/8837">answer</a> (hopefully!)</p>
<p>It strongly distinguishes between</p>
<ul>
<li><em>counting</em> which must invariably be something from ℕ</li>
<li><em>enumerating</em> which actually creates the entities being counted</li>
<li>with the convention that if the first is <code>foo</code> the second is <code>fooE</code></li>
</ul>
<p>What I've called <code>c</code> here should (in this new convention) be <code>cE</code></p>
<p>And that <code>cE</code> returns a list whose <em>length</em> is the catalan number known in standard combinatorics accounts eg wikipedia</p>
<p>After you get that I'll uniformly change the convention and remove this &quot;Added later&quot;<br />
[It'd be rude to change a text notations while someone is reading!!<br />
For now I've changed the confusing type <code>[a]</code> to <code>ℒ.t</code> ]</p>

CC BY-SA 4.0
2022-02-01T18:14:41.473Z
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.
Victor Eijkhout
CC BY-SA 4.0
2022-02-02T02:49:03.713Z
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.
Victor Eijkhout
CC BY-SA 4.0
2022-02-02T03:17:43.733Z
@VictorEijkhout Check now Heres equivalent python code; shud run in python (3)
Rushi
CC BY-SA 4.0
2022-02-02T03:36:11.383Z
@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
Rushi
CC BY-SA 4.0
2022-02-02T19:50:33.857Z
@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?
Rushi
CC BY-SA 4.0
2022-02-03T18:14:31.107Z
Ok, so why is there a list parameter? C(n) is a function of an integer. Also, your code in either language does not output an integer. So I don't know if it's correct because the code is not "obviously correct". For instance why does a sum-of-products involve splitting a list? Please have your code print out a number. I get "C_20 = 6564120420" (or maybe that's 19). How long does your program take for that, in seconds? It's a pity I can not paste code blocks in this comment.
Victor Eijkhout
CC BY-SA 4.0
2022-02-03T18:18:05.853Z
It *enumerates* the actual trees @victoreijkhout. The first line comment correlates with the Wikipedia entry which it's mirroring
Rushi
CC BY-SA 4.0
2022-02-03T19:33:12.673Z
I guess you were leading me astray by showing one formula and then computing something that gives the same result, but with a different computation. I was looking at that sum-of-products and your trees and really not seeing the relation.
Anyway, that sum of products gets really slow around C17 (on my laptop). Hence my question how long it takes you to compute the actual value of C20. (Since you're creating recursive trees I'm guessing your machine will actually barf before it gives the result. Computing the trees and then enumerating has the right time but wrong space complexity.)
Victor Eijkhout
CC BY-SA 4.0
2022-02-01T17:27:57.660Z
2022-02-06T04:08:22.930Z
2022-02-06T04:08:22.930Z
Rushi
<p>My <a href="https://cseducators.stackexchange.com/a/7268/8837">other answer</a> 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.</p>
<h2>Combinatorics : Conspectus</h2>
<p>To the lay-person combinatorics consists of some formula eg <span class="math-container">$n!$</span> <span class="math-container">$\binom{n}{r}$</span><br />
<sub> I will write it in the older style as <span class="math-container">${}^n\!C_r$</span> so that making a <code>c</code> function becomes straightforward map
</sub></p>
<p>But where do these formulae come from??</p>
<h2>Enumerative Processes</h2>
<p>There are certain sets/lists/processes whose size/length/what-have-you are the context of these formulae</p>
<p>To be more concrete:
Given set <span class="math-container">$S$</span> having <span class="math-container">$n$</span> elements the powerset of <span class="math-container">$S$</span> is <span class="math-container">$\wp(S)$</span></p>
<p><span class="math-container">$\begin{aligned}\text{Where if} \quad \vert S\vert &amp;= n\\     
\text{Then }\quad \vert\wp(S)\vert &amp;= 2^n
\end{aligned}$</span></p>
<p>In short combinatorics straddles two worlds:</p>
<ol>
<li>One where things like <span class="math-container">$S$</span>, <span class="math-container">$\wp(S)$</span> etc live</li>
<li>One where things like <span class="math-container">$n$</span>, <span class="math-container">$2^n$</span> live</li>
<li>Mappings like the <span class="math-container">$\vert \cdot \vert$</span> (size) function that steps from one to the other world</li>
</ol>
<p>Now a strange phenomenon: Clearly the second world <em>derives</em> from the first, yet the second is formalized as the standard formulae of combinatorics the first remains more informal... pictures, descriptions, English text...</p>
<p>What would it take to formalize the first world also and <em>from there</em> the mapping to the second??</p>
<p>IMHO it would be a better presentation of the combinatorial identities</p>
<h2>Notational Notes</h2>
<ol>
<li>If the numerical function is <code>foo</code>, I'll call the enumerative function <code>fooE</code>.</li>
<li>The function call <code>foo.x.y</code> can be written infix as<br />
<code>x `foo` y</code> :
With this, we can read <span class="math-container">${}^n\!C_r$</span> &quot;en-see-aar&quot;</li>
<li><code>ℒ.t</code> is the type List-of-t (t is an arbitrary type). <code>ℒ.ℕ</code> etc are specific list types</li>
<li>Its de-ASCII-ized eg <code>∈</code> not <code>&lt;-</code>, <code>ℒ.t</code> not <code>[t]</code> etc. If someone actually gets round to <a href="https://github.com/rusimody/gofer" rel="nofollow noreferrer">compiling it</a> and trying out: please ask me! I can give literal running code if desired.</li>
</ol>
<h2>Some examples</h2>
<h3>1. Powerset of a set</h3>
<p>If <span class="math-container">$S = \{a,b,c\}$</span> then<br />
<span class="math-container">$\wp(S) = \{\emptyset, a, b, c, ab, ac, bc, abc\}$</span><br />
<sub>Dropping brackets and commas for obvious reasons! ie read <span class="math-container">$ab$</span> as <span class="math-container">$\{a,b\}$</span> </sub></p>
<p>For a finite set of <span class="math-container">$n$</span> elements, lets write <code>pE</code> ie powerset enumerator</p>
<pre><code>pE :   ℒ.t → ℒ.(ℒ.t))
pE.     [] = [[]]
pE.(x::xs) = concat.[[s, x::s] | s ∈ pE.xs]

</code></pre>
<p>It should be clear that pE starts with a singleton list
And at every stage its size doubles</p>
<p>So that there is the clear correlation between <span class="math-container">$\wp(S)$</span> <em>construction</em> and <span class="math-container">$\wp(S)$</span> size</p>
<p>We can formalize this by actually writing <code>p</code></p>
<pre><code>p :  ℕ  → ℕ   -- p is good ol power of 2
p.   0  = 1
p.(n+1) = 2*p.n
</code></pre>
<p>Usage</p>
<pre><code>? pE.&quot;abc&quot;
[[], &quot;a&quot;, &quot;b&quot;, &quot;ab&quot;, &quot;c&quot;, &quot;ac&quot;, &quot;bc&quot;, &quot;abc&quot;] : ℒ.(ℒ.Char))
</code></pre>
<p>And defining identity:  <code>length.(pE.l)</code> <span class="math-container">$=$</span> <code>p.(length.l)</code></p>
<h3>2. Combinations</h3>
<p>Also known as the binomial coefficient <span class="math-container">${}^n\!C_r$</span></p>
<p>But what exactly does it count??</p>
<p>If <span class="math-container">$S$</span> is an <span class="math-container">$n$</span>-set <span class="math-container">${}^n\!C_r$</span> is the <strong>number</strong> of all <span class="math-container">$r$</span> length subsets of <span class="math-container">$S$</span></p>
<p>But what are those (sub)sets <strong>themselves</strong>? Lets make that explicit</p>
<p>So here's the Pascal triangle — classic version.</p>
<pre><code>1
1 1
1 2 1
1 3 3 1
</code></pre>
<p>Pascal triangle showing the universal set from which the combinations are made for each row</p>
<pre><code>1               ∅
1 1             a
1 2 1           ab
1 3 3 1         abc
</code></pre>
<p>Above with the specific sets at each level made explicit</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>counts</th>
<th>base set S</th>
<th>all combs</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>∅</td>
<td>«∅»</td>
</tr>
<tr>
<td>1 1</td>
<td>a</td>
<td>«∅,{a}»</td>
</tr>
<tr>
<td>1 2 1</td>
<td>ab</td>
<td>«∅, {a, b} {ab}»</td>
</tr>
<tr>
<td>1 3 3 1</td>
<td>abc</td>
<td>«∅, {a, b, c} {ab, bc, ac} {abc}»</td>
</tr>
</tbody>
</table>
</div>
<p>The parallel between first and third column should be patent enough.<br />
Lets anyhow capture that in a pair of functions: <code>cE</code> and <code>c</code></p>
<pre><code>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)
</code></pre>
<p>Note that the <span class="math-container">$c$</span> def is just the classic Pascal identity:
<span class="math-container">${}^{n+1}\!C_r  = {}^n\!C_r + {}^n\!C_{r-1}$</span>. And <code>cE</code> explains why that</p>
<p>Usage:</p>
<pre><code>? 5 `c` 2
10 : ℕ
? [5 `c` i | i ∈ [0...5]]
[1, 5, 10, 10, 5, 1] : ℒ.ℕ

? &quot;abcde&quot; `cE` 2
[&quot;de&quot;, &quot;ce&quot;, &quot;cd&quot;, &quot;be&quot;, &quot;bd&quot;, &quot;bc&quot;, &quot;ae&quot;, &quot;ad&quot;, &quot;ac&quot;, &quot;ab&quot;] : ℒ.(ℒ.Char)
</code></pre>
<p>So as for the relation between <code>p</code> and <code>pE</code> likewise between <code>c</code> and <code>cE</code></p>
<p>And the defining identity between <code>c</code> and <code>cE</code>: <code>length.(l `cE` r)</code> <span class="math-container">$=$</span> <code>(length.l) `c` r</code></p>
<p>Note the types:</p>
<ul>
<li><code>c</code> takes 2 numbers (ℕ) <code>n</code> and <code>r</code> and returns an ℕ</li>
<li><code>cE</code> takes a list (<code>ℒ.t</code>) and an ℕ and returns a <code>ℒ.(ℒ.t)</code> type list</li>
</ul>
<h2>Philosophical Slant</h2>
<p>The above is a foray into basic combinatorics.<br />
And combinatorics is math!</p>
<p>So there's a definite slant:</p>
<ul>
<li>Math is the primary topic of this</li>
<li>That it runs on a computer is secondary</li>
<li>You could call it <em>executable math</em> but note that...</li>
<li>...  we need to stop thinking of programs as <strong>executing</strong> and start thinking of them as calculators <strong>evaluating over sophisticated data structures</strong><br />
vide <a href="https://cseducators.stackexchange.com/questions/1090/how-should-the-paradigm-shift-associated-with-functional-programming-be-approach/7262#7262">other answer</a></li>
<li>(With nod to @ScottRowe) <strong>It's all about data; only peripherally about computation!</strong><br />
And <em>function</em>-al programming is a particularly inept description of it...<br />
But we seem stuck with that term for now.</li>
</ul>

CC BY-SA 4.0
2022-02-04T20:05:38.880Z
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.
Victor Eijkhout
CC BY-SA 4.0
2022-02-04T22:52:13.223Z
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.
Scott Rowe
CC BY-SA 4.0
2022-02-05T09:28:45.647Z
Comments at chat : https://chat.stackexchange.com/rooms/59174/the-classroom
Rushi
CC BY-SA 4.0
2022-04-10T11:05:21.770Z
@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-`a`s to list-of-lists-of-`a`s", where `a` is a type parameter, IOW `pE` is a parametrically polymorphic function. It is really *the* standard way to write a function type.
Jörg W Mittag
CC BY-SA 4.0
2022-04-11T15:14:41.007Z
@JörgWMittag (Since you're a couple of months late to the party). Here's the link to the longer chat ensuing from here https://chat.stackexchange.com/transcript/59174/2022/2/5
Rushi
CC BY-SA 4.0
2022-02-04T17:01:57.877Z
2022-02-05T13:16:04.760Z
2022-02-05T13:16:04.760Z
Rushi
<p>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.</p>
<p>Because of immutability, concurrency is far safer.</p>
<p>Your set of five questions would work very well in FP, though obviously step 4 would be modified.</p>
<p>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.</p>
<p>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 <code>next-prime</code> method that takes a prime number as an argument, and finds the next one.</p>
<p>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.</p>
<p>The sickness modeling problem is fine, though it would involve passing a fair amount of state information from one function call to the next.</p>
<p>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 &quot;imperative&quot; languages, and you can gain the benefits as well.</p>

CC BY-SA 4.0
2022-02-01T16:17:06.420Z
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?
Victor Eijkhout
CC BY-SA 4.0
2022-02-02T04:40:24.123Z
@VictorEijkhout I hope I clarified!
Ben I.
CC BY-SA 4.0
2022-02-02T17:16:01.777Z
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?
Victor Eijkhout
CC BY-SA 4.0
2022-02-02T20:28:24.423Z
@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.
CC BY-SA 4.0
2022-02-02T20:31:26.737Z
@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.
CC BY-SA 4.0
2022-02-02T21:47:49.847Z
Thanks. But passing state explicitly is the sort of uglyness that OO languages elegantly solve by keeping it internal. Automatic memoization: never thought of it as a compiler technique, though it's conceivable. In extremely simple cases. I think compiler optimization are rather the stateless type: they can reason when instructions can be executed in a different order from specified (because they are independent) to make them more efficient. Btw, that's another reason I don't like FP languages: if you formulate everything recursively you're throwing up roadblocks for compiler optimizations.
Victor Eijkhout
CC BY-SA 4.0
2022-02-03T00:02:02.413Z
@VictorEijkhout In FP, statements can be executed in almost any order. It makes it very easy to parallel process, and automatic memoizing is a real thing. I think you're backwards about the compiler optimisations, though. We're writing code that seems like it should be much slower, and winding up with close-to-c speeds because statelessness triviality allows for compiler optimizations that no imperative compiler could ever automatically perform.
Ben I.
CC BY-SA 4.0
2022-02-03T00:30:59.297Z
I think we should stop the discussion. Move to chat or find my email. But I don't believe for a second that FP code can be competitive in speed or parallelism. I understand the argument, I just don't buy it. Does a Haskell compiler do loop exchange to increase cache usage? Does an FP code have nonzero cache reuse to begin with? Anyway. Let's call it a night. Day. Whatever.
Victor Eijkhout
CC BY-SA 4.0
2022-02-03T00:47:10.410Z
@VictorEijkhout That's fine.  I'm not even necessarily arguing with you.  I'm not an expert in this area by any stretch.  I just see things like this, and I am perhaps a bit too credulous: https://stackoverflow.com/q/35027952. It could all be exaggerated, and I would not be shocked.  I'm pretty sure that the optimisations are surprisingly good, even if they're not generally what people claim, if only because I regularly see pages like the one I just linked to.
Ben I.
CC BY-SA 4.0
2022-02-04T03:15:17.443Z
@victoreijkhout State threading is a (the) fundamental use case why Haskell uses monads: classic prehistory paper https://www.microsoft.com/en-us/research/wp-content/uploads/1993/01/imperative.pdf (there's much packed into the cute title)
Rushi
CC BY-SA 4.0
2022-02-04T03:29:40.877Z
When I talk of "conspective view" the first and most obvious thing I'm throwing out the window is efficiency. Efficiency is not unimportant mind you (even in my book ) But if we don't reasonably **separate** efficiency questions from existential ones the conversation soon becomes confused and pointless. In short we need to have *three separate* conversations: (1) existential (2) efficiency (3) why rigorously separate the 2. I gave my key efficiency-dictum (I called it "slogan") here https://cseducators.stackexchange.com/a/7257/8837. Do reflect on it
Rushi
CC BY-SA 4.0
2022-02-01T15:36:51.213Z
2022-02-02T04:39:34.350Z
2022-02-02T04:39:34.350Z
Ben I.
<p>I teach programming to a science/engineering students. Here is a typical sequence of assignments for a beginning programming class:</p>
<ol>
<li>Arithmetic and conditionals: does <code>x</code> divide <code>y</code></li>
<li>Looping: is a number prime</li>
<li>Functions: test prime-ness</li>
<li>Object-oriented: make a <code>primegenerator</code> class with a <code>nextprime</code> method.</li>
<li>All together: test the hypothesis that each prime is the average of two other primes.</li>
</ol>
<p>Apart from side-effect-free coding, does FP offer anything in this sort of exercise set?</p>
<p>Bigger project: write a <code>person</code> class, and model diseases: the person has an <code>infect</code> method and a <code>nextday</code> method, and after a fixed number of days, they are healthy again. Now make a <code>population</code> class which contains a bunch of <code>person</code>s, and model disease propagation. Again a <code>nextday</code> method, where in each day people can infect each other with some probability, or they are vaccinated. Do parameter studies of herd immunity.</p>
<p>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?</p>

CC BY-SA 4.0
2022-02-01T15:28:36.367Z
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?
Buffy
CC BY-SA 4.0
2022-02-01T16:06:29.557Z
@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.
Victor Eijkhout
CC BY-SA 4.0
2022-02-01T16:11:29.053Z
Actually, I think he answers would be very different. Learning a first paradigm is much easier than changing paradigms.
Buffy
CC BY-SA 4.0
2022-02-01T16:14:20.057Z
@Buffy I see what you're saying. I wasn't actually much thinking about changing paradigms, more: what would good assignments be at two different levels of difficulty.
Victor Eijkhout
CC BY-SA 4.0
2022-02-01T23:06:37.147Z
The 'infection' assignment sounds interesting, have you seen the old Atari game Agent USA?
Scott Rowe
CC BY-SA 4.0
2022-02-01T23:29:59.450Z
@ScottRowe No, why?
Victor Eijkhout
CC BY-SA 4.0
2022-02-01T23:39:10.677Z
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.
Scott Rowe
<curriculum-design><exercises><functional-programming>
What sort of programming assignments do you give in an FP course?
# What sort of programming assignments do you give in an FP course?

(Asked by: username_0 on 2022-02-01)

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 `person`s, 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?

**Tags:** curriculum-design, exercises, functional-programming

> **Comments:**
> **username_1**: 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?  
> **username_0**: @username_1 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.  
> **username_1**: Actually, I think he answers would be very different. Learning a first paradigm is much easier than changing paradigms.  
> **username_0**: @username_1 I see what you're saying. I wasn't actually much thinking about changing paradigms, more: what would good assignments be at two different levels of difficulty.  
> **username_2**: The 'infection' assignment sounds interesting, have you seen the old Atari game Agent USA?  
> **username_0**: @ScottRowe No, why?  
> **username_2**: 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.  

---

## 3 answers

### Answer by username_5 on 2022-02-01. Score: 2

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.

> **Comments:**
> **username_0**: 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?  
> **username_5**: @VictorEijkhout I hope I clarified!  
> **username_0**: 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?  
> **username_5**: @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.  
> **username_5**: @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.  
> **username_0**: Thanks. But passing state explicitly is the sort of uglyness that OO languages elegantly solve by keeping it internal. Automatic memoization: never thought of it as a compiler technique, though it's conceivable. In extremely simple cases. I think compiler optimization are rather the stateless type: they can reason when instructions can be executed in a different order from specified (because they are independent) to make them more efficient. Btw, that's another reason I don't like FP languages: if you formulate everything recursively you're throwing up roadblocks for compiler optimizations.  
> **username_5**: @VictorEijkhout In FP, statements can be executed in almost any order. It makes it very easy to parallel process, and automatic memoizing is a real thing. I think you're backwards about the compiler optimisations, though. We're writing code that seems like it should be much slower, and winding up with close-to-c speeds because statelessness triviality allows for compiler optimizations that no imperative compiler could ever automatically perform.  
> **username_0**: I think we should stop the discussion. Move to chat or find my email. But I don't believe for a second that FP code can be competitive in speed or parallelism. I understand the argument, I just don't buy it. Does a Haskell compiler do loop exchange to increase cache usage? Does an FP code have nonzero cache reuse to begin with? Anyway. Let's call it a night. Day. Whatever.  
> **username_5**: @VictorEijkhout That's fine.  I'm not even necessarily arguing with you.  I'm not an expert in this area by any stretch.  I just see things like this, and I am perhaps a bit too credulous: https://stackoverflow.com/q/35027952. It could all be exaggerated, and I would not be shocked.  I'm pretty sure that the optimisations are surprisingly good, even if they're not generally what people claim, if only because I regularly see pages like the one I just linked to.  
> **username_3**: @victoreijkhout State threading is a (the) fundamental use case why Haskell uses monads: classic prehistory paper https://www.microsoft.com/en-us/research/wp-content/uploads/1993/01/imperative.pdf (there's much packed into the cute title)  
> **username_3**: When I talk of "conspective view" the first and most obvious thing I'm throwing out the window is efficiency. Efficiency is not unimportant mind you (even in my book ) But if we don't reasonably **separate** efficiency questions from existential ones the conversation soon becomes confused and pointless. In short we need to have *three separate* conversations: (1) existential (2) efficiency (3) why rigorously separate the 2. I gave my key efficiency-dictum (I called it "slogan") here https://cseducators.stackexchange.com/a/7257/8837. Do reflect on it  

---

### Answer by username_3 on 2022-02-01. Score: 1

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)

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

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

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...

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]


Just load this up into python
Try out interm first to get the sense of all non trivial splits
ie try first interm([1]), interm([1,2]), interm([1,2,3]) etc
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 ]

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  
> **username_3**: @VictorEijkhout Check now Heres equivalent python code; shud run in python (3)  
> **username_3**: @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  
> **username_3**: @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?  
> **username_0**: Ok, so why is there a list parameter? C(n) is a function of an integer. Also, your code in either language does not output an integer. So I don't know if it's correct because the code is not "obviously correct". For instance why does a sum-of-products involve splitting a list? Please have your code print out a number. I get "C_20 = 6564120420" (or maybe that's 19). How long does your program take for that, in seconds? It's a pity I can not paste code blocks in this comment.  
> **username_3**: It *enumerates* the actual trees @victoreijkhout. The first line comment correlates with the Wikipedia entry which it's mirroring  
> **username_0**: I guess you were leading me astray by showing one formula and then computing something that gives the same result, but with a different computation. I was looking at that sum-of-products and your trees and really not seeing the relation. Anyway, that sum of products gets really slow around C17 (on my laptop). Hence my question how long it takes you to compute the actual value of C20. (Since you're creating recursive trees I'm guessing your machine will actually barf before it gives the result. Computing the trees and then enumerating has the right time but wrong space complexity.)  

---

### Answer by username_3 on 2022-02-04. Score: 1

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:

One where things like $S$, $\wp(S)$ etc live
One where things like $n$, $2^n$ live
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

If the numerical function is foo, I'll call the enumerative function fooE.
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"
ℒ.t is the type List-of-t (t is an arbitrary type). ℒ.ℕ etc are specific list types
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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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.  
> **username_3**: Comments at chat : https://chat.stackexchange.com/rooms/59174/the-classroom  
> **username_4**: @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-`a`s to list-of-lists-of-`a`s", where `a` is a type parameter, IOW `pE` is a parametrically polymorphic function. It is really *the* standard way to write a function type.  
> **username_3**: @JörgWMittag (Since you're a couple of months late to the party). Here's the link to the longer chat ensuing from here https://chat.stackexchange.com/transcript/59174/2022/2/5  

---

