<h1>Execution? Or Evaluation?</h1>
<p>One of the most pervasive metaphors that dominates programming is the idea of <em>execution</em>. Programs execute, as do functions, as do the tiniest of assignment statements.</p>
<p>One purpose of FP is to defeat — or at least deflate — this metaphor.</p>
<p>The alternate metaphor that obtains in FP is <em>evaluation</em>.  FP programs are basically calculators except that they are not over mere numbers but over arbitrarily complex data structures.</p>
<p>To do FP is to <strong>replace execution by evaluation.</strong></p>
<h1>Abstract? or Concrete?</h1>
<p>The related flip is that whereas OOP-ers like their data structures to be <em>abstract data types</em> FP-ers try to keep all their data as concrete as possible.</p>
<p>ie the Java embarrassment that <code>int</code> is not a proper class is flipped into a positive and pervades the language/paradigm. If we can keep all types concrete its a Good Thing!</p>
<h1>Lets see a session</h1>
<pre><code>? 1 + 3
4 : ℤ
</code></pre>
<p>Simple calc model like python; though notice the type</p>
<pre><code>? [1,2] ++ [3,4]
[1, 2, 3, 4] : ℒ.ℤ
</code></pre>
<p>So the calc model applies to list data structures as to nos uniformly</p>
<pre><code>? [(&quot;Eggs&quot;, 12), (&quot;Bread&quot;, 2)]
[(&quot;Eggs&quot;,12), (&quot;Bread&quot;,2)] : ℒ.⦇ℒ.Char, ℤ⦈
</code></pre>
<p>More complex; notice that strings are just lists of <code>Char</code>
No spurious excess ontologies here!</p>
<pre><code>? [(&quot;Eggs&quot;, 12), (&quot;Bread&quot;, 2)] ++ [(&quot;PeanutButter&quot;, 1)]
[(&quot;Eggs&quot;,12), (&quot;Bread&quot;,2), (&quot;PeanutButter&quot;,1)] : ℒ.⦇ℒ.Char, ℤ⦈
</code></pre>
<p>And these more sophisticated data structures are as easily handled as the simplest; So far looks just like python</p>
<pre><code>? [(&quot;Eggs&quot;, 12), (&quot;Bread&quot;, 2)] ++ [&quot;PeanutButter&quot;]
ERROR: Type error in application
*** expression     : [(&quot;Eggs&quot;,12),(&quot;Bread&quot;,2)] ++ [&quot;PeanutButter&quot;]
*** term           : [(&quot;Eggs&quot;,12),(&quot;Bread&quot;,2)]
*** type           : ℒ.⦇ℒ.Char, ℤ⦈]
*** does not match : ℒ.(ℒ.Char)
</code></pre>
<p>Whoops! Type error
Python etc will give the error but at a later inconvenient point</p>
<p>Now we move on</p>
<h1>Expression trees</h1>
<pre><code>ctype Expr where
  Plus, Mul : Expr → Expr → Expr
  Lf        : ℤ → Expr
</code></pre>
<p>Whats the <code>ctype</code>?? A <strong>concrete</strong> type.<br />
They (trees) can be constructed</p>
<ul>
<li>trivially as an <code>Lf</code> (leaf) wrapping an <code>ℤ</code> to give a trivial tree</li>
<li>Or take two trees <code>l</code> and <code>r</code> and make <code>Plus.l.r</code>; Likewise <code>Mul.l.r</code></li>
</ul>
<p>What does it mean that the type is <em>concrete</em>?</p>
<pre><code>? Plus.(Lf.2).(Lf.3)
Plus.(Lf.2).(Lf.3) : Expr
</code></pre>
<p>This is trivial looking but actually deep<br />
Just as <code>3:ℤ</code> SELF-EVALUATES to <code>3:ℤ</code> (the trivial case of evaluation)
<code>Plus.(Lf.2).(Lf.3) : Expr</code> self-evaluates to itself</p>
<p>Further just as <code>2+3</code> (non-trivially) evaluates to <code>5</code></p>
<p>Similarly for expression trees
If we want to say that the &quot;2+3&quot; tree is the l-subtree of the &quot;(2+3)*5&quot; tree
we could do</p>
<pre><code>t1 = Plus.(Lf.2).(Lf.3)
t2 = Mul.t1.(Lf.5)
? t2
Mul.(Plus.(Lf.2).(Lf.3)).(Lf.5) : Expr
</code></pre>
<p>Finally an expression evaluator</p>
<pre><code>eval.(Lf.x)     = x
eval.(Plus.l.r) = eval.l + eval.r
eval.(Mul.l.r)  = eval.l * eval.r
 
