· 6 years ago · Aug 06, 2019, 10:42 PM
1{"version":"https://jsonfeed.org/version/1","title":"Kabir Shah's Blog","home_page_url":"https://blog.kabir.sh/","feed_url":"https://blog.kabir.sh/feed.json","items":[{"id":"https://blog.kabir.sh/inventing-monads.html","url":"https://blog.kabir.sh/inventing-monads.html","title":"Inventing Monads","content_html":"<p>Monads are an esoteric concept to many, resulting in hundreds of tutorials, guides, and examples attempting to explain them. Curious developers might look into them only to find the classic answer, "Monads are monoids in the category of endofunctors". In the end, they're just another abstraction to help deal with repetitive patterns in functional code.</p>\n<p>This guide will use JavaScript instead of a pure functional programming language (e.g. Haskell) to make things more approachable for developers accustomed to imperative languages. It will, however, assume you have basic knowledge of functional programming, including currying and lambdas.</p>\n<p>Think of monads as a way to overload a semicolon. It might sound a little crazy at first, but imagine being able to override the semicolon to reduce boilerplate in specific code blocks. That's basically how monads are used in practice.</p>\n<p>As a final note before we start, I am by no means an expert on this topic. I'm fifteen years old with good knowledge of mostly high school level math, and may have missed some parts. Monads are complex and closely tied with category theory, which is a very abstract and vast branch of mathematics that can be hard to grok. If I missed something, feel free to reach out and let me know — I'm always open to learning something new.</p>\n<h2 id='blocks'>Blocks</h2>\n<p>First, many languages have a pattern that allows for creating a set of bindings and then a value based on it. In JavaScript, this is accomplished with a self-invoking function. They can also be transformed into a recursive structure of function calls with variable values. Being explicit about composing functions in this way can help clarify how exactly monads can modify the flow of a program.</p>\n<p>For example, the following block of code:</p>\n<pre><code lang='js'><span class='special'>const </span><span class='global'>middleName</span> = (() => {\n <span class='special'>const </span><span class='global'>id</span> = <span class='method'>getId </span>();\n <span class='special'>const </span><span class='global'>user</span> = <span class='method'>getUser </span>(id);\n <span class='special'>return</span> <span class='method'>getMiddleName </span>(user);\n})();\n</code></pre>\n<p>Can be represented as:</p>\n<pre><code lang='js'><span class='special'>const </span><span class='global'>apply</span> = x => f => <span class='method'>f </span>(x);\n<span class='special'>const </span><span class='global'>middleName</span> = <span class='method'>apply </span>(<span class='method'>getId</span>()) (id =>\n <span class='method'>apply </span>(<span class='method'>getUser</span>(id)) (user =>\n <span class='method'>getMiddleName</span>(user)\n )\n);\n</code></pre>\n<p>It's a dense representation, but they are equivalent. Note that functions are called with a space between the name and opening parenthesis, this isn't common syntax but it's valid JavaScript. It's there to simulate "call by juxtaposition" syntax in languages like Haskell, where functions are called with <code>f x y z</code>. But instead of calling them like you normally would in JavaScript with <code>f(x)(y)(z)</code>, we call them with <code>f (x) (y) (z)</code>.</p>\n<p>This functional version of blocks works by breaking them down into two parts:</p>\n<pre><code lang='js'><span class='special'>const </span><span class='global'>middleName</span> = (() => {\n <span class='special'>const </span><span class='global'>id</span> = <span class='method'>getId </span>();\n <span class='special'>return</span> (() => {\n <span class='special'>const </span><span class='global'>user</span> = <span class='method'>getUser </span>(id);\n <span class='special'>return</span> <span class='method'>getMiddleName </span>(user);\n })();\n})();\n</code></pre>\n<p>Instead of having everything in the same block, we define a "block" simply as a value based on a variable. In the outer block, the <code>id</code> is the variable, and the value is a function of the <code>id</code>. In this case, the value is another block, where <code>user</code> is the variable and the value is a function of the user.</p>\n<h2 id='null-everywhere'>Null Everywhere</h2>\n<p>Revisiting the previous example, the code might look like this:</p>\n<pre><code lang='js'><span class='special'>const </span><span class='global'>apply</span> = x => f => <span class='method'>f </span>(x);\n<span class='special'>const </span><span class='global'>middleName</span> = <span class='method'>apply </span>(<span class='method'>getId</span>()) (id =>\n <span class='method'>apply </span>(<span class='method'>getUser</span>(id)) (user =>\n <span class='method'>getMiddleName</span>(user)\n )\n);\n</code></pre>\n<p>It's clean enough, right? Now imagine if <code>id</code> could be <code>null</code>, <code>user</code> could be <code>null</code>, or <code>middleName</code> could be <code>null</code>. The utility functions will all end up looking like this:</p>\n<pre><code lang='js'><span class='comment'>// Simulate the fetching of an ID.</span>\n<span class='special'>const </span><span class='global'>getId</span> = () => {\n <span class='special'>const </span><span class='global'>random</span> = Math.<span class='method'>floor</span>(Math.<span class='method'>random</span>() * <span class='global'>1000</span>);\n\n <span class='special'>return</span> random < <span class='global'>700</span> ? random : <span class='global'>null</span>;\n};\n\n<span class='comment'>// Simulate the fetching of a user.</span>\n<span class='special'>const </span><span class='global'>getUser</span> = id => {\n <span class='special'>if</span> (id === <span class='global'>null</span>) {\n <span class='special'>return</span> <span class='global'>null</span>;\n } <span class='special'>else</span> {\n <span class='special'>return</span> {\n first: <span class='string'>"John"</span>,\n last: <span class='string'>"Doe"</span>,\n middle: Math.<span class='method'>random</span>() < <span class='global'>0.7</span> ? <span class='string'>"Bob"</span> : <span class='global'>null</span>\n };\n }\n};\n\n<span class='comment'>// Simulate the fetching of a middle name.</span>\n<span class='special'>const </span><span class='global'>getMiddleName</span> = user => {\n <span class='special'>if</span> (user.middle === <span class='global'>null</span>) {\n <span class='special'>return</span> <span class='global'>null</span>;\n } <span class='special'>else</span> {\n <span class='special'>return</span> user.middle;\n }\n};\n</code></pre>\n<p>Every utility function has to check and handle <code>null</code> values, and has the possibility of returning <code>null</code> as well. But what if we checked for it automatically?</p>\n<p>Once again, the functional version of the block would look like this:</p>\n<pre><code lang='js'><span class='special'>const </span><span class='global'>apply</span> = x => f => <span class='method'>f </span>(x);\n<span class='special'>const </span><span class='global'>middleName</span> = <span class='method'>apply </span>(<span class='method'>getId</span>()) (id =>\n <span class='method'>apply </span>(<span class='method'>getUser</span>(id)) (user =>\n <span class='method'>getMiddleName</span>(user)\n )\n);\n</code></pre>\n<p>Looking at this, we can find a pattern: every <code>apply</code> takes a nullable value as input and applies it to a function. This function always returns another nullable value, and by extension <code>apply</code> needs to also return a nullable value because it may be used within the function itself. Instead of handling <code>null</code> within each function, <code>apply</code> can handle it.</p>\n<pre><code lang='js'><span class='special'>const </span><span class='global'>apply</span> = x => f => x === <span class='global'>null</span> ? <span class='global'>null</span> : <span class='method'>f </span>(x);\n</code></pre>\n<p>Since the inputs can be <code>null</code>, it checks and returns <code>null</code> whenever the input is <code>null</code>. If not, it passes <code>x</code> to the function. It treats the function as a black box that can return anything, but assumes that it takes a non-null value as input. Since <code>apply</code> itself will have a nullable value as input, it handles the <code>null</code> case and then passes any real values into the function. Now, the full the code will look like this:</p>\n<pre><code lang='js'><span class='comment'>// Simulate the fetching of an ID.</span>\n<span class='special'>const </span><span class='global'>getId</span> = () => {\n <span class='special'>const </span><span class='global'>random</span> = Math.<span class='method'>floor</span>(Math.<span class='method'>random</span>() * <span class='global'>1000</span>);\n\n <span class='special'>return</span> random < <span class='global'>700</span> ? random : <span class='global'>null</span>;\n};\n\n<span class='comment'>// Simulate the fetching of a user.</span>\n<span class='special'>const </span><span class='global'>getUser</span> = id => ({\n first: <span class='string'>"John"</span>,\n last: <span class='string'>"Doe"</span>,\n middle: Math.<span class='method'>random</span>() < <span class='global'>0.7</span> ? <span class='string'>"Bob"</span> : <span class='global'>null</span>\n});\n\n<span class='comment'>// Simulate the fetching of a middle name.</span>\n<span class='special'>const </span><span class='global'>getMiddleName</span> = user => user.middle;\n\n<span class='comment'>// Get the middle name, <span class='special'>if</span> it exists.</span>\n<span class='special'>const </span><span class='global'>apply</span> = x => f => x === <span class='global'>null</span> ? <span class='global'>null</span> : <span class='method'>f </span>(x);\n<span class='special'>const </span><span class='global'>middleName</span> = <span class='method'>apply </span>(<span class='method'>getId</span>()) (id =>\n <span class='method'>apply </span>(<span class='method'>getUser</span>(id)) (user =>\n <span class='method'>getMiddleName</span>(user)\n )\n);\n\nconsole.<span class='method'>log</span>(middleName);\n<span class='comment'>// <span class='global'>49</span>% => <span class='string'>"Bob"</span>, <span class='global'>51</span>% => <span class='global'>null</span></span>\n</code></pre>\n<h2 id='logging'>Logging</h2>\n<p>Keeping the same example, let's say we want to keep track of log messages. In a functional language, you can't modify a global variable to keep track of all of the messages. Instead, each function can return an output along with a log message.</p>\n<pre><code lang='js'><span class='special'>const </span><span class='global'>getId</span> = () => [<span class='global'>7</span>, <span class='string'>"Got an id of <span class='global'>7</span>."</span>];\n<span class='special'>const </span><span class='global'>getUser</span> = id => [{\n first: <span class='string'>"John"</span>,\n last: <span class='string'>"Doe"</span>,\n middle: <span class='string'>"Bob"</span>\n}, id[<span class='global'>1</span>] + <span class='string'>" Got a user with name John Bob Doe."</span>];\n<span class='special'>const </span><span class='global'>getMiddleName</span> = user => [user[<span class='global'>0</span>].middle, user[<span class='global'>1</span>] + <span class='string'>" Got the middle name of a user."</span>];\n\n<span class='special'>const </span><span class='global'>apply</span> = x => f => <span class='method'>f </span>(x);\n<span class='special'>const </span><span class='global'>middleName</span> = <span class='method'>apply </span>(<span class='method'>getId</span>()) (id =>\n <span class='method'>apply </span>(<span class='method'>getUser</span>(id)) (user =>\n <span class='method'>getMiddleName</span>(user)\n )\n);\n</code></pre>\n<p>This is messy, and we had to modify the utility functions in order to handle the incoming array input. Instead, we can change the <code>apply</code> function to propagate the log for us. In this case, the inputs to <code>apply</code> always have the structure of <code>[output, log]</code>. However, we want the function <code>f</code> to only receive the output. Unlike the previous example, we will now assume that <code>f</code> returns the same <code>[output, log]</code> pair. Since <code>f</code> can return the output of <em>another</em> <code>apply</code>, we need to return the same type from <code>apply</code>.</p>\n<pre><code lang='js'><span class='special'>const </span><span class='global'>apply</span> = x => f => {\n <span class='special'>const </span><span class='global'>result</span> = <span class='method'>f </span>(x[<span class='global'>0</span>]);\n <span class='special'>return</span> [result[<span class='global'>0</span>], x[<span class='global'>1</span>] + <span class='string'>" "</span> + result[<span class='global'>1</span>]];\n};\n</code></pre>\n<p>Since everything has the same array type, we take it as an input. Instead of passing the log to the function though, we only pass the output of the value <code>x[0]</code> to the function <code>f</code>. We assume that this function will return its own output and log. Since this function can return the output of <code>apply</code>, we return a new pair with the function output along with the combined logs.</p>\n<p>The full code will then be much simpler, and doesn't include anything related to the previous log message in the utility functions:</p>\n<pre><code lang='js'><span class='comment'>// Get various data from a user.</span>\n<span class='special'>const </span><span class='global'>getId</span> = () => [<span class='global'>7</span>, <span class='string'>"Got an id of <span class='global'>7</span>."</span>];\n<span class='special'>const </span><span class='global'>getUser</span> = id => [{\n first: <span class='string'>"John"</span>,\n last: <span class='string'>"Doe"</span>,\n middle: <span class='string'>"Bob"</span>\n}, <span class='string'>"Got a user with name John Bob Doe."</span>];\n<span class='special'>const </span><span class='global'>getMiddleName</span> = user => [user.middle, <span class='string'>"Got the middle name of a user."</span>];\n\n<span class='comment'>// Get the middle name along with logs.</span>\n<span class='special'>const </span><span class='global'>apply</span> = x => f => {\n <span class='special'>const </span><span class='global'>result</span> = <span class='method'>f </span>(x[<span class='global'>0</span>]);\n <span class='special'>return</span> [result[<span class='global'>0</span>], x[<span class='global'>1</span>] + <span class='string'>" "</span> + result[<span class='global'>1</span>]];\n};\n<span class='special'>const </span><span class='global'>middleName</span> = <span class='method'>apply </span>(<span class='method'>getId</span>()) (id =>\n <span class='method'>apply </span>(<span class='method'>getUser</span>(id)) (user =>\n <span class='method'>getMiddleName</span>(user)\n )\n);\n\nconsole.<span class='method'>log</span>(middleName);\n<span class='comment'>// => [<span class='string'>"Bob"</span>, <span class='string'>"Got an id of <span class='global'>7</span>. Got a user with name John Bob Doe. Got the middle name of a user."</span>]</span>\n</code></pre>\n<h2 id='global-environment'>Global Environment</h2>\n<p>Let's say we have a global object fetched from somewhere, and it holds data for a user.</p>\n<pre><code lang='js'>{\n id: <span class='global'>7</span>,\n first: <span class='string'>"John"</span>,\n last: <span class='string'>"Doe"</span>\n}\n</code></pre>\n<p>Along with that, we have a calculation based on this environment.</p>\n<pre><code lang='js'><span class='special'>const </span><span class='global'>getInitials</span> = environment => environment.first[<span class='global'>0</span>] + environment.last[<span class='global'>0</span>];\n<span class='special'>const </span><span class='global'>getName</span> = initials => environment => <span class='string'>`${initials} ${environment.first} ${environment.last}`</span>;\n<span class='special'>const </span><span class='global'>getIdentity</span> = name => environment => environment.id.<span class='method'>toString</span>() + <span class='string'>" "</span> + name;\n\n<span class='special'>const </span><span class='global'>apply</span> = x => f => <span class='method'>f </span>(x);\n<span class='special'>const </span><span class='global'>identity</span> = <span class='method'>apply </span>(<span class='method'>getInitials </span>(environment)) (initials =>\n <span class='method'>apply </span>(<span class='method'>getName </span>(initials) (environment)) (name =>\n <span class='method'>getIdentity </span>(name) (environment)\n )\n);\n</code></pre>\n<p>In this case, every single function requires the <code>environment</code> as an input. What if we made that implicit?</p>\n<pre><code lang='js'><span class='special'>const </span><span class='global'>getInitials</span> = environment => environment.first[<span class='global'>0</span>] + environment.last[<span class='global'>0</span>];\n<span class='special'>const </span><span class='global'>getName</span> = initials => environment => <span class='string'>`${<span class='method'>initials </span>(environment)} ${environment.first} ${environment.last}`</span>;\n<span class='special'>const </span><span class='global'>getIdentity</span> = name => environment => environment.id.<span class='method'>toString</span>() + <span class='string'>" "</span> + <span class='method'>name </span>(environment);\n\n<span class='special'>const </span><span class='global'>apply</span> = x => f => <span class='method'>f </span>(x);\n<span class='special'>const </span><span class='global'>identity</span> = <span class='method'>apply </span>(getInitials) (initials =>\n <span class='method'>apply </span>(<span class='method'>getName </span>(initials)) (name =>\n <span class='method'>getIdentity </span>(name)\n )\n);\n</code></pre>\n<p>It looks nicer, but the utility functions had to change. They now have to call their first argument with the environment in order to get their true value. However, <code>apply</code> can make some assumptions in this case. It can assume that every input is a <em>function of the environment</em>, and every function takes a value and returns another function of the environment.</p>\n<p>We can solve this problem using <code>apply</code>. Every input <code>x</code> is a function of the environment, but it would be nice if given function <code>f</code> could expect the <em>output</em> of <code>x</code>. How can we get the output out of <code>x</code>? We need to pass it the environment, so we can return a <em>new function</em> that depends on the environment and calls <code>x</code>. Now it can pass the output to <code>f</code> as it expects. Since <code>f</code> is also a function of the environment, we can call it with our given environment and finally return the result.</p>\n<pre><code lang='js'><span class='special'>const </span><span class='global'>apply</span> = x => f => environment => <span class='method'>f </span>(<span class='method'>x </span>(environment)) (environment);\n</code></pre>\n<p>It's a little confusing, but <code>apply</code> uses the assumptions to its advantage. First of all, it returns a function of the environment. This function applies the environment to the input <code>x</code>, and passes it to <code>f</code>. Since we assume <code>f</code> returns another function of the environment, we apply it with the given environment <em>again</em> and return its output.</p>\n<p>With that, the final code looks like:</p>\n<pre><code lang='js'><span class='comment'>// Utility functions to <span class='special'>return</span> calculations based on an environment.</span>\n<span class='special'>const </span><span class='global'>getInitials</span> = environment => environment.first[<span class='global'>0</span>] + environment.last[<span class='global'>0</span>];\n<span class='special'>const </span><span class='global'>getName</span> = initials => environment => <span class='string'>`${initials} ${environment.first} ${environment.last}`</span>;\n<span class='special'>const </span><span class='global'>getIdentity</span> = name => environment => environment.id.<span class='method'>toString</span>() + <span class='string'>" "</span> + name;\n\n<span class='comment'>// Get the identity of the environment user.</span>\n<span class='special'>const </span><span class='global'>apply</span> = x => f => environment => <span class='method'>f </span>(<span class='method'>x </span>(environment)) (environment);\n<span class='special'>const </span><span class='global'>identity</span> = <span class='method'>apply </span>(getInitials) (initials =>\n <span class='method'>apply </span>(<span class='method'>getName </span>(initials)) (name =>\n <span class='method'>getIdentity </span>(name)\n )\n);\n\n<span class='comment'>// Since <span class='string'>`identity`</span> is a <span class='special'>function</span> of an environment, we can pass it any environment.</span>\nconsole.<span class='method'>log</span>(<span class='method'>identity </span>({\n id: <span class='global'>7</span>,\n first: <span class='string'>"John"</span>,\n last: <span class='string'>"Doe"</span>\n}));\n<span class='comment'>// => <span class='global'>7</span> JD John Doe</span>\n</code></pre>\n<h2 id='passing-state'>Passing State</h2>\n<p>Let's say we have a state for holding the seed of a random number generator.</p>\n<pre><code lang='js'><span class='global'>7</span>\n</code></pre>\n<p>In pure functional languages, there is no concept of mutation, only pure functions. However, for things like random number generation, there is often a seed that is kept track of as state. It needs to be sent around so that the next number and seed can be generated from it. We can write a block like this:</p>\n<pre><code lang='js'><span class='special'>const </span><span class='global'>getRandom</span> = state => {\n <span class='special'>const </span><span class='global'>result</span> = <span class='global'>7</span> * state + <span class='global'>7</span>;\n <span class='special'>return</span> [result % <span class='global'>100</span>, result];\n};\n\n<span class='special'>const </span><span class='global'>getSum</span> = x => y => state => {\n <span class='special'>const </span><span class='global'>xResult</span> = <span class='method'>x </span>(state);\n <span class='special'>const </span><span class='global'>yResult</span> = <span class='method'>y </span>(xResult[<span class='global'>1</span>]);\n <span class='special'>return</span> [xResult[<span class='global'>0</span>] + yResult[<span class='global'>0</span>], yResult[<span class='global'>1</span>]];\n};\n\n<span class='special'>const </span><span class='global'>apply</span> = x => f => <span class='method'>f </span>(x);\n<span class='special'>const </span><span class='global'>sum</span> = <span class='method'>apply </span>(getRandom) (random1 =>\n <span class='method'>apply </span>(getRandom) (random2 =>\n <span class='method'>getSum </span>(random1) (random2)\n )\n);\n</code></pre>\n<p>In this example, every value is a function of state that returns and output along with new state. It's not the best code though, because <code>getSum</code> has to call both of its arguments with the state in order to get their value, then it has to correctly manage the latest state and return it.</p>\n<p>However, <code>apply</code> can assume that every input is a <em>function of state that returns output and new state</em>. It can also assume that the function takes only an output value and returns another function of state.</p>\n<p>Using these assumptions, it would be nice if the function <code>f</code> could expect only the output portion of <code>x</code>'s return value. To get <code>x</code>'s output, we need to call it with the state, so we can return a new function of state. Within this function, we can pass <code>x</code> the state and get an output along with new state. Now we can supply <code>f</code> the output, and since <code>f</code> returns a function of state, we can call it again with the new state returned by <code>x</code>. Finally, we can return this result.</p>\n<pre><code lang='js'><span class='special'>const </span><span class='global'>apply</span> = x => f => state => {\n <span class='special'>const </span><span class='global'>result</span> = <span class='method'>x </span>(state);\n <span class='special'>return</span> <span class='method'>f </span>(result[<span class='global'>0</span>]) (result[<span class='global'>1</span>]);\n};\n</code></pre>\n<p>It's elegant, but dense. Since the output of the given function is assumed to be another function of state, <code>apply</code> starts by returning a new function of state. This function calls the input <code>x</code> with the state to get an output along with new state. It passes the output to <code>f</code>, which expects just the output of <code>x</code> as its input. Since <code>f</code> returns another function of state, it calls it again with the new state returned by <code>x</code>.</p>\n<p>The full code looks like:</p>\n<pre><code lang='js'><span class='comment'>// Utility functions <span class='special'>for</span> number manipulation.</span>\n<span class='special'>const </span><span class='global'>getRandom</span> = state => {\n <span class='special'>const </span><span class='global'>result</span> = <span class='global'>7</span> * state + <span class='global'>7</span>;\n console.<span class='method'>log</span>(<span class='string'>"Random number: "</span> + (result % <span class='global'>100</span>)); <span class='comment'>// Log random numbers <span class='special'>for</span> debugging.</span>\n <span class='special'>return</span> [result % <span class='global'>100</span>, result];\n};\n\n<span class='special'>const </span><span class='global'>getSum</span> = x => y => state => [x + y, state];\n\n<span class='comment'>// Generate the sum of two random numbers.</span>\n<span class='special'>const </span><span class='global'>apply</span> = x => f => state => {\n <span class='special'>const </span><span class='global'>result</span> = <span class='method'>x </span>(state);\n <span class='special'>return</span> <span class='method'>f </span>(result[<span class='global'>0</span>]) (result[<span class='global'>1</span>]);\n};\n\n<span class='special'>const </span><span class='global'>sum</span> = <span class='method'>apply </span>(getRandom) (random1 =>\n <span class='method'>apply </span>(getRandom) (random2 =>\n <span class='method'>getSum </span>(random1) (random2)\n )\n);\n\nconsole.<span class='method'>log</span>(<span class='method'>sum </span>(<span class='global'>7</span>));\n<span class='comment'>// => Random number: <span class='global'>56</span></span>\n<span class='comment'>// => Random number: <span class='global'>99</span></span>\n<span class='comment'>// => [<span class='global'>155</span>, <span class='global'>399</span>]</span>\n</code></pre>\n<h2 id='conclusion'>Conclusion</h2>\n<p>You'll notice how I didn't mention monads throughout the examples. That's because the code was just written using a natural abstraction, and that abstraction was the <code>apply</code> function, which applied functions that made up do-blocks in special ways. The truth is, we just implemented four different monads:</p>\n<ol>\n<li>Null Everywhere - <code>Maybe</code> Monad - Assumed <code>x: nullable</code> and <code>f: nullable -> any</code></li>\n<li>Logging - <code>Writer</code> Monad - Assumed <code>x: [any, string]</code> and <code>f: any -> [any, string]</code></li>\n<li>Global Environment - <code>Reader</code> Monad - Assumed <code>x: environment -> any</code> and <code>f: any -> environment -> any</code></li>\n<li>Passing State - <code>State</code> Monad - Assumed <code>x: state -> [any, state]</code> and <code>f: any -> state -> [any, state]</code></li>\n</ol>\n<p>The monad itself is a triple of a type constructor, a type converter, and a type combinator.</p>\n<p>The type constructor is just a way of defining the type of value that stayed constant throughout the do-blocks. For example, the <code>Maybe</code> monad type constructor returns <code>T | null</code>, and the <code>State</code> monad type constructor returns <code>state -> [output, state]</code>.</p>\n<p>The type converter is a way of creating a "unit" value of the type. For example, the <code>Writer</code> monad type converter is <code>const unit = x => [x, ""]</code>. It wraps any value within a <code>Writer</code> type that includes the value along with an empty log. We didn't cover these much to reduce the complexity of getting started.</p>\n<p>The type combinator is another name for our <code>apply</code> function, with a signature of <code>m -> (any -> m) -> m</code>. It basically means that it accepts an input with the type constructor of a monad and a function that returns the same type. Using these two, it returns an output with the same type. This is commonly named <code>bind</code>.</p>\n<p>Together, the three of these form a monad. Think of it like this: a do-block can be split into recursive <code>apply</code> calls. If we make assumptions that every input is a certain type, then <code>apply</code> can transform the input before applying it to the function. If we make assumptions that the function outputs a certain type, then <code>apply</code> can transform the output of the function to combine it with the original input. Basically, it can return whatever it wants using the given input and function. To make this even more useful, <code>apply</code> can return the same type that it assumes the function will return. This allows the function to use <code>apply</code> within itself.</p>\n<p>Some other great resources on monads include:</p>\n<ul>\n<li><a href='http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html'>You Could Have Invented Monads! (And Maybe You Already Have.)</a></li>\n<li><a href='http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html'>Functors, Applicatives, And Monads In Pictures</a></li>\n<li><a href='http://adit.io/posts/2013-06-10-three-useful-monads.html'>Three Useful Monads</a></li>\n<li><a href='https://en.wikipedia.org/wiki/Monad_(functional_programming)'>Monad (functional programming)</a></li>\n</ul>\n<p>In the end, the monad is just an abstraction that has access to the inner workings of block expressions, giving it control over how things flow from input to function.</p>\n","date_published":"2019-08-01T07:00:00.000Z"},{"id":"https://blog.kabir.sh/interval-map.html","url":"https://blog.kabir.sh/interval-map.html","title":"Interval Map","content_html":"<p>Many programs require a mathematical function capable of mapping an interval of numbers linearly onto another interval. A <code>$\\mathit{map}$</code> function maps one interval linearly onto another.</p>\n<pre><code class=\"lang-math\">\\mathit{map}(x):[a,b]\\to[c,d] \\\\\n\\mathit{map}(x) = \\frac{d - c}{b - a}(x - a) + c\n</code></pre>\n<h3 id=\"example\">Example</h3>\n<p>The interval <code>$[0, 10]$</code> can be mapped to <code>$[0, 100]$</code> using <code>$\\mathit{map}$</code>.</p>\n<pre><code class=\"lang-math\">\\begin{align}\n \\mathit{map}(x) & = 10x \\\\\n \\\\\n \\mathit{map}(0) & = 0 \\\\\n \\mathit{map}(10) & = 100\n\\end{align}\n</code></pre>\n<h3 id=\"derivation\">Derivation</h3>\n<p>The <code>$\\mathit{map}$</code> function can be thought of as a linear function that passes through the points <code>$(a,c)$</code> and <code>$(b,d)$</code>. This means that the function should map <code>$a$</code> to <code>$c$</code> and <code>$b$</code> to <code>$d$</code>.</p>\n<pre><code class=\"lang-math\">\\begin{align}\n \\mathit{map}(a) & = c \\\\\n \\mathit{map}(b) & = d\n\\end{align}\n</code></pre>\n<p>With two points the slope can be obtained and the function can be written and simplified.</p>\n<pre><code class=\"lang-math\">\\begin{align}\n \\mathit{map}(x) - c & = \\frac{d - c}{b - a}(x - a) \\\\\n \\mathit{map}(x) & = \\frac{d - c}{b - a}(x - a) + c\n\\end{align}\n</code></pre>\n<p>The function can be verified to ensure a correct mapping of <code>$a$</code> to <code>$c$</code>.</p>\n<pre><code class=\"lang-math\">\\begin{align}\n \\mathit{map}(a) &= \\frac{d - c}{b - a}(a - a) + c \\\\\n \\mathit{map}(a) &= c\n\\end{align}\n</code></pre>\n<p>The same can be done to ensure <code>$b$</code> maps to <code>$d$</code>.</p>\n<pre><code class=\"lang-math\">\\begin{align}\n \\mathit{map}(b) &= \\frac{d - c}{b - a}(b - a) + c \\\\\n \\mathit{map}(b) &= d - c + c \\\\\n \\mathit{map}(b) &= d\n\\end{align}\n</code></pre>\n","date_published":"2018-01-21T08:00:00.000Z"},{"id":"https://blog.kabir.sh/template-optimizations.html","url":"https://blog.kabir.sh/template-optimizations.html","title":"Template Optimizations","content_html":"<p>The majority of JavaScript libraries/frameworks use either templates or JSX to define a view. Templates allow for a well-defined structure, using a special syntax for binding data to the view. JSX allows for JavaScript to be used anywhere in the template, which adds a lot of power but can result in repetitive code.</p>\n<p><a href='http://moonjs.ga'>Moon</a> is a 7kb library with syntax inspired by Vue. Both Moon and Vue use a template system (although JSX can be used with Vue as well). To implement the template syntax, they have compilers that optimize the templates in different ways.</p>\n<h2 id='virtual-dom'>Virtual DOM</h2>\n<p>In the end, a compiler has the job of converting the template syntax into a function that can return a virtual DOM tree.</p>\n<p>The virtual DOM is essentially a representation of the DOM as a set of objects. This lightweight representation is important because it can be implemented as a function of the current state. Every time data in an app is updated, an entirely new version of the virtual DOM can be generated and compared with the current version.</p>\n<p>While the virtual DOM is lightweight, creating the whole tree for every render can use a lot of memory and impact performance. That is why it is important for compilers to be able to optimize templates and reuse static virtual nodes, as they do not need to be recreated on every render.</p>\n<p>The virtual DOM consists of virtual nodes, which look something like:</p>\n<pre><code lang='js'>{\n type: <span class='string'>"div"</span>, <span class='comment'>// Type of element</span>\n props: {}, <span class='comment'>// <span class='method'>Properties </span>(attributes, directives, DOM properties),</span>\n data: {}, <span class='comment'>// Internal <span class='method'>data </span>(SVG utilities, event listeners)</span>\n children: [] <span class='comment'>// Children virtual nodes</span>\n}\n</code></pre>\n<p>Moon and Vue both compare a new virtual DOM with the old one, and update the DOM with a minimum amount of transformations. They also both have different ways of creating the virtual DOM.</p>\n<p>Both provide a function to create virtual nodes. These functions are responsible for transforming a set of arguments into an object containing all of the required data for the current state of the view.</p>\n<h3 id='vue'>Vue</h3>\n<p>In Vue, a developer-friendly function is used to define a virtual DOM tree. This function is extremely flexible and can accept a variety of arguments with multiple types. This flexibility requires a normalization step at runtime.</p>\n<p>For example:</p>\n<pre><code lang='js'><span class='method'>_c</span>(\n <span class='string'>"div"</span>,\n {},\n [\n <span class='string'>"Text"</span>,\n <span class='method'>_c</span>(<span class='string'>"h1"</span>, <span class='string'>"Heading"</span>),\n <span class='method'>_c</span>(FooComponent, {\n props: {\n bar: <span class='string'>"baz"</span>\n }\n })\n ]\n);\n</code></pre>\n<h3 id='moon'>Moon</h3>\n<p>The virtual DOM utilities in Moon are more verbose and require fewer checks at runtime. Moon can allow this syntax because the compiler is meant to generate the normalized code rather than a developer.</p>\n<p>For example:</p>\n<pre><code lang='js'><span class='method'>m</span>(<span class='string'>"div"</span>, {}, {}, [\n <span class='method'>m</span>(<span class='string'>"#text"</span>, <span class='string'>"Text"</span>),\n <span class='method'>m</span>(<span class='string'>"h1"</span>, {}, {}, [<span class='method'>m</span>(<span class='string'>"#text"</span>, <span class='string'>"Heading"</span>)]),\n <span class='method'>m</span>(\n <span class='string'>"Foo"</span>,\n {\n props: {\n attrs: {\n bar: <span class='string'>"baz"</span>\n }\n }\n },\n {},\n []\n )\n]);\n</code></pre>\n<h3 id='optimizations'>Optimizations</h3>\n<p>Both Moon and Vue have ways of detecting static elements at compile time. On top of that, Moon optimizes static directives and attributes.</p>\n<p>Moon optimizes by hoisting virtual DOM nodes. Instead of returning a new virtual DOM node with a function call, static virtual nodes are cached and reused every time. When comparing this virtual DOM with the actual DOM, Moon skips static nodes because they have the same reference.</p>\n<p>It has a recursive method to detect static nodes. When a parent element is composed of all static children, the parent will be hoisted out of the render function, rather than the children.</p>\n<h2 id='static-elements'>Static Elements</h2>\n<p>Moon and Vue both detect a completely static template, and optimize by hoisting the whole virtual DOM tree out of the render function.</p>\n<h3 id='vue'>Vue</h3>\n<pre><code lang='html'><span class='method'><div</span><span class='method'>></span>\n <span class='method'><h1</span><span class='method'>></span>Static Heading<span class='method'></h1</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<pre><code lang='js'><span class='method'>_m</span>(<span class='global'>0</span>): <span class='special'>function</span> <span class='method'>anonymous</span>() {\n <span class='method'>with </span>(<span class='global'>this</span>) {\n <span class='special'>return</span> <span class='method'>_c</span>(<span class='string'>"div"</span>, [<span class='method'>_c</span>(<span class='string'>"h1"</span>, [<span class='method'>_v</span>(<span class='string'>"Static Heading"</span>)])]);\n }\n}\n\n<span class='special'>function</span> <span class='method'>render</span>() {\n <span class='method'>with </span>(<span class='global'>this</span>) {\n <span class='special'>return</span> <span class='method'>_m</span>(<span class='global'>0</span>);\n }\n}\n</code></pre>\n<p>In this case, the function <code>_m(0)</code> is created, and it returns a tree used in the render function.</p>\n<h3 id='moon'>Moon</h3>\n<pre><code lang='html'><span class='method'><div</span><span class='method'>></span>\n <span class='method'><h1</span><span class='method'>></span>Static Heading<span class='method'></h1</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<pre><code lang='js'><span class='special'>function</span> <span class='method'>render</span>(m) {\n <span class='special'>var</span> instance = <span class='global'>this</span>;\n <span class='special'>var</span> staticNodes = instance.compiledRender.staticNodes;\n\n <span class='special'>if</span> (staticNodes === <span class='global'>undefined</span>) {\n staticNodes = instance.compiledRender.staticNodes = [\n <span class='comment'>// Static root element</span>\n <span class='method'>m</span>(<span class='string'>"div"</span>, {}, {}, [<span class='method'>m</span>(<span class='string'>"h1"</span>, {}, {}, [<span class='method'>m</span>(<span class='string'>"#text"</span>, <span class='string'>"Static Heading"</span>)])])\n ];\n }\n\n <span class='special'>return</span> staticNodes[<span class='global'>0</span>]; <span class='comment'>// Cached root element</span>\n}\n</code></pre>\n<p>The most significant difference here is the prelude of the function. At the start of every render function, Moon inserts a declaration of the static nodes of that instance.</p>\n<p>First, this part checks if the <code>instance.compiledRender.staticNodes</code> array exists. If it doesn't, then Moon declares all of the static nodes in it. This initial step only happens <em>once</em>, and the static nodes will be reused on every subsequent render.</p>\n<p>In this case, Moon marks the outer <code>div</code> as static and creates it once. After the initial creation, it will always return the same virtual node from <code>staticNodes[0]</code>.</p>\n<h2 id='nested-elements'>Nested Elements</h2>\n<p>When nesting multiple elements, it is important for the compiler to hoist all of the static elements out of the render function, while only creating new nodes for the dynamic parts.</p>\n<h3 id='vue'>Vue</h3>\n<pre><code lang='html'><span class='method'><div</span><span class='method'>></span>\n <span class='method'><div</span><span class='method'>></span>\n <span class='method'><div</span><span class='method'>></span>\n <span class='method'><p</span><span class='method'>></span>Static<span class='method'></p</span><span class='method'>></span>\n <span class='method'></div</span><span class='method'>></span>\n <span class='method'><div</span><span class='method'>></span>\n <span class='method'><p</span><span class='method'>></span>Dynamic {{foo}}<span class='method'></p</span><span class='method'>></span>\n <span class='method'></div</span><span class='method'>></span>\n <span class='method'></div</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<pre><code lang='js'><span class='method'>_m</span>(<span class='global'>0</span>): <span class='special'>function</span> <span class='method'>anonymous</span>() {\n <span class='method'>with </span>(<span class='global'>this</span>) {\n <span class='special'>return</span> <span class='method'>_c</span>(<span class='string'>"div"</span>, [<span class='method'>_c</span>(<span class='string'>"p"</span>, [<span class='method'>_v</span>(<span class='string'>"Static"</span>)])]);\n }\n}\n\n<span class='special'>function</span> <span class='method'>render</span>() {\n <span class='method'>with </span>(<span class='global'>this</span>) {\n <span class='special'>return</span> <span class='method'>_c</span>(<span class='string'>"div"</span>, [\n <span class='method'>_c</span>(<span class='string'>"div"</span>, [<span class='method'>_m</span>(<span class='global'>0</span>), <span class='method'>_c</span>(<span class='string'>"div"</span>, [<span class='method'>_c</span>(<span class='string'>"p"</span>, [<span class='method'>_v</span>(<span class='string'>"Dynamic "</span> + <span class='method'>_s</span>(foo))])])])\n ]);\n }\n}\n</code></pre>\n<p>Vue optimizes the <code>div</code> containing the static paragraph by hoisting it out of the render function into <code>_m(0)</code>.</p>\n<h3 id='moon'>Moon</h3>\n<pre><code lang='html'><span class='method'><div</span><span class='method'>></span>\n <span class='method'><div</span><span class='method'>></span>\n <span class='method'><div</span><span class='method'>></span>\n <span class='method'><p</span><span class='method'>></span>Static<span class='method'></p</span><span class='method'>></span>\n <span class='method'></div</span><span class='method'>></span>\n <span class='method'><div</span><span class='method'>></span>\n <span class='method'><p</span><span class='method'>></span>Dynamic {{foo}}<span class='method'></p</span><span class='method'>></span>\n <span class='method'></div</span><span class='method'>></span>\n <span class='method'></div</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<pre><code lang='js'><span class='special'>function</span> <span class='method'>render</span>(m) {\n <span class='special'>var</span> instance = <span class='global'>this</span>;\n <span class='special'>var</span> staticNodes = instance.compiledRender.staticNodes;\n <span class='special'>var</span> foo = instance.<span class='method'>get</span>(<span class='string'>"foo"</span>);\n\n <span class='special'>if</span> (staticNodes === <span class='global'>undefined</span>) {\n staticNodes = instance.compiledRender.staticNodes = [\n <span class='method'>m</span>(<span class='string'>"div"</span>, {}, {}, [<span class='method'>m</span>(<span class='string'>"p"</span>, {}, {}, [<span class='method'>m</span>(<span class='string'>"#text"</span>, <span class='string'>"Static"</span>)])]) <span class='comment'>// Static div</span>\n ];\n }\n\n <span class='special'>return</span> <span class='method'>m</span>(<span class='string'>"div"</span>, {}, {}, [\n <span class='method'>m</span>(<span class='string'>"div"</span>, {}, {}, [\n staticNodes[<span class='global'>0</span>], <span class='comment'>// Cached div</span>\n <span class='method'>m</span>(<span class='string'>"div"</span>, {}, {}, [<span class='method'>m</span>(<span class='string'>"p"</span>, {}, {}, [<span class='method'>m</span>(<span class='string'>"#text"</span>, <span class='string'>"Dynamic "</span> + foo)])])\n ])\n ]);\n}\n</code></pre>\n<p>Moon does the same optimization by hoisting the <code>div</code> containing the static paragraph out of the render function.</p>\n<h2 id='dynamic-properties'>Dynamic Properties</h2>\n<p>Surprisingly, when given a dynamic property, Vue ignores any static elements inside of the parent element. On the other hand, Moon detects the static element and hoists it out of the render function.</p>\n<h3 id='vue'>Vue</h3>\n<pre><code lang='html'><span class='method'><div</span><span class='method'>></span>\n <span class='method'><h1</span><span class='method'>></span>Static Heading<span class='method'></h1</span><span class='method'>></span>\n <span class='method'><p</span><span class='method'>></span>Dynamic Paragraph: {{foo}}<span class='method'></p</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<pre><code lang='js'><span class='special'>function</span> <span class='method'>render</span>() {\n <span class='method'>with </span>(<span class='global'>this</span>) {\n <span class='special'>return</span> <span class='method'>_c</span>(<span class='string'>"div"</span>, [\n <span class='method'>_c</span>(<span class='string'>"h1"</span>, [<span class='method'>_v</span>(<span class='string'>"Static Heading"</span>)]),\n <span class='method'>_c</span>(<span class='string'>"p"</span>, [<span class='method'>_v</span>(<span class='string'>"Dynamic Paragraph: "</span> + <span class='method'>_s</span>(foo))])\n ]);\n }\n}\n</code></pre>\n<p>In this case, Vue did not optimize the static heading, and a new virtual node is being created and returned every time.</p>\n<h3 id='moon'>Moon</h3>\n<pre><code lang='html'><span class='method'><div</span><span class='method'>></span>\n <span class='method'><h1</span><span class='method'>></span>Static Heading<span class='method'></h1</span><span class='method'>></span>\n <span class='method'><p</span><span class='method'>></span>Dynamic Paragraph: {{foo}}<span class='method'></p</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<pre><code lang='js'><span class='special'>function</span> <span class='method'>render</span>(m) {\n <span class='special'>var</span> instance = <span class='global'>this</span>;\n <span class='special'>var</span> staticNodes = instance.compiledRender.staticNodes;\n <span class='special'>var</span> foo = instance.<span class='method'>get</span>(<span class='string'>"foo"</span>);\n\n <span class='special'>if</span> (staticNodes === <span class='global'>undefined</span>) {\n staticNodes = instance.compiledRender.staticNodes = [\n <span class='method'>m</span>(<span class='string'>"h1"</span>, {}, {}, [<span class='method'>m</span>(<span class='string'>"#text"</span>, <span class='string'>"Static Heading"</span>)]) <span class='comment'>// Static heading</span>\n ];\n }\n\n <span class='special'>return</span> <span class='method'>m</span>(<span class='string'>"div"</span>, {}, {}, [\n staticNodes[<span class='global'>0</span>], <span class='comment'>// Cached heading</span>\n <span class='method'>m</span>(<span class='string'>"p"</span>, {}, {}, [<span class='method'>m</span>(<span class='string'>"#text"</span>, <span class='string'>"Dynamic Paragraph: "</span> + foo)])\n ]);\n}\n</code></pre>\n<p>In this case, Moon detects the static <code>h1</code> and hoists it out of the render function. After this, it is cached and referenced as <code>staticNodes[0]</code>, allowing Moon to skip it when rendering.</p>\n<h2 id='dynamic-attributes'>Dynamic Attributes</h2>\n<p>When given dynamic attributes, Vue does not optimize static elements. In contrast, Moon optimizes the static children elements.</p>\n<h3 id='vue'>Vue</h3>\n<pre><code lang='html'><span class='method'><div</span><span class='method'>></span>\n <span class='method'><h1</span><span class='method'>></span>Static Heading<span class='method'></h1</span><span class='method'>></span>\n <span class='method'><p</span> <span class='global'>v-bind:foo</span>=<span undefined>"foo"</span><span class='method'>></span>Dynamic Paragraph<span class='method'></p</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<pre><code lang='js'><span class='special'>function</span> <span class='method'>render</span>() {\n <span class='method'>with </span>(<span class='global'>this</span>) {\n <span class='special'>return</span> <span class='method'>_c</span>(<span class='string'>"div"</span>, [\n <span class='method'>_c</span>(<span class='string'>"h1"</span>, [<span class='method'>_v</span>(<span class='string'>"Static Heading"</span>)]),\n <span class='method'>_c</span>(<span class='string'>"p"</span>, { attrs: { foo: foo } }, [<span class='method'>_v</span>(<span class='string'>"Dynamic Paragraph"</span>)])\n ]);\n }\n}\n</code></pre>\n<p>Here Vue does not optimize the static <code>h1</code> element or the static paragraph text element.</p>\n<h3 id='moon'>Moon</h3>\n<pre><code lang='html'><span class='method'><div</span><span class='method'>></span>\n <span class='method'><h1</span><span class='method'>></span>Static Heading<span class='method'></h1</span><span class='method'>></span>\n <span class='method'><p</span> <span class='global'>m-literal:foo</span>=<span undefined>"foo"</span><span class='method'>></span>Dynamic Paragraph<span class='method'></p</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<pre><code lang='js'><span class='special'>function</span> <span class='method'>render</span>(m) {\n <span class='special'>var</span> instance = <span class='global'>this</span>;\n <span class='special'>var</span> staticNodes = instance.compiledRender.staticNodes;\n <span class='special'>var</span> foo = instance.<span class='method'>get</span>(<span class='string'>"foo"</span>);\n\n <span class='special'>if</span> (staticNodes === <span class='global'>undefined</span>) {\n staticNodes = instance.compiledRender.staticNodes = [\n <span class='method'>m</span>(<span class='string'>"#text"</span>, <span class='string'>"Dynamic Paragraph"</span>), <span class='comment'>// Static paragraph text</span>\n <span class='method'>m</span>(<span class='string'>"h1"</span>, {}, {}, [<span class='method'>m</span>(<span class='string'>"#text"</span>, <span class='string'>"Static Heading"</span>)]) <span class='comment'>// Static heading</span>\n ];\n }\n\n <span class='special'>return</span> <span class='method'>m</span>(<span class='string'>"div"</span>, {}, {}, [\n staticNodes[<span class='global'>1</span>], <span class='comment'>// Cached heading</span>\n <span class='method'>m</span>(<span class='string'>"p"</span>, { attrs: { foo: foo } }, {}, [staticNodes[<span class='global'>0</span>]]) <span class='comment'>// Cached text</span>\n ]);\n}\n</code></pre>\n<p>Moon detects the static text of the paragraph and the static <code>h1</code> node. It hoists both elements out of the render function. When updating the DOM, these elements will be skipped because they have the same reference.</p>\n<h2 id='conditionals'>Conditionals</h2>\n<p>When conditionally rendering elements, Vue does not optimize the conditional elements at all. Moon detects static elements and hoists them out of the render function. Also, when given a static condition (although unlikely), Moon will hoist the whole condition out of the render function.</p>\n<h3 id='vue'>Vue</h3>\n<pre><code lang='html'><span class='method'><div</span><span class='method'>></span>\n <span class='method'><p</span> <span class='global'>v-if</span>=<span undefined>"fooCondition"</span><span class='method'>></span>Condition True<span class='method'></p</span><span class='method'>></span>\n <span class='method'><p</span> v-else<span class='method'>></span>Condition False<span class='method'></p</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<pre><code lang='js'><span class='special'>function</span> <span class='method'>render</span>() {\n <span class='method'>with </span>(<span class='global'>this</span>) {\n <span class='special'>return</span> <span class='method'>_c</span>(<span class='string'>"div"</span>, [\n fooCondition\n ? <span class='method'>_c</span>(<span class='string'>"p"</span>, [<span class='method'>_v</span>(<span class='string'>"Condition True"</span>)])\n : <span class='method'>_c</span>(<span class='string'>"p"</span>, [<span class='method'>_v</span>(<span class='string'>"Condition False"</span>)])\n ]);\n }\n}\n</code></pre>\n<p>Vue does not optimize by hoisting the static paragraphs and will recreate them on every render depending on <code>fooCondition</code>.</p>\n<h3 id='moon'>Moon</h3>\n<pre><code lang='html'><span class='method'><div</span><span class='method'>></span>\n <span class='method'><p</span> <span class='global'>m-if</span>=<span undefined>"fooCondition"</span><span class='method'>></span>Condition True<span class='method'></p</span><span class='method'>></span>\n <span class='method'><p</span> m-else<span class='method'>></span>Condition False<span class='method'></p</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<pre><code lang='js'><span class='special'>function</span> <span class='method'>render</span>(m) {\n <span class='special'>var</span> instance = <span class='global'>this</span>;\n <span class='special'>var</span> staticNodes = instance.compiledRender.staticNodes;\n <span class='special'>var</span> fooCondition = instance.<span class='method'>get</span>(<span class='string'>"fooCondition"</span>);\n\n <span class='special'>if</span> (staticNodes === <span class='global'>undefined</span>) {\n staticNodes = instance.compiledRender.staticNodes = [\n <span class='method'>m</span>(<span class='string'>"p"</span>, {}, {}, [<span class='method'>m</span>(<span class='string'>"#text"</span>, <span class='string'>"Condition True"</span>)]), <span class='comment'>// Static paragraph</span>\n <span class='method'>m</span>(<span class='string'>"p"</span>, {}, {}, [<span class='method'>m</span>(<span class='string'>"#text"</span>, <span class='string'>"Condition False"</span>)]) <span class='comment'>// Static paragraph</span>\n ];\n }\n\n <span class='comment'>// Cached paragraphs</span>\n <span class='special'>return</span> <span class='method'>m</span>(<span class='string'>"div"</span>, {}, {}, [fooCondition ? staticNodes[<span class='global'>0</span>] : staticNodes[<span class='global'>1</span>]]);\n}\n</code></pre>\n<p>Moon marks both paragraphs as static and hoists them out of the function in <code>staticNodes[0]</code> and <code>staticNodes[1]</code>. The function returns the same paragraphs whenever the condition is evaluated.</p>\n<h2 id='events'>Events</h2>\n<p>Lastly, Vue does not optimize on static events with <code>on</code>. This is likely done because methods and data in Vue are mutable, and they can change at any time. On the contrary, methods in Moon are immutable, and Moon's compiler can optimize them as a result.</p>\n<h3 id='vue'>Vue</h3>\n<pre><code lang='html'><span class='method'><div</span><span class='method'>></span>\n <span class='method'><button</span> <span class='global'>v-on:click</span>=<span undefined>"fooMethod"</span><span class='method'>></span><span class='method'></button</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<pre><code lang='js'><span class='special'>function</span> <span class='method'>render</span>() {\n <span class='method'>with </span>(<span class='global'>this</span>) {\n <span class='special'>return</span> <span class='method'>_c</span>(<span class='string'>"div"</span>, [\n <span class='method'>_c</span>(<span class='string'>"button"</span>, {\n on: {\n click: fooMethod\n }\n })\n ]);\n }\n}\n</code></pre>\n<p>On each render, new virtual nodes for the <code>div</code> and the <code>button</code> will be created, and Vue will update the event listeners if they changed.</p>\n<h3 id='moon'>Moon</h3>\n<pre><code lang='html'><span class='method'><div</span><span class='method'>></span>\n <span class='method'><button</span> <span class='global'>m-on:click</span>=<span undefined>"fooMethod"</span><span class='method'>></span><span class='method'></button</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<pre><code lang='js'><span class='special'>function</span> <span class='method'>render</span>(m) {\n <span class='special'>var</span> instance = <span class='global'>this</span>;\n <span class='special'>var</span> staticNodes = instance.compiledRender.staticNodes;\n <span class='special'>var</span> fooMethod = instance.methods[<span class='string'>"fooMethod"</span>];\n\n <span class='special'>if</span> (staticNodes === <span class='global'>undefined</span>) {\n staticNodes = instance.compiledRender.staticNodes = [\n <span class='method'>m</span>(<span class='string'>"div"</span>, {}, {}, [ <span class='comment'>// Static root element</span>\n <span class='method'>m</span>(\n <span class='string'>"button"</span>,\n {},\n {\n events: {\n click: [\n <span class='special'>function</span>(event) {\n <span class='method'>fooMethod</span>();\n }\n ]\n }\n },\n []\n )\n ])\n ];\n }\n\n <span class='special'>return</span> staticNodes[<span class='global'>0</span>]; <span class='comment'>// Cached root element</span>\n}\n</code></pre>\n<p>After analyzing this template, Moon detected the static root element and hoisted it out of the render function. Whenever the app is rendered, the same outer <code>div</code> will be returned every time from <code>staticNodes[0]</code>.</p>\n<h2 id='conclusion'>Conclusion</h2>\n<p>In the end, Vue only optimizes in a few test cases, in which there were static elements inside of a static parent element. However, Moon detected many of the static elements and hoisted them out of the render function so that the static virtual nodes could be reused. This also allows for the virtual DOM engine to skip over static elements because they have the same reference on every render.</p>\n","date_published":"2017-10-28T07:00:00.000Z"},{"id":"https://blog.kabir.sh/identifying-ideas.html","url":"https://blog.kabir.sh/identifying-ideas.html","title":"Identifying Ideas","content_html":"<p>Your perspective on problems is critical. Instead of treating a problem as an obstacle, it is important to treat it as an opportunity instead.</p>\n<p>People often try to come up with ideas by creating solutions <em>first</em> and then seeing what problems it solves <em>after</em>. This process is the <em>opposite</em> of how to find a plausible idea.</p>\n<p>A while ago, I began working on a web application. The code became extremely bloated, and the user interface was painfully slow. Instead of viewing this as an obstacle, I saw it as an opportunity. I set out to create a minimal, blazing fast user interface library that worked for me, and it turned into <a href='https://kbrsh.github.io/moon'>Moon</a>.</p>\n<p>It may seem like you can't find a problem with your daily life. That's because you need to change your perspective on things. A problem often won't be hard to find. Excellent ideas are always hiding in <em>plain sight</em>.</p>\n<p>These unique ideas are ones that solve a problem that a lot of people have. In hindsight, these are the types of ideas that seem the most obvious.</p>\n<p>Many creators automate tasks that they regularly encounter every day (especially developers). Attempt to find what's missing from your daily life. If there is a repetitive task that you frequently find yourself running into, ask yourself — <em>Can I automate this?</em></p>\n<p>Be aware of your surroundings. Instead of just dealing with the reality of something annoying you, <em>notice it as an opportunity</em>. Most will overlook any inefficiencies in what they do. Instead, it's crucial to see how the current situation can be improved.</p>\n<p>Question everything about the world.</p>\n<ul>\n<li><em>Why is this done like that?</em></li>\n<li><em>Why does this have to be so inefficient?</em></li>\n<li><em>Why is this step necessary?</em></li>\n</ul>\n<p>After asking enough questions like this, your brain will begin to do it automatically. You'll notice more and more problems about your life. A constant stream of ideas will start to flow through your head.</p>\n<p>A problem might seem too small to solve, but it usually isn't. A "little" problem can often be expanded or marketed to a select group of people. Don't dismiss an idea just because it seems like it only applies to you; there are almost always more individuals with the same problem.</p>\n<p>After you've found the problem, analyze it. There are multiple questions that you should ask yourself.</p>\n<ul>\n<li><em>Is there already a solution? Can it be improved?</em></li>\n<li><em>How can it be more efficient?</em></li>\n<li><em>How can a product help solve this?</em></li>\n<li><em>What makes this problem worthy of addressing?</em></li>\n</ul>\n<p>Once you start to answer these questions, you'll naturally find a solution to the problem. Your perspective of the problem changed, and it is now an opportunity for a product.</p>\n<p>After you have a relevant problem along with a solution, <em>write it down</em>. Having the solution to a problem means that you have an idea, and you should always write these down <em>no matter what</em>.</p>\n<p>Keeping track of your problems and possible solutions can help you find inspiration for even more ideas. On top of that, you'll be able to pick and choose what problem you want to solve and when you want to build it.</p>\n<p>Find problems you face and turn them into an opportunity. An idea should contribute to improving lives by solving a meaningful problem that you are passionate about addressing.</p>\n","date_published":"2017-09-30T07:00:00.000Z"},{"id":"https://blog.kabir.sh/inside-wade.html","url":"https://blog.kabir.sh/inside-wade.html","title":"Inside Wade","content_html":"<p><a href=\"https://github.com/kbrsh/wade\">Wade</a> is a 1kb Javascript search library. It allows you to search for a query through a set of documents. This query is processed, split into keywords, and then searched within an index structure.</p>\n<h2 id=\"api\">API</h2>\n<p>The API is extremely minimal and self-explanatory. It looks like:</p>\n<pre><code class=\"lang-js\">const search = Wade(\n ["Moon is fast!", "Also Slash!", "Spark too!", "Is Wade fast?"]\n);\n\nsearch("Moon");\n</code></pre>\n<h2 id=\"processor\">Processor</h2>\n<p>Wade processes all documents and queries. This works by moving each item through a separate processing function. These do the following operations:</p>\n<ul>\n<li>Make everything lowercase.\nThis helps with searching. All queries and data are made lowercase, resulting in the search being case-insensitive.</li>\n<li>Remove punctuation.\nPunctuation is usually irrelevant to the search query and does not need to be searched for.</li>\n<li>Remove stop words.\nWade has a list of stop words that are removed from all data and queries. Stop words are extra words that have little meaning or can apply to any item in the data, and removing them allows for more relevant results to be returned. These can be configured through <code>Wade.config.stopWords</code>.</li>\n</ul>\n<h3 id=\"example\">Example</h3>\n<p>When given the data:</p>\n<pre><code class=\"lang-js\">["Moon is fast!", "Slash is fast also!", "Spark is fast too!", "Is Wade fast?"]\n</code></pre>\n<p>It is processed into:</p>\n<pre><code class=\"lang-js\">["moon fast", "slash fast", "spark fast", "wade fast"]\n</code></pre>\n<p>Notice how everything is lowercase, does not contain punctuation, and does not contain stop words.</p>\n<h2 id=\"index\">Index</h2>\n<p>After processing the data, an index can be generated to allow for optimized searches within a text. This index can be generated by:</p>\n<ol>\n<li>Processing each document.</li>\n<li>Splitting each document into a multiset of terms.</li>\n<li>Generating a trie of the terms and storing the indexes of the corresponding documents containing the term.</li>\n<li>Storing the weighted significance of the term in the documents.</li>\n</ol>\n<p>A <em>set</em> is used to store multiple unique items. The <em>cardinality</em> of a set represents the amount of elements in the set.</p>\n<p>On the other hand, a <em>multiset</em> is used to store multiple items (including duplicates). The <em>multiplicity</em> of an item in a multiset is the number of instances of that item in the multiset.</p>\n<h3 id=\"significance\">Significance</h3>\n<p>Wade uses a special function to find how significant a term is to the data. This function takes various factors into account, including the length of the documents, the length of a specific document with the term, and the number of occurrences of the term.</p>\n<p>The significance of the term <code>$t$</code> in the set of documents <code>$d$</code> can be represented by the function:</p>\n<pre><code class=\"lang-math\">wm(t, d) = 1.5 - \\frac{\\sum_{i=0}^{|d|} [\\frac{\\mu(t)}{\\sum_{p \\in d_i}(\\mu(p))}]}{|d|}\n</code></pre>\n<ol>\n<li><code>$d$</code> is a set of multisets <code>$d_i$</code></li>\n<li><code>$\\exists d_i(t \\in d_i) \\lor \\nexists d_i(t \\in d_i)$</code></li>\n<li><code>$\\mu(t)$</code> is the multiplicity of <code>$t$</code> in the multiset <code>$d_i$</code></li>\n<li><code>$\\sum_{p \\in d_i}(\\mu(p))$</code> is the cardinality of the multiset <code>$d_i$</code></li>\n<li><code>$\\frac{\\mu(t)}{\\sum_{p \\in d_i}(\\mu(p))}$</code> is the ratio of occurrences of the term <code>$t$</code> in the document <code>$d_i$</code> to the total amount of terms in the document <code>$d_i$</code></li>\n</ol>\n<p>This works by finding the average of how often the term appears within a document. After this, the significance is normalized between <code>0.5</code> and <code>1.5</code>, allowing it to become higher when the average occurrence is lower. This allows for rarer terms to be amplified in significance.</p>\n<h3 id=\"example\">Example</h3>\n<p>When given the processed data:</p>\n<pre><code class=\"lang-js\">["moon fast", "slash fast", "spark fast", "wade fast"]\n</code></pre>\n<p>An index is generated:</p>\n<pre><code class=\"lang-js\">{\n "m": {\n "o": {\n "o": {\n "n": {\n "data": [\n 1.375,\n 0\n ]\n }\n }\n }\n },\n "f": {\n "a": {\n "s": {\n "t": {\n "data": [\n 1,\n 0,\n 1,\n 2,\n 3\n ]\n }\n }\n }\n },\n "s": {\n "l": {\n "a": {\n "s": {\n "h": {\n "data": [\n 1.375,\n 1\n ]\n }\n }\n }\n },\n "p": {\n "a": {\n "r": {\n "k": {\n "data": [\n 1.375,\n 2\n ]\n }\n }\n }\n }\n },\n "w": {\n "a": {\n "d": {\n "e": {\n "data": [\n 1.375,\n 3\n ]\n }\n }\n }\n }\n}\n</code></pre>\n<p>This is a map of every single character so that they can be searched through individually. At the end of a specific term, there is a <code>data</code> property. The first item in this array is the significance of the term. The other items are the indexes of the documents in which the term appears.</p>\n<p>Notice how the unique terms <code>"moon"</code>, <code>"slash"</code>, <code>"spark"</code>, and <code>"wade"</code> all have a higher weight of <code>1.375</code>. In contrast, the term <code>"fast"</code> appears in all of the documents half of the time, and has a lower weight of <code>1</code>.</p>\n<h2 id=\"search\">Search</h2>\n<p>Searching works by:</p>\n<ol>\n<li>Processing the query.</li>\n<li>Splitting the query into a multiset of terms.</li>\n<li>Searching the index for each term.</li>\n</ol>\n<p>To correctly increment the score, the relevance must be taken into account. The relevance of the term <code>$t$</code> in the query <code>$q$</code> to the set of documents <code>$d$</code> can be represented by the function:</p>\n<pre><code class=\"lang-math\">wr(t, q, d) = wm(t, d)[\\frac{1}{\\sum_{p \\in\\ q}(\\mu(p))}]\n</code></pre>\n<ol>\n<li><code>$q$</code> is a multiset</li>\n<li><code>$\\mu(p)$</code> is the multiplicity of <code>$p$</code> in the multiset <code>$q$</code></li>\n<li><code>$\\sum_{p \\in\\ q}(\\mu(p))$</code> is the cardinality of the multiset <code>$q$</code></li>\n</ol>\n<p>This can be used to represent how much each term should affect the score of the query. It works by taking <a href=\"#significance\">significance</a> of the term and the length of the query into account.</p>\n<h3 id=\"example\">Example</h3>\n<p>Let's say you are searching in real-time and have a partial query:</p>\n<pre><code>Fast S\n</code></pre><p>This is processed and split into terms:</p>\n<pre><code class=\"lang-js\">["fast", "s"]\n</code></pre>\n<p>All terms except for the last term are searched for exact matches. This means that Wade will only increment the score for documents that have the term in them.</p>\n<p>First, the term <code>"fast"</code> is searched for in the index. The process looks like:</p>\n<ol>\n<li>Check if the letter <code>"f"</code> is in the index. Set it to the current node and continue.</li>\n<li>Set the current node to the <code>"a"</code> node.</li>\n<li>Set the current node to the <code>"s"</code> node.</li>\n<li>Set the current node to the <code>"t"</code> node.</li>\n</ol>\n<p>At this point, the current node is:</p>\n<pre><code class=\"lang-js\">"t": {\n "data": [\n 1,\n 0,\n 1,\n 2,\n 3\n ]\n}\n</code></pre>\n<p>It has a <code>data</code> property, meaning that this term was present in at least one document. We store the significance (<code>1</code>), and increment the score for the indexes.</p>\n<p>In this case, the indexes are <code>[0, 1, 2, 3]</code>. The current relevance can be evaluated using the <code>$wr$</code> function by setting <code>$t$</code> to <code>"fast"</code>, <code>$q$</code> to the query, and <code>$d$</code> to the documents.</p>\n<pre><code class=\"lang-math\">wr(t, q, d) = 1(\\frac{1}{2}) = 0.5\n</code></pre>\n<p>As a result, we update the score for all documents containing the term <code>"fast"</code> by <code>0.5</code>. So far, the results are:</p>\n<pre><code class=\"lang-js\">[\n {\n index: 0,\n score: 0.5\n },\n {\n index: 1,\n score: 0.5\n },\n {\n index: 2,\n score: 0.5\n },\n {\n index: 3,\n score: 0.5\n }\n]\n</code></pre>\n<p>Next, we have the term <code>"s"</code>. This term is treated as a prefix, and every single document containing a term with the prefix <code>"s"</code> will have their score updated.</p>\n<p>After checking if <code>"s"</code> is in the index, we find the node:</p>\n<pre><code class=\"lang-js\">"s": {\n "l": {\n "a": {\n "s": {\n "h": {\n "data": [\n 1.375,\n 1\n ]\n }\n }\n }\n },\n "p": {\n "a": {\n "r": {\n "k": {\n "data": [\n 1.375,\n 2\n ]\n }\n }\n }\n }\n}\n</code></pre>\n<p>After looking through each individual node, we find <code>data</code> properties after <code>"slash"</code> and <code>"spark"</code>:</p>\n<pre><code class=\"lang-js\">// "slash"\n"h": {\n "data": [\n 1.375,\n 1\n ]\n}\n\n// "spark"\n"k": {\n "data": [\n 1.375,\n 2\n ]\n}\n</code></pre>\n<p>The relevance for the terms <code>"slash"</code> and <code>"spark"</code> can be calculated:</p>\n<pre><code class=\"lang-math\">wr(t, q, d) = 1.375(\\frac{1}{2}) = 0.6875\n</code></pre>\n<p>With this value, we can update the score for the documents containing the terms <code>"slash"</code> and <code>"spark"</code> by <code>0.6875</code>.</p>\n<p>After updating the results using the indexes, the final results are:</p>\n<pre><code class=\"lang-js\">[\n // Moon is fast!\n {\n index: 0,\n score: 0.5\n },\n\n // Slash is fast also!\n {\n index: 1,\n score: 1.1875\n },\n\n // Spark is fast too!\n {\n index: 2,\n score: 1.1875\n },\n\n // Is Wade fast?\n {\n index: 3,\n score: 0.5\n }\n]\n</code></pre>\n<p>The most relevant results were:</p>\n<pre><code>"Slash is fast also!"\n"Spark is fast too!"\n</code></pre><p>They both have a term with the prefix <code>"s"</code>, and the term <code>"fast"</code>. The rest of the results were given a lower score of <code>0.5</code> because they only had the term <code>"fast"</code> in them.</p>\n<h2 id=\"conclusion\">Conclusion</h2>\n<p>In a nutshell, Wade processes data, splits it into terms, and creates an index containing the indexes of the items along with how relevant each term is to the data. A query is also processed and split into terms. These terms are individually searched within the index and the scores are updated as needed.</p>\n<p>Wade's source is available on <a href=\"https://github.com/kbrsh/wade\">GitHub</a>.</p>\n","date_published":"2017-07-16T07:00:00.000Z"},{"id":"https://blog.kabir.sh/machine-learning.html","url":"https://blog.kabir.sh/machine-learning.html","title":"Machine Learning","content_html":"<p>Artificial Intelligence is a topic that has been attracting a lot of interest from people lately, myself included. Around a 6 months ago, I became interested in machine learning.</p>\n<p>I tried looking for information on the internet, but most of the articles I found included complex mathematic notations and often used a machine learning framework to show code samples. While the frameworks are great, I think it is just as important to know what exactly goes on under the hood.</p>\n<p>This will be a series of blog posts set to help you understand how machine learning works, with a in-depth guide and code samples. The code samples will use Python, with NumPy. NumPy allows for complex math operations to be extremely simple in code, and is not specifically for machine learning. We will be using it for matrix multiplication, dot products, etc.</p>\n<h2 id=\"what-is-machine-learning-\">What is Machine Learning?</h2>\n<p>Machine learning essentially allows for a machine to learn patterns between certain items without any of it having to be hard-coded or specified. The machine itself learns these patterns as it trains.</p>\n<p>The flexibility of machine learning allows it to be used for a variety of topics. They are used to solve problems such as <strong>classification</strong> and <strong>regression</strong> problems.</p>\n<p>I'll use an example of emails and spam to explain these two types of problems.</p>\n<p>Classification problems are problems in which an input is taken in, and it is classified into a certain group.</p>\n<p><img src=\"../img/machine-learning/classification.svg\" alt=\"Classification Visual\"></p>\n<p>Regression problems are problems in which an input is taken in, and there is an output that doesn't correspond to a group.</p>\n<p><img src=\"../img/machine-learning/regression.svg\" alt=\"Regression Visual\"></p>\n<p>There are also <strong>two main types of learning</strong> methods: supervised and unsupervised.</p>\n<p>Supervised learning is when you have a set of inputs and outputs, and you train the machine on that. Unsupervised learning is when you only have a set of inputs, and you train the machine to find patterns between them. Essentially, machine learning is the process of a machine finding the relationship between inputs and outputs.</p>\n<h2 id=\"feedforward-neural-networks\">Feedforward Neural Networks</h2>\n<p>One method of machine learning is to use a <strong>Feedforward Neural Network</strong>. They work by:</p>\n<ul>\n<li>Taking an input</li>\n<li>Multiplying the input by a certain set of weights</li>\n<li>Applying an <strong>activation function</strong></li>\n<li>Returning an output</li>\n</ul>\n<p><img src=\"../img/machine-learning/FeedForwardNeuralNetwork.svg\" alt=\"Feedforward Neural Network\"></p>\n<p>Those <strong>weights</strong> are where the magic happens. The neural network has to find the perfect set of weights to get the desired output, after starting with a random set of weights. The act of multiplying the inputs by the weights to form an output is <strong>forward propagation</strong>, as you are moving the inputs through the network. The activation function is just a function that can squash a value between a certain range, it introduces <strong>nonlinearity</strong> into the model.</p>\n<p>Throughout this article, <code>$X$</code> refers to the input, <code>$W_h$</code> refers to the weight(s), and <code>$b_h$</code> refers to the bias (we will get to this later).</p>\n<p>Let's use a simple example, with a single input, single weight, and single output. The neural network will be extremely simple:</p>\n<pre><code class=\"lang-math\">X W_h\n</code></pre>\n<p>That's it! A neural network in a simple multiplication problem, we take the input, multiply it by the weight, and get an output. Now this weight can only adapt to represent a certain <strong>feature</strong> of the relationship between the input and output, so we need to add more. To do this, we use vectors. We can use them to represent multiple inputs and outputs as well. We will still be doing the same thing, but using more numbers.</p>\n<p>Instead of multiplying, our weights and inputs can have different dimensions, so we use a <strong>dot product</strong>. Getting a dot product of a vector with another vector will lead to a new vector with the same number of rows as the first vector, and the same number of columns as the second.</p>\n<p>Basically, the dot product performs the multiplication while transforming the shape of the input into the shape of the output.</p>\n<p>Our activation function is used to make things nonlinear.</p>\n<p>With all of that, we have the basic forward propagation of a feedforward neural network, which is represented in math as:</p>\n<pre><code class=\"lang-math\">activation((X W_h) + b_h)\n</code></pre>\n<h3 id=\"back-propagation\">Back Propagation</h3>\n<p>We multiplied some numbers, so what?</p>\n<p>The output can be random if our weight is random, which means our network isn't really learning anything, it's just returning an output for each input. It doesn't adjust anything to try and improve the output to match the expected one.</p>\n<p>How can we change the output? One thing we can do is change the input itself, but we don't have control over that, so we just have to change the weights.</p>\n<p>First, we need a way to see how far off our network was. We can do that by using a <strong>loss function</strong>. We'll use the <strong>mean sum squared</strong> loss function, represented mathematically as:</p>\n<pre><code class=\"lang-math\">l(o, y) = \\sum 0.5(o - y)^2\n</code></pre>\n<p>Where <code>o</code> is the output of our network, and <code>y</code> is the target output. All this does is take the output and expected output, and gives us a representation of how far off each part in the output is. We use this function to see how good the network is performing.</p>\n<p>The goal is for our network to get the loss to equal 0, meaning the weights used map all of the inputs to the outputs correctly.</p>\n<p>You might think that the best way doing this is to try all of the possible weights until we get a good result. While that might work for extremely small networks, when you get hundreds of thousands of weights, it may take <em>years</em> to compute.</p>\n<p>Instead of that, what if we could track exactly what the weights should change by to decrease the loss? That is what a <strong>derivative</strong> is for.</p>\n<p>We can find the derivative of the loss function with respect to the weights. This allows us adjust the weights in the correct way in order to lower the loss.</p>\n<p>Let's visualize this by graphing a range of weights and their corresponding loss.</p>\n<p><img src=\"../img/machine-learning/weightToLoss.svg\" alt=\"Weight to Loss Visual\"></p>\n<p>If we find the derivative of the loss function with respect to the weights, we can find our way downhill from where we are, and move a little closer to our goal: having a loss of 0.</p>\n<p>First, let's go through an example of how a derivative works.</p>\n<p>For simplicity, let's have a simple function that takes some input <code>X</code> and returns it multiplied by a weight <code>w</code>.</p>\n<pre><code class=\"lang-math\">f(X, w) = Xw\n</code></pre>\n<p>The derivative of this function with respect to the weight is:</p>\n<pre><code class=\"lang-math\">\\frac{\\partial f}{\\partial w} = X\n</code></pre>\n<p>We need to find the effect the weight has on <code>X</code>. Let's use a weight of <code>5</code>, and an input of <code>2</code>. If we plug it into the derivative function, we get <code>2</code> as a result.</p>\n<p>That means that if we change the weights by one, then the output of the function will increase by <code>2</code>, and it does!</p>\n<p>Now, we have to do the same thing, but for our loss function, with respect to our weights. This gives us a <strong>gradient</strong> of how much our loss will <em>increase</em> based on how we change our weights. A gradient is basically the derivative of all of the inputs in a vector. All we have to do after that, is <em>decrease</em> our weights by the gradient, and we will decrease the loss!</p>\n<p>Let's find the partial derivative of the loss function with respect to some weights.</p>\n<pre><code class=\"lang-math\">\\frac{\\partial l}{\\partial w}\n</code></pre>\n<p>If we use the chain rule, we get:</p>\n<pre><code class=\"lang-math\">\\frac{\\partial l}{\\partial w} = \\frac{\\partial l}{\\partial o} * \\frac{\\partial o}{\\partial h} * \\frac{\\partial h}{\\partial w}\n</code></pre>\n<p>Let's find all parts of the equation:</p>\n<pre><code class=\"lang-math\">\\frac{\\partial l}{\\partial o} = o - y\\\\\n\\frac{\\partial o}{\\partial h} = \\frac{e^{-o}}{\\left(1\\ +e^{-o}\\right)^2}\\\\\n\\frac{\\partial h}{\\partial w} = X^\\intercal\n</code></pre>\n<p>We can multiply all of them, and we'll have the gradients! Now we'll know exactly what will happen as a result of updating our weights in a certain direction, and can push them into the direction that makes the loss function zero.</p>\n<h2 id=\"the-problem-coming-soon-\">The Problem (Coming Soon)</h2>\n<h2 id=\"the-code-coming-soon-\">The Code (Coming Soon)</h2>\n<h2 id=\"conclusion\">Conclusion</h2>\n<p>This article is a work in progress. Feel free to give any suggestions or fixes.</p>\n","date_published":"2017-04-29T07:00:00.000Z"},{"id":"https://blog.kabir.sh/introducing-moon.html","url":"https://blog.kabir.sh/introducing-moon.html","title":"Introducing Moon","content_html":"<p>I used <a href='https://vuejs.org/'>Vue</a> for a while, and it solved all of my problems beautifully. After a while, in late 2015, I began to notice some performance issues with my application. So I began to create something new, as a learning project. Hopefully to see how this DOM stuff actually works, and write a solution specifically for me.</p>\n<p>After researching how Vue works under the hood, I came across <a href='https://facebook.github.io/react/'>React</a>. It had the concept of a virtual DOM, and patching this with state updates in order to update the DOM. I also came across the fact that Vue didn’t use this idea at the time (it does now).</p>\n<p>I began writing a simple library, not meant for anyone else to use. It was a single file, with jumbled up code, attempting to make something. I just didn’t know what it was yet.</p>\n<p>After getting it to work, no matter what I did, it was <em>ridiculously slow!</em> So I gave up, and kept on using my slow implementation.</p>\n<h2 id='remake'>Remake</h2>\n<p>Later, I came across <a href='https://preactjs.com/'>Preact</a>. It was game-changing, a React alternative, that was <em>faster</em>, and only in <em>3kb!</em> I read the code, it was beautiful, easy-to-read, and I learned a lot about how a UI library actually works.</p>\n<p>So I set out to recreate what I called “Moon”. The goal was to be like Preact, but for Vue, as I preferred Vue’s API.</p>\n<h2 id='performance'>Performance</h2>\n<p>The performance of these frameworks can be so much better, but no library has it right. They all have their benefits, but still are weak in some areas. For example, library A might be good at adding items to the end of a large list, and library B might be good at adding items to the start of a large list.</p>\n<p>There’s a <a href='http://webreflection.blogspot.co.uk/2015/04/the-dom-is-not-slow-your-abstraction-is.html'>great article</a> explaining why some abstractions are slow. In a nutshell, interfacing with the DOM directly is faster than an abstraction over the DOM.</p>\n<p>Still, dealing directly with the DOM can get messy, often leading to spaghetti code if not written correctly. All libraries have their abstraction, React and Vue use a virtual DOM, the Ember team created Glimmer, and hyperHTML uses bindings between the DOM and context fragments.</p>\n<p>These all are specific to the library, each with its’ own performance benefits and weaknesses. The question is, which library should you use?</p>\n<h2 id='moon-to-the-rescue'>Moon to the Rescue</h2>\n<p>After a couple months of development, what was originally supposed to be a library for my use, was rewritten into a library ready for anyone to mess around with.</p>\n<ul>\n<li>⚡️ It uses a version of the virtual DOM, but intelligently marks static nodes\nand skips over them, and only updates the parts of the DOM that have changed.</li>\n<li>? It provides a beautiful API, <em>very similar</em> to Vue. Complete with directives,\nreactive DOM updates, computed properties, etc.</li>\n<li>? It is only <em>6kb</em>!</li>\n<li>? It has a built in component system, allowing you to compose your UI out of\ndifferent components.</li>\n</ul>\n<h3 id='benchmarks'>Benchmarks</h3>\n<p>Here are the DBMonster results (higher is better):</p>\n<ul>\n<li>Moon — 102 rerenders/second</li>\n<li>Preact — 85 rerenders/second</li>\n<li>Vue — 50 rerenders/second</li>\n<li>React — 50 rerenders/second</li>\n</ul>\n<p>Here are the results benchmarking TodoMVC implementations (lower is better):</p>\n<p><img src='../img/introducing-moon/benchmark.png' alt=''>\n<span class='caption'>Benchmark for adding 100 items, completing 100 items, and deleting 100 items</span></p>\n<h3 id='another-one-'>Another One?</h3>\n<p>I know, I know, there seems to be a new Javascript framework released every day. Moon is one of them.</p>\n<p>This doesn’t mean you have to use it, in fact, it doesn’t mean anyone has to. If you are fine with your current solution, great! Keep on grinding.</p>\n<p>If you are starting a new project, or are looking for some performance benefits, or want a nice API, feel free to try out Moon!</p>\n<h3 id='why-so-long-'>Why so Long?</h3>\n<p>Moon, an idea that started in late 2015, is now almost production ready in early 2017. Why did it take so long?</p>\n<p>Remember, Moon started as a learning project. At the time, I was looking\nto make something for myself, without all the bloated features of popular\nlibraries I <em>didn’t need</em>. I also knew nothing about the DOM.</p>\n<p>It’s amazing how much I’ve learned since then.</p>\n","date_published":"2017-03-25T07:00:00.000Z"},{"id":"https://blog.kabir.sh/centering-in-css.html","url":"https://blog.kabir.sh/centering-in-css.html","title":"Centering In CSS","content_html":"<p>Unfortunately, there is no built in support for centering in CSS, but there are some ways to do it. I will be talking about two of the most effective ways to do it.</p>\n<h3 id='flexbox'>Flexbox</h3>\n<p>Using flexbox is a clean, hack-free way to center elements. The only downside is browser support, don't use this if you need to support IE 10 and below.</p>\n<p>Say you have the following HTML:</p>\n<pre><code lang='html'><span class='method'><div</span> <span class='global'>class</span>=<span undefined>"center"</span><span class='method'>></span>\n <span class='method'><h1</span><span class='method'>></span>Centered Content<span class='method'></h1</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<p>You need to center everything <strong>within</strong> the <code>div</code>. So you would apply the following styles to the <strong>parent element</strong>. Which is <code>.center</code> in this case.</p>\n<pre><code lang='css'>.center {\n display: flex; <span class='comment'>/* activates flexbox */</span>\n align-items: center; <span class='comment'>/* align items vertically */</span>\n justify-content: center; <span class='comment'>/* align items horizontally */</span>\n}\n</code></pre>\n<h3 id='table'>Table</h3>\n<p>Using a table will require more code than flexbox, but will support many more browsers; this includes IE 6 and up!</p>\n<p>With the following HTML:</p>\n<pre><code lang='html'><span class='method'><div</span> <span class='global'>class</span>=<span undefined>"center"</span><span class='method'>></span>\n <span class='method'><div</span> <span class='global'>class</span>=<span undefined>"cell"</span><span class='method'>></span>\n <span class='method'><div</span> <span class='global'>class</span>=<span undefined>"content"</span><span class='method'>></span>\n <span class='method'><h1</span><span class='method'>></span>Centered Content<span class='method'></h1</span><span class='method'>></span>\n <span class='method'></div</span><span class='method'>></span>\n <span class='method'></div</span><span class='method'>></span>\n<span class='method'></div</span><span class='method'>></span>\n</code></pre>\n<p>You will need three containers:</p>\n<ol>\n<li>One on the outside, representing a <code>table</code></li>\n<li>A <code>cell</code> inside of of the <code>table</code>, this will be a <code>table-cell</code></li>\n<li>A container for all of the centered content</li>\n</ol>\n<p>Now, you can style them:</p>\n<pre><code lang='css'>.center {\n display: table; <span class='comment'>/* make .center a table */</span>\n}\n\n.cell {\n display: table-cell; <span class='comment'>/* make table cell */</span>\n vertical-align: middle; <span class='comment'>/* vertically align cell <span class='special'>in</span> the middle */</span>\n}\n\n.content {\n margin-left: auto; <span class='comment'>/* the content&#<span class='global'>39</span>;s left side margin is <span class='method'>auto </span>(centering it) */</span>\n margin-right: auto; <span class='comment'>/* the content&#<span class='global'>39</span>;s right side margin is <span class='method'>auto </span>(centering it) */</span>\n text-align: center; <span class='comment'>/* align any other text items <span class='special'>in</span> the center*/</span>\n <span class='comment'>/* text-align: center; is optional */</span>\n}\n</code></pre>\n<p>There, now you can center things supporting IE 6 and up.</p>\n","date_published":"2016-09-03T07:00:00.000Z"}]}