Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-31T16:31:32.453Z
Answers.Text: 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
Answers.UserDisplayName: Rushi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-07T19:45:54.847Z
Answers.Text: I would love such an example.
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-07T23:29:29.513Z
Answers.Text: Perhaps it would have to be a second Answer? I once asked a Question about recasting Asp.Net as more OO.
Answers.UserDisplayName: Scott Rowe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-31T16:29:45.803Z
Answers.LastActivityDate: 2022-02-07T15:42:08.613Z
Answers.LastEditDate: 2022-02-07T15:42:08.613Z
Answers.UserDisplayName: Rushi
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-16T18:50:32.817Z
Answers.LastActivityDate: 2022-02-16T18:50:32.817Z
Answers.UserDisplayName: ctrl-alt-delor
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-25T20:53:14.093Z
Answers.LastActivityDate: 2017-06-25T21:03:56.520Z
Answers.LastEditDate: 2017-06-25T21:03:56.520Z
Answers.UserDisplayName: Buffy
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-14T19:56:35.127Z
Answers.Text: 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!
Answers.UserDisplayName: Scott Rowe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-23T06:07:15.670Z
Answers.Text: @Rusi Thanks! Really enjoyed this explanation.
Answers.UserDisplayName: Taimoor Zaeem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-23T08:34:24.757Z
Answers.Text: 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...
Answers.UserDisplayName: Rushi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-23T11:37:41.690Z
Answers.Text: 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!
Answers.UserDisplayName: Rushi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-23T13:15:14.047Z
Answers.Text: @Rusi Thank you so much for this.
Answers.UserDisplayName: Taimoor Zaeem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-14T17:05:35.853Z
Answers.LastActivityDate: 2022-02-14T18:04:24.893Z
Answers.LastEditDate: 2022-02-14T18:04:24.893Z
Answers.UserDisplayName: Rushi
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-10-23T09:06:53.870Z
Comments.Text: @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
Comments.UserDisplayName: Rushi
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-29T14:07:14.657Z
Comments.Text: 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”.
Comments.UserDisplayName: beroal
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-29T14:07:28.157Z
Comments.Text: 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.
Comments.UserDisplayName: beroal
Tags: <undergraduate><functional-programming>
Title: How should the paradigm shift associated with functional programming be approached?
ThreadText: # 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](https://cseducators.stackexchange.com/a/7262/8837), 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
  
  ```C
  #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
  
  ```C
  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
  
  ```C
  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**
  
  ```C
  if C
    return a;
  else
    return b;
  
  ```
  
  is equivalent to
  
  ```C
    return C ? a : b;
  
  ```
  
  ```C
  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`
  
  ```C
  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
  
  ```C
  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!]
  
  ```C
  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`
  
  ```C
  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??)
  
  ```C
  int ip2h(unsigned x)
  {
    return x == 0 ? false : (x==1 || even(x) && ip2h(x>>1));
  }
  
  ```
  
  ## i. Again `?:` to `&&`
  
  ```C
  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!!!
  
  ```C
  int ip2KaR(unsigned x)
  {
    return (x & (x-1)) == 0;
  }
  
  ```
  
  If you enjoy that look at the Henry Warren's book [Hacker's Delight](https://en.wikipedia.org/wiki/Hacker%27s_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 @username_7 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 @username_7! 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, …
  
  
  ---
  
  