? eval.(Plus.(Lf.2).(Lf.3))
5 : ℤ
? eval.t2
25 : ℤ
</code></pre>
<p>In short a tree data structure in 3 lines — NO IO NO MEMORY MGMT<br />
And the exp-evaluator (or tree-interpreter) another 3 lines!</p>

CC BY-SA 4.0
2022-01-31T16:31:32.453Z
The above gives an FP view of FP
One could also make a C view of FP
ie start with a C program as a C programmer would write
Then gradually FP-ize it.
If this is deisred I'll add one such example
Rushi
CC BY-SA 4.0
2022-02-07T19:45:54.847Z
I would love such an example.
Ben I.
CC BY-SA 4.0
2022-02-07T23:29:29.513Z
Perhaps it would have to be a second Answer? I once asked a Question about recasting Asp.Net as more OO.
Scott Rowe
CC BY-SA 4.0
2022-01-31T16:29:45.803Z
2022-02-07T15:42:08.613Z
2022-02-07T15:42:08.613Z
Rushi
<p>Functional programming is mostly about unlearning bad habits. The best was it to not be taught them in the first place.</p>
<p>You don't need to teach the more advanced bits to beginners. However also don't teach mutation.</p>
<p>I teach python, but the examples that I give to the students have a functional style. I just avoid the bits of procedural, that should be tough much later. MUCH LATER after the student has learnt all of functional techniques.</p>
<p>In structure and interpretation of computer programs, we are introduced to mutation in hour 20. After lists, inheritance, lambdas, etc, …</p>

CC BY-SA 4.0
2022-02-16T18:50:32.817Z
2022-02-16T18:50:32.817Z
ctrl-alt-delor
<p>Any true paradigm shift requires <em>literally</em> re-wiring the brain. Thinking functionally is not the same as thinking procedurally (for example). The neural pathways of the brain need to be connected appropriately for the new paradigm to become natural. When you were a kid you were, if typical, used to walking and running. Then you probably got a bicycle (or a skateboard if you are young enough). You tried, you fell down, you tried again. Your brain got used to the subtle balancing required. Swimming - same deal. Differentiation - same deal. Haskell - same deal. </p>

<p>As an instructor, the above implies that you should provide guided practice at the beginning - a skateboard park for the mind. If your students solve a lot of simple problems (not syntactical, but logical) they will skin their knees on these but if they are <em>well chosen</em> will get the skills. In scheme, reversing a list with only <em>head</em> and <em>tail</em> is simple enough. Doing it in linear time takes a bit more skill, but the technique is both cool and satisfying. Writing the code wires the brain. And, like riding a bicycle, it is hard to un-learn it once you get it, since the brain is now different. </p>

<p>So, make it possible for the students to fall a lot, but to get up without getting discouraged. </p>

<p>To add a bit of specificity to this. Assuming you know the paradigm well yourself, what are its 100 most important techniques? Can you come up with a 10-30 minute exercise for each of them? Try to have each exercise focus on just one thing (mostly anyway). These are your Etudes. Can you come up with 10 exercises for each of the 100 techniques, even if they vary only slightly? </p>

<p>Acknowledgement: At SIGCSE 2004, Owen Astrachan (of Duke) convinced Microsoft Research, through Jane Prey, to give every attendee the book <em>The Art of Changing the Brain</em> by James E Zull. </p>

