<?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 Steven Leiva on Medium]]></title>
        <description><![CDATA[Stories by Steven Leiva on Medium]]></description>
        <link>https://medium.com/@StevenLeiva1?source=rss-1d471de4a3dd------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*Q-tiPDMfkvb3T5hW.jpeg</url>
            <title>Stories by Steven Leiva on Medium</title>
            <link>https://medium.com/@StevenLeiva1?source=rss-1d471de4a3dd------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 23:06:16 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@StevenLeiva1/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[The Tao of Servant]]></title>
            <link>https://medium.com/@StevenLeiva1/the-tao-of-servant-6389ba23eef9?source=rss-1d471de4a3dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/6389ba23eef9</guid>
            <category><![CDATA[web-development]]></category>
            <category><![CDATA[api]]></category>
            <category><![CDATA[haskell]]></category>
            <category><![CDATA[functional-programming]]></category>
            <dc:creator><![CDATA[Steven Leiva]]></dc:creator>
            <pubDate>Sat, 21 Oct 2017 23:02:34 GMT</pubDate>
            <atom:updated>2017-10-22T00:43:14.892Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>Servant</strong> is one of many high-quality Haskell packages available for writing web applications. I cannot hope to best the <a href="https://haskell-servant.readthedocs.io/en/stable/">official Servant docs</a>. However, while the docs do a great job of explaining the mechanics of Servant, in this post, I want to impart my conceptual model of Servant.</p><h3><strong>A Formalization of an Endpoint as a Type</strong></h3><p>The big idea behind Servant is that we can <strong>describe an endpoint in a web application formally, as a Haskell type</strong>. Once we have a formal description of the endpoint, Servant can do many “nice” things, such as generate documentation, generation client functions, etc. However, those features are tangential to serving the actual web application. Where Servant’s true benefits lie is that, once it has this formal specification of the endpoint, <strong>Servant can ensure that the request adheres to that specification</strong>.<strong> </strong>It can ensure that the data our request handlers require — query params, request headers, request bodies / content — is available. What if the request doesn’t adhere to the specification? Well, Servant will then respond with a <strong>Bad Request</strong>, <strong>Unsupported Content-Type</strong>, or other error as appropriate. (Please read the caveat at the end of this post).</p><h4>A Quick Example of an Endpoint Specification</h4><p>Let’s take a look at a small formal specification of an endpoint:</p><p>type MyEndpoint = &quot;users&quot; :&gt; ReqBody &#39;[JSON] User :&gt; Post &#39;[JSON] User</p><p>MyEndPoint is a formal specification of an endpoint. The specification specifies where the endpoint is available; &quot;/users&quot;. It specifies the contract that the request must adhere to — i.e., the request must contain a request body in JSON format that is deserializable into a value of type User. Finally, the specification specifies the contract that the response will adhere to; it will return a User in JSON format. (The Post type doesn’t fit nicely into this conceptual model, but for completeness’s sake, it is simply the HTTP Verb under which that endpoint is available).</p><p><strong>Benefits</strong></p><p>The fact that, given a specification, Servant can generate client function is huge. But it is not the most important thing.</p><p>The fact that, given a specification, Servant can generate documentation is huge. But it is not the most important thing.</p><p>The fact that, given a specification, Servan will ensure the request conforms to that specification IS huge. A whole swath of un-happy paths are now being dealt with before they even reach our request handlers. Want to specify that the request include a certain Authorization header?</p><p>type MyEndpoint = &quot;users&quot; :&gt; Header &quot;Authentication&quot; Text :&gt; ReqBody &#39;[JSON] User :&gt; Post &#39;[JSON] User</p><p>We’ll talk more about how to build an endpoint specification below, but given the above specification, if a request to “/users” comes in without an Authentication header, Servant will deal with it.</p><h3>Mechanics</h3><p>Note: This is still under construction.</p><p>Frankly, at this point, you should go read the <a href="https://haskell-servant.readthedocs.io/en/stable/">Servant docs</a>. They do a great job of explaining the mechanics. The list below is more of a reference for myself, but if it helps you too, great.</p><ol><li>First of all, we want to specify our endpoints. To do that, we create a type alias and use the :&gt; combinator to chain combinators and create an endpoint specification.</li><li>Most people don’t build websites with a single endpoint (this ain’t GraphQL), so we want to use the :&lt;|&gt; combinator to chain endpoints together.</li><li>With our endpoint(s) fully specified, we have to create handlers to handle the requests that do meet specification. We combine each handler using the :&lt;|&gt; operator, taking special precaution to combine the handlers in the same order in which we combined the endpoints.</li></ol><h3>Caveat</h3><p>I didn’t want to litter the post with this caveat everywhere, so I have saved it for the end. While Servant ensures that the requests received by our handlers adhere to our specification, it <strong>doesn’t break with the semantics of the web</strong>. For example, if we add the specification QueryParam &quot;name&quot; String, our handlers will receive a value of type Maybe String, because “an endpoint can technically still be accessed without specifying any query string”. The end of the section <strong>From combinators to handler arguments</strong> in the official docs has all the details.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6389ba23eef9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Haskell — A Simple Example of MonadIO]]></title>
            <link>https://medium.com/@StevenLeiva1/haskell-a-simple-example-of-monadio-29ce3f96f0d8?source=rss-1d471de4a3dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/29ce3f96f0d8</guid>
            <category><![CDATA[web-development]]></category>
            <category><![CDATA[haskell]]></category>
            <category><![CDATA[functional-programming]]></category>
            <dc:creator><![CDATA[Steven Leiva]]></dc:creator>
            <pubDate>Sat, 14 Oct 2017 12:56:36 GMT</pubDate>
            <atom:updated>2017-10-14T12:56:36.525Z</atom:updated>
            <content:encoded><![CDATA[<p>In this post, I want to explain <strong>how to use</strong> the MonadIO typeclass in Haskell. Note that this post is an explanation of <strong>what</strong> MonadIO does for us, not <strong>how</strong> it does it.</p><p>In fact, more than anything, this is going to be an example of using the <strong>substitution model</strong> and <strong>equational reasoning</strong> to understand a small program.</p><h3>Some Real Code via Scotty</h3><p>The code that we are going to be looking at is this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/53726f014f08dcb035d1101727ccb145/href">https://medium.com/media/53726f014f08dcb035d1101727ccb145/href</a></iframe><p>If you have stack installed, you can play around with this by creating a new stack project with the scotty-hello-world template:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a87b60d29415e26ade59a89bf09263c5/href">https://medium.com/media/a87b60d29415e26ade59a89bf09263c5/href</a></iframe><h3>ScottyM Monad</h3><p>Our main function above, the entry point for our program, is defined as scotty 3000 &lt;second argument here&gt;. Let&#39;s look at the type of scotty:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6b9a21de119fef53cff5a311f0b3769b/href">https://medium.com/media/6b9a21de119fef53cff5a311f0b3769b/href</a></iframe><p>Based on the type of scotty, we know that our second argument - what I labeled &lt;second argument here&gt; - must have the type ScottyM ().</p><h3>do Notation</h3><p>The second argument to scotty is a value of type ScottyM (). That value was built using do notation, which we know to be syntactic sugar for &gt;&gt; and &gt;&gt;=. That means that we need to &quot;play by the rules of&quot; those operators. What are those rules? Well, specializing those operators to the ScottyM monad that we are in, they are:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6e48193864b8b2a941c701bc9bd79da3/href">https://medium.com/media/6e48193864b8b2a941c701bc9bd79da3/href</a></iframe><h3>Printing in the Middle of the ScottyM Monad</h3><p>Let’s say that we wanted to modify our code so that, whenever someone makes a request to our web server, we print that out. A first pass at that would look like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f14144d507efd42b57c0d05983ca2a0c/href">https://medium.com/media/f14144d507efd42b57c0d05983ca2a0c/href</a></iframe><p>Notice that we added putStrLn &quot;hello&quot; right in the middle of our monad.</p><p>That, however, won’t type check. The reason is that putStrLn &quot;hello&quot; :: IO (), and, based on the types of &gt;&gt; and &gt;&gt;=, each line must be a value of type ScottyM a. We can&#39;t just plop a value of type IO () in the middle of our do block.</p><h3>liftIO</h3><p>This brings us, finally, to the motiviation of this post, MonadIO.</p><p>You can look up the information for this typeclass on your own. For our purposes, suffice it to say that liftIO is the only method in the MonadIO typeclass. It has the signature liftIO :: Monad m =&gt; IO a -&gt; m a. This means that it takes any IO a value and turns that into another monad that, when ran, produces a value of type a.</p><p>In our specific case, liftIO will take our IO () and return back a ScottyM (). A value of type ScottyM () is exactly the type we need in order to plop it down in the middle of our do block.</p><h3>Finally</h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6882f71d5b1a57071e5e28bd2cc510bb/href">https://medium.com/media/6882f71d5b1a57071e5e28bd2cc510bb/href</a></iframe><p><em>Originally published at </em><a href="https://gist.github.com/bc273116981a0d80d550aab4f8732e86"><em>gist.github.com</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=29ce3f96f0d8" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Haskell Book: Chapter 22: Reader]]></title>
            <link>https://medium.com/@StevenLeiva1/haskell-book-chapter-22-reader-4b74b1c3b563?source=rss-1d471de4a3dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/4b74b1c3b563</guid>
            <category><![CDATA[functional-programming]]></category>
            <category><![CDATA[haskell]]></category>
            <dc:creator><![CDATA[Steven Leiva]]></dc:creator>
            <pubDate>Wed, 27 Sep 2017 13:30:57 GMT</pubDate>
            <atom:updated>2017-09-27T13:30:57.681Z</atom:updated>
            <content:encoded><![CDATA[<p>Note: This was translated from markdown to medium via <a href="http://www.markdowntomedium.com/">markdowntomedium.com</a>.</p><p>Reader is a type that is useful when we want to make some information available <em>intermittently</em> or <em>universally</em> throughout an application. Conceptually, the Reader type allows us to read a value from the environment. Mechanically, Reader is a newtype wrapper for a function of type r -&gt; a.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/938e5bcd1b8f9274fc47396fb204f6aa/href">https://medium.com/media/938e5bcd1b8f9274fc47396fb204f6aa/href</a></iframe><h3>Functor of Functions</h3><p>In order to understand how Reader works, it is necessary to understand how the functor of functions works.</p><p>In short, the functor of functions is simply function composition:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/67b1a703a6a328f735d22a9b6fe6a08a/href">https://medium.com/media/67b1a703a6a328f735d22a9b6fe6a08a/href</a></iframe><p>The above may look a bit strange but we can rearrange the (specialized) type signature:</p><p>(a -&gt; b) -&gt; ((-&gt;) r a) -&gt; ((-&gt;) r b) ~ (a -&gt; b) -&gt; (r -&gt; a) -&gt; (r -&gt; b)</p><p>r, which represents the argument to the function, is part of the structure that we are mapping over. It is therefore not possible to change it. Instead, we will transform the value returned by the function. In our case, the value of type a will be transformed into a value of type b.</p><p>So, for functions, we can read the type signature as saying fmap takes a function from a to b, a function from r to a, and returns another function from r to b. How? Through function composition.</p><h3>Applicative of Functions</h3><p>The Reader newtype also has an applicative instance:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/667d2f64358b8d5723faca2a3651c185/href">https://medium.com/media/667d2f64358b8d5723faca2a3651c185/href</a></iframe><p>pure a will give us back a Reader that, applied to an argument r, discards the r and gives us back the a.</p><p>(&lt;*&gt;) is more interesting. In this case, the first argument to &lt;*&gt; - Reader r (a -&gt; b) - is a Reader that wraps a function with the signature r -&gt; (a -&gt; b). That is more commonly writen as r -&gt; a -&gt; b. The second argument is a function (wrapped in Reader) that, when applied to an argument r produces a value a. From the implementation, the &lt;*&gt; for Reader returns back a wrapped function that, given a value r, applies that to the second record to get an a, and then uses that a and the r to fully saturate the function wrapped in the first Reader.</p><p>In other words, &lt;*&gt; will give us back a Reader that when &quot;ran&quot; will run the two readers we gave it, one after the other, and use the output of one as part of the input of the other.</p><p>The applicative of functions is very instructive. If we look at the definition of &lt;*&gt; again, we can see that both Readers are waiting for the same input - r. The first Reader is awaiting even more input, but that&#39;s OK. The point is that, if we have a function r -&gt; a -&gt; b and a function r -&gt; a, we can compose in such a way that we get back a function simply waiting an r to give us a b. We no longer have to manually worry about getting the a, that will be handled for us.</p><p>One of the things we have to understand about Applicative an applicative allows us to <strong>apply a function in a structure to a value in a structure</strong>. It combines the structures for us. A perfect example is the following:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/590677282c78cebae879e4d0ce743b05/href">https://medium.com/media/590677282c78cebae879e4d0ce743b05/href</a></iframe><p>Let’s expand the last expression above:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e58193f6aa02cb0eab413a1c13f0e124/href">https://medium.com/media/e58193f6aa02cb0eab413a1c13f0e124/href</a></iframe><p>Now, let’s take one reduction step We know that fmap / &lt;$&gt; is going to lift the function (, ) over the &quot;Maybe container&quot; and apply it to the value inside:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/482b8e32137160c09e0ea0bbd7954df5/href">https://medium.com/media/482b8e32137160c09e0ea0bbd7954df5/href</a></iframe><p>(Note that we can write (6, ); it should be (, ) 6, but conceptually it is easier to use (6, )).</p><p>Now, for the interesting part, &lt;*&gt; is actually going to apply the function inside our Maybe container to the value inside another maybe container, <strong>and</strong> &quot;merge&quot; the containers:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/33fc99b29dc2e1da52ed2fefda895510/href">https://medium.com/media/33fc99b29dc2e1da52ed2fefda895510/href</a></iframe><p>This is how we go from two values of type Maybe Integer to Maybe (Integer, Integer. Of course, if any of our values had been Nothing, the result of the entire expression would have been Nothing.</p><h3>Functor / Applicative of Functions</h3><p>This is a tricky subject, so we are going to try this again:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/53b3a72c08953a3f97a64b14cead7723/href">https://medium.com/media/53b3a72c08953a3f97a64b14cead7723/href</a></iframe><p>The bolt function takes an integer and calculates if the integer is greater than 3 and greater than 8. But how is it doing that?</p><p>First, let’s remember that the functor of functions is function composition, so that (&amp;&amp;) &lt;$&gt; (&gt; 3) is the same as (&amp;&amp;) . (&gt; 3) - i.e., a function that will pipe its argument to (&gt; 3) and then to (&amp;&amp;). Let&#39;s reduce:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d56d0457329f41ca35a07fe3d62caa95/href">https://medium.com/media/d56d0457329f41ca35a07fe3d62caa95/href</a></iframe><p>The type of that expression is a -&gt; Bool -&gt; Bool (with constraints elided).</p><p>Now, we know that &lt;*&gt; takes a function &quot;inside a container&quot; and a value inside the container, and applies the function to the value and &quot;merges&quot; the container:</p><p>Let’s re-arrange our type from a -&gt; Bool -&gt; Bool to a -&gt; (Bool -&gt; Bool). We can then further rearrange this to (-&gt;) a (Bool -&gt; Bool). This shows more clearly that our container is ((-&gt;) a), and our function is Bool -&gt; Bool.</p><p>Let’s do the same with the expression &gt; 8. It&#39;s type is a -&gt; Bool (constraints elided), which we can rearrange to (-&gt;) a Bool. Now, we have our two applicatives: (-&gt;) a (Bool -&gt; Bool) and (-&gt;) a Bool. If we were to &quot;apply and merge&quot; these via &lt;*&gt;, we would apply Bool -&gt; Bool from the first type to the Bool in the second type, to get (-&gt;) a Bool.</p><p>Let’s go back to the value level:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/77107065f2a9c120869e5ed45cb0bdb0/href">https://medium.com/media/77107065f2a9c120869e5ed45cb0bdb0/href</a></iframe><p>If we look at how &lt;*&gt; is defined for functions, we see that: f &lt;*&gt; g = \a -&gt; f a (g a). So we can reduce bolt again to this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b2f708e572b2934140536f0eb0541fbc/href">https://medium.com/media/b2f708e572b2934140536f0eb0541fbc/href</a></iframe><p>So there we go. We’ve used the <strong>substitution model</strong>, essentially just plugging in the expressions in the right place, to figure out how to reduce &lt;*&gt;. We can see how liftA2 gets us the function we wanted.</p><p>In the bolt example, what is hard to recognize is what the Applicative of functions is. It is easy to figure it out for Maybe a values. Forgetting about Nothing, we take a value Just someFunction and another value Just argument and we return Just (someFunction argument). No biggie, but applicative of functions?</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4b74b1c3b563" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Haskell Book: Chapter 23 — State]]></title>
            <link>https://medium.com/@StevenLeiva1/haskell-book-chapter-23-state-757f8423ff1?source=rss-1d471de4a3dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/757f8423ff1</guid>
            <category><![CDATA[haskell]]></category>
            <category><![CDATA[functional-programming]]></category>
            <dc:creator><![CDATA[Steven Leiva]]></dc:creator>
            <pubDate>Sun, 24 Sep 2017 21:08:51 GMT</pubDate>
            <atom:updated>2017-09-24T21:08:51.264Z</atom:updated>
            <content:encoded><![CDATA[<p>This is a continuation of my trials and tribulations as I work through the <a href="http://haskellbook.com/">Haskell Book</a>.</p><p>Unlike some of my other posts, in which the material came came almost exclusively from the Haskell Book itself, the material from this post is an amalgamation of different source, include the <a href="https://en.wikibooks.org/wiki/Haskell">Haskell wikibook</a>, <a href="http://learnyouahaskell.com/for-a-few-monads-more#state">Learn You a Haskell</a>, and others source which I can’t now recall.</p><h4>Stateful Computations</h4><p>Conceptually, we can think of a “stateful” computation as a function with the<br>type signature: f :: s -&gt; (a, s)</p><p>In other words, given a state, the function will return an answer and a new<br>state.</p><h4>The State newtype</h4><p>There is a type that we can use to wrap stateful computations:</p><p>newtype State s a = State { runState :: s -&gt; (a, s) }</p><p>There are a few things going on here. First, when we see a value with the<br>following type signature: State s a, we know that we have a function that,<br>when applied to a value s, will yield a value (a, s). That function is<br>wrapped — it is a field in the State data constructor.</p><h4>The State Monad</h4><p>The reason that the function is wrapped is that it allows us to create an<br>instance of monad for it:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/75c61a7da35ccf045fffd9a7509089dc/href">https://medium.com/media/75c61a7da35ccf045fffd9a7509089dc/href</a></iframe><p>The big idea with the State monad is that we have a state processor, and a<br>function that yields a state processor. From those two ingredients, we get a<br>third state processor that will, when “ran” will:</p><ul><li>Apply the state to the first state processor to get an “answer” and a new state.</li><li>It will apply the answer to the function to yield a new state processor.</li><li>It will run that new state processor with the state from the first state<br> processor.</li></ul><p>At the end of the day, the big picture idea is that the state monad allows us to<br>thread state through several state processors automagically.</p><h4>Using the State Monad</h4><p>OK. The whole deal is to have two state processors, where we want to collect the output of each state processor, and we want the state of one state processor to influence the state of the second state processor. Let’s see if we can get thatdone.</p><p>First, we’ll assume we have the following type in scope:</p><p>newtype State = State { runState :: s -&gt; (a, s) }</p><p>Second, let’s create our first state processor.</p><p>stateProcessor = State $ randomR (1,6)</p><p>The expression runState stateProcessor (mkStdGen 0) evaluates to (6,40014 40692).</p><p>So what happens when we run the state processor again with the new state from the first application of our processor:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4221811e44c33426b074f51539e1a926/href">https://medium.com/media/4221811e44c33426b074f51539e1a926/href</a></iframe><p>Great. Now, let’s try and write some functions that combine the same state<br>processor.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c5b5eb5819302bc18f3753132fe9405d/href">https://medium.com/media/c5b5eb5819302bc18f3753132fe9405d/href</a></iframe><p>runState newStateProcess (mkStdGen 0) evaluates to (6,1601120196<br>1655838864). We can conclude from this that the second stateProcessor was<br>evaluated with the state produced from the first state processor! In other<br>words, the state passing was handled for us!</p><p>The interesting part about this is that, even though we are <strong>not</strong> using the<br>answer produced from running the first stateProcessor, we are <strong>definitely</strong><br>using the state it produced, even when we use &gt;&gt; instead of &gt;&gt;=. The first<br>computation is <strong>100% affecting the second computation</strong>, because the monad instance is taking care of passing threading the state! In other words, &gt;&gt; does <strong>not</strong> mean that everything from the first application is thrown away.</p><p>Now, let’s create a state processor that does use the answer produced from the<br>first state processor:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7487016cf3d50583ff42bf71f688c59a/href">https://medium.com/media/7487016cf3d50583ff42bf71f688c59a/href</a></iframe><p>anotherStateProcessor is simply a clear indication that we can use the answer provided from the first state processor, as well as the state.</p><p>We know that runState stateProcessor (mkStdGen 0) will evaluate to (6,40014 40692), which means that we will be evaluating the else branch of the if..then..else expression: runState anotherStateProcessor (mkStdGen 0) evaluates to (1,40014 40692).</p><h4>Specifying the Semantics of the State Monad</h4><p>&gt;&gt;= means run the stateful computation, use the answer, and pass the new state down.</p><p>&gt;&gt; is the same as &gt;&gt;=, except that we know for a fact that the answer part of the stateful computation is going to be discarded.</p><h4>Auxiliary Functions</h4><p>We can use put to create a state processor that, when “ran”, will return the<br>state we gave to put:</p><p>put newState = State $ \_ -&gt; ((), newState)</p><p>We can use get to create a state processor that, when given the state, will<br>return that state as both the answer and the new state:</p><p>get = State $ \s -&gt; (s, s)</p><p>We can use evalState to run the state processor with the given state, but only<br>give us back the answer:</p><p>evalState stateProcessor state = fst $ runState stateProcessor state</p><p>We can use execState when we care not about the answer that the state<br>processor returns, but about the state.</p><p>execState stateProcessor state = snd $ runState stateProcessor state</p><h4>Monadic Functions</h4><p>It is important to remember that we have defined an instance of the Monad<br>typeclass for the State s type constructor. Notice that s in this case is a<br>type variable. This indicates that s can be instantiated to any type constant.</p><p>This is very important, because it means that we can use all of the functions<br>that are used to manipulate monads. For example:</p><p>sequence :: Monad m =&gt; [m a] -&gt; m [a]</p><p>The type signature is telling us that sequence can be used with any type<br>constructor m which has an instance of the Monad typeclass. State StdGen<br>Int, which we have used throughout our example, has an instance of the Monad typeclass <strong>because</strong> we have an instance of the Monadtypeclass for State s, where, again, s can be any type constant.</p><p>(Note: sequence is more polymorphic than the type signature shown here, but it adds a bit of noise not relevant to our point; look it up in GHCi)</p><h4>Seeing the Forest for the Trees</h4><p>Details are important, but at this point it might be easy to forget how the<br>State type and the state monad are supposed to make our lives easier. What we have to keep in mind is that the ideas we’re talking about here are all about helping us model state, as we would understand coming from an imperative language.</p><p>For example, let’s take the problem where we want to count how many times we perform an operation. In an imperative language, we’d have global state that we could update. Here is how we would model that using the State type:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6f6be710f0bbd1f829079af175ad1e6d/href">https://medium.com/media/6f6be710f0bbd1f829079af175ad1e6d/href</a></iframe><p>increaseApplicationCount is a state processor. It takes in a state (the<br>previous count of the number of applications), and returns it to us increased by 1</p><p>The expression execState countApplications 0 will return 5, because that is<br>the number of times that we “ran” the state processor.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=757f8423ff1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Understanding Servant — Conceptually]]></title>
            <link>https://medium.com/@StevenLeiva1/understanding-servant-conceptually-321039fea3ee?source=rss-1d471de4a3dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/321039fea3ee</guid>
            <category><![CDATA[functional-programming]]></category>
            <dc:creator><![CDATA[Steven Leiva]]></dc:creator>
            <pubDate>Sun, 03 Sep 2017 20:37:22 GMT</pubDate>
            <atom:updated>2017-09-03T20:37:22.109Z</atom:updated>
            <content:encoded><![CDATA[<p>NOTE: This entire post is in draft stage. The reason why it is published is because I want others to review. Once enough errors have been fixed, I’ll remove this, though it will probably always be considered “beta”.</p><p>Servant is a Haskell library that can be used as the back-end for a website. There are many web frameworks in Haskell, but what is interesting about Servant is that, given a <strong>type describing an API, </strong>the framework can write the server, produce client functions, and generate documentation.</p><p>This might seem kind of magical, and frankly it is. I don’t understand the implementation details of this myself. However, in order to be productive with Servant, we only need to understand what is going on at a conceptual level — we need a correct mental model.</p><p>This post is for beginning Haskellers — folks who know the basics such as types, typeclasses, polymorphism, but still haven’t started playing around with the advanced features (made possible mostly through language extensions) in Haskell. The goal is to take what seems like magic and tie it back to what a beginner “should” know, so that we can work with Servant with a bit more confidence.</p><h4>Data</h4><p>First, let’s start from a fundamental principle of programming that is often lost to most beginners. Data is the only thing that exists in a computer program. Everything gets boiled down to 1s and 0s, of course, but at a higher level of abstraction, we use data to configure out libraries all the time.</p><pre>class UsersController &lt; ApplicationController<br>  before_action :ensure_authenticated, only: [:create, :update]<br>end</pre><p>Those of you that come from a Ruby on Rails background will quickly recognize the controller above. We’ve configured our library by passing in data. We have passed a symbol :ensure_authenticated and hash with an only key and an array of symbols — {only: [:create, :update]}. This pattern is so incredibly common in almost all languages that we forget that, at the end of the day, from a conceptual standpoint all we are doing is passing in data to a function.</p><p>Why do I bring up something so obvious? It’s to ensure that we understand that Servant is not doing any magic. We describe our web application as a type. From that type, Servant will generate a web application. Servant is using the type that we write as the “configuration hash”, in a way.</p><h4>Types as Data</h4><p>What does a type as “configuration data” look like? Well, from the <a href="https://haskell-servant.readthedocs.io/en/stable/tutorial/ApiType.html">docs</a>, it looks like this:</p><pre><strong>type</strong> <strong>UserAPI</strong> <strong>=</strong> &quot;users&quot; <strong>:&gt;</strong> <strong>QueryParam</strong> &quot;sortby&quot; <strong>SortBy</strong> <strong>:&gt;</strong> <strong>Get</strong> <strong>&#39;[JSON]</strong> [<strong>User</strong>]</pre><p>(The above is a description of a web application. It says that the /users endpoint expects a GET request with a query param called sortby which is a value of type SortBy, and returns a list of users encoded in JSON).</p><p>By now, you should be getting a bit confused. Beginners such as ourselves are taught that types and terms (values) live in two separate worlds. So what is going on here?</p><p><strong>Deconstructing type UserAPI</strong></p><p>First, let’s understand that a type declaration is always a type declaration. We know that a type declaration creates a synonym for another type. The alias is on the left of the equal sign, and the underlying type is on the right of the equal sign. These are axioms — apriori truths that we can rely on to tease out the rest of the story.</p><p>But we’ve never seen <em>type expression</em> use values before. Type expressions are supposed to contain type constructors, type variables, and type constants. However, &quot;users&quot; and &quot;sortby&quot; are none of those things — they are most definitely values / terms, so what are they doing in their our type declaration? As you probably guessed from the sub-heading of this section, <strong>DataKinds</strong> makes it possible to use <strong>type-level strings</strong>.</p><p>Next, let’s tackle :&gt;. Again, these might look weird to a beginning Haskeller, but we are all <em>very well-acquainted</em> with another infix type constructor: -&gt;.</p><pre>shout :: String -&gt; String<br>shout n = n ++ &quot;!&quot;</pre><p>Normally, -&gt; is the only infix type constructor allowed in Haskell. However, the language extension TypeOperators allows developers to define their own infix type constructors, and that is exactly what :&gt; is. It’s an infix type constructor. It takes types and return types. (The <em>kind</em> of :&gt; in ghci looks like this k1 -&gt; k -&gt; *).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=321039fea3ee" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Purity Enables Laziness / Parallelism]]></title>
            <link>https://medium.com/@StevenLeiva1/purity-enables-laziness-parallelism-77c9223d81ac?source=rss-1d471de4a3dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/77c9223d81ac</guid>
            <category><![CDATA[functional-programming]]></category>
            <dc:creator><![CDATA[Steven Leiva]]></dc:creator>
            <pubDate>Sun, 13 Aug 2017 01:48:58 GMT</pubDate>
            <atom:updated>2017-08-13T01:48:58.975Z</atom:updated>
            <content:encoded><![CDATA[<p>Functional programming is a hot topic nowadays. Because pure functions are an important part of functional programming, that means that pure functions are a hot topic too.</p><p>The question is, why should you care about pure functions?</p><h3>What is a pure function</h3><p>First, what is a pure function? A pure function is a <strong>function that will return the same results given the same arguments, and has no side-effects</strong>.</p><p>For example, the function below (in JavaScript) is a pure function:</p><pre>// JavaScript<br>function addFifteen(n){<br>  return 15 + n;<br>}</pre><p>No-matter how often or when you call it, the invocation of addFifteen(10) will always, in all cases, unequivocally return 25.</p><p><strong>Note:</strong> Many definitions of a pure function will include the requirement that a pure function only depends on the arguments passed in. As you can see, the addFifteen function depends on the value 15. Even though that value is not passed in, addFifteen is still a pure function. Remember, <strong>always gives the same results</strong>, <strong>no side-effects.</strong></p><h3>Why Does It Matter?</h3><p>Why does it matter if a function is pure? There are a few reasons.</p><p>First, the interesting parts of a pure function are often the arguments passed in to the function. Because the arguments are passed in to the function, we do not have to make a mental “non-local” jump looking for other state.</p><p>Secondly, because pure functions will always return the same results (given the same arguments), it is possible for us to <strong>delay computation</strong>. If our function depended on state / values that can where not passed in and can change, then we need to call the function immediately. This is because, even though we passed in the same arguments, the “arguments” that we didn’t pass in can change over time, so we’d potentially get a different result calling the function with the same arguments now versus 5 minutes from now versus 10 minutes from now.</p><p>Third, the multiple functions can be called in any order — the order of the evaluation doesn’t matter, because I am always going to get the same result back. This idea (the Church-Rosser theorem) means that we can trivially parallelize a program. If I can anthropomorphize a bit, we can take two functions and, instead of executing them on different computers, and then “add” the results.</p><h3>Conclusion</h3><p>Functional purity is a big deal. It helps in making our programs easier to understand, it is a prerequisite for laziness, and it allows us to easily parallelize our programs.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=77c9223d81ac" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Haskell Book: Chapter 11 — Algebraic Data Types]]></title>
            <link>https://medium.com/@StevenLeiva1/haskell-book-chapter-11-algebraic-data-types-c83ab083c45a?source=rss-1d471de4a3dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/c83ab083c45a</guid>
            <category><![CDATA[haskell]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Steven Leiva]]></dc:creator>
            <pubDate>Tue, 16 May 2017 12:18:43 GMT</pubDate>
            <atom:updated>2017-05-16T12:18:43.358Z</atom:updated>
            <content:encoded><![CDATA[<h3>Big Ideas</h3><p><strong>Custom Data Types</strong> — A Haskell best practice is to <em>create custom</em> <em>datatypes</em> to model a domain. We want to use datatypes to describe the structure of the data that our program is going to be processing. Modeling our domain through datatypes is very important, because it allows the compiler to help us later on. Modeling our domain through datatypes is like modeling our persistence layer in databases — get this part right, and the rest of the program will be easier and more obvious.</p><p><strong>Cardinality, Sum Types, Product Types</strong> — Why do we care about <em>sum types</em>, <em>product types</em> and cardinality? (Note: Definition of all of these terms are provided in the section below). The reason these things are important is because it tells us <em>how many different implementations</em> there are for a given type.</p><p>For example, let’s take the following type signature myFunc :: Bool. If we take a look at the datatype Bool, there are only two possible values for Bool — True or False. This means that there are only two possible implementations of myVal: myVal = True OR myVal = False. There is no other possible way to implement myVal, given the type signature.</p><p>Let’s try something with a <em>product type</em>. Let’s say we have the following type: data Product = Product Int8 Int8. The data constructor Product must be applied to two values, so we know that the Product datatype is a product type. What is the cardinality of the datatype Product? Well, Int8 is a type that represents the values from -127 to 128. It’s cardinality is 256, so the cardinality of Product is 256 * 256 = 65,536. This means that if I have the type signature myVal :: Product, there are 65,536 ways that I can satisfy that type signature.</p><p>At the end of the day, <em>the lesson is that it is much easier to reason about a type whose cardinality is smaller</em>. This becomes very important for functions, because the cardinality for a function is <em>exponential</em>. We take the cardinality of the second argument, and <em>raise it</em> to the cardinality of the first.</p><p>For example, let’s say I have the following type signature:</p><p>myFunc :: Bool —&gt; Bool</p><p>The cardinality of Bool is 2. I can calculate the cardinality of the type of myFunc (remember that -&gt; is a type constructor) as 2 ^ 2, or 4. However, because things are exponential, even a small increase in the cardinality of the type arguments to -&gt; leads to a large increase in the cardinality of the entire type.</p><p><strong>Kind</strong> — Like cardinality, <em>kind</em> refers to a property of datatypes. Specifically, kind is the type of a type. For example:</p><p>data Person = Person String</p><p>The datatype Person has the kind *. * indicates a concrete data type. In other words, the type constructor Person is already a concrete data type / type constant, and it therefore does not have to be applied to a type argument.</p><p>However, let’s take another data declaration:</p><p>data Person&#39; a = Person&#39; String a</p><p>The datatype Person&#39; has the kind * -&gt; *. What this indicates is that Person&#39; type constructor must be applied to a concrete type in order to yield a concrete type. Notice that it is extremely helpful to keep the fact that -&gt; is a type constructor at the forefront of one’s mind. The kind for the -&gt; type constructor is -&gt; :: * -&gt; * -&gt; *. In other words, -&gt; must be applied to two concrete types in order to yield a concrete type.</p><p><strong>Newtype</strong> — The vast majority of the benefits of Haskell comes from its type system. It follows, then, that knowing how to use the type system effectively is important. We won’t get all of Haskell’s purported benefits without knowing how to wield the type system. I bring this up now, under the section on <strong>newtype</strong>, because I think that <strong>newtype</strong> is a perfect example of how using the type system effectively is necessary to increase our code’s safety — i.e., the number of errors that the type system can catch.</p><p>For example, let’s say we have the following function:</p><p>tooManyGoats = Int -&gt; Bool</p><p>Because we have used Int, we haven’t really modeled our domain. That value could have come from anywhere, and can refer to anything. Maybe it refers to the number of cows we have, yet our function name indicates it should be checking the number of goats we have.</p><p>We can increase the safety of our code — we can wield the type system more effectively — by using a newtype declaration in this case:</p><p>newtype Goat -&gt; Goat Int</p><p>(We could have done the same with a data declaration instead of a newtype declaration, but newtype is more efficient. (The newtype data constructor is also strict, while a data constructor from a data declaration is lazy, but whatever — not important to me).</p><p>So, newtype can help us wield Haskell’s type system more effectively, and thereby increase the safety of our code. However, there is one other reason for using newtype declarations, and that’s that we can create an instance of a typeclass that differs from the instance of that typeclass implemented by value contained.</p><p><strong>Record Syntax</strong> — I don’t really want to talk about record syntax. I’m not a fan. I like the idea of passing in arguments by field rather than position, but there are more than a few edge cases where I think records might be more of a hassle than they are worth. For example, can’t have two different records with the same field, since accessor functions are automatically constructed. Then there’s the section in the book about accidental bottoms, etc.</p><h3>Terminology / Concepts</h3><p><strong>Nullary Data Constructor</strong> — A nullary data constructor is a data constructor that takes no arguments. For example:</p><p>data Bool = True | False</p><p>The data constructors True and False are both <em>nullary</em>. Nullary data constructors are also referred to as constants.</p><p><strong>Unary Data Constructor</strong> — A unary data constructor is a data constructor that must be applied to one argument before a value is created / yielded. For example:</p><p>data Person = Person String</p><p>The Person data constructor must be applied to a value of type String before a value of type Person is created.</p><p><strong>Sum Types</strong> — A sum type is a type that has <em>more than one constructor inhabiting it</em>. The sum type is denoted by the |, and it means that we have <em>disjunction</em>. For example:</p><p>data Bool = True | False</p><p>Again, the | clues us in on the fact that we have a sum type. What the sum type is telling us is that a value of type Bool will be constructed from the data constructor True OR the data constructor False. It is one or the other — not both.</p><p><strong>Product Types</strong> — A product type is a type whose data constructor takes more than one argument. In other words, in order to create a value of that type, we must apply the data constructor to a value of the first type AND a value of the second type. For example:</p><p>data Person = Person String Integer</p><p>The Person data constructor must be applied to a value of type String AND value of type Integer in order for a value of type Person to be created.</p><p><strong>Cardinality</strong> — Cardinality refers to a property of<strong> </strong><em>datatypes</em>. Specifically, it refers to the number of possible values that can inhabit that datatype. If we think of datatypes as a set of related values, the cardinality of a datatype is the number of values in that set. In the section above, we spoke about how the cardinality of a type can be deduced solely from its type signature.</p><p><strong>Extending Code in Haskell</strong> — One of the reasons why I want to learn Haskell is because Haskell’s type system allows us to <em>refactor without fear</em>, and also extend our program without fear. (Of course, this all assumes we are using the type system to our advantage — we need to be able to model our domain in the type system).</p><p>One perfect example of this benefit of Haskell is problem #5 of the Vehicles exercise. In it, we’ve decided that we are going to change our model — specifically, we’re going to extend the Vehicle datatype such that the Plane data constructor now needs to be applied to not only a value of type Airline, but also a value of type Size. If we make this change in the type, and then try to compile our program, Haskell’s type system will tell us everywhere else that we need to account for this change.</p><p>In other words, we change our domain model to incorporate a new requirement — something that happens all the time in software development — and Haskell will point us to where that change breaks our code, so that we can fix it.</p><h3>Misc</h3><p><strong>Type Level</strong> — Remember that type constructors are used at the <em>type level</em>, and data constructors are used at the <em>term level</em>.</p><p><strong>Data Constants</strong> — We already mentioned this, but nullary data constructors are also known as constants.</p><p><strong>Type Constant — </strong>Like data constructors / constants, we also have type constructors and type constants. A type with the kind * is a concrete type / type constant.</p><p><strong>Type Constructors</strong> — Because types can also be parameterized — meaning that they must be applied to <em>type argument</em> — they can also be described using terms such as nullary, unary, etc.</p><p><strong>Type Variables</strong> — Types that have a type variable in their data declaration are called <em>parameterized types</em>. It is very important to remember that type variable is a placeholder — eventually, we have to replace that type variable with a concrete type. Only after we’ve applied a type constructor to a concrete type do we get another concrete type.</p><p><strong>Data Constructor Classifications</strong> — Data constructors are classified according to the number of arguments that they must be applied to:</p><ul><li>0 arguments — <em>nullary</em> data constructor; more properly, a <em>data constant</em>.</li><li>1 argument — <em>unary</em> data constructor</li><li>2 arguments — <em>binary</em> data constructor; also a product.</li></ul><p><strong>Language Pragma</strong> — A language pragma is an instruction to the compiler to process input in ways beyond what the standard provides for.</p><p><strong>type declarations</strong> — Type declarations create type constructors, but <em>not</em> data constructors. For example:</p><p>type Name = String</p><p>We now have a type constructor Name, but there is no data constructor String.</p><p><strong>dependent types</strong> — We don’t talk about dependent types in Haskell, but one thought that struck me during the discussion of cardinality is that dependent types is all about making the cardinality smaller.</p><p><strong>The typechecker helps those who help themselves.</strong></p><p><strong>Infix Operators — </strong>None-alphanumeric operators are infix by default. All infix <em>data constructors</em> must start with a colon — :. The single colon data constructor is already taken up by cons operation.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c83ab083c45a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Haskell Book: Chapter 10 — Folding Lists]]></title>
            <link>https://medium.com/@StevenLeiva1/haskell-book-chapter-10-folding-lists-3e9e82ce5201?source=rss-1d471de4a3dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/3e9e82ce5201</guid>
            <category><![CDATA[haskell]]></category>
            <category><![CDATA[functional-programming]]></category>
            <dc:creator><![CDATA[Steven Leiva]]></dc:creator>
            <pubDate>Thu, 04 May 2017 12:07:17 GMT</pubDate>
            <atom:updated>2017-05-04T12:07:17.554Z</atom:updated>
            <content:encoded><![CDATA[<h3>Big Ideas</h3><p><strong>Folds</strong> — Folds are is a family of higher order functions that process a data structure in some order and build a return value. It is common to use folds to <em>reduce</em> a list (let’s forget about Foldable for a bit) to a single value. However, a fold doesn’t <em>have</em> to return a single value. It can return a collection, such as another list, as well. The fact that folds are higher-order functions are very important, because the reason why have higher order functions at all is to <em>take a common programming pattern and encapsulate it in a function</em>. To understand folds, and to understand foldr and foldl in particular, we need to understand the common pattern that they are abstracting.</p><p><strong>Foldr</strong> — foldr is a higher-order function in Haskell with the following type signature:</p><pre>foldr :: (a -&gt; b -&gt; b) -&gt; b -&gt; [a] -&gt; b</pre><p>The easiest way to think about foldr is that it <em>takes a list, and replace the </em><em>: operator with the given function</em>, and the empty list with the given value. For example:</p><pre>foldr (+) 0 [1, 2, 3] == (1 + 2 + 3 + 0)</pre><p>How did we get the right-hand expression?</p><p>Well, [1, 2, 3] is syntactic sugar for (1 : (2 : (3 : []))). We just said that foldr replaces the cons operator : with the given function:</p><p>(1 + (2 + (3 + [])))</p><p>And, we also said that foldr replace the empty list with the given value:</p><pre>(1 + (2 + (3 + 0)))</pre><p>Another way to think about foldr is that it takes a function. That function is a function that takes the first element of the list, and, crucially, the <em>value of having already processed the rest of the list</em>. (<strong>Note</strong>: Please see the My Thought section on foldr regarding this statement regarding foldr and laziness). For example, let’s say we wanted to implemented map in terms of foldr. That would look like this:</p><pre>myMap :: (a -&gt; b) -&gt; [a] -&gt; [b]<br>myMap f xs = foldr (\x processed -&gt; f x : processed) [] xs</pre><p>Notice the first argument to foldr. It is a function that takes the first element and the results of having already processed the list, and just processes that one element.</p><p>Finally, it is helpful to think of foldr as encapsulating the pattern</p><pre>f [] = v<br>f (x:xs) = x © f xs </pre><pre>Here, © is a function that, again, takes the first element of the list as its first argument, and the rest of the processed list as its second argument. </pre><p>This last conceptualization of foldr can best be seen by example:</p><pre>myMap :: (a -&gt; b) -&gt; [a] -&gt; [b]<br>myMap _ [] = []<br>myMap f (x:xs) = f x : myMap f xs</pre><pre>mySum :: (Num a) =&gt; [a] -&gt; a<br>mySum [] = 0<br>mySum (x:xs) = x + mySum xs</pre><pre>myProduct :: (Num a) =&gt; [a] -&gt; a <br>myProduct [] = 0<br>myProduct (x:xs) = x * myProduct xs</pre><p>myMap, mySum, and myProduct all have the same pattern, and it is this pattern that foldr is meant to encapsulate.</p><p>Finally, as a final tool, take a look at a definition for foldr:</p><pre>foldr :: (a -&gt; b -&gt; b) -&gt; b -&gt; [a] -&gt; b<br>foldr f b [] = b<br>foldr f b (x:xs) = f x (foldr f b xs)</pre><p>Notice how, when the third argument to foldr is not empty, we just pass the second argument along. That’s how that second argument ends up replacing the empty list.</p><p><strong>Folds, Traversals and Folds</strong> — Yes, folds is there twice. The big idea here is that folding happens in two stages. First, the list must be traversed. Both foldr and foldl do this traversal in the same way. After traversal, the folding function must be applied to the values in the list, and here, foldl and foldr differ. foldl uses left associativity, while foldr uses right associativity.</p><p><strong>Foldl</strong> —In my opinion, the key to understanding foldr is the what the purpose of the function argument to foldr is. I think this holds for foldl as well. The way I like to think about the function argument to foldl is that it is a function that takes the default value, the first element in the list, and returns a new default value. When the list is empty, the default value is returned.</p><p>Let’s take a look at an example by implementing myMap, but this time with foldl:</p><pre>myMap :: (a -&gt; b) -&gt; [a] -&gt; [b]<br>myMap f xs = foldl (\def x -&gt; f x : def) [] xs</pre><p>Again, the key is to figure out what the first argument to foldl should be. Again, the purpose of the function argument to foldl is to take the default value, the first value of the list (the third argument to foldl), and return a new default value.</p><p>Let’s define filter in terms of foldl.</p><pre>myFilter :: (a -&gt; Bool) -&gt; [a] -&gt; [a]<br>myFilter p xs = foldl (\def x -&gt; if f x then x : def else def) [] xs</pre><p>Again, the first argument to foldl should be a function that is all about taking a default value, the first element of the list, and then returning a new default for the process to continue with a shortened list.</p><p>How can we define foldl?</p><pre>foldl :: (b -&gt; a -&gt; b) -&gt; b -&gt; [a] -&gt; b<br>foldl _ v [] = v<br>foldl f v (x:xs) = foldl f (f v x) xs</pre><p><strong>The Argument Function to Folds</strong> — In the sections of foldr and foldr, I’ve been spending a lot of time on how to think about the first argument to these functions. To recap, with foldr, the purpose of the function argument is to take the first element of the list and the results of having folded the rest of the list, and return the new value. With foldl, the function argument takes a default value, the first element of the list, and returns a new default value. When the list is empty, that default value will be the result of the fold.</p><p>While this works for me conceptually, it can often lead to some very in-elegant code. For example, let’s we are looking at implementing and in terms of foldr:</p><pre>myAnd :: [Bool] -&gt; Bool<br>myAnd = foldr (\x processed -&gt; x &amp;&amp; processed) True</pre><p>This works, but is not pretty. However, we can see that the type of our lambda is Bool -&gt; Bool -&gt; Bool, and we can then hop over to <a href="http://hoogle.haskell.org/">hoogle.haskell.org</a> and search for a function with that signature. If we do that, we will see that &amp;&amp; already has this type signature, and it would in fact work in our case:</p><pre>myAnd :: [Bool] -&gt; Bool<br>myAnd = foldr (&amp;&amp;) True</pre><p>This is admittedly a simple example. You might have been able to deduce what the refactoring was without looking at Hoogle, but the technique is applicable in more complicated cases.</p><p><strong>Note</strong>: When using this technique, it is important to remember what <em>alpha equivalence</em> tells us about these two type signatures:</p><pre>f :: (a -&gt; b -&gt; a)<br>g :: (b -&gt; a -&gt; b)</pre><p>Remember, even though the letters used to represent the type variable are different, these two type signatures are equivalent.</p><p><strong>Folds and Default Arguments</strong> — When approaching folds, I often think first and foremost about the first argument to foldr and foldl — i.e., the function argument. However, foldr and foldr both take a second and third argument. The third argument is easy — it is the list that we want to fold over. The second argument deserves some consideration. In the case of both foldr and foldl, I consider the second argument to be the <em>default</em> result of the fold. That is, what do I want the fold to return if the list was empty. One very common way to think about it is to use a value that is, essentially, a <em>no-op</em>. For example, if we are summing a list, 0 would be a no-op, as adding 0 to anything doesn’t change its value. In the case of multiplying, 1 would be the no-op, as multiplying anything by 1 doesn’t change its value. It is important to remember that the type of the default argument and the type of the return value of the folds must be the same:</p><pre>foldr :: (a -&gt; b -&gt; b) -&gt; b -&gt; [a] -&gt; b<br>foldl :: (b -&gt; a -&gt; b) -&gt; b -&gt; [a] -&gt; b</pre><p><strong>Scans</strong> — Scans are like folds, but they return a list of all the intermediary results produced by a fold. Because scans always return a list, they are not proper <em>catamorphisms</em>. In a sense, scans are simply making a list of one of the folds, each time applying the fold to a different list. For example:</p><pre>scanl (+) 0 [1, 2]</pre><pre>[foldl (+) 0 [], foldl (+) 0 [1], foldl (+) 0 [1, 2]]</pre><h3>Terminology / Concepts</h3><p><strong>Catamorphism</strong> — A catamorphism is… I dunno.</p><h3>My Thoughts</h3><p><strong>Foldr</strong> — When I was speaking about foldr before, I was being a bit cavalier by saying that the function that is the first argument to foldr should take the first element of the list and the rest of the already processed list. Haskell is lazy, so any expression will not be evaluated unless it is actually used. Let’s take a look at an implementation of foldr again.</p><pre>foldr :: (a -&gt; b -&gt; b) -&gt; b -&gt; [a] -&gt; b<br>foldr f b [] = b<br>foldr f b (x:xs) = f x (foldr f b xs)</pre><p>If the function f has no need to evaluate it’s second argument, then the expression (foldr f b xs) will remain unevaluated. This is why foldr, unlike foldl, can deal with potentially infinite lists. For example:</p><pre>foldr const 0 [1..]</pre><p>The above expression evaluates to 1, even though the list argument is an infinite list and cannot, therefore, be <em>already evaluated</em>. If we expand that expression given the definition of foldr, we have the following expression:</p><pre>const 1 (foldr const 0 [2..])</pre><p>But const doesn’t need or evaluate its second argument, so the expression (foldr const 0 [2..]) is thrown away, essentially, by const and the value 1 is the fully reduced expression.</p><p>However, foldl make recursion of the <em>entire</em> spine of a list unconditional. Because of this, foldl is not suitable for infinite lists. In foldl, the recursion of the list is not modulated by the function argument to foldl. It is modulated — i.e., conditional on — the function argument to foldr.</p><p>Misc</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3e9e82ce5201" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Haskell Book: Chapter 9 — Lists]]></title>
            <link>https://medium.com/@StevenLeiva1/haskell-book-chapter-9-lists-cfea9e93fc86?source=rss-1d471de4a3dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/cfea9e93fc86</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[functional-programming]]></category>
            <category><![CDATA[haskell]]></category>
            <dc:creator><![CDATA[Steven Leiva]]></dc:creator>
            <pubDate>Tue, 02 May 2017 11:54:16 GMT</pubDate>
            <atom:updated>2017-05-02T11:54:16.503Z</atom:updated>
            <content:encoded><![CDATA[<h3>Big Ideas</h3><p><strong>Data Structures and Spines</strong> — When we talk about data structures in Haskell, and in particular <em>lists</em>, <em>sequences</em>, and <em>trees</em>, we talk about these data structures having a <em>spine</em>. This is the connective structure that ties the collection of values together. The spine of a structure can be evaluated separately from the values contained by the structure.</p><p><strong>List Comprehensions</strong> — List comprehensions are a way to write concise map and filter operations in one go. In the expression[x ^ 2 | x &lt;- xs, x &gt; 5], x ^ 2 is the <em>output function</em>, x &lt;- xs is the <em>generator</em>, and x &gt; 5 is the <em>predicate</em> function. Note that we can have more than one generator, and more than one predicate. <em>Nested</em> generators behave like nested loops, in that the right-most generator gets exhausted first. (Remember, there are no loops in Haskell).</p><p><strong>Weak-Head Normal Form</strong> — Weak-Head Normal Form occurs when an expression has been evaluated enough to determine the <em>data constructor</em> used in creating the value. (Remember, all data / values in Haskell have a type, and the only way to create data of a particular type is through that type’s data constructors. Therefore, all data in Haskell is created via data constructors, even if syntactic sugar hides this). Normal form is when an expression has been fully reduced. If an expression is in normal form, it must also be in weak-head normal form. The reverse is not true.</p><h3>Terminology / Concepts</h3><p><strong>Cons Cell</strong> — A cons cell is the <em>conceptual</em> space that values may inhibit.</p><p><strong>Spine</strong> —<strong> </strong>The connective structure that holds cons cells together and in place.</p><p><strong>Nullary Data Constructors</strong> — A data constructor that takes no arguments — .e.g., the data constructor False.</p><p><strong>:</strong> — : is an <em>infix data constructor</em>. It can be applied to a value of type a and a list of items of type a.</p><p><strong>Sum Type</strong> — A sum type is a type with <em>two or more </em>data constructors<em>. </em>The simplest sum type is data Bool = False | True. Notice how we use | to separate the two data constructors. This is how we know we are looking at a sum type. (Credit: <a href="https://www.schoolofhaskell.com/school/to-infinity-and-beyond/pick-of-the-week/sum-types">School of Haskell</a>)</p><p><strong>Product Type</strong> — A product type is a type with at least one data constructor which accepts <em>two or more</em> arguments. For example:</p><pre>data Fake = Lie | AlternativeFact String Int </pre><p>The type Fake has two data constructors, one of which takes two type arguments. The data constructor AlternativeFact makes the Fake datatype a product type. Notice that the values that we can create with the AlternativeType data constructor are the values of String * the values of Int, hence the name product type.</p><h3>My Thoughts</h3><p><strong>Data Structures and Spines</strong> — Spines and cells are hard to describe in abstract, so I like to think about a concrete example — lists. This mental model might have to change, but the way I like to think about it is that the spine is whatever holds two nodes of the structure together. The nodes contains the value, the spine connects the nodes. The spine can be evaluated separately from the values contained in the nodes, because we can pattern match on the spine (which will be a data constructor) and not evaluate the values contained therein. For example, if I pattern match on (_:xs), I have evaluated part of the spine, but I didn’t evaluate any values contained by the list. (Credit: <a href="https://cs.gmu.edu/~sean/lisp/cons/">About Cons Cells</a>)</p><p><strong>Implementing enumFromTo</strong> — The exercises for this book asked us to implement enumFromTo for a few different types. Here is some of the code:</p><pre>eftOrd :: Ordering -&gt; Ordering -&gt; [Ordering]<br>eftOrd = calcEnum</pre><pre>eftInt :: Int -&gt; Int -&gt; [Int]<br>eftInt = calcEnum</pre><pre>eftChar :: Char -&gt; Char -&gt; String<br>eftChar = calcEnum</pre><pre>calcEnum :: (Enum a, Ord a) =&gt; a -&gt; a -&gt; [a]</pre><p>I didn’t put in the implementation of calcEnum, but the idea is that calcEnum has a <em>more general </em>type signature than either eftOrd, eftInt, or eftChar. However, by specifying the signature of eftChar, and then making eftChar = calcEnum, we are, in a sense, making calcEnum less polymorphic. While eftChar can be applied <em>only</em> to values of type Char, calcEnum can be applied to any value whose type has an instance of Enum and Ord. This is very cool because we took something general — calcEnum — and made it more specific. This is a perfect example of why using typeclass constraints, instead of concrete types, has benefits. We can re-use the code with the typeclass constraint in many contexts. We didn’t even lose the ability to restrict the type of values that calcEnum can accept, because we can just create a type signature that we want, and point the implementation to calcEnum.</p><p><strong>Functions in Terms of Other Functions</strong> — Writing functions in terms of other functions is a common part of functional programming. We’ll often write functions that take one less argument than another function, and that simply delegates to the other function with default arguments. For example:</p><pre>myMinimumBy :: (a -&gt; a -&gt; Ordering) -&gt; [a] -&gt; a<br>myMinimumBy _ [x] = x<br>myMinimumBy f (x:x&#39;:xs)<br>  | f x x&#39; == GT = myMinimumBy f (x&#39;:xs)<br>  | otherwise    = myMinimumBy f (x:xs)</pre><pre>myMinimum :: Ord a =&gt; [a] -&gt; a<br>myMinimum = myMinimumBy compare</pre><p>In the snippet above, we have two functions, myMinimumBy and myMinimum. myMinimum is written in terms of myMinimumBy. It takes one less argument than myMinimumBy, but then delegates to myMinimumBy with the appropriate default argument. In other words, we created a more specific function from a more general one.</p><h3>Misc</h3><p><strong>Lists</strong> — Lists can serve as both a container for a fixed set of values, or as streams of infinite data.</p><p><strong>Syntactic Sugar on Lists</strong> — The expression [1, 2, 3] is simply syntactic sugar for 1 : 2 : 3 : []. Because : has the fixity infixr 5, the fully parenthesized expression is (1 : (2 : (3 : []))).</p><p><strong>Pattern Matching</strong> — As long as the data constructor is in scope, we can pattern match on all data constructors, including infix data constructors such a :.</p><p><strong>Enumeration Syntax</strong> — We can use <em>enumeration syntax</em> with values whose type has an instance of Enum.</p><p><strong>Length</strong> — The length function only has to evaluate the spine of a list, not the values contained in the list. That’s why this expression works just fine: length [1, 2, undefined]. undefined is a value in the list, and is never evaluated.</p><p><strong>Common Idioms In Haskell</strong> — In this chapter, we are exposed to a few common idioms on Haskell. For example, the function arguments to a higher-order function are often bound to the names f and g, increasing alphabetically if there are more arguments. Another idiom is to bind lists to the name xs, and use x whenever we are manipulating a value extract from the xs list. It is common to substitute n and ns if the list is a list of numbers.</p><p><strong>unzip</strong> — unzip is a function that takes a list of tuples and returns a tuple of two lists. While we can view unzip as undoing the work of zip, we have to be cognizant that we will not always get the exact same arguments to zip back. This is because information can be lost when we use zip, since it stops processing at the shortest list: unzip $ zip [1, 2] [3, 4, 5] will evaluate to ([1, 2], [3, 4]).</p><p><strong>++ vs :</strong> — Of course, it is obvious that ++ and : are two different operators. The first takes two lists of the same type and concatenates them, and the second takes a value of type a, a list of values of type a, and adds the : to the front of the list. Despite how obvious these differences are, I found myself constantly using : when I should have been using ++.</p><p><strong>Pattern Matching</strong> — We can match on multiple elements of a list. For example:</p><pre>extractTwo (x:y:xs) = ...</pre><p>The function extractTwo above will decompose a list, bind its first element to the name x, its second element to the name y, and the rest of the list to the name xs.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=cfea9e93fc86" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Haskell Book: Chapter 8 — Recursion]]></title>
            <link>https://medium.com/@StevenLeiva1/haskell-book-chapter-8-recursion-39ca8e5df60e?source=rss-1d471de4a3dd------2</link>
            <guid isPermaLink="false">https://medium.com/p/39ca8e5df60e</guid>
            <category><![CDATA[functional-programming]]></category>
            <category><![CDATA[haskell]]></category>
            <dc:creator><![CDATA[Steven Leiva]]></dc:creator>
            <pubDate>Sun, 30 Apr 2017 12:09:18 GMT</pubDate>
            <atom:updated>2017-04-30T12:09:18.399Z</atom:updated>
            <content:encoded><![CDATA[<h3>Big Ideas</h3><p><strong>Recursion — </strong>A recursive function is a function defined in terms of itself. When writing a recursive function, we must handle two cases. The first is the <strong>base case</strong>, when no further computation is needed and we can return a result. The second case is the <strong>inductive case</strong>, which occurs when further computation is in fact needed. When writing recursive functions, it is helpful to think about the base case first. It is important to keep in mind that, for any given recursive function, we might have several base / inductive cases. For example:</p><pre>fibonacci :: Integer -&gt; Integer<br>fibonacci 0 = 0<br>fibonacci 1 = 1<br>fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)</pre><p>Notice the two base cases in our definition of fibonacci above.</p><p><strong>Base Case</strong> — The base case is the case in a function in which we no longer have any further computation to do and can simply return a result. The base case is required in all recursive functions in order to prevent an infinite loop. The base case will often be an operation that doesn’t change the results. For example, in a recursive definition of sum, the base case may be adding 0.</p><p><strong>Function Composition and Recursion</strong> — Function composition is related to recursion, in that in both cases we are simply taking the results of one operation and using it as the input to another operation. The difference is that, with recursion, the “other” operation is itself, and the number of applications is determined by the inputs.</p><p><strong>Go Functions</strong> — go functions are a common idiom in Haskell. It allows us to define a local function that accepts more arguments than the top-level function.</p><h3>Terminology / Concepts</h3><p><strong>Bottom</strong> — Bottom is a term used in Haskell to refer to computations that do <strong>not</strong> successfully return a value. An infinite loop and functions that raise an error are also examples of bottom. (The Maybe datatype makes the use of bottom unnecessary).</p><h3>My Thoughts</h3><p><strong>Function Composition and Recursion</strong> — One of the more interesting ideas in this chapter is the relationship between function composition and recursion. As has already been mentioned, recursion is self-referential function composition where the number of applications is determined by the inputs. In the exercises to this chapter, the following function exemplifies this idea:</p><pre>applyTimes :: (Eq a, Num a) =&gt; a -&gt; (b -&gt; b) -&gt; b -&gt; b<br>applyTimes 0 _ b = b<br>applyTimes n f b = f (applyTimes (n - 1) f b)</pre><p>The above function is taking three arguments. First, the number of times to apply f, the function f, and the argument to use in the first application — i.e., b. We can re-write the function to make the composition more explicit:</p><pre>applyTimes&#39; :: (Eq a, Num a) =&gt; a -&gt; (b -&gt; b) -&gt; b -&gt; b<br>applyTimes&#39; 0 _ b = b<br>applyTimes&#39; n f b = f . applyTimes (n - 1) f $ b</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=39ca8e5df60e" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>