Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-01T18:14:41.473Z
Answers.Text: 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.
Answers.UserDisplayName: Victor Eijkhout
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-02T02:49:03.713Z
Answers.Text: 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.
Answers.UserDisplayName: Victor Eijkhout
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-02T03:17:43.733Z
Answers.Text: @VictorEijkhout Check now Heres equivalent python code; shud run in python (3)
Answers.UserDisplayName: Rushi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-02T03:36:11.383Z
Answers.Text: @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
Answers.UserDisplayName: Rushi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-02T19:50:33.857Z
Answers.Text: @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?
Answers.UserDisplayName: Rushi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-03T18:14:31.107Z
Answers.Text: 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.
Answers.UserDisplayName: Victor Eijkhout
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-03T18:18:05.853Z
Answers.Text: It *enumerates* the actual trees @victoreijkhout. The first line comment correlates with the Wikipedia entry which it's mirroring
Answers.UserDisplayName: Rushi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-03T19:33:12.673Z
Answers.Text: 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.)
Answers.UserDisplayName: Victor Eijkhout
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-01T17:27:57.660Z
Answers.LastActivityDate: 2022-02-06T04:08:22.930Z
Answers.LastEditDate: 2022-02-06T04:08:22.930Z
Answers.UserDisplayName: Rushi
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-04T20:05:38.880Z
Answers.Text: 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.
Answers.UserDisplayName: Victor Eijkhout
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-04T22:52:13.223Z
Answers.Text: 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.
Answers.UserDisplayName: Scott Rowe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-05T09:28:45.647Z
Answers.Text: Comments at chat : https://chat.stackexchange.com/rooms/59174/the-classroom
Answers.UserDisplayName: Rushi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-10T11:05:21.770Z
Answers.Text: @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.
Answers.UserDisplayName: Jörg W Mittag
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-11T15:14:41.007Z
Answers.Text: @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
Answers.UserDisplayName: Rushi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-04T17:01:57.877Z
Answers.LastActivityDate: 2022-02-05T13:16:04.760Z
Answers.LastEditDate: 2022-02-05T13:16:04.760Z
Answers.UserDisplayName: Rushi
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-01T16:17:06.420Z
Answers.Text: 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?
Answers.UserDisplayName: Victor Eijkhout
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-02T04:40:24.123Z
Answers.Text: @VictorEijkhout I hope I clarified!
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-02T17:16:01.777Z
Answers.Text: 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?
Answers.UserDisplayName: Victor Eijkhout
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-02T20:28:24.423Z
Answers.Text: @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.
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-02T20:31:26.737Z
Answers.Text: @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.
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-02T21:47:49.847Z
Answers.Text: 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.
Answers.UserDisplayName: Victor Eijkhout
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-03T00:02:02.413Z
Answers.Text: @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.
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-03T00:30:59.297Z
Answers.Text: 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.
Answers.UserDisplayName: Victor Eijkhout
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-03T00:47:10.410Z
Answers.Text: @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.
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-04T03:15:17.443Z
Answers.Text: @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)
Answers.UserDisplayName: Rushi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-04T03:29:40.877Z
Answers.Text: 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
Answers.UserDisplayName: Rushi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-01T15:36:51.213Z
Answers.LastActivityDate: 2022-02-02T04:39:34.350Z
Answers.LastEditDate: 2022-02-02T04:39:34.350Z
Answers.UserDisplayName: Ben I.
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-01T15:28:36.367Z
Comments.Text: 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?
Comments.UserDisplayName: Buffy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-01T16:06:29.557Z
Comments.Text: @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.
Comments.UserDisplayName: Victor Eijkhout
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-01T16:11:29.053Z
Comments.Text: Actually, I think he answers would be very different. Learning a first paradigm is much easier than changing paradigms.
Comments.UserDisplayName: Buffy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-01T16:14:20.057Z
Comments.Text: @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.
Comments.UserDisplayName: Victor Eijkhout
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-01T23:06:37.147Z
Comments.Text: The 'infection' assignment sounds interesting, have you seen the old Atari game Agent USA?
Comments.UserDisplayName: Scott Rowe
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-01T23:29:59.450Z
Comments.Text: @ScottRowe No, why?
Comments.UserDisplayName: Victor Eijkhout
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-02-01T23:39:10.677Z
Comments.Text: 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.
Comments.UserDisplayName: Scott Rowe
Tags: <curriculum-design><exercises><functional-programming>
Title: What sort of programming assignments do you give in an FP course?
ThreadText: # 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**: @username_2 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**: @username_0 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**: @username_0 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**: @username_0 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**: @username_0 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**: @username_0 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**: @username_0 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](http://www.paulgraham.com/mcilroy.html) 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](https://stackoverflow.com/questions/34888245/alan-kays-eval-apply-einstein-moment) 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](https://en.wikipedia.org/wiki/GNU_Compiler_Collection)??
  
  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](https://skeptics.stackexchange.com/questions/8742/did-einstein-say-if-you-cant-explain-it-simply-you-dont-understand-it-well-en))
  
  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](https://en.wikipedia.org/wiki/Algebraic_data_type). 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 (username_0) 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](https://en.wikipedia.org/wiki/Catalan_number#Properties), 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 `i`s 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](https://cseducators.stackexchange.com/a/7280/8837) (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**: @username_0 Check now Heres equivalent python code; shud run in python (3)  
  > **username_3**: @username_0 «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**: @username_0  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 @username_0. 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](https://cseducators.stackexchange.com/a/7268/8837) 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](https://github.com/rusimody/gofer) 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](https://cseducators.stackexchange.com/questions/1090/how-should-the-paradigm-shift-associated-with-functional-programming-be-approach/7262#7262)
  * (With nod to @username_2) **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**: @username_0: `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**: @username_4 (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  
  
  ---
  
  