CC BY-SA 3.0
2017-06-25T20:53:14.093Z
2017-06-25T21:03:56.520Z
2017-06-25T21:03:56.520Z
Buffy
<p>In response to comments on the other <a href="https://cseducators.stackexchange.com/a/7262/8837">answer</a>, I'll take a C running example:<br />
To detect whether an unsigned number <code>x</code> is a power of 2.</p>
<ul>
<li>Using ideas from FP to move from one version to next</li>
<li>Entirely staying within C as coding language</li>
</ul>
<h2>The Base C version</h2>
<pre class="lang-C prettyprint-override"><code>#define even(x) (((x) &amp; 0x1) == 0)
int ip2(unsigned x)
{
  if (x==0) return false;
  while (even(x) &amp;&amp; x &gt; 1)
    x &gt;&gt;= 1;
  if (x == 1)
    return true;
  else
    return false;
}
</code></pre>
<h2>a. Recursive Version</h2>
<pre class="lang-C prettyprint-override"><code>int ip2a(unsigned x)
{
  if (x==0) return false;
  if (x==1) return true;
  if (even(x))
    return ip2a(x&gt;&gt;1);
  else
    return false;
}
</code></pre>
<h2>b. Eliding the zero check</h2>
<p>The zero case is odd and special; we'll come back to it later</p>
<pre class="lang-C prettyprint-override"><code>int ip2b(unsigned x)
{
  if (x==1) return true;
  if (even(x))
    return ip2b(x&gt;&gt;1);
  else
    return false;
}
</code></pre>
<h2>c. Transforming <code>if-else</code> to <code>?:</code></h2>
<p><strong>Identity</strong></p>
<pre class="lang-C prettyprint-override"><code>if C
  return a;
else
  return b;
</code></pre>
<p>is equivalent to</p>
<pre class="lang-C prettyprint-override"><code>  return C ? a : b;
</code></pre>
<pre class="lang-C prettyprint-override"><code>int ip2c(unsigned x)
{
  if (x==1) return true;
  return even(x) ? ip2c(x&gt;&gt;1) : false;
}

