-
Notifications
You must be signed in to change notification settings - Fork 18
Expand file tree
/
Copy pathLessons-Lesson13.html
More file actions
22 lines (22 loc) · 12.2 KB
/
Lessons-Lesson13.html
File metadata and controls
22 lines (22 loc) · 12.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><meta name="viewport" content="width=device-width, initial-scale=1" /><title>Lessons.Lesson13</title><link href="linuwial.css" rel="stylesheet" type="text/css" title="Linuwial" /><link rel="stylesheet" type="text/css" href="quick-jump.css" /><link rel="stylesheet" type="text/css" href="https://fonts.googleapis.com/css?family=PT+Sans:400,400i,700" /><script src="haddock-bundle.min.js" async="async" type="text/javascript"></script><script type="text/x-mathjax-config">MathJax.Hub.Config({ tex2jax: { processClass: "mathjax", ignoreClass: ".*" } });</script><script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"></script></head><body><div id="package-header"><span class="caption empty"> </span><ul class="links" id="page-menu"><li><a href="src/Lessons.Lesson13.html">Source</a></li><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul></div><div id="content"><div id="module-header"><table class="info"><tr><th>Safe Haskell</th><td>Safe-Inferred</td></tr></table><p class="caption">Lessons.Lesson13</p></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Notes taken by Jonas Grybė</p><p>Lambda Calculus Foundations:
People wanted to formalize computations - what are computations, how do they work?
Lambda calculus emerged as a very primitive language that still allows calculation.
It's amazing because it detaches computations from physical things.</p></div></div><div id="synopsis"><details id="syn"><summary>Synopsis</summary><ul class="details-toggle" data-details-id="syn"><li class="src short"><a href="#v:e">e</a> :: <a href="Lessons-Lesson11.html#t:Expr" title="Lessons.Lesson11">Expr</a></li><li class="src short"><a href="#v:myProgram">myProgram</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram0">myProgram0</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram1">myProgram1</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram2">myProgram2</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram3">myProgram3</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram4">myProgram4</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram5">myProgram5</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram6">myProgram6</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram7">myProgram7</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram8">myProgram8</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram9">myProgram9</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram10">myProgram10</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram11">myProgram11</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram12">myProgram12</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram13">myProgram13</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li><li class="src short"><a href="#v:myProgram14">myProgram14</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer</li></ul></details></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><a id="v:e" class="def">e</a> :: <a href="Lessons-Lesson11.html#t:Expr" title="Lessons.Lesson11">Expr</a> <a href="src/Lessons.Lesson13.html#e" class="link">Source</a> <a href="#v:e" class="selflink">#</a></p></div><div class="top"><p class="src"><a id="v:myProgram" class="def">myProgram</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram" class="link">Source</a> <a href="#v:myProgram" class="selflink">#</a></p><div class="doc"><p>Original program in do-notation.
Calls restore, bind, bind with argument v, then store, bind (ignoring result), then return.</p></div></div><div class="top"><p class="src"><a id="v:myProgram0" class="def">myProgram0</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram0" class="link">Source</a> <a href="#v:myProgram0" class="selflink">#</a></p><div class="doc"><p>Step 0: Desugar do-notation into explicit bind (>>=) operators.
Shows the structure hidden by do-notation syntax.</p></div></div><div class="top"><p class="src"><a id="v:myProgram1" class="def">myProgram1</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram1" class="link">Source</a> <a href="#v:myProgram1" class="selflink">#</a></p><div class="doc"><p>Step 1: Replace method names (calculte, restore, store) with their actual implementations.
Now we see the Free constructors (Calculate, Restore, Store) explicitly.</p></div></div><div class="top"><p class="src"><a id="v:myProgram2" class="def">myProgram2</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram2" class="link">Source</a> <a href="#v:myProgram2" class="selflink">#</a></p><div class="doc"><p>Step 2: Apply the Monad instance rule: Free m >>= f = Free (fmap (>>= f) m)
The first bind gets transformed, revealing the fmap.</p></div></div><div class="top"><p class="src"><a id="v:myProgram3" class="def">myProgram3</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram3" class="link">Source</a> <a href="#v:myProgram3" class="selflink">#</a></p><div class="doc"><p>Step 3: Replace fmap with its realization from the Functor instance.
fmap f (Calculate e next) = Calculate e (a -> f (next a))</p></div></div><div class="top"><p class="src"><a id="v:myProgram4" class="def">myProgram4</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram4" class="link">Source</a> <a href="#v:myProgram4" class="selflink">#</a></p><div class="doc"><p>Step 4: Move Pure a from the end to the front as the first argument of bind.
Prepares for applying the Pure >>= f = f a rule.</p></div></div><div class="top"><p class="src"><a id="v:myProgram5" class="def">myProgram5</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram5" class="link">Source</a> <a href="#v:myProgram5" class="selflink">#</a></p><div class="doc"><p>Step 5: Apply Pure >>= f = f a rule from Monad instance.
The <code>a</code> from Calculate goes to Pure, becomes <code>r</code>, so we remove Pure and just use <code>r</code>.</p></div></div><div class="top"><p class="src"><a id="v:myProgram6" class="def">myProgram6</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram6" class="link">Source</a> <a href="#v:myProgram6" class="selflink">#</a></p><div class="doc"><p>Step 6: Deal with the second bind. Apply Free m >>= f = Free (fmap (>>= f) m).
We have Free (Restore Pure) and a function on the right.</p></div></div><div class="top"><p class="src"><a id="v:myProgram7" class="def">myProgram7</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram7" class="link">Source</a> <a href="#v:myProgram7" class="selflink">#</a></p><div class="doc"><p>Step 7: Replace fmap with the Restore realization.
fmap f (Restore next) = Restore (a -> f (next a))</p></div></div><div class="top"><p class="src"><a id="v:myProgram8" class="def">myProgram8</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram8" class="link">Source</a> <a href="#v:myProgram8" class="selflink">#</a></p><div class="doc"><p>Step 8: Apply Pure a >>= f = f a again.
The function already had name <code>v</code>, so we simplify by removing brackets.</p></div></div><div class="top"><p class="src"><a id="v:myProgram9" class="def">myProgram9</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram9" class="link">Source</a> <a href="#v:myProgram9" class="selflink">#</a></p><div class="doc"><p>Step 9: We have Free and bind again, apply the transformation rule.
Free m >>= f = Free (fmap (>>= f) m)</p></div></div><div class="top"><p class="src"><a id="v:myProgram10" class="def">myProgram10</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram10" class="link">Source</a> <a href="#v:myProgram10" class="selflink">#</a></p><div class="doc"><p>Step 10: Replace fmap with Store realization.
fmap f (Store i next) = Store i (a -> f (next a))</p></div></div><div class="top"><p class="src"><a id="v:myProgram11" class="def">myProgram11</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram11" class="link">Source</a> <a href="#v:myProgram11" class="selflink">#</a></p><div class="doc"><p>Step 11: Move Pure a to the front of bind again.
Take the argument from the end and put it in front.</p></div></div><div class="top"><p class="src"><a id="v:myProgram12" class="def">myProgram12</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram12" class="link">Source</a> <a href="#v:myProgram12" class="selflink">#</a></p><div class="doc"><p>Step 12: Apply Pure a >>= f = f a using the Monad rule.
Simplifies the bind with Pure.</p></div></div><div class="top"><p class="src"><a id="v:myProgram13" class="def">myProgram13</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram13" class="link">Source</a> <a href="#v:myProgram13" class="selflink">#</a></p><div class="doc"><p>Step 13: The <code>a</code> comes as an argument, but we ignore it (use _) and return v.
Simplify to a function with no <code>a</code>.</p></div></div><div class="top"><p class="src"><a id="v:myProgram14" class="def">myProgram14</a> :: <a href="Lessons-Lesson12.html#t:MyDomain" title="Lessons.Lesson12">MyDomain</a> Integer <a href="src/Lessons.Lesson13.html#myProgram14" class="link">Source</a> <a href="#v:myProgram14" class="selflink">#</a></p><div class="doc"><p>Step 14: Replace <code>return</code> with <code>Pure</code> (return = pure = Pure in our Monad).
Final form in continuation-passing style!
We calculate e, get result r, call Free with Restore, which gives us v,
pass to Store, ignore result, and end with Pure v signaling completion.</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.29.2</p></div></body></html>