<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Mia Tang on Medium]]></title>
        <description><![CDATA[Stories by Mia Tang on Medium]]></description>
        <link>https://medium.com/@mia-tang?source=rss-8bf524e9e5f8------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*hzvSuKzdHBLWCuTA28oHEg.jpeg</url>
            <title>Stories by Mia Tang on Medium</title>
            <link>https://medium.com/@mia-tang?source=rss-8bf524e9e5f8------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 09:27:26 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@mia-tang/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Interactive & Zero-Knowledge Proof]]></title>
            <link>https://mia-tang.medium.com/interactive-proof-ed5050e8e78d?source=rss-8bf524e9e5f8------2</link>
            <guid isPermaLink="false">https://medium.com/p/ed5050e8e78d</guid>
            <dc:creator><![CDATA[Mia Tang]]></dc:creator>
            <pubDate>Sat, 05 Dec 2020 00:35:24 GMT</pubDate>
            <atom:updated>2020-12-12T04:59:38.147Z</atom:updated>
            <content:encoded><![CDATA[<h4>A Creative Guide Into the Theoretical CS’s Complexity Class I.P.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*uv2XyxqvEf0Pk8mEwxbe6Q.png" /></figure><h3>🌠 Motivation</h3><p>In the world of mathematical logic, the most rigorous and formal proof is a deduction where each line is either an assumption, an instance of an axiom scheme, or a result of applying some inference rules on previous lines depending on the given logic language.</p><p>But, normally (&amp; luckily ✨), writing a proof does not require such formality, and the word <strong><em>proof </em></strong>in our daily life requires some form of evidence being passed on from the person who wishes to prove something (the<strong> prover</strong>) to the person who verifies the evidence (the <strong>verifier</strong>). The verifier can ask for <strong>additional evidence</strong> if not convinced.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/683/1*dClP6ISOsKRTGnKnNgtdFg.png" /><figcaption>A ball tossing game is an interaction.</figcaption></figure><blockquote>In short, a proof can be defined as an <strong><em>interaction </em></strong>between two sides.</blockquote><h3>📕 Basic Definitions</h3><p>Before diving into how Interactive Proof works with a concrete example and why it is so useful, we first explore the basic machinery needed for learning this topic rigorously.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iyTLaGPkpt0yidtuw7K0xA.png" /></figure><p>First, we have Mr.Prover and Mr.Verifier, with the verifier asking questions and the prover responding, and at the end, the verifier can either accept or reject. However, there’s something special about our Mr.Verifier.</p><h4>🙅 Mr. Verifier is NOT perfect! We allow him to be wrong.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/641/1*EZvxlboT5dkUR2XgTfeVaA.png" /></figure><p>To put it formally, our verifier is probabilistic, and it <strong><em>can </em></strong>be wrong with a small probability. Furthermore, we can regard our verifier and prover as functions (<em>just as everything else in life</em>), and since our verifier is probabilistic, our final output (whether the verifier accepts or not) is a random variable.</p><p>To further simply the situation, essentially Mr. Prover comes up with a proof (the answers to Mr. Verifier’s questions), and Mr. Verifier has a final say in if he believed the prover or not, which can be a ❎ false conclusion.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/618/1*1Y8xgZg0VpAdm4fz-m2-vg.png" /><figcaption>Now we are no longer tossing balls, we are tossing proofs and questions!</figcaption></figure><p>Now we finally introduce the formal definition of the complexity class<strong> IP</strong>:</p><p>📗 <strong><em>Defintion:</em></strong></p><p>A language <em>L</em> is in <strong>IP</strong> if there is a Turing Machine<em> V </em>such that on inputs <em>x</em>,<em> V</em> runs in polynomial time <em>p</em> with respect to the length of <em>x</em>, i.e. <em>|x|</em>, such that</p><ul><li>(Completeness) <em>x</em> ∈ <em>L ⇒ ∃ P </em>Pr[outᵥ⟨ <em>P, V</em> ⟩(<em>x</em>)=1] =1.</li><li>(Soundness) <em>x</em> ∉ <em>L</em> ⇒ ∀ <em>P</em> Pr[outᵥ ⟨ <em>P, V</em> ⟩<em>(x)</em>=1] ≤ <em>1/2</em></li></ul><p>Note that here we chose the arbitrary Turing Machine’s name to be <em>V</em>, which is intentional since it is our <em>V</em>erifier.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GHLyoiNPjwzZ92B1hKBmhw.png" /></figure><p>🔈 To say it in plain English, a language is in the class <strong>IP</strong> if:</p><ul><li>If the input <em>x</em> we are looking at is in <em>L</em>, then there exists some polynomial length proof such that the Verifier will confirm <em>x</em>’s membership.</li><li>If the input <em>x </em>we are looking at is <strong><em>not</em></strong> in <em>L</em>, then for any possible proof out there, the Verifier rejects<em> x</em> with a probability of at least <em>1/2</em>.</li></ul><p>We can further increase the correctness probability by using the boosting technique of independent repeated trials and returning the majority answer.</p><p>📩 <strong>Long story short:</strong></p><ul><li>Proof can be an interaction between a Prover and a Verifier.</li><li>If we allow the Verifier to be probabilistic, we have a high chance of solving <strong>NP </strong>hard problems correctly.</li></ul><h3>🏃 I.P. In Action: Graph Isomorphism</h3><p>Now we step through a classic example that demonstrates the power of I.P..</p><p>First, we introduce the definition of having graphs being <strong><em>isomorphic</em></strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4GoyTHBGiSrfTeIzS1_7Ww.png" /><figcaption>Isomorphic Graphs</figcaption></figure><p>We say that two graphs <em>(G₁, G₂) </em>are isomorphic if there is a permutation π of the vertices <em>V </em>such that <em>π(G₁)=G₂.</em> To put it it more plainly, if we can rename/recolor the vertices and get the other graph, then they are isomorphic. If <em>G₁, G₂</em> are isomorphic, we write that<em> G₁ ≡ G₂.</em></p><p>The problem of determining whether if 2 graphs are isomorphic is in the complexity class <strong>NP </strong>since a valid polynomial length certificate would simply be the description of the permutation/renaming/recoloring π.</p><p>The protocol we use in the I.P. strategy for Graph Isomorphism:</p><ul><li><strong><em>Verifier</em></strong>: Pick<em> i </em>∈ {1, 2} uniformly at random. Then randomly permute the vertices of the chosen<em> Gᵢ</em> to get the nw graph <em>H</em>. Send <em>H</em> to <em>P.</em></li><li><strong><em>Prover:</em></strong> Identify which of <em>G₁, G₂</em> was used to produce <em>H</em>. Let that graph be <em>Gⱼ</em>, and send the vertex <em>j</em> to the Verifier.</li><li><strong><em>Verifier:</em></strong> accept if <em>i = j</em>; reject otherwise.</li></ul><p>🌱 <strong>Correctness Proof:</strong></p><p>Now we show that this is a valid Interactive Proof protocol as defined above. First, for Completeness, if <em>G₁≢ G₂</em>, then there must be a prover such that Pr[<em>V</em> accepts] = 1 since if the graphs are non-isomorphic, a powerful prover can recognize which one of the two is isomorphic to <em>H</em>. Second, for Soundness, if <em>G₁ ≡ G₂</em>, then the prover can only guess since a random permutation of <em>G₁</em> will be the same as the random permutation of <em>G₂</em>. Therefore for all prover out there, Pr[<em>V</em> accepts] ≤ 1/2.</p><h3>🔖 Zero Knowledge Proofs</h3><p>A natural next step in studying Interactive Proof related topics would be the Zero-Knowledge Proof. The intuition is that an interactive proof is zero-knowledge if after reading the proof sent by the Prover, our Verifier cannot efficiently perform computational tasks that she could not efficiently perform before. Zero-knowledge is a property that could be desirable for a prover that suspects a malicious verifier.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/1*6nkFsA51f-XwLTRkK18ZOQ.png" /></figure><h4>The prover wants the convince the verifier that he indeed has the correct answer without revealing any part of his answer.</h4><p>📗 <strong><em>Defintion:</em></strong></p><p>Given an interactive proof system ⟨ <em>P, V</em> ⟩ for a language <em>L</em> and an input <em>x</em>, we define the view of <em>V </em>on <em>x</em> to be all messages sent from <em>P</em> to <em>V</em> as well as all the random bits used by <em>V</em> during the protocol. We write the <em>view </em>on <em>x</em> as</p><blockquote><em>Viewᵥ [</em>P(x) ↔ V(x)<em>]</em></blockquote><p>An interactive proof system ⟨ <em>P, V</em> ⟩ for a language L is zero-knowledge if for any poly-time Turing Machine Verifier V there exists an expected probabilistic poly-time Turing Machine S such that,</p><blockquote>∀ x ∈ L, z ∈ <em>{0, 1}*</em>, <em>Viewᵥ [</em>P(x) ↔ V(x, z)<em>] =</em> S(x, z)</blockquote><p>As usual, our Prover<em> P</em> is a randomized TM and has unlimited computation power. The intuition here is that an interactive proof system is zero-knowledge if for any verifier<em> V</em> we have, we can find an efficient simulator <em>S </em>that produces a transcript of the conversation that would have taken place between<em> P</em> and<em> V</em> on any given input <em>x</em>. Therefore, even if <em>V</em> had the conversation with <em>P</em>, <em>V </em>will not be able to compute something she could not have computed before the conversation.</p><p>The string <em>z</em> here represents “prior knowledge”. It means that <em>V </em>cannot use any prior knowledge to mine information out of its conversation with <em>P</em> since we give the same prior knowledge to our simulator <em>S</em>. <strong><em>Transparency is nice!</em></strong> 🎐</p><p>Now we give a zero-knowledge proof system for the same question we explored above with ordinary interactive proof, graph isomorphism.</p><p>We take in 2 graphs (<em>G₀, G₁</em>):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7OQJ5HgLg1c8KPseImuKeg.png" /></figure><p>🌱 <strong>Correctness Proof:</strong> For Soundness, there is at most 1/2 chance that we get b=b’, and that’s the only case where if <em>G₁ </em>and <em>G₂</em> are not isomorphic but we would still have the equivalence to hold on the last line. For completeness, if <em>G₁ ≡ G₂</em>, then the last line will always hold. Therefore the protocol shown above is a valid I.P. system.</p><p>Now we show that it is indeed zero-knowledge. We first assume that all the random picking are indeed honest. By definition, we want the following claim to hold ∀ x ∈ L, z ∈ {0, 1}*, Viewᵥ [<em>P(x) ↔ V(x, z)</em>] = <em>S(x, z)</em>. We will prove this by defining a simulator <em>S</em> for an arbitrary verifier <em>V</em>.</p><p>We define <em>S(G₀, G₁, z) </em>as follows,</p><ul><li>Randomly choose a permutation σ and <em>b</em> ∈ {0, 1}.</li><li>Set <em>H = σ(G_b) </em>and<em> b’ = h*(G₀, G₁, z, H).</em></li><li>If <em>b’=b</em>, output <em>(b’, H, σ)</em>, otherwise restart with a new σ, <em>b</em>.</li></ul><p>Now we show that <em>S</em> is indeed a valid simulator by showing if <em>G₀ ≡ G₁</em>, then <strong>(a)</strong> S runs in poly-time and <strong>(b)</strong> Viewᵥ [<em>P(x) ↔ V(x, z)</em>] = <em>S(x, z).</em></p><p>For<strong> (a)</strong>, if we have <em>G₀ ≡ G₁</em>, then we have σ is random, therefore<em> b’ </em>and<em> b</em> are chosen independently thus having probability of 1/2 to be equal. Thus <em>S</em> must run only twice before halting. For (b), the fact that Prob[<em>b=b’</em>]=1/2 guarantees that the distribution of <em>S</em> is indeed the same as Viewᵥ.</p><h3>📚Conclusion</h3><p>There are immense power to combing interactivity and randomness with certificates for NP problems, and the fact that we can boost up correctness possibility through repeated trials gives us greater hope in returning the correct answer. Furthermore, the fact that we can convey that we have a valid result without revealing any piece of it is quite fascinating. ✨</p><h3>📖 References</h3><ul><li>[interactive proof] <a href="https://www.cs.princeton.edu/courses/archive/spring06/cos522/ip.pdf">https://www.cs.princeton.edu/courses/archive/spring06/cos522/ip.pdf</a></li><li>[interactive proof] <a href="https://www.anilada.com/courses/15251f18/www/slides/lec26slides.pdf">https://www.anilada.com/courses/15251f18/www/slides/lec26slides.pdf</a></li><li>[zero-knowledge proof] <a href="https://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture18.pdf">https://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture18.pdf</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ed5050e8e78d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Note On Higher Order Functions]]></title>
            <link>https://mia-tang.medium.com/a-note-on-higher-order-functions-191dc1a48ed4?source=rss-8bf524e9e5f8------2</link>
            <guid isPermaLink="false">https://medium.com/p/191dc1a48ed4</guid>
            <dc:creator><![CDATA[Mia Tang]]></dc:creator>
            <pubDate>Mon, 09 Mar 2020 21:18:01 GMT</pubDate>
            <atom:updated>2020-03-18T01:32:39.665Z</atom:updated>
            <content:encoded><![CDATA[<h4>map / filter / foldl / foldr</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lR9DO03wY5B5F0uktcF49Q.jpeg" /></figure><h3>👋 😸 🌻 ☁️ 💖 Hey!</h3><p>This is a short article on the <strong>Higher Order Functions </strong>we’ve covered in the last few weeks. Ideas are visualized through illustrations &amp; animations. Hope you enjoy and gain more clarity regarding the concepts.</p><h4>The following HOFs are covered 📔</h4><ul><li>map</li><li>filter</li><li>foldl</li><li>foldr</li></ul><p>Note 🗒: For simplicity we take for example List.map as map. You can also just write map, filter, ... on the test for <strong><em>~SPEED 😎~</em></strong>. But when you are writing actual code, you need List.filter .</p><h3>So, what are H😮Fs?</h3><p>Higher Order Functions are <strong>functions that accepts another function as an argument</strong>, treating <strong>functions as first-class citizens 💂.</strong></p><p>Before understanding how HOFs work, it is key to understand <strong>currying.</strong></p><h3>Curry is my fav 🍛</h3><p>Let’s consider a function with <strong><em>multiple</em></strong> arguments.</p><p>To demonstrate the reason why a curried function is <strong><em>better</em></strong>, introduce</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*l1GKseRF-sbTc-UOB2L9vw.jpeg" /><figcaption>Mr.Curry &amp; Mr.Uncurry</figcaption></figure><p>Mr. Uncurry and Mr. Curry here represents an argument in a uncurried function and an argument in a curried function.</p><h4>The difference between a uncurried and curried function is:</h4><blockquote>When we want to pass in multiple arguments into an uncurried function, we package them in a tuple.</blockquote><blockquote>With curried functions, we pass in one argument, and <strong>the function application evaluates to another function</strong> that takes in the remaining arguments.</blockquote><p>So what that means is when Mr. Uncurry wants to have a dinner with his friends (the rest of the arguments we need),</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_uP1G8vo8_GJxon7nnuEXg.png" /><figcaption>Mr. Uncurry has a dinner date with his friends 🍲</figcaption></figure><p>Mr. Uncurry cannot just go in the restaurant! 😩 He needs <strong>ALL</strong> of his friends to be there with him <strong>at the same time</strong>.</p><pre>(* pseudo alert *)</pre><pre>fun showUncurry (MrUncurry, x, y, z) = * some random code * </pre><p>Here we have x, y, z as MrUncurry’s friends (i.e. the remaining arguments), and <strong>we cannot call the function</strong> showUncurry unless we have the tuple containing MrUncurry, x, y, and z!</p><p>On the other hand, Mr. Curry <em>does not need to wait for nobody</em> 🙉.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kELEYkiFn_0MzwxHMYV4bQ.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/714/1*_OsyjOoZsZfBVrQ8C38xlg.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*I6JBUYOTNU0-iOSuxmOd_g.jpeg" /><figcaption>Mr.Curry having his meal without waiting for his friends!</figcaption></figure><pre>(* pseudo alert *)</pre><pre>fun showCurry MrCurry x y z = * some random code *</pre><p>Here we also have x, y, z as MrCurry’s friends, but we can call showCurry with MrUncurry as its only argument, then it will evaluate to a different function that waits for x, y, and z.</p><blockquote>*Some more notes on curry and curried types can be found in the midterm 1 review notes (<a href="https://medium.com/@xinrant/functional-programming-manual-v-1-510ae8671b88">link</a>)</blockquote><h4>Now that we see the advantage of currying a function,</h4><p>we can use that when developing our common list HOFs! 😻</p><h3>Map</h3><pre>(* map : ( ’a -&gt; ’b) -&gt; ’a list -&gt; ’b list *)</pre><pre>fun map _ [] = [] <br>  | map f ( x :: xs ) = f x :: map f xs</pre><p>We start with the rather straight-forward map function that takes in a function from &#39;a to &#39;b , and an &#39;a list , then returns a &#39;b list .</p><h4>Now, imagine</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-WWZG5vKcDCQ4SbOLCaQvw.png" /><figcaption>This is our list `L`</figcaption></figure><p>we have a list L of unhappy men in suits, i.e.</p><pre>datatype unhappysuit = * someway to construct it *<br>datatype happysuit = * someway to construct it *</pre><pre>L : unhappysuit list </pre><p><strong>Our goal</strong> is to convert the list of unhappysuit to a list of happysuit , and luckily, we know the<strong><em> magic</em></strong> 🔮 that makes a unhappysuit into a happysuit .</p><h4>We give him a cake! 🍰🍰🍰 ✨</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lWQKETwgrX3jLGAkSqZTHA.png" /></figure><pre>cake : unhappysuit -&gt; happysuit</pre><p>So, how do we change the list of unhappysuit into a list of happysuit ?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_90BkU8Ym6H3FeErOLplRA.png" /><figcaption>~our goal~</figcaption></figure><h3>We use the map function! 🗺 💪</h3><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F9G6HLwaSsBw%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D9G6HLwaSsBw&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F9G6HLwaSsBw%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/7c527dcf982face88df140d923b1e767/href">https://medium.com/media/7c527dcf982face88df140d923b1e767/href</a></iframe><p>In a sense, map and the other HOFs lets you apply a function element-wise over a list.</p><h3>filter</h3><pre>(* filter : ( ’a -&gt; bool ) -&gt; ’a list -&gt; ’a list *) </pre><pre>fun filter _ [] = [] <br>  | filter p ( x :: xs ) = if <br>                               p x <br>                           then <br>                               x :: filter p xs <br>                           else <br>                               filter p xs</pre><pre>(* formatted weirdly because Medium code block does not have syntax highlight. Hope it reads more clearly? :&#39;) *)</pre><p>Similarly, filter goes through the list, but this time, we work with a predicate function of type &#39;a -&gt; bool .</p><p>Suppose we have happysuits with different colored hats, and we <strong><em>ONLY </em></strong>want the ones with the blue hats, thus we want to <strong><em>filter out </em></strong>the ones in the list that are <strong><em>not</em></strong> wearing blue hats.</p><blockquote>It’s very easy to forget if we are keeping the ones that the predicate function returns true or false. Whenever you are confused, check the implementation.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QnadMh03WJ8MawjikEL2rQ.png" /><figcaption>What we have originally</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lMoMZNxvj_t7dF4-t__YDg.png" /><figcaption>What we want!</figcaption></figure><p>The filter function is made for this kind of operations. We simply need to write a predicate function that checks if the hat is blue.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F2_1d6yeX-LA%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D2_1d6yeX-LA&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F2_1d6yeX-LA%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/44ea8bb9f71eacf071e476db9ded8f4b/href">https://medium.com/media/44ea8bb9f71eacf071e476db9ded8f4b/href</a></iframe><h4>🔑 A Key Observation</h4><ul><li>map and filter preserve the ordering of the input list</li></ul><blockquote>Before continuing make sure you have understood the content above, which is supposedly much easier to grasp! 👐</blockquote><h4>😆❗️ Now we are getting to the interesting part ❗ 😆</h4><h3>folds 📁</h3><blockquote>They are extremely similar except for the order / direction they iterate over the input list, therefore we will talk about them at the same time.</blockquote><pre>(* foldl : ( ’a * ’b -&gt; ’b) -&gt; ’b -&gt; ’a list -&gt; ’b *) </pre><pre>fun foldl _ z [] = z <br>  | foldl g z ( x :: xs ) = foldl g ( g (x , z ) ) xs</pre><pre>(* foldr : ( ’a * ’b -&gt; ’b) -&gt; ’b -&gt; ’a list -&gt; ’b *)</pre><pre>fun foldr _ z [] = z <br>  | foldr g z ( x :: xs ) = g (x , foldr g z xs )</pre><p>In total, we are taking in 3 arguments: a combining function of type &#39;a * &#39;b -&gt; &#39;b , a base value of type &#39;b , and our input list of type &#39;a list .</p><p>We are going to try to understand foldl, foldr with an abstract example without code, but to guide you through the thinking process step by step.</p><h4>A Bunny Wants Her Fruits! 🐰 🥝</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*R5kKUBmjRKJ6t2ZHaOUGPg.png" /></figure><p>Miss.Bunny 🐰 here wants to have the 🍓, 🍏, 🍌, 🍇 in her basket <strong>in the given order</strong>, and right now, the fruits are in the list L .</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CLgfhFB1yrfotB9wTDU-5Q.png" /><figcaption>L = [ 🍓, 🍏, 🍌, 🍇]</figcaption></figure><h4><strong>First</strong>,</h4><p>we know no matter which fold function we use, our <strong>base value</strong> will be an empty basket to contain the fruits, i.e. the empty basket is <strong><em>literally the accumulator</em></strong><em>.</em><strong><em> </em></strong>(The empty basket would correspond to an empty list in the SML world)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZT6isbC9mpFZn3no0X-KMg.png" /></figure><h4><strong>Second</strong>,</h4><p>we know no matter which fold function we use, our <strong>combining function</strong> needs to do the action of putting a single fruit into the basket.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*E3iSv10LIcZfUF8nJI1DWQ.png" /></figure><p>So, in each step, we keep track of the basket, and the current fruit we are at in the list, and we update the basket by putting in a new fruit, hence why the combining function takes in 2 arguments.</p><h4>We can imagine 💭 👀 something like this:</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QC4vaTafvYHis7jSlPCzrg.png" /></figure><p>Since folds take in the function of type (&#39;a * &#39;b) -&gt; &#39;b , when we iterate over the given &#39;a list , which is the fruits list, we also hold on to our &#39;b , which is our fruit basket.</p><h4>⭐️ → Always keep in mind that whenever you have access to any certain element in the list, you ALSO have access to an accumulator that you have been carrying around the whole time.</h4><h3>⏬ foldl in action 🏊 ⏬</h3><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2Fc6sh09WDzvI%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3Dc6sh09WDzvI&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2Fc6sh09WDzvI%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/3616bf567402fd0251fe6504e9bfce88/href">https://medium.com/media/3616bf567402fd0251fe6504e9bfce88/href</a></iframe><h3>🚀 Takeaway #1</h3><h4>🙅 OH NO, we ended up with the wrong order! ❎</h4><p>As we used foldl to put the fruits in the basket, notice that we start from the left of the list (i.e. the l from foldl ), and because each time we put our current fruit into the basket starting from the very bottom of the basket, we ended up with the wrong order!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aS_d-HaAMO78f0yJ9wWqTA.png" /></figure><p>I find that using the idea of <strong><em>stack</em></strong> to understand the order issue with foldl and foldr to be very helpful.</p><blockquote>FIRST IN, LAST OUT</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Vd9cIdREuaR_iWxrW7EFIw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*irCn_sUEFDjrhtwXCzmXPg.png" /><figcaption>foldl v.s. foldr</figcaption></figure><p>A more concrete example using <em>SML </em>could be:</p><pre>(* fresh from the REPL *)</pre><pre>foldl (op ::) [] [1,2,3,4,5];</pre><pre>val it = [5,4,3,2,1] : int list<br></pre><pre>foldr (op ::) [] [1,2,3,4,5];</pre><pre>val it = [1,2,3,4,5] : int list </pre><h3>🚀 Takeaway #2</h3><h4>We update our ‘b as we iterate through the list 🆙</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*N86JUgchrNcmmTvYfLojhw.png" /></figure><p>The &#39;b value gets updates as you iterate through the list.</p><p>Normally, you would have a more complex task than just returning the elements in a list.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*z7t4TtBWvymfjPlQzJd86w.png" /><figcaption>A possible more complex fold’s (‘a * ‘b) with ‘b as a tuple of 3 elements</figcaption></figure><p>To solve complex problems such as only returning the element(s) that has 2 different neighbors, you need to keep track of elements in the list that you need to compare it to, and remember, your &#39;b can be anything you want it to as long as you remember to return the right value satisfying the spec.</p><p>Use the accumulator to store necessary information that you need.</p><h3>Last Last Last Note 🗒 💛</h3><p>I am very sorry that we all have to go through this difficult time, and no matter where you are at this moment, <strong>we will get through this</strong> 💪 and meet again in the future.</p><p>Take <strong>GREAT</strong> care of yourself for us, and <strong><em>always</em></strong> prioritize your mental health over school. Feel free to contact anyone on the staff team if you need help! 💖</p><h4>— 15150 S20 Staff</h4><p><em>Illustration, animation &amp; typeset by Mia 🍀</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=191dc1a48ed4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Functional Programming Manual V.1]]></title>
            <link>https://mia-tang.medium.com/functional-programming-manual-v-1-510ae8671b88?source=rss-8bf524e9e5f8------2</link>
            <guid isPermaLink="false">https://medium.com/p/510ae8671b88</guid>
            <dc:creator><![CDATA[Mia Tang]]></dc:creator>
            <pubDate>Sat, 08 Feb 2020 07:51:50 GMT</pubDate>
            <atom:updated>2020-02-09T23:54:01.859Z</atom:updated>
            <content:encoded><![CDATA[<h4><em>Expressions / Totality / Datatypes &amp; Structural Induction / Functions Types</em></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*g8vZOI0yLT5WwGnhb8RAxw.png" /></figure><h3>🕴Hey!</h3><p>This is a short article on the <strong>key ideas</strong> we’ve covered in the last few weeks. Ideas are visualized through illustrations. Hope you enjoy and gain more clarity regarding the concepts. <strong><em>We, 150 TAs, are always here for you! 💞</em></strong></p><h4><em>The following topics are covered </em>↘</h4><ul><li><em>Expressions</em></li><li><em>Totality</em></li><li><em>Datatypes &amp; Structural Induction</em></li><li><em>Strong Induction</em></li><li><em>Functions Types</em></li></ul><h3>Expressions</h3><h4>🌲 In the beautiful land of Standard ML, we have …</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FUzXJvav3DgNIIGyAfK_zQ.png" /><figcaption>(You can find this in the lab handout for basics_lab)</figcaption></figure><p>And we really care about <strong>EXPRESSIONS</strong>, and <strong>whether if they are well-typed. </strong>When they are NWT , the SML/NJ compiler will yell at you. 😡</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1l2c7bm5_L9TFF_KMqOiUQ.png" /></figure><p>We do not want the broken whatever on the left, instead, we only want the golden egg 🥚💛. We want everything to <strong><em>TYPE CHECK</em></strong>.</p><p>There are <strong>three possibilities</strong> for all well-typed expressions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qbILSfUskzpd0PfE8FZB2g.png" /></figure><ul><li>could be valuable (*values are valuable!)</li><li>could loop forever</li><li>could raise an exception</li></ul><blockquote>So, why do we care? When do we need to be REALLY careful about it?</blockquote><h3>Totality &amp; Proofs</h3><p>When given a piece of code (or your own code), and asked to prove that certain theorem holds, you encounter situations <strong><em>when you are not sure if you can take the step</em></strong> because of a function input that does not look like our regular inputs <strong><em>that are ALREADY values</em></strong>, e.g. 1 ,2, 3, true, false, [1,2,3], [4,5,6], (true, 1), …</p><p>Instead, you would have something like listSum(inord L) , and there is no way you can find out what inord L is, but you know that it must be a WT expression. So, let’s go back to our golden egg a.k.a well-typed expressions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DKMyTR4n4IqWLEtpcefN7Q.jpeg" /></figure><p>Here you are, holding a WT expression, and knowing where you need to get to, but unsure of whether if you can take the step.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*imn-g3Qd8UmvkJKnXwM1SQ.jpeg" /></figure><p>So, we need something to promise us that <strong>inside that egg will be a valuable expression</strong>. We <strong><em>NEED</em></strong> the inord L in listSum(inord L) to be a value or valuable because SML is a<strong><em> call-by-value, eager language</em></strong>, which just means that functions evaluate their arguments before doing anything else.</p><h4>✨ ✨ TOTALITY COMES TO RESCUE✨ ✨</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-7U5W62D4-ofw3EAzrSgzQ.png" /></figure><p>By citing totality of inord , we are promised to have inord L as a value or a valuable expression, which allows us to take the step to go on in our proof.</p><h3>Don’t we all 💘 Induction?</h3><h4>Strong Induction</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KUZsr25aAYpqJzTWEcnfYQ.jpeg" /><figcaption>💪 Strong Induction 💪</figcaption></figure><p>When you are proving something that involves recursive calls to different smaller values, you probably need strong induction. By assuming the theorem holds for a <strong><em>RANGE</em></strong> of values, you have more to use in your inductive step.</p><h4>Structural Induction</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*I7XLhV_JFnsAwGS8B6Hg-w.png" /></figure><p>The cases you have to prove using structural induction should <strong><em>come natural because your proof should follow the datatype.</em></strong></p><pre>(* just some pseudo proof structure *)</pre><pre>datatype iceCreamFlavor = chocolate | vanilla | strawberry</pre><pre>WTS: P(x) holds for all x : iceCreamFlavor </pre><pre>Case 1: Let x be chocolate <br>Case 2: Let x b vanilla<br>Case 3: Let x be strawberry </pre><p>A more complex example would be,</p><pre>(* just some pseudo proof structure *)</pre><pre>datatype starbucks = CannotFind | starbucks * string * starbucks</pre><pre>WTS: P(x) holds for all x : starbucks</pre><pre>Base Case: Let x be CannotFind</pre><pre>I.S.: Let x be (LS, s, RS), where LS : starbucks, s : string, RS : starbucks. </pre><pre>I.H.: Assume P(LS) and P(RS) hold. (WTS P(LS, s, RS) holds) </pre><blockquote><strong>So why does this work?</strong></blockquote><p>Let’s take our ice cream 🍦datatype as an example.</p><pre>datatype iceCreamFlavor = chocolate | vanilla | strawberry</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZnspYRtciI6EjMz3BW8MGw.jpeg" /></figure><p>Saying for some theorem P , P(x) holds for all x : iceCreamFlavor , you can visualize as all chocolate | vanilla | strawberry need to jump through the fire hoop of P to<strong><em> prove</em></strong> that P holds for them.</p><p>And that’s the beauty of structural induction. You can just simply look at the datatype, and show that they can jump through the hoop successfully.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*koitVk1cpTYKLGQNrh9QQw.jpeg" /></figure><p>So when you are trying to figure what to case on, <strong><em>look at the datatype constructors, and you should know what to do.</em></strong></p><p>Also, A rule of thumb to figure out B.C. versus I.S. would be non-recursive cases are base cases, and recursive cases should be proved with I.H. and I.S..</p><h3>Function Types</h3><p>Figuring types for functions can be confusing, and how I like to do it is to see fn as <strong>a door that only welcomes a specific kind of guest.</strong></p><p><strong>Some Ideas:</strong></p><ul><li>all functions written using fun keyword can be rewritten using fn</li><li>the number of fn you have = the number of arguments you are taking in</li><li>the last type in a function type will be the <strong><em>result type</em></strong></li><li>fn <strong>should <em>NEVER</em> be in any of your type annotations</strong></li></ul><p><strong><em>~Let’s do some examples~</em></strong></p><pre>val f = fn x : int =&gt; fn y : bool =&gt; (x, y)</pre><p>So the first door only opens when you give f a int , and the second door only opens when you give f 1 (or any other int) a bool .</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5jFf5fzwN--b6-PyCWCdpw.png" /></figure><pre>f : int -&gt; bool -&gt; (int * bool) </pre><p>Let’s get a bit more complex!</p><pre>val g = fn x : int =&gt; fn y : int =&gt; fn z : bool =&gt; fn m : int list =&gt; fn b : bool list =&gt; fn k : (bool * int) list =&gt; (* what you want to return  *)</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_01N10Dg6pllOgl0BaPv4w.png" /><figcaption>If you count the fn, we have 6 fns, and here we have 6 doors, hence we can take in 6 arguments</figcaption></figure><p>Let’s go back to our previous example of f</p><pre>val f = fn x : int =&gt; fn y : bool =&gt; (x, y)</pre><pre>f : int -&gt; bool -&gt; (int * bool)</pre><p>When we give f the argument 1 : int , f sees that, “Oh, it’s a value of type int , I will let her in.”</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SgYToH7M2g6hRKELJV_SIA.png" /></figure><p>Then 1 walks into the first door, and now x is bound to 1 . As 1 walks in, 1 has good manners and makes sure she has closed the door 🚪.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GZaoU2oc53295GkGN-Q3qA.png" /></figure><p>f 1 is f with its first door closed.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6aX2_u-kTusV5Rfq3oa3MA.png" /></figure><p>So the type of f 1 is bool -&gt; int * bool .</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cZnPXKbMuu84TNgbP2eOtg.png" /></figure><pre>f 1 : bool -&gt; (int * bool)</pre><pre>val g = f 1 <br>(* val g = fn y : bool =&gt; (1, y) *)</pre><p>The same goes for <strong><em>constructors with functions types</em></strong><em>. </em>Recall the following datatypes from the hw,</p><pre>datatype professor = Erdmann | Pfenning</pre><pre>datatype job = Student | Professor of professor | TA of string</pre><p>Here we have the two function type constructors Professor of professor and TA of string . You can see them as normal functions that takes in a value (of whatever type it is after of ) and outputs a value of the datatype which the constructors are defined along with.</p><pre>Professor : professor -&gt; job<br>TA : string -&gt; job</pre><p>And we know, val f : string -&gt; bool is a valid function type, so TA : string -&gt; job is also a well-typed expression with a function type. TA is a completely valid function that’s just waiting for its argument of type string.</p><h3>Recap On Important Ideas</h3><p>As we come to an end, I would like to jot down some important things to watch out for.</p><ul><li>No fn in ANY type annotations</li><li>Cite totality when you are assuming some function input must be valuable</li><li>Let the datatype lead your structural induction proof</li><li>Expression with a function type without inputs is STILL well-typed. It is simply waiting for its input.</li><li><strong><em>FUNCTIONS ARE VALUES</em></strong></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*YIg0etbGO3VFMdtzI0Yl2Q.gif" /></figure><blockquote>Good luck on your midterm! 💖 You got this!</blockquote><blockquote>— 15150 S20 Staff</blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=510ae8671b88" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>