</code></pre>
<h2>d. Using identity connecting <code>?:</code> to <code>&amp;&amp;</code></h2>
<p><strong>Identity</strong><br />
For boolean <code>a</code>, <code>b</code>, <code>a ? b : false</code> $\equiv$ <code>a &amp;&amp; b</code></p>
<pre class="lang-C prettyprint-override"><code>int ip2d(unsigned x)
{
  if (x==1) return true;
  return even(x) &amp;&amp; ip2d(x&gt;&gt;1);
}
</code></pre>
<h2>e. Remove C 'laziness'</h2>
<p>Can we functionalize this further?<br />
Notice that I've done the C programmer's typical laziness of avoiding writing an <code>else</code> clause<br />
Reintroducing</p>
<pre class="lang-C prettyprint-override"><code>int ip2e(unsigned x)
{
  if (x==1)
    return true;
  else
    return even(x) &amp;&amp; ip2e(x&gt;&gt;1);
}
</code></pre>
<h2>f. Re-apply <code>if</code> to <code>?:</code> transformation</h2>
<p>This <strong>seemingly</strong> more complex as in nested version is again amenable to the transformation above. [There's a lesson here!]</p>
<pre class="lang-C prettyprint-override"><code>int ip2f(unsigned x)
{
   return x==1 ? true : even(x) &amp;&amp; ip2f(x&gt;&gt;1);
}
</code></pre>
<h2>g. Using identity connecting <code>?:</code> to <code>||</code></h2>
<p><strong>Identity</strong><br />
Analogous to the <code>?:</code> to <code>&amp;&amp;</code> we have for <code>||</code><br />
For boolean <code>a</code>, <code>b</code>, <code>a ? true: b</code> $\equiv$ <code>a || b</code></p>
<pre class="lang-C prettyprint-override"><code>int ip2g(unsigned x)
{
   return x==1 || even(x) &amp;&amp; ip2g(x&gt;&gt;1);
}
</code></pre>
<h2>Verbalization</h2>
<p>Notice how smoothly this verbalizes:
For <code>x</code> to be a power of 2</p>
<ul>
<li>Either <code>x</code> is 1 (trivial case)... Or...</li>
<li><code>x</code> is even and its half is also a power of 2</li>
</ul>
<h2>h. Stop??</h2>
<p>At this stage we could stop...<br />
But this is an infinite loop for <code>x==0</code>!!<br />
(We removed the zero check earlier remember??)</p>
<pre class="lang-C prettyprint-override"><code>int ip2h(unsigned x)
{
  return x == 0 ? false : (x==1 || even(x) &amp;&amp; ip2h(x&gt;&gt;1));
}
</code></pre>
<h2>i. Again <code>?:</code> to <code>&amp;&amp;</code></h2>
<pre class="lang-C prettyprint-override"><code>int ip2i(unsigned x)
{
  return x == 0 &amp;&amp; (x == 1 || even(x) &amp;&amp; ip2i(x&gt;&gt;1));
}
</code></pre>
<h1>So...???</h1>
<p>Q: So are you SERIOUSLY suggesting this way of writing <code>ip2</code>?!?</p>
<p>A: No this is not a serious suggestion of <code>ip2</code>.<br />
Nor is it a serious suggestion of recursion.
It is a serious suggestion of</p>
<ul>
<li>how to use algebraic identities to transform programs into other equivalent programs</li>
<li>And of giving the boolean type a more first class status. [O how I miss Pascal!]</li>
</ul>
<p>All of which is about the possibility that whatever the language one needs to use, functional thinking is applicable.</p>
<h1>¿Efficiency?</h1>
<p>Yeah efficiency:
This is classic KaR C
No recursion; no loop;<br />
Not just constant time; but just 3 operations!!!</p>
<pre class="lang-C prettyprint-override"><code>int ip2KaR(unsigned x)
{
  return (x &amp; (x-1)) == 0;
}

</code></pre>
<p>If you enjoy that look at the Henry Warren's book <a href="https://en.wikipedia.org/wiki/Hacker%27s_Delight" rel="nofollow noreferrer">Hacker's Delight</a><br />
Which is the above multiplied thousand-fold!!</p>
<p>But believe me: For the beginning student worrying about efficiency before basics of semantics is invariably a wrong priority!<br />
[My minority opinion of course!]</p>

CC BY-SA 4.0
2022-02-14T19:56:35.127Z
Interesting, nice to see things like Boolean operations substituting for the ? operator. I found a good use for the comma operator once, so I could invoke a macro in place of a function call. Thanks for going to the effort of creating the example!
Scott Rowe
CC BY-SA 4.0
2022-10-23T06:07:15.670Z
@Rusi Thanks! Really enjoyed this explanation.
Taimoor Zaeem
CC BY-SA 4.0
2022-10-23T08:34:24.757Z
Tnx @TaimoorZaeem for reminding me to this old discussion!  Our paper on teaching recursion FP style was just published in [IEEE-FIE](https://www.fie2022.org/detailed-program/). Methinks I should include it here...
Rushi
CC BY-SA 4.0
2022-10-23T11:37:41.690Z
Just noticed you're a student @TaimoorZaeem! You may find my other answers on functional prog useful.  Eg https://cseducators.stackexchange.com/a/7257/8837 ... Nearing 40 years now doing/teaching FP!
Rushi
CC BY-SA 4.0
2022-10-23T13:15:14.047Z
@Rusi Thank you so much for this.
Taimoor Zaeem
CC BY-SA 4.0
2022-02-14T17:05:35.853Z
2022-02-14T18:04:24.893Z
2022-02-14T18:04:24.893Z
Rushi
<p>As a student primarily experienced with imperative and object-oriented languages, my first few hours learning Haskell at university were a bit of a struggle. There's a real shift involved in terms of how you approach problem solving and concepts like pure functions, side effects, currying, higher order functions etc. were very new to me and took me a while to properly grasp and begin using.</p>

<p>I did eventually get the hang of it, and now happily write production code in Scala that uses a lot of these techniques. I think it can result in incredibly elegant code.</p>

<p>But I'm curious: is there is a way to make the initial struggle easier? I've seen some suggestions that students should <em>start with</em> a functional language - but I don't think it's reasonable to assume all of the students won't have prior knowledge of working in an imperative language.</p>

CC BY-SA 4.0
2022-10-23T09:06:53.870Z
@beroal your comment especially 2nd deserves a bounty! Both "paradigm" and "functional" are disservices. If "functional P" were *anything* to do with functions C would be the most functional lang out there -- and by order of billions ). The older term "applicative" is slightly more accurate signifying usage rather than definition
Rushi
CC BY-SA 3.0
2017-06-29T14:07:14.657Z
IMHO, the struggle exists because students start from an imperative PL. This order is incorrect from a theoretical viewpoint: imperative programming is a special case of functional programming, as you know from learning Haskell. This is the reason for the suggestion that “students should start with a functional language”.
beroal
CC BY-SA 3.0
2017-06-29T14:07:28.157Z
The paradigm of functional programming, as it is commonly understood, is a bunch of concepts. You mentioned some of them. For example, sum types belong there too. Every concept require its own approach. Considering them together as one monolithic thing is not useful. The “paradigm” concept is doing a disservice here.
beroal
<undergraduate><functional-programming>
How should the paradigm shift associated with functional programming be approached?
# How should the paradigm shift associated with functional programming be approached?

(Asked by: username_0 on 2017-06-25)

As a student primarily experienced with imperative and object-oriented languages, my first few hours learning Haskell at university were a bit of a struggle. There's a real shift involved in terms of how you approach problem solving and concepts like pure functions, side effects, currying, higher order functions etc. were very new to me and took me a while to properly grasp and begin using.

I did eventually get the hang of it, and now happily write production code in Scala that uses a lot of these techniques. I think it can result in incredibly elegant code.

But I'm curious: is there is a way to make the initial struggle easier? I've seen some suggestions that students should *start with* a functional language - but I don't think it's reasonable to assume all of the students won't have prior knowledge of working in an imperative language.

**Tags:** undergraduate, functional-programming

> **Comments:**
> **username_2**: IMHO, the struggle exists because students start from an imperative PL. This order is incorrect from a theoretical viewpoint: imperative programming is a special case of functional programming, as you know from learning Haskell. This is the reason for the suggestion that “students should start with a functional language”.  
> **username_2**: The paradigm of functional programming, as it is commonly understood, is a bunch of concepts. You mentioned some of them. For example, sum types belong there too. Every concept require its own approach. Considering them together as one monolithic thing is not useful. The “paradigm” concept is doing a disservice here.  
> **username_1**: @username_2 your comment especially 2nd deserves a bounty! Both "paradigm" and "functional" are disservices. If "functional P" were *anything* to do with functions C would be the most functional lang out there -- and by order of billions ). The older term "applicative" is slightly more accurate signifying usage rather than definition  

---

## 4 answers

### Answer by username_6 on 2017-06-25. Score: 8 | Accepted answer

Any true paradigm shift requires *literally* re-wiring the brain. Thinking functionally is not the same as thinking procedurally (for example). The neural pathways of the brain need to be connected appropriately for the new paradigm to become natural. When you were a kid you were, if typical, used to walking and running. Then you probably got a bicycle (or a skateboard if you are young enough). You tried, you fell down, you tried again. Your brain got used to the subtle balancing required. Swimming - same deal. Differentiation - same deal. Haskell - same deal.

As an instructor, the above implies that you should provide guided practice at the beginning - a skateboard park for the mind. If your students solve a lot of simple problems (not syntactical, but logical) they will skin their knees on these but if they are *well chosen* will get the skills. In scheme, reversing a list with only *head* and *tail* is simple enough. Doing it in linear time takes a bit more skill, but the technique is both cool and satisfying. Writing the code wires the brain. And, like riding a bicycle, it is hard to un-learn it once you get it, since the brain is now different.

So, make it possible for the students to fall a lot, but to get up without getting discouraged.

To add a bit of specificity to this. Assuming you know the paradigm well yourself, what are its 100 most important techniques? Can you come up with a 10-30 minute exercise for each of them? Try to have each exercise focus on just one thing (mostly anyway). These are your Etudes. Can you come up with 10 exercises for each of the 100 techniques, even if they vary only slightly?

Acknowledgement: At SIGCSE 2004, Owen Astrachan (of Duke) convinced Microsoft Research, through Jane Prey, to give every attendee the book *The Art of Changing the Brain* by James E Zull.


---

### Answer by username_1 on 2022-02-14. Score: 2

In response to comments on the other answer, I'll take a C running example:
To detect whether an unsigned number x is a power of 2.

Using ideas from FP to move from one version to next
Entirely staying within C as coding language

The Base C version
#define even(x) (((x) & 0x1) == 0)
int ip2(unsigned x)
{
  if (x==0) return false;
  while (even(x) && x > 1)
    x >>= 1;
  if (x == 1)
    return true;
  else
    return false;
}

a. Recursive Version
int ip2a(unsigned x)
{
  if (x==0) return false;
  if (x==1) return true;
  if (even(x))
    return ip2a(x>>1);
  else
    return false;
}

b. Eliding the zero check
The zero case is odd and special; we'll come back to it later
int ip2b(unsigned x)
{
  if (x==1) return true;
  if (even(x))
    return ip2b(x>>1);
  else
    return false;
}

c. Transforming if-else to ?:
Identity
if C
  return a;
else
  return b;

is equivalent to
  return C ? a : b;

int ip2c(unsigned x)
{
  if (x==1) return true;
  return even(x) ? ip2c(x>>1) : false;
}


d. Using identity connecting ?: to &&
Identity
For boolean a, b, a ? b : false $\equiv$ a && b
int ip2d(unsigned x)
{
  if (x==1) return true;
  return even(x) && ip2d(x>>1);
}

e. Remove C 'laziness'
Can we functionalize this further?
Notice that I've done the C programmer's typical laziness of avoiding writing an else clause
Reintroducing
int ip2e(unsigned x)
{
  if (x==1)
    return true;
  else
    return even(x) && ip2e(x>>1);
}

f. Re-apply if to ?: transformation
This seemingly more complex as in nested version is again amenable to the transformation above. [There's a lesson here!]
int ip2f(unsigned x)
{
   return x==1 ? true : even(x) && ip2f(x>>1);
}

g. Using identity connecting ?: to ||
Identity
Analogous to the ?: to && we have for ||
For boolean a, b, a ? true: b $\equiv$ a || b
int ip2g(unsigned x)
{
   return x==1 || even(x) && ip2g(x>>1);
}

Verbalization
Notice how smoothly this verbalizes:
For x to be a power of 2

Either x is 1 (trivial case)... Or...
x is even and its half is also a power of 2

h. Stop??
At this stage we could stop...
But this is an infinite loop for x==0!!
(We removed the zero check earlier remember??)
int ip2h(unsigned x)
{
  return x == 0 ? false : (x==1 || even(x) && ip2h(x>>1));
}

i. Again ?: to &&
int ip2i(unsigned x)
{
  return x == 0 && (x == 1 || even(x) && ip2i(x>>1));
}

So...???
Q: So are you SERIOUSLY suggesting this way of writing ip2?!?
A: No this is not a serious suggestion of ip2.
Nor is it a serious suggestion of recursion.
It is a serious suggestion of

how to use algebraic identities to transform programs into other equivalent programs
And of giving the boolean type a more first class status. [O how I miss Pascal!]

All of which is about the possibility that whatever the language one needs to use, functional thinking is applicable.
¿Efficiency?
Yeah efficiency:
This is classic KaR C
No recursion; no loop;
Not just constant time; but just 3 operations!!!
int ip2KaR(unsigned x)
{
  return (x & (x-1)) == 0;
}


If you enjoy that look at the Henry Warren's book Hacker's Delight
Which is the above multiplied thousand-fold!!
But believe me: For the beginning student worrying about efficiency before basics of semantics is invariably a wrong priority!
[My minority opinion of course!]

> **Comments:**
> **username_4**: Interesting, nice to see things like Boolean operations substituting for the ? operator. I found a good use for the comma operator once, so I could invoke a macro in place of a function call. Thanks for going to the effort of creating the example!  
> **username_7**: @Rusi Thanks! Really enjoyed this explanation.  
> **username_1**: Tnx @TaimoorZaeem for reminding me to this old discussion!  Our paper on teaching recursion FP style was just published in [IEEE-FIE](https://www.fie2022.org/detailed-program/). Methinks I should include it here...  
> **username_1**: Just noticed you're a student @TaimoorZaeem! You may find my other answers on functional prog useful.  Eg https://cseducators.stackexchange.com/a/7257/8837 ... Nearing 40 years now doing/teaching FP!  
> **username_7**: @Rusi Thank you so much for this.  

---

### Answer by username_1 on 2022-01-31. Score: 1

Execution? Or Evaluation?
One of the most pervasive metaphors that dominates programming is the idea of execution. Programs execute, as do functions, as do the tiniest of assignment statements.
One purpose of FP is to defeat — or at least deflate — this metaphor.
The alternate metaphor that obtains in FP is evaluation.  FP programs are basically calculators except that they are not over mere numbers but over arbitrarily complex data structures.
To do FP is to replace execution by evaluation.
Abstract? or Concrete?
The related flip is that whereas OOP-ers like their data structures to be abstract data types FP-ers try to keep all their data as concrete as possible.
ie the Java embarrassment that int is not a proper class is flipped into a positive and pervades the language/paradigm. If we can keep all types concrete its a Good Thing!
Lets see a session
? 1 + 3
4 : ℤ

Simple calc model like python; though notice the type
? [1,2] ++ [3,4]
[1, 2, 3, 4] : ℒ.ℤ

So the calc model applies to list data structures as to nos uniformly
? [("Eggs", 12), ("Bread", 2)]
[("Eggs",12), ("Bread",2)] : ℒ.⦇ℒ.Char, ℤ⦈

More complex; notice that strings are just lists of Char
No spurious excess ontologies here!
? [("Eggs", 12), ("Bread", 2)] ++ [("PeanutButter", 1)]
[("Eggs",12), ("Bread",2), ("PeanutButter",1)] : ℒ.⦇ℒ.Char, ℤ⦈

And these more sophisticated data structures are as easily handled as the simplest; So far looks just like python
? [("Eggs", 12), ("Bread", 2)] ++ ["PeanutButter"]
ERROR: Type error in application
*** expression     : [("Eggs",12),("Bread",2)] ++ ["PeanutButter"]
*** term           : [("Eggs",12),("Bread",2)]
*** type           : ℒ.⦇ℒ.Char, ℤ⦈]
*** does not match : ℒ.(ℒ.Char)

Whoops! Type error
Python etc will give the error but at a later inconvenient point
Now we move on
Expression trees
ctype Expr where
  Plus, Mul : Expr → Expr → Expr
  Lf        : ℤ → Expr

Whats the ctype?? A concrete type.
They (trees) can be constructed

trivially as an Lf (leaf) wrapping an ℤ to give a trivial tree
Or take two trees l and r and make Plus.l.r; Likewise Mul.l.r

What does it mean that the type is concrete?
? Plus.(Lf.2).(Lf.3)
Plus.(Lf.2).(Lf.3) : Expr

This is trivial looking but actually deep
Just as 3:ℤ SELF-EVALUATES to 3:ℤ (the trivial case of evaluation)
Plus.(Lf.2).(Lf.3) : Expr self-evaluates to itself
Further just as 2+3 (non-trivially) evaluates to 5
Similarly for expression trees
If we want to say that the "2+3" tree is the l-subtree of the "(2+3)*5" tree
we could do
t1 = Plus.(Lf.2).(Lf.3)
t2 = Mul.t1.(Lf.5)
? t2
Mul.(Plus.(Lf.2).(Lf.3)).(Lf.5) : Expr

Finally an expression evaluator
eval.(Lf.x)     = x
eval.(Plus.l.r) = eval.l + eval.r
eval.(Mul.l.r)  = eval.l * eval.r
 
? eval.(Plus.(Lf.2).(Lf.3))
5 : ℤ
? eval.t2
25 : ℤ

In short a tree data structure in 3 lines — NO IO NO MEMORY MGMT
And the exp-evaluator (or tree-interpreter) another 3 lines!

> **Comments:**
> **username_1**: The above gives an FP view of FP One could also make a C view of FP ie start with a C program as a C programmer would write Then gradually FP-ize it. If this is deisred I'll add one such example  
> **username_3**: I would love such an example.  
> **username_4**: Perhaps it would have to be a second Answer? I once asked a Question about recasting Asp.Net as more OO.  

---

### Answer by username_5 on 2022-02-16. Score: 0

Functional programming is mostly about unlearning bad habits. The best was it to not be taught them in the first place.

You don't need to teach the more advanced bits to beginners. However also don't teach mutation.

I teach python, but the examples that I give to the students have a functional style. I just avoid the bits of procedural, that should be tough much later. MUCH LATER after the student has learnt all of functional techniques.

In structure and interpretation of computer programs, we are introduced to mutation in hour 20. After lists, inheritance, lambdas, etc, …


---

