tag:blogger.com,1999:blog-7868165776819241692023-09-05T06:38:37.769-04:00Abstract NonsenseRamblings on Math and Programming by Benjamin KovachAnonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-786816577681924169.post-29636369362823712922014-01-03T10:19:00.002-05:002014-01-03T10:19:31.831-05:00I've moved!I've moved to <a href="http://5outh.github.io/">http://5outh.github.io/</a>!Anonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com0tag:blogger.com,1999:blog-786816577681924169.post-19769558794629333332013-11-13T16:13:00.003-05:002013-11-13T16:46:39.559-05:00Parsing and Negating Boolean Strings in Haskell<div style="background-color: white; margin-bottom: 5px; margin-top: 5px; padding: 0px;">
<span style="font-family: inherit;">It appears that <a href="http://www.reddit.com/r/dailyprogrammer/">the dailyprogrammer subreddit</a> is back after a pretty long hiatus, and they kicked back into gear with a really interesting problem. The problem was, paraphrasing:</span></div>
<blockquote class="tr_bq">
Given a Boolean expression as a string S, compute and print the negation of S as a string using DeMorgan's laws.</blockquote>
<a href="http://www.reddit.com/r/dailyprogrammer/comments/1qira9/111213_challenge_135_intermediate_de_morgans_law/">The problem is also detailed in full here</a>.<br />
I completed the challenge and posted my solution to reddit, but wanted to share it here as well, so here it is, with slight modifications:<br />
<br />
This is a problem that is heavily suited to three major things that Haskell advocates: Algebraic Data Types, Pattern Matching, and Monadic Parsing.<br />
<br />
First off, if you've had any experience with automata theory, it's pretty clear that the input language of Boolean expressions can be represented by a <a href="http://en.wikipedia.org/wiki/Context-free_grammar" style="color: #551a8b; text-decoration: none;">context free grammar</a>. It just so happens that Haskell makes it incredibly easy to model CFGs right out of the box using Algebraic Data Types. Let's take a look at this data type representing Boolean expressions:<br />
<br />
<script src="https://gist.github.com/5outh/7456287.js"></script><br />
<span style="font-family: inherit;">Simple. Now, the main problem of this challenge was actually performing the simplification of the not operation. Using pattern matching, we can <em>directly encode these rules</em> in the following manner:</span><br />
<br />
<script src="https://gist.github.com/5outh/7456295.js"></script><br />
<span style="font-family: inherit;">Here we're giving a literal definition of rules for negating Boolean expressions. If you use Haskell, this is really easy to read. If you don't: stare at it for a second; you'll see what it's doing! That's the brunt of the challenge, right there. That's it. Encode a Boolean expression into an <code>Expr</code> and call <code>not</code> on it, and it will spit out a new <code>Expr </code>expressing the negation of your original expression. DeMorgan's laws are represented in the <code>And</code> and <code>Or</code> rules.</span><span style="font-family: inherit;">We can also do this in a slightly modified way, using a function </span><span style="font-family: monospace;">simplify :: Expr -> </span><span style="font-family: monospace;">Expr</span><span style="font-family: inherit;"> that simplifies expressions and another function </span><span style="font-family: monospace;">not = simplify . Not</span><span style="font-family: inherit;">. Not to compute the same thing. It's a similar solution so I won't post it, but if you'd like to, feel free to experiment and/or add more simplification rules (e.g. </span><span style="font-family: monospace;">simplify e@(And a b) = if a == b then a else e</span><span style="font-family: inherit;">). </span><span style="font-family: inherit;">We can also display our expressions as a string by declaring </span><span style="font-family: monospace;">Expr</span><span style="font-family: inherit;"> an instance of Show in the following way:</span><br />
<br />
<script src="https://gist.github.com/5outh/7456324.js"></script><br />
Now we can type in Boolean expressions using our data type, <span style="font-family: monospace;">not</span> them, and print them out as nice expressions. But, now we are faced with, in my opinion, the tougher part of the challenge. We're able to actually compute everything we need to, but what about parsing a Boolean expression (as a string) into an <span style="font-family: monospace;">Expr</span>? We can use a <em>monadic parsing</em> library, namely Haskell's beloved <a href="http://www.haskell.org/haskellwiki/Parsec">Parsec</a>, to do this in a rather simple way. We'll be using Parsec's <a href="http://hackage.haskell.org/package/parsec-3.0.0/docs/Text-Parsec-Token.html">Token</a> and <a href="http://hackage.haskell.org/package/parsec-3.0.0/docs/Text-Parsec-Expr.html">Expr</a> libraries, as well as the base, in this example. Let's take a look.<br />
<br />
<script src="https://gist.github.com/5outh/7456315.js"></script><br />
<span style="font-family: inherit;">We essentially define the structure of our input here and parse it into an </span><span style="font-family: monospace;">Expr</span><span style="font-family: inherit;"> using a bunch of case-specific parsing rules. <code>variable</code> parses a single <code>char</code> into a <code>Var</code>, <code>parens</code> matches and returns a <code>SubExpr</code>, and everything else is handled by using the convenience function <code>buildExpressionParser</code> along with a list of operator strings, the types they translate to and their operator precedence. Here we're using applicative style to do our parsing, but monadic style is fine too. <a href="http://www.serpentine.com/blog/2008/02/06/the-basics-of-applicative-functors-put-to-practical-work/" style="color: #551a8b; text-decoration: none;">Check this out for more on applicative style parsing</a>.</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;">Given that, we can define a </span><span style="font-family: monospace;">main</span><span style="font-family: inherit;"> function to read in a file of expressions and output the negation of each of the expressions, like so:</span><br />
<br />
<script src="https://gist.github.com/5outh/7456330.js"></script><br />
Concise and to the point. We make sure that each line gets parsed properly, <span style="font-family: monospace;">not</span> the expressions, and print them. Here's what we get when we run the program:<br />
<pre style="margin: 10px; padding: 0px;"><code>inputs.txt --- output</code></pre>
<pre style="margin: 10px; padding: 0px;"><code>a --- <span style="background-color: white;">NOT a</span>
NOT a --- a
a AND b --- NOT a OR NOT b
NOT a AND b --- a OR NOT b
NOT (a AND b) --- a AND b
NOT (a OR b AND c) OR NOT(a AND NOT b) --- </code><span style="background-color: white;">(a OR b AND c) AND (a AND NOT b)</span></pre>
<a href="https://gist.github.com/5outh/7452588#file-demorgan-hs" style="color: #551a8b; text-decoration: none;">Finally, here's the full (40 line!) source on Github</a>!<br />
<br />
Thanks for reading.<br />
<div style="background-color: white; font-family: verdana, arial, helvetica, sans-serif; font-size: small; margin-bottom: 5px; margin-top: 5px; padding: 0px;">
<br /></div>
Anonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com2tag:blogger.com,1999:blog-786816577681924169.post-82342075498025760482013-08-27T15:50:00.004-04:002013-08-27T15:55:21.312-04:00Ludum Dare #27 (10 Seconds): A post-mortem<b>WTF is Ludum Dare?</b><br />
<a href="http://www.ludumdare.com/compo/">Ludum Dare</a> is a friendly competition among game developers to see who can make the best game based on a given theme in 48 hours. This was the 27th competition, and the theme was "10 seconds."<br />
<br />
<b>Why did I want to participate?</b><br />
For a long time, I've been looking at the game development community from the outside with a lens that I feel a lot of people tend to see through. I've always considered game development an extremely intricate and difficult field to enter, and I was scared of trying my hand at it for a long time. I have made small clones of other games (pong, sokoban, etc) and I have enjoyed making those games, but they're both relatively simple (exercise-sized, almost, to a certain extent). I have been wanting to get a little further into the game development scene for a while, and Ludum Dare seemed like the perfect opportunity. I've se<br />
en several Ludum Dare competitions go by over the past couple of years and I never thought I was good enough to actually do it. This time, I just went for it, and I'm really glad I did.<br />
<div>
<b><br /></b></div>
<b>What did you make?</b><br />
<a href="http://2.bp.blogspot.com/-C5uKdb6VMHA/Uh0CIyE4VOI/AAAAAAAAAHg/Ws8COqbSITA/s1600/25390-shot0.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="315" src="http://2.bp.blogspot.com/-C5uKdb6VMHA/Uh0CIyE4VOI/AAAAAAAAAHg/Ws8COqbSITA/s400/25390-shot0.png" width="400" /></a>When the theme "10 seconds" was announced, I had a billion and one ideas going through my head, because it's so open-ended. Everyone's first idea was to make a 10-second game, but that doesn't really work, so you had to move on to the next thing. I bounced a couple of ideas around in my head, but I ultimately decided to make a twin-stick roguelike-like because:<br />
<ol>
<li> Movement and collision detection is relatively simple to implement, and</li>
<li> As all of my friends know, I'm a big fan of <a href="http://en.wikipedia.org/wiki/The_Binding_of_Isaac_(video_game)">The Binding of Isaac</a>, and I'm always thinking about how that game and games similar in nature to it are put together.</li>
</ol>
I ended up calling my game "Wappansai!" because it was one of the random strings I stuck in as a debug message as I was developing. It doesn't mean anything other than that.<br />
<br />
Anyway, in Wappansai!, you're a big fat square ninja man who is stuck in a dungeon with some red business-men enemies. They don't move, but if you don't murder all of the enemies in the room within <b>10 seconds</b>, you die. Running into enemies also kills you, as does falling into the many pits laid out around the room. Later on, moving spike tiles get added, and those kill you as well. When you clear a room under 10 seconds, a door opens up and you move on to the next room where things get progressively more difficult. I think my high score in the final version of the game was somewhere around 17 rooms, so I definitely challenge everyone to beat that!<br />
<br />
Oh, and the tools I used were C++ and SDL 2.0, sfxr for sound bytes, and photoshop for graphics. I didn't get around to making music because I don't even know where to start with that!<br />
<br />
<b>What did you learn?</b><br />
I have been reading <a href="http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782">Programming Game AI by Example</a> on and off for a little while, and I decided to use Ludum Dare as an opportunity to start learning a little more about the <a href="http://en.wikipedia.org/wiki/State_pattern">State Design Pattern</a> and <a href="http://en.wikipedia.org/wiki/Singleton_pattern">Singletons</a>, two concepts introduced early on in that book. I worked on throwing together a shell of a program that implemented these things before the competition, so I wouldn't have to figure everything out as I was trying to get things done over the 48 hours, which was definitely a good idea. I was able to start working right when the clock started ticking instead of worrying about getting the design right as I was trying to implement the program. I'd recommend doing this if you plan to participate in a game jam; it really helped me out. That said, there were still some design pitfalls. For example, when you open chests in the game, there's a (very slim) chance that you'll get a laser gun from inside of it (usually it just takes all of your currently held items -- haha!), but the gun doesn't spawn anywhere when this happens; it just magically goes into your character's weapon slot and suddenly you're firing lasers. The way I wanted this to work was, if you got lucky and got the laser gun from the chest, the gun would spawn somewhere on the map and you could go pick it up and feel awesome that that chest that normally screws you over by stealing all of your items just happened to spawn a freakin' laser gun for you to play with. But, the way I organized my project, Tile objects had no way to modify Level objects, so I was unable to trigger an event when the chest (a type of Tile) was touched to modify the level (a Level), so I had to make a compromise there. There are certainly workarounds that I considered, but I couldn't really do them within the time limit. It was a design flaw, and now I know that it was a design flaw. I can structure my code better now -- that was one major learning point.<br />
<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; text-align: right;"><tbody>
<tr><td style="text-align: center;"><a href="http://4.bp.blogspot.com/-d2Tcd-4PCiM/Uh0CI8r_h7I/AAAAAAAAAHc/NsQtn54CdGo/s1600/25390-shot1.png" imageanchor="1" style="clear: right; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="316" src="http://4.bp.blogspot.com/-d2Tcd-4PCiM/Uh0CI8r_h7I/AAAAAAAAAHc/NsQtn54CdGo/s400/25390-shot1.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Randomly Generated...everything!</td></tr>
</tbody></table>
I also learned a lot about randomly generated content, that was crazy! It actually went a lot smoother than I thought it would, but just seeing everything so randomized was amazing. Items, weapons, enemies, pits, and walls all get generated randomly based on how many rooms you've traversed, and just seeing that in play working (relatively) nicely was so cool. So I learned a lot there.<br />
<br />
The final, really huge thing that I discovered was that...holy crap, there are a lot of assets that go into games! I must have made over 50 sprites for Wappansai!, on top of tons of different sound clips (sfxr made this easy). A lot more time went into art than I expected, and I didn't even animate anything...you don't really think about it, but games have tons and tons of assets involved.<br />
<br />
<b>Would I do it again?</b><br />
Finishing a game in two days was really hard work and it could be really frustrating at times (especially using C++ with VS, those error messages are completely incomprehensible). But, it was totally worth the effort. I can say that I've made a game that is completely mine, and even though it's not very good, it's something that<i> I</i> made and I love that I made it and I'm excited to make more things. It's also really amazing that people actually do play your games. I've had several comments on my ludum dare game's page already discussing the game that <i>I</i> made, and it's so cool to see that. Playing everyone else's games is also really awesome because you know that they went through the same thing that you did. Everyone's really proud of their work, everyone worked hard to get something done, and it's just a really nice community event that I'm so happy to have been a part of. I would absolutely do it again, and plan to!<br />
<br />
<b>Who would I recommend Ludum Dare to?</b><br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-left: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><a href="http://2.bp.blogspot.com/-D5-Ewsy8IWs/Uh0CI_MUg3I/AAAAAAAAAHY/TIYg51u7Xqc/s1600/25390-shot2.png" imageanchor="1" style="clear: right; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="316" src="http://2.bp.blogspot.com/-D5-Ewsy8IWs/Uh0CI_MUg3I/AAAAAAAAAHY/TIYg51u7Xqc/s400/25390-shot2.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">As you can see, my game had Dark Souls elements.</td></tr>
</tbody></table>
If you want to make games, do it. If you don't know where to start, there are plenty of websites that can teach you the basics, and even if you don't want/ know how to program, there are tools out there like <a href="http://www.yoyogames.com/gamemaker/studio">GameMaker Studio</a> that will allow you to program your game's logic without actually writing code. If you don't think you can do it alone, team up with someone. But if you want to make video games and have at least a basic knowledge of how they work, I think that Ludum Dare is an excellent way to test your skills and build something that you'll be proud of.<br />
<br />
<b>Where can I download your game?</b><br />
You can download, rate, and comment on <a href="http://www.ludumdare.com/compo/ludum-dare-27/?action=preview&uid=25390">Wappansai!</a> over at the <a href="http://www.ludumdare.com/compo/ludum-dare-27/?action=preview&uid=25390">Ludum Dare page</a> for it.<br />
<br />
Thanks for reading!<br />
<br />
5outhAnonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com0tag:blogger.com,1999:blog-786816577681924169.post-21102758852921320072013-05-01T12:27:00.000-04:002013-05-02T10:48:37.485-04:00Symbolic Calculus in Haskell<h3>
Motivation</h3>
It's relatively simple to write a program to approximate derivatives. We simply look at the limit definition of a derivative:<br />
<br />
$$ \frac{d}{dx} f(x) = \lim_{h \rightarrow 0} \frac{f(x+h) - f(x)}{h} $$<br />
<br />
and choose some small decimal number to use for $h$ instead of calculating the limit of the function as it goes to $0$. Generally, this works pretty well. We get good approximations as long as $h$ is small enough. However, these approximations are not quite exact, and they can only be evaluated at specific points (for example, we can find $\frac{d}{dx}f(5)$, but not the actual symbolic function). So, what if we want to know what $\frac{d}{dx}f(x)$ is <i>for all x</i>? Calculating derivatives with this approximation method won't do the trick for us -- we'll need something a little more powerful, which is what we will build in this post.<br />
<br />
Admittedly, this idea didn't come to me through necessity of such a system; I was just curious. It ended up being pretty enlightening, and it's amazing how simple Haskell makes this type of thing. Most of the code in this post didn't take too long to write, it's relatively short (only 108 lines total, including whitespace) and has a lot of capability.<br />
<br />
With that, let's get started!<br />
<br />
<h3>
The Data Type</h3>
<div>
I don't want to over-complicate the process of taking derivatives, so my data type for algebraic expressions is kept minimal.<br />
<br />
We support six different types of expressions:</div>
<div>
<ul>
<li>Variables (denoted by a single character)</li>
<li>Constant values</li>
<li>Addition</li>
<li>Multiplication</li>
<li>Exponentiation</li>
<li>Division</li>
</ul>
<div>
This can be expanded upon, but this is adequate for the purpose of demonstration.</div>
</div>
<div>
<br /></div>
<div>
Here is our <span style="font-family: Courier New, Courier, monospace;">Expr a</span> type, with a sample expression representing $3x^2$:</div>
<div>
<br /></div>
<script src="https://gist.github.com/5outh/5490739.js"></script><br />
<span style="font-family: inherit;">Haskell allows infix operators to act as data constructors, which allows us to express algebraic expressions cleanly and concisely without too much mental parsing. Also note that, since we explicitly defined operator precedence above the data type declaration, we can write expressions without parentheses according to order of operations, like we did in the sample expression.</span><br />
<br />
<h3>
The Algebra</h3>
Taking derivatives simply by the rules can get messy, so we might as well go ahead and set up an algebra simplification function that cleans up our final expressions for us. This is actually incredibly simple. As long as you know algebraic laws, this kind of thing basically writes itself in Haskell. We just need to pattern match against certain expressions and meld them together according to algebraic law.<br />
<br />
This function ends up being lengthy long due to the fact that symbolic manipulation is mostly just a bunch of different cases, but we can encode algebraic simplification rules for our above data type in a straightforward way.<br />
<br />
The following <span style="font-family: Courier New, Courier, monospace;">simplify</span><span style="font-family: inherit;"> </span>function takes an expression and spits out a simpler one that means the same thing. It's really just a bunch of pattern-matching cases, so feel free to skim it.<br />
<br />
<script src="https://gist.github.com/5outh/5490732.js"></script><br />
I've also included a <span style="font-family: Courier New, Courier, monospace;">fullSimplify</span> function that runs <span style="font-family: Courier New, Courier, monospace;">simplify</span> on an expression until the current input matches the last output of <span style="font-family: "Courier New",Courier,monospace;">simplify</span> (which ensures an expression is completely simplified)*. Note that in the <span style="font-family: Courier New, Courier, monospace;">simplify</span> function, I've covered a lot of bases, but not all of them. Specifically, division simplification is lacking because it gets complicated quickly and I didn't want to focus on that in this blog post.<br />
<br />
We should also note that we don't have a data type expressing subtraction or negative numbers, so we'll deal with that now. In order to express the negation of expressions, we define the <span style="font-family: Courier New, Courier, monospace;">negate'</span> function, which basically multiplies expressions by $-1$ and outputs the resultant expression.<br />
<br />
<script src="https://gist.github.com/5outh/5490816.js"></script><br />
Now we have a relatively robust system for computing symbolic expressions. However, we aren't able to actually plug anything into these expressions yet, so we'll fix that now.<br />
<br />
<i>*Thanks to zoells on Reddit for the suggestion!</i><br />
<h3>
Evaluating Expressions</h3>
The first thing we'll need to do to begin the process of evaluating expressions is write a function to plug in a value for a specific variable. We do this in terms of a function called <span style="font-family: Courier New, Courier, monospace;">mapVar</span>, implemented as follows:<br />
<br />
<script src="https://gist.github.com/5outh/5490833.js"></script><br />
<span style="font-family: Courier New, Courier, monospace;">mapVar</span> searches through an expression for a specific variable and performs a function on each instance of that variable in the function. <span style="font-family: Courier New, Courier, monospace;">plugIn</span> takes a character and a value, and is defined using <span style="font-family: Courier New, Courier, monospace;">mapVar</span> to map variables with a specific name to a constant provided by the user.<br />
<br />
Now that we have <span style="font-family: Courier New, Courier, monospace;">plugIn</span>, we can define two functions: One that takes an expression full of only constants and outputs a result (<span style="font-family: Courier New, Courier, monospace;">evalExpr'</span>), and one that will replace a single variable with a constant and output the result (<span style="font-family: Courier New, Courier, monospace;">evalExpr</span>):<br />
<br />
<script src="https://gist.github.com/5outh/5490842.js"></script><br />
What we're doing here is simple. With <span style="font-family: Courier New, Courier, monospace;">evalExpr'</span>, we only need to replace our functional types (<span style="font-family: Courier New, Courier, monospace;">:+:</span>, <span style="font-family: Courier New, Courier, monospace;">:*:</span>, etc) with the actual functions (<span style="font-family: Courier New, Courier, monospace;">+</span>, <span style="font-family: Courier New, Courier, monospace;">*</span>, etc). When we run into a <span style="font-family: Courier New, Courier, monospace;">Const</span>, we simply replace it with it's inner number value. When we run into a <span style="font-family: Courier New, Courier, monospace;">Var</span>, we note that it's not possible to evaluate, and tell the user that there is still a variable in the expression that needs to be plugged in.<br />
<br />
With <span style="font-family: Courier New, Courier, monospace;">evalExpr</span>, we just plug in a value for a specific variable before evaluating the expression. Simple as that!<br />
<br />
Here are some examples of expressions and their evaluations:<br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;"><br /></span>
<span style="color: blue; font-family: 'Courier New', Courier, monospace;">*Main></span><span style="font-family: 'Courier New', Courier, monospace;"> evalExpr 'x' 2 (Var 'x')</span><br />
<span style="font-family: Courier New, Courier, monospace;">2.0</span><br />
<span style="font-family: Courier New, Courier, monospace;"><span style="color: blue;">*Main></span> evalExpr 'a' 3 (Const 3 :+: Var 'a' :*: Const 6)</span><br />
<span style="font-family: Courier New, Courier, monospace;">21.0</span><br />
<span style="font-family: Courier New, Courier, monospace;"><span style="color: blue;">*Main></span> evalExpr 'b' 2 (Var 'b' :/: (Const 2 :*: Var 'b'))</span><br />
<span style="font-family: Courier New, Courier, monospace;">0.5</span><br />
<br />
We can even evaluate multivariate expressions using <span style="font-family: Courier New, Courier, monospace;">plugIn</span>:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;"><span style="color: blue;">*Main></span> evalExpr' . plugIn 'x' 1 $ plugIn 'y' 2 (Var 'x' :+: Var 'y')</span><br />
<span style="font-family: Courier New, Courier, monospace;">3.0</span><br />
<br />
Now that we've extended our symbolic expressions to be able to be evaluated, let's do what we set out to do -- find derivatives!<br />
<br />
<h3>
Derivatives</h3>
We aren't going to get into super-complicated derivatives involving logorithmic or implicit differentiation, etc. Instead, we'll keep it simple for now, and only adhere to some of the 'simple' derivative rules. We'll need one of them for each of our six expression types: constants, variables, addition, multiplication, division, and exponentiation. We already know the following laws for these from calculus:<br />
<br />
Differentiation of a constant: $\frac{d}{dx}k = 0$<br />
<br />
Differentiation of a variable: $\frac{d}{dx}x = 1$<br />
<br />
Addition differentiation: $\frac{d}{dx}\left(f(x) + g(x)\right) = \frac{d}{dx}f(x) +\frac{d}{dx}g(x)$<br />
<br />
Power rule (/chain rule): $\frac{d}{dx}f(x)^n = nf(x)^{n-1} \cdot \frac{d}{dx}f(x)$<br />
<br />
Product rule: $\frac{d}{dx}\left(f(x) \cdot g(x)\right) = \frac{d}{dx}f(x) \cdot g(x) + f(x) \cdot \frac{d}{dx}g(x)$<br />
<br />
Quotient rule: $\frac{d}{dx}\frac{f(x)}{g(x)} = \frac{\frac{d}{dx}f(x) \cdot g(x) - \frac{d}{dx}g(x) \cdot f(x)}{g(x)^2}$<br />
<br />
As it turns out, we can almost directly represent this in Haskell. There should be no surprises here -- following along with the above rules, it is relatively easy to see how this function calculates derivatives. We will still error out if we get something like $x^x$ as input, as it will require a technique we haven't implemented yet. However, this will suffice for a many different expressions.<br />
<br />
<script src="https://gist.github.com/5outh/5490810.js"></script><br />
So, what can we do with this? Well, let's take a look:<br />
<br />
<script src="https://gist.github.com/5outh/5491555.js"></script><br />
The first, most obvious thing we'll note when running the derivative function on an expression is that what it produces is rather ugly. To fix this, we'll write a function <span style="font-family: Courier New, Courier, monospace;">ddx</span> that will simplify the derivative expression three times to make our output cleaner.<br />
<br />
(Remember <span style="font-family: Courier New, Courier, monospace;">sampleExpr</span> = $3x^2$)<br />
<br />
<span style="font-family: Courier New, Courier, monospace;"><span style="color: blue;">*Main></span> derivative sampleExpr</span><br />
<span style="font-family: Courier New, Courier, monospace;">Const 3.0 :*: ((Const 2.0 :*: Var 'x' :^: Const 1.0) :*: Const 1.0) :+: Var 'x' :^: Const 2.0 :*: Const 0.0</span><br />
<span style="font-family: Courier New, Courier, monospace;"><span style="color: blue;">*Main></span> ddx sampleExpr</span><br />
<span style="font-family: Courier New, Courier, monospace;">Const 6.0 :*: Var 'x' -- 6x</span><br />
<br />
Another thing we can do is get a list of derivatives. The <span style="font-family: Courier New, Courier, monospace;">iterate</span> method from the <span style="font-family: Courier New, Courier, monospace;">Prelude</span> suits this type of thing perfectly -- we can generate a (infinite!) list of derivatives of a function just by calling <span style="font-family: Courier New, Courier, monospace;">iterate ddx</span>. Simple, expressive, and incredibly powerful.<br />
<br />
<span style="font-family: Courier New, Courier, monospace;"><span style="color: blue;">*Main></span> take 3 $ ddxs sampleExpr</span><br />
<span style="font-family: Courier New, Courier, monospace;">[Const 3.0 :*: Var 'x' :^: Const 2.0,Const 6.0 :*: Var 'x',Const 6.0] </span><span style="font-family: 'Courier New', Courier, monospace;">-- [3x^2, 6x, 6]</span><br />
<span style="color: blue; font-family: 'Courier New', Courier, monospace;">*Main></span><span style="font-family: 'Courier New', Courier, monospace;"> let ds = take 4 $ ddxs sampleExpr</span><br />
<span style="font-family: Courier New, Courier, monospace;"><span style="color: blue;">*Main></span> fmap (evalExpr 'x' 2) ds</span><br />
<span style="font-family: Courier New, Courier, monospace;">[12.0,12.0,6.0,0.0]</span><br />
<br />
We're also able to grab the $n^{th}$ derivative of an expression. We could simply grab the $n^{th}$ term of <span style="font-family: Courier New, Courier, monospace;">ddxs</span>, but we'll do it without the wasted memory by repeatedly composing <span style="font-family: Courier New, Courier, monospace;">ddx</span> $n$ times using <span style="font-family: Courier New, Courier, monospace;">foldr1</span> and <span style="font-family: Courier New, Courier, monospace;">replicate</span>.<br />
<br />
<span style="font-family: Courier New, Courier, monospace;"><span style="color: blue;">*Main></span> nthDerivative 2 sampleExpr</span><br />
<span style="font-family: Courier New, Courier, monospace;">Const 6.0</span><br />
<br />
<span style="font-family: inherit;">There's one last thing I want to touch on. Since it's so simple to generate a list of derivatives of a function, why not use that to build functions' Taylor series expansions?</span><br />
<br />
<h3>
Taylor Series Expansions</h3>
The Taylor series expansion of a function $f(x)$ about $a$ is defined as follows:<br />
<br />
$$ \sum_{n=1}^{\infty} \frac{f^{(n)}(a)}{n!} \cdot (x - a)^n $$<br />
<br />
The Maclaurin series expansion for a function is the Taylor series of a function with a = 0, and we will also implement that.<br />
<br />
Given that we can:<br />
<ul>
<li>Have multivariate expressions</li>
<li>Easily generate a list of derivatives</li>
</ul>
<div>
We can actually find the Taylor series expansion of a function easily. Again, we can almost directly implement this function in Haskell, and evaluating it is no more difficult.</div>
<br />
<script src="https://gist.github.com/5outh/5490857.js"></script><br />
To produce a Taylor series, we need a couple of things:<br />
<ul>
<li>A list of derivatives</li>
<li>A list of indices</li>
<li>A list of factorials</li>
</ul>
<div>
We create these three things in <span style="font-family: Courier New, Courier, monospace;">where</span> clauses in the <span style="font-family: Courier New, Courier, monospace;">taylor</span> declaration. indices are simple, <span style="font-family: Courier New, Courier, monospace;">derivs</span> calculates a list of derivatives (using <span style="font-family: Courier New, Courier, monospace;">mapVar</span> again to change all variables into $a$s), and <span style="font-family: Courier New, Courier, monospace;">facts</span> contains our factorials wrapped in <span style="font-family: Courier New, Courier, monospace;">Const</span>s. We generate a list of <span style="font-family: Courier New, Courier, monospace;">(expression, index)</span>s in <span style="font-family: Courier New, Courier, monospace;">exprs</span>, and then map the "gluing" function <span style="font-family: Courier New, Courier, monospace;">series</span> over <span style="font-family: Courier New, Courier, monospace;">exprs</span> to produce a list of expressions in the series expansion. We then <span style="font-family: Courier New, Courier, monospace;">fmap superSimplify </span>over the list in order to simplify down our expressions, and we get back a list of Taylor series terms for the given expression. The Maclaurin expansion can be defined as mentioned above in terms of the Taylor series, and again, we basically directly encode it (though we do have to re-simplify our expressions due to the plugging in of a variable).<br />
<br />
Let's take a look at the Taylor expansion for $f(x) = x$. We note that:<br />
<br />
$f(a) = a$<br />
$f'(a) = 1$<br />
$f''(a) = 0$<br />
<br />
And the rest of the derivatives will be 0. So our Taylor series terms $T_n$ should look something like:<br />
<br />
$T_1 = \frac{a}{1} \cdot (x - a) = a \cdot (x-a)$<br />
<br />
$T_2 = \frac{1}{2} \cdot (x-a)^2$<br />
<br />
$T_3 = \frac{0}{6} \cdot (x-a)^3 = 0$<br />
<br />
...and so on. Let's take a look at what <span style="font-family: Courier New, Courier, monospace;">taylor</span> produces:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;"><span style="color: blue;">*Main></span> take 3 $ taylor (Var 'x')</span><br />
<span style="font-family: Courier New, Courier, monospace;">[Var 'a' :*: (Var 'x' :+: Const (-1.0) :*: Var 'a'), </span><br />
<span style="font-family: Courier New, Courier, monospace;">--^ a * (x-a)</span><br />
<span style="font-family: Courier New, Courier, monospace;">(Const 1.0 :/: Const 2.0) :*: (Var 'x' :+: Const (-1.0) :*: Var 'a') </span><span style="font-family: Courier New, Courier, monospace;">:^: Const 2.0, </span><br />
<span style="font-family: 'Courier New', Courier, monospace;">--^ 1/2 * (x-a)^2</span><br />
<span style="font-family: Courier New, Courier, monospace;">Const 0.0]</span><br />
<br />
This matches what we determined earlier.<br />
<br />
To evaluate a Taylor expression, we need a value for $a$, a value for $x$, and a specified number of terms for precision. We default this precision to 100 terms in the <span style="font-family: Courier New, Courier, monospace;">evalTaylor</span> function, and the logic takes place in the <span style="font-family: Courier New, Courier, monospace;">evalTaylorWithPrecision</span> function. In this function, we get the Taylor expansion, take the first <span style="font-family: Courier New, Courier, monospace;">prec</span> terms, plug in a and x for all values of the function, and finally sum the terms. Maclaurin evaluation is again defined in terms of Taylor evaluation.</div>
<div>
<br />
Taking a look at the above Taylor series expansion of $f(x) = x$, there is only one term where a zero-valued $a$ will produce any output (namely $\frac{1}{2} \cdot (x-a)^2$). So when we evaluate our Maclaurin series for this function at x, we should simply get back $\frac{1}{2}x^2$. Let's see how it works:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;"><span style="color: blue;">*Main></span> evalMaclaurin 2 (Var 'x')</span><br />
<span style="font-family: Courier New, Courier, monospace;">2.0 --1/2 2^2 = 1/2 * 4 = 2</span><br />
<span style="font-family: Courier New, Courier, monospace;"><span style="color: blue;">*Main></span> evalMaclaurin 3 (Var 'x')</span><br />
<span style="font-family: Courier New, Courier, monospace;">4.5 -- 1/2 * 3^2 = 1/2 * 9 = 4.5</span><br />
<span style="font-family: Courier New, Courier, monospace;"><span style="color: blue;">*Main></span> evalMaclaurin 10 (Var 'x')</span><br />
<span style="font-family: Courier New, Courier, monospace;">50.0 -- 1/2 * 10^2 = 1/2 * 100 = 50</span><br />
<span style="font-family: inherit;">Looks like everything's working!<br /><br />Please leave any questions, suggestions, etc, in the comments!<br /><br />Until next time,</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;">Ben</span></div>
Anonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com11tag:blogger.com,1999:blog-786816577681924169.post-6203805313256414452013-01-24T10:40:00.001-05:002013-01-28T16:52:29.320-05:00Graph Theory and the Handshake Problem<div class="separator" style="clear: both; text-align: center;">
</div>
<div style="margin-left: 1em; margin-right: 1em;">
</div>
<h3>
The Handshake Problem</h3>
<br />
The Handshake Problem is something of a classic in mathematics. I first heard about it in an algebra course I took in high school, and it's stuck with me through the years. The question is this:<br />
<br />
<blockquote class="tr_bq">
In a room containing $n$ people, how many handshakes must take place for everyone to have shaken hands with everyone else? </blockquote>
The goal of this short blog post will be to present a solution to this problem using the concept of graphs.<br />
<br />
<h3>
The Complete Graph</h3>
<h3>
</h3>
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="clear: right; float: right; margin-bottom: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><a href="http://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Complete_graph_K7.svg/611px-Complete_graph_K7.svg.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="File:Complete graph K7.svg" border="0" height="195" src="http://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Complete_graph_K7.svg/611px-Complete_graph_K7.svg.png" width="200" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><i>fig. I</i>: A complete graph with 7 vertices</td></tr>
</tbody></table>
First, we must understand the idea of a complete graph. A <b>complete graph</b><i> </i>is a graph such that each node is connected to every other node. A graphical example can be seen in <i>fig. I</i>.<br />
<br />
We can use the model of a complete graph to reason about the problem at hand. The nodes in the graph may represent the people in the room, while the connecting edges represent the handshakes that must take place. As such, the key to solving the Handshake Problem is to count the edges in a complete graph.<br />
<br />
But it would be silly to draw out a graph and count the edges one-by-one in order to solve this problem (and would take a very long time for large values of $n$), so we'll use math!<br />
<br />
<h3>
The Solution</h3>
<h3>
</h3>
To find the solution, we have to make a few key observations. The easiest way to start out in this case is to map out the first few complete graphs and try to find a pattern:<br />
<br />
Let $n$ = the number of nodes, $e$ = the number of edges.<br />
<ul>
<li>$n = 1 \Rightarrow e = 0$</li>
<li>$n = 2 \Rightarrow e = 1$</li>
<li>$n = 3 \Rightarrow e = 3$</li>
<li>$n = 4 \Rightarrow e = 6$</li>
</ul>
At this point, you may be noticing a pattern. As $n$ increases, we're adding $n -1$ edges. This makes sense -- each time a new node is introduced, it must connect to each node other than itself. In other words, $n-1$ connections must be made.<br />
<br />
It follows that the number of the edges ($e$) in a complete graph with $n$ vertices can be represented by the sum $(n-1) + (n-2) + \dots + 1 + 0$, or more compactly as:<br />
$$\sum_{i=1}^n i-1$$<br />
You may already know from summation laws that this evaluates to $\frac{n(n-1)}{2}$. Let's prove it.<br />
<br />
<h3>
The Proof</h3>
<h3>
</h3>
<i>Theorem:</i><b> </b>$\forall n \in \mathbb{N} : \sum_{i=1}^{n} i-1 = \frac{n(n-1)}{2}$<br />
<br />
<i>Proof: </i><b>Base case</b>: Let $n = 1$. Then, $\frac{1(1-1)}{2} = \sum_{i=1}^1 i-1 = 0$.<br />
<b>Inductive case</b>: Let $n \in \mathbb{N}$. We need to prove that $\frac{n(n-1)}{2} + n = \frac{n(n+1)}{2}$.<br />
$$\begin{array} {lcl}<br />
\frac{n(n-1)}{2} + n & = & \frac{n(n-1)+2n}{2} \\ <br />
& = & \frac{n^2 - n + 2n}{2} \\<br />
& = & \frac{n^2 + n}{2} \\<br />
& = & \frac{n(n+1)}{2}■\end{array}$$<br />
We can now use the theorem knowing it's correct, and, in fact, provide a solution to the original problem. The answer to the Handshake Problem involving $n$ people in a room is simply $\frac{n(n-1)}{2}$. So, the next time someone asks you how many handshakes would have to take place in order for everyone in a room with 1029 people to shake each other's hands, you can proudly answer "<b>528906 handshakes!</b>"<br />
<br />
Until next time,<br />
<br />
BenAnonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com0tag:blogger.com,1999:blog-786816577681924169.post-22018093214752884412013-01-16T15:58:00.001-05:002013-01-16T18:45:04.802-05:00Comonadic TreesWe've seen in the previous post what monads are and how they work. We saw a few monad instances of some common Haskell structures and toyed around with them a little bit. Towards the end of the post, I asked about making a Monad instance for a generalized tree data type. My guess is that it was relatively difficult. But why?<br />
<br />
Well, one thing that I didn't touch on in my last post was that the monadic<span style="font-family: Courier New, Courier, monospace;"> >>=</span> operation can also be represented as <span style="font-family: Courier New, Courier, monospace;">(join . fmap f)</span>, that is, <span style="font-family: Courier New, Courier, monospace;">a</span> <span style="font-family: Courier New, Courier, monospace;">>>= f = join \$ fmap f a</span>, as long as <span style="font-family: Courier New, Courier, monospace;">a</span> has a<span style="font-family: Courier New, Courier, monospace;"> Functor </span>instance.<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">join</span> is a generalized function of the following type:<br />
<br />
$$ join :: (Monad ~m) \Rightarrow m ~(m ~a) \rightarrow m ~a $$<br />
<br />
Basically, this function takes a nested monad and "joins" it with the top level in order to get a regular <span style="font-family: Courier New, Courier, monospace;">m a</span> out of it. Since you bind to functions that take as and produce <span style="font-family: Courier New, Courier, monospace;">m a</span>s, <span style="font-family: Courier New, Courier, monospace;">fmap f </span>actually makes <span style="font-family: Courier New, Courier, monospace;">m (m a)</span>s and <span style="font-family: Courier New, Courier, monospace;">join </span>is just the tool to fix up the<span style="font-family: Courier New, Courier, monospace;"> >>=</span> function to produce what we want.<br />
<br />
Keep in mind that join is not a part of the <span style="font-family: Courier New, Courier, monospace;">Monad </span>typeclass, and therefore the above definition for<span style="font-family: Courier New, Courier, monospace;"> >>=</span> will not work. However, if we are able to make a specific join function (named something else, since <span style="font-family: Courier New, Courier, monospace;">join </span>is taken!) for whatever type we are making a <span style="font-family: Courier New, Courier, monospace;">Monad </span>instance for, we can certainly use the above definition.<br />
<br />
I don't want to spend too much time on this, but I would like to direct the reader to the <span style="font-family: Courier New, Courier, monospace;">Monad </span>instance for <span style="font-family: Courier New, Courier, monospace;">[]</span> that I mentioned in the last post -- can you see any similarities between this and the way I structured <span style="font-family: Courier New, Courier, monospace;">>>=</span> above?<br />
<br />
Now back to the <span style="font-family: Courier New, Courier, monospace;">Tree</span> type. Can you devise some way to join <span style="font-family: Courier New, Courier, monospace;">Tree</span>s? That is, can you think of a way to flatten a <span style="font-family: Courier New, Courier, monospace;">Tree</span> of<span style="font-family: Courier New, Courier, monospace;"> Tree a</span>s into a <span style="font-family: Courier New, Courier, monospace;">Tree a</span>?<br />
<br />
This actually turns out to be quite difficult, and up to interpretation as to how you want to do it. It's not as straightforward as moving<span style="font-family: Courier New, Courier, monospace;"> Maybe (Maybe a)</span>s into <span style="font-family: Courier New, Courier, monospace;">Maybe a</span>s or<span style="font-family: Courier New, Courier, monospace;"> [[a]]</span>s into <span style="font-family: Courier New, Courier, monospace;">[a]</span>s. Maybe if we put a <span style="font-family: Courier New, Courier, monospace;">Monoid</span> restriction on our <span style="font-family: Courier New, Courier, monospace;">a</span> type, as such...<br />
<br />
$$ instance ~(Monoid ~a) \Rightarrow Monad ~(Tree ~a) ~where ~\dots $$<br />
<br />
...we could use <span style="font-family: Courier New, Courier, monospace;">mappend </span>in some way in order to concatenate all of the nested elements using some joining function. While this is a valid way to define a <span style="font-family: Courier New, Courier, monospace;">Tree Monad</span>, it seems a little bit "unnatural." I won't delve too deeply into that, though, because that's not the point of this post. Let's instead take a look at a structure related to monads that may make more sense for our generalized <span style="font-family: Courier New, Courier, monospace;">Tree</span> type.<br />
<br />
<h3>
What is a comonad?</h3>
Recall the type signature of <span style="font-family: Courier New, Courier, monospace;">>>=</span> for Monads:<br />
$$ (>>=) :: (Monad ~m) \Rightarrow m ~a \rightarrow ~(a \rightarrow m ~b) \rightarrow m ~b $$<br />
That is, we're taking an <span style="font-family: Courier New, Courier, monospace;">m a</span> and converting it to an <span style="font-family: Courier New, Courier, monospace;">m b</span> by means of some function that operates on the contained type. In other words, we're producing a new value using elements contained inside the <span style="font-family: Courier New, Courier, monospace;">Monad</span>. <span style="font-family: Courier New, Courier, monospace;">Comonads </span>have a similar function:<br />
$$ (=>>) :: (Comonad ~w) \Rightarrow w ~a \rightarrow (w ~a \rightarrow ~b) \rightarrow w ~b $$<br />
The difference here is that the function that we use to produce a new value operates on the whole -- we're not operating on the elements contained inside the <span style="font-family: Courier New, Courier, monospace;">Comonad</span>, but the <span style="font-family: Courier New, Courier, monospace;">Comonad </span>itself, to produce a new value.<br />
<br />
We also have a function similar to the Monadic <span style="font-family: Courier New, Courier, monospace;">return</span>:<br />
$$ coreturn :: (Comonad ~w) \Rightarrow w ~a \rightarrow a $$<br />
Whereas <span style="font-family: Courier New, Courier, monospace;">return </span>puts a value into a <span style="font-family: inherit;"><i>Monadic</i></span> context, <span style="font-family: Courier New, Courier, monospace;">coreturn </span>extracts a value from a <i>Comonadic</i> context.<br />
<br />
I mentioned the Monadic <span style="font-family: Courier New, Courier, monospace;">join </span>function above because I would also like to mention that there is a similar operation for <span style="font-family: Courier New, Courier, monospace;">Comonad</span>s:<br />
$$ cojoin :: (Comonad ~w) \Rightarrow w ~a \rightarrow w ~(w ~a) $$<br />
Instead of "removing a layer," we're "adding" a layer. And, as it turns out, just as <span style="font-family: Courier New, Courier, monospace;">a >>= f</span> can be represented as <span style="font-family: Courier New, Courier, monospace;">join \$ fmap f a, =>></span> can be represented as:<br />
$$ a ~=>> ~f = fmap ~f ~\$ ~cojoin ~a $$<br />
<br />
The full <span style="font-family: Courier New, Courier, monospace;">Comonad </span>typeclass (as I like to define it) is as follows:<br />
<br />
$$ class ~(Functor ~w) \Rightarrow Comonad ~w ~a ~where \\<br />
\hspace{22pt}coreturn :: (Comonad ~w) \Rightarrow w ~a \rightarrow a \\<br />
\hspace{38pt}cojoin :: (Comonad ~w) \Rightarrow w ~a \rightarrow w ~(w ~a) \\<br />
a ~=>> ~f = fmap ~f ~\$ ~cojoin ~a $$<br />
<br />
By now, it should at least be clear that <span style="font-family: Courier New, Courier, monospace;">Monad</span>s and <span style="font-family: Courier New, Courier, monospace;">Comonad</span>s are related -- it shouldn't be hard to see why they are so similar in name!<br />
<br />
<i>Note: There is a package called Control.Comonad on Hackage. It uses different names for the Comonad operations, but they do the same things. It's a good package, but I wanted to show how Comonads are built and use the operation names I used to make things clearer.</i><br />
<i><br /></i>
<br />
<h3>
What can I do with Comonads?</h3>
<div>
<br />
As it turns out, the <span style="font-family: Courier New, Courier, monospace;">Tree a</span> structure that I've been mentioning fits into the Comonadic context quite well, and provides a simple example as to how <span style="font-family: Courier New, Courier, monospace;">Comonad</span>s work.</div>
<div>
<br /></div>
<div>
We'll start with the implementation of the <span style="font-family: Courier New, Courier, monospace;">Comonad</span> typeclass mentioned above:</div>
<div>
<br />
<script src="https://gist.github.com/4478677.js"></script><br />
Then we'll go ahead and make a <span style="font-family: Courier New, Courier, monospace;">Functor </span>instance of our <span style="font-family: Courier New, Courier, monospace;">Tree a</span> data type:<br />
<br />
<script src="https://gist.github.com/4478700.js"></script><br />
From here, we're able to make a Comonadic <span style="font-family: Courier New, Courier, monospace;">Tree </span>like so:<br />
<br />
<script src="https://gist.github.com/4478716.js"></script><br />
The only real point of confusion here is in the <span style="font-family: Courier New, Courier, monospace;">cojoin </span>function for <span style="font-family: Courier New, Courier, monospace;">Nodes</span>. But, all we are doing is wrapping the entire node in a new node, and then mapping <span style="font-family: Courier New, Courier, monospace;">cojoin </span>over every child node of the current node to produce its children. In other words, we're turning a <span style="font-family: Courier New, Courier, monospace;">Node a</span> into a <span style="font-family: Courier New, Courier, monospace;">Node (Node a)</span>, which is exactly what we want to do.<br />
<br />
So what can we do with a comonadic tree? Let's tackle a simple problem. Say we're hanging out in California, and we want to get to the East coast as quickly as possible. We don't really care where on the East coast we end up -- we just want to get there. We can map out the different paths that we can take, along with the time it takes to get to each one. In other words, we're going to model spots on the map as <span style="font-family: Courier New, Courier, monospace;">Nodes</span> on a <span style="font-family: Courier New, Courier, monospace;">Tree</span> and give them a weight corresponding to the time it takes to get there. We can model this situation with a <span style="font-family: Courier New, Courier, monospace;">Tree</span> as follows:<br />
<br />
<script src="https://gist.github.com/4495151.js"></script><br />
The number of each <span style="font-family: Courier New, Courier, monospace;">Node</span> marks its distance from the previous<span style="font-family: Courier New, Courier, monospace;"> Node</span>. The root <span style="font-family: Courier New, Courier, monospace;">Node</span> of the <span style="font-family: Courier New, Courier, monospace;">Tree </span>is the starting point, so it is 0 distance away from itself.<br />
<br />
What we want to do to find the shortest path through the country is essentially, as follows. First, we're going to need to check the deepest nodes, and find their minimum distance children. We will add the distance of the <span style="font-family: Courier New, Courier, monospace;">Node </span>closest to the one we're examining to its own distance, to find the shortest way to get from the node we're examining to the destination. Once all of that has been done, we'll need to traverse up the tree, repeating this as we go. By the end of the algorithm, the root <span style="font-family: Courier New, Courier, monospace;">Node </span>will be marked with the shortest distance to the destination.<br />
<br />
Now, that may sound somewhat iterative in nature, but we're going to morph this into a comonadic operation. First, let's take a look at a function we can use to find the minimum distance to the next level of our tree:<br />
<br />
<script src="https://gist.github.com/4487797.js"></script><br />
This is relatively simple, and does precisely what was mentioned above: adds the minimum value contained in the connected <span style="font-family: Courier New, Courier, monospace;">Node</span>s to the parent <span style="font-family: Courier New, Courier, monospace;">Node</span>. Next, take a look at the type signature. We can see that this function produces a new number from a tree full of numbers. This coincides precisely with the function type we need to use with <span style="font-family: Courier New, Courier, monospace;">=>></span>, so we'll be able to use it to get exactly what we want.<br />
<br />
The rest is very simple:<br />
<br />
<br />
<script src="https://gist.github.com/4550764.js"></script><br />
This produces a tree full of the minimum distances from each node to the East coast. Pulling the actual value out is as easy as calling <span style="font-family: Courier New, Courier, monospace;">coreturn </span>on the resultant tree.<br />
<br />
Thanks for reading!<br />
<br />
Ben<br />
<br />
<i>For further reading on Comonads, I recommend the article <a href="http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html">Evaluating Cellular Automata is Comonadic</a>.</i></div>
Anonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com0tag:blogger.com,1999:blog-786816577681924169.post-67430215993386142512013-01-02T16:04:00.002-05:002013-01-02T16:42:28.556-05:00Introductory Monads<h3>
What is a Monad?</h3>
If you've used Haskell before, chances are that you've heard the term "monad" a good bit. But, you might not know what they are, or what they are really used for. It is my goal in this blog post to shed some light on what monads are, introduce and define few simple ones, and touch on their usefulness.<br />
<br />
I will assume basic familiarity with Haskell syntax in this blog post. A working knowledge of monoids and functors will also be beneficial, although not strictly necessary.<br />
<br />
Without further ado, let's go ahead and look at the <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> typeclass:<br />
<br />
<script src="https://gist.github.com/4391987.js"></script><br />
We can see a <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> has two operations, <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">return</span> and <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">>>=</span> (this is commonly pronounced "bind"). You may suspect that you know what <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">return</span> does from other programming languages, but be warned: <b>Haskell's return is very different</b>! Haskell's <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">return</span> <i>only</i> operates on <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monads</span>, and essentially acts as a "wrapping" function. That is, if you call <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">return</span> on a value, it will turn it into a monadic value of that type. We will look at an example of this shortly. The second operation, <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">>>=</span>, takes two arguments: an <span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;">a</span></span> wrapped in a <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> <span class="n" style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">m</span> (I will refer to this as <span class="n" style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">m</span><span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;"> </span><span class="n" style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">a</span> from now on), and a function that converts an <span class="n" style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">a</span> to <span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;">b</span></span> wrapped in the same type of <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span>, <span class="n" style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">m</span>. It produces a value of type <span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;">b</span></span>, wrapped in a <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> <span class="n" style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">m</span> (I will call this <span class="n" style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">m</span><span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;"> b</span> from now on). This may sound complicated, but I'll do my best to explain it after showing the most basic <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> type, namely, the Identity <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span>:<br />
<br />
<br />
<script src="https://gist.github.com/4392149.js"></script><br />
<i>Also defined in <a href="http://hackage.haskell.org/packages/archive/mtl/latest/doc/html/Control-Monad-Identity.html" target="_blank">Control.Monad.Identity</a></i><br />
<br />
The Identity data declaration defines only one type: <span class="kt" style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Identity</span><span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;"> </span><span class="n" style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">a</span>. Basically, this is just a wrapper for a value, and nothing more. return is simply defined as <span class="kt" style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Identity</span>. We can, for example, call <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">return</span> 3 and get an <span class="kt" style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Identity</span><span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;"> 3</span>. Turning values into <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Identitys</span> is as simple as that. The bind function may look a little bit more obscure, though. Let's look closely: We first use pattern matching to be able to operate on the type that the Identity <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> wraps (<span class="kt" style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Identity</span><span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;"> </span><span class="n" style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">a</span>), bind it (<span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">>>=</span>) to a function (<span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">f</span>). Since <span class="n" style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">f</span> converts normal values into monadic ones (look at the type declaration), we can simply apply <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">f </span>to <span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;">a</span></span>, and we've produced a new <span class="kt" style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Identity</span>. I've provided a couple of examples of how this works. <span style="background-color: ghostwhite; color: #990000; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">addThree</span> adds 3 to an <span class="kt" style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Identity</span><span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;"> Int</span> (<span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;">m1</span></span>) and <span style="color: #990000; font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>getLength</b></span></span> turns an <span class="kt" style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Identity</span><span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;"> [a]</span> (<span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;">m2</span></span>) into an <span class="kt" style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Identity</span><span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;"> Int</span>. Both of the bind examples produce the value <span class="kt" style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Identity</span><span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;"> 6</span>. Can you see why?<br />
<br />
I want to take a little sidebar here and try to explain how I understand <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monads</span> before moving on. Basically the real tough part of understanding <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monads</span> is just understanding <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">>>=</span>. A little bit of dissection can explain a lot, but it took me months to really grasp the concept. On the surface, you're morphing an <span style="font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">m a</span> into an <span style="font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">m b</span>. At first, I thought that the m's in the type signature were allowed to different types of <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monads</span>. For instance, I thought that <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monads</span> made it possible to bind <span class="kt" style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Identity</span><span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;"> Int</span>s to functions that produced <span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;">[String]</span></span>s (we'll look at the list <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> in a minute). This is wrong, and for good reason! It was incredibly confusing to think about a function that could generalize to this degree and it is, to my knowledge, not possible to do so. The <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> (wrapper) type is retained, but the <i>wrapped</i> type can be changed by means of the function you bind to.<br />
<br />
The second thing that I want to stress is what <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">>>=</span> really does. What we're doing with the <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">>>=</span> function is turning an m a into an m b, but it's not so direct as you might want to think. The function argument in <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">>>=</span> ( (<span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>a -> m b</b></span></span>) ) was really confusing to me to begin with, so I'm going to try to explain it. The function you're binding your <b style="font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">m a</b> to must take an <span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>a</b></span></span> and return an <b style="font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">m b</b>. This means that you're acting on the <i>wrapped</i> part of the <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> in order to produce an entirely new <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span>. It took me a while to realize what exactly was happening, that I wasn't supposed to be directly converting <b style="font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">m a</b> to <b style="font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">m b</b> by means of my argument function (that's actually what <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">>>=</span> is for). Just remember that <b>the function you bind to should operate on an a to produce an m b</b>.<br />
<br />
With that knowledge, let's take a look at some more examples of <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monads</span>:<br />
<br />
<h3>
More Monads</h3>
<div>
<br />
If you're a Haskell user, you're likely already familiar with the <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Maybe</span> data type:</div>
<br />
<br />
<script src="https://gist.github.com/4392596.js"></script><br />
<i>Defined in the <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html" target="_blank">Prelude</a></i><br />
<br />
The <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Maybe</span> <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> is hardly an extension of the aforementioned <span style="color: #445588; font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>Identity</b></span></span> <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span>. All we are really adding is the functionality to fail -- that is, to produce a <span style="color: #445588; font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>Nothing</b></span></span> value if necessary. In fact, the <span style="color: #445588; font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>Just </b></span></span><b style="font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">a</b> type is exactly the same as <span style="color: #445588; font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>Identity </b></span></span><b style="font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">a</b>, except that a <b style="color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">Nothing</b> value anywhere in the computation will produce a <b style="color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">Nothing</b> as a result. Next, we'll look at the <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> instance for lists:<br />
<br />
<br />
<script src="https://gist.github.com/4392613.js"></script><br />
<i>Defined in the <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html" target="_blank">Prelude</a></i><br />
<br />
The list <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> is a little more complicated, but it's really nothing too new. For <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">return</span>, we just have to wrap our value inside a list. Now, let's look at <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">>>=</span>. <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">concatMap</span> actually <i>is</i> the <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">>>=</span> instance for lists. Why? Well, <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">concatMap</span> is, simply, (<span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">concat . map</span>). We know that <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">map</span> takes a list of <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">a</span>s and maps a function over them, and concat is a function that flattens lists, that is, turns <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">[[a]]</span>s into <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">[a]</span>s. When we compose these two functions (or use <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">concatMap</span>), we're making a function that must produce <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">[[a]]</span>s out of <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">[a]</span>s, and then flatten them back to <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">[a]</span>s. That is exactly how <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">>>=</span> works for lists! Now, let's take a look at a slightly more complicated <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span>:<br />
<br />
<br />
<script src="https://gist.github.com/4437366.js"></script><br />
<i>Also defined in <a href="http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/Control-Monad-Instances.html">Control.Monad.Instances</a></i><br />
<br />
This one requires some explanation, because it's a bit of a leap from the last three, since we're defining a <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> instance for <i>functions</i>. I have added a couple of comments in the above code in order to further explain how everything is working in the <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">(->) r</span> <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span>.<br />
<br />
Well, first things's first. We define <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">return</span> as <span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;">const</span></span>, which takes some arbitrary argument and produces a function that produces a constant value (what we pass in to <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">return</span>). This is exactly what we want; a minimal context for functions.<br />
<br />
(<span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">>>=</span>) is a bit more complex. First, let's take a look at the type signature, specific to this <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span>. We're binding a function (<span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>r -> a</b></span></span>) to a function (<span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>a -> (r -> b)</b></span></span>) to produce a function of type (<span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>r -> b</b></span></span>). So in the declaration of the function, <span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>f</b></span></span> is of type (<span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>r -> a</b></span></span>) and <span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>g</b></span></span> is of type (<span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>a -> (r -> b)</b></span></span>). I've conveniently named the argument our function is going to take <b style="font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">r</b>, for clarity. This is what the user will pass into the function that (<span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">>>=</span>) produces.<br />
<br />
<span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>f</b></span></span> takes an <span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>r</b></span></span>, so we apply the value from the lambda into it to produce an <b style="font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">a</b>. We then use that <b style="font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; line-height: 21px; white-space: pre;">a</b> to produce an (<span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>r -> b</b></span></span>), using <span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>g</b></span></span>. This produces our function, but it needs to be fed some value, so we finally apply it to <span style="font-family: Consolas, Liberation Mono, Courier, monospace;"><span style="font-size: 15px; line-height: 21px; white-space: pre;"><b>r</b></span></span> in order to complete everything. If any of this sounds confusing, try to work through it on paper and read the comments in my code -- after a bit of staring, it should start to make sense.<br />
<br />
I've also implemented the <span style="background-color: ghostwhite; color: #990000; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">mean</span> function here, using the <span style="background-color: ghostwhite; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">(->) r</span> <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> with and without do-notation. I think it's a pretty elegant way to express it.<br />
<br />
We've only seen the tip of the iceberg when it comes to <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monads</span>, but this should serve as a good basic introduction. Once you get used to seeing <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monads</span>, they become a bit less scary. The more time you spend with them, the more comfortable you'll feel with them.<br />
<br />
Before I end this post, I want to leave a question for the reader. Given the general <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Tree</span> data type represented below, can you intuitively make a <span style="background-color: ghostwhite; color: #445588; font-family: Consolas, 'Liberation Mono', Courier, monospace; font-size: 15px; font-weight: bold; line-height: 21px; white-space: pre;">Monad</span> instance?<br />
<br />
<br />
<script src="https://gist.github.com/d38f56c4bee49f1a15de.js"></script><br />
I'll explain why this is difficult when we talk about a similar mathematical type in the next post.<br />
<br />
Thanks for reading,<br />
<br />
Ben<br />
<br />
<i>For more introductory monad material, I suggest the following resources:</i><br />
<br />
<ul>
<li><a href="http://learnyouahaskell.com/a-fistful-of-monads">Learn You a Haskell For Great Good! A Fistful of Monads</a></li>
<li><a href="http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html" target="_blank">A Neighborhood of Infinity - You Could Have Invented Monads</a></li>
<li><a href="http://channel9.msdn.com/Shows/Going+Deep/Brian-Beckman-Dont-fear-the-Monads" target="_blank">Brian Beckman - Don't Fear the Monad</a></li>
</ul>
Anonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com2tag:blogger.com,1999:blog-786816577681924169.post-29732207006727970782012-12-16T21:12:00.002-05:002013-02-16T21:58:55.665-05:00Uncountable Infinity and The Diagonalization Method<h3>
Introduction</h3>
<br />
I took a class on Discrete Mathematics this past semester, and one of the topics we covered very briefly was the concept of countable and uncountable infinity. I didn't end up getting a great grasp on it, however, and the topic I'm writing about today didn't make a lick of sense to me at the time. It was never covered on exams, so I never had to revisit the idea. But, I've been reading through Douglas R. Hofstadter's <i><a href="http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach">Gödel, Escher, Bach</a></i>, and it just so happens that the topic is covered in the book. As it turns out, it's not actually too difficult a thing to understand, so I'm hoping to relay the ideas in this blog post. If you've heard about the concept of multiple infinities but not understood it, hopefully this will shed some light! If you haven't yet heard about the concept of multiple infinities, enjoy the read!<br />
<br />
Anyway, on with the show...<br />
<br />
<h3>
Natural Numbers Form an Infinite Set</h3>
<br />
It is a widely known fact (<a href="http://en.wikipedia.org/wiki/Axiom_of_infinity">axiom of ZFC Set Theory</a>) that the set of natural numbers (all non-negative integers) extends on to infinity. That is to say, there is no "largest" natural number. We can order the set of natural numbers in this way:<br />
<br />
$$ <br />
\begin{matrix} <br />
N_0 & = & 0 \cr<br />
N_1 & = & 1 \cr <br />
N_2 & = & 2 \cr<br />
N_3 & = & 3 \cr<br />
N_4 & = & 4 \cr<br />
N_5 & = & 5 \cr<br />
\cdots <br />
\end{matrix}<br />
$$<br />
This ordering comes very naturally to us. The nth term of the set of natural numbers will be, simply, n. Because of this fact, we can tell that this set of natural numbers contains all of them -- if you give me any natural number, it will correspond to the nth number in the set.<br />
<br />
There is a similar way of ordering the integers (including negatives) in this fashion. It may not be heavily intuitive at first, because we have to extend in two directions rather than one. But, it is apparent that this ordering of integers will allow us to find the location of any integer in it:<br />
<br />
$$ \begin{matrix}<br />
Z_0 & = & 0 \cr<br />
Z_1 & = & 1 \cr<br />
Z_2 & = & -1 \cr<br />
Z_3 & = & 2 \cr<br />
Z_4 & = & -2 \cr<br />
Z_5 & = & 3 \cr<br />
\cdots<br />
\end{matrix}<br />
$$<br />
Any integer, positive or negative, is contained in this infinite set. An infinite set that can be ordered in a way such as this is said to be <i>countably infinite.</i><br />
<br />
<h3>
What About Real Numbers?</h3>
<br />
For the purposes of this post, we're going to focus on the real numbers between 0 and 1. We can represent them in the following way:<br />
<br />
$$<br />
\begin{matrix}<br />
R_0 & = & 0 . & a_0 & a_1 & a_2 & a_3 & a_4 & \cdots \cr<br />
R_1 & = & 0 . & b_0 & b_1 & b_2 & b_3 & b_4 & \cdots \cr<br />
R_2 & = & 0 . & c_0 & c_1 & c_2 & c_3 & c_4 & \cdots \cr<br />
R_3 & = & 0 . & d_0 & d_1 & d_2 & d_3 & d_4 & \cdots \cr<br />
\cdots<br />
\end{matrix}<br />
$$<br />
We can see that this set goes on forever, that is, extends infinitely, just as the set of integers and naturals does. However, the set of real numbers is "built" in a different way. Both of these facts are important in what we will observe next.<br />
<br />
<h3>
Cantor's Diagonalization Method</h3>
<br />
I claim now that I can produce a number that the above set does not contain. To do this, I will be using Georg Cantor's famous <a href="http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument">Diagonalization Method</a>. Here's how it works.<br />
<br />
First, I will grab the $n$th term of each $n$th element in our set of real numbers to compose a new number, like so:<br />
<br />
$$<br />
\begin{matrix}<br />
R_0 & = & 0 . & \color{red}{a_0} & a_1 & a_2 & a_3 & a_4 & \cdots \cr<br />
R_1 & = & 0 . & b_0 & \color{red}{b_1} & b_2 & b_3 & b_4 &\cdots \cr<br />
R_2 & = & 0 . & c_0 & c_1 & \color{red}{c_2} & c_3 & c_4 & \cdots \cr<br />
R_3 & = & 0 . & d_0 & d_1 & d_2 & \color{red}{d_3} & d_4 & \cdots \cr<br />
\cdots &&& &&&& \color{red}{\ddots}<br />
\end{matrix}<br />
$$<br />
So my new number becomes:<br />
<br />
$$<br />
\begin{matrix}<br />
0 . & a_0 & b_1 & c_2 & d_3 & \cdots<br />
\end{matrix}<br />
$$<br />
Now I'm going to perform some transformation on each digit of this number to produce a new digit. A simple way (the simplest way?) to do this would just be to add 1 to each digit. This will produce a new number as follows:<br />
<br />
$$<br />
\begin{matrix}<br />
M_0 & = & 0 . & a_0 + 1 & b_1 + 1 & c_2 + 1 & d_3 + 1 & \cdots<br />
\end{matrix}<br />
$$<br />
We can see $M_0$ cannot be the same as $R_0$ because its first term differs. Same goes for $R_1$ with its second digit, and so on, <i>ad infinitum</i>. Therefore, each element of set of real numbers between 0 and 1 is going to differ from $M_0$ by at least one digit. We can conclude from this observation that our (infinite!) set of real numbers excludes $M_0$. That is to say, our set of real numbers between 0 and 1 isn't actually complete, and cannot actually be complete.<br />
<br />
That last part, "cannot be complete," may sound confusing, because, why can't we just add $M_0$ to the set, and call it complete?<br />
<br />
Well, let's do it! We'll tack on $M_0$ to the set to produce something like this:<br />
<br />
$$<br />
\begin{matrix}<br />
M_0 & = & 0 . & a_0 & b_1 & c_2 & d_3 & e_4 & \cdots \cr<br />
R_0 & = & 0 . & a_0 & a_1 & a_2 & a_3 & a_4 & \cdots \cr<br />
R_1 & = & 0 . & b_0 & b_1 & b_2 & b_3 & b_4 & \cdots \cr<br />
R_2 & = & 0 . & c_0 & c_1 & c_2 & c_3 & c_4 & \cdots \cr<br />
R_3 & = & 0 . & d_0 & d_1 & d_2 & d_3 & d_4 & \cdots \cr<br />
\cdots \cr\<br />
\end{matrix}<br />
$$<br />
You might foresee what's going to happen next. We can perform diagonalization again:<br />
<br />
$$<br />
\begin{matrix}<br />
M_0 & = & 0 . & \color{red}{a_0} & b_1 & c_2 & d_3 & e_4 & f_5 & \cdots \cr<br />
R_0 & = & 0 . & a_0 & \color{red}{a_1} & a_2 & a_3 & a_4 & a_5 & \cdots \cr<br />
R_1 & = & 0 . & b_0 & b_1 & \color{red}{b_2} & b_3 & b_4 & b_5 & \cdots \cr<br />
R_2 & = & 0 . & c_0 & c_1 & c_2 & \color{red}{c_3} & c_4 & c_5 & \cdots \cr<br />
R_3 & = & 0 . & d_0 & d_1 & d_2 & d_3 & \color{red}{d_4} & d_5 & \cdots \cr<br />
\cdots & & & &&&&& \color{red}{\ddots} \cr<br />
\end{matrix}<br />
$$<br />
...to produce a new number...<br />
<br />
$$ \begin{matrix} 0. & a_0 & a_1 & b_2 & c_3 & d_4 & \cdots \end{matrix} $$<br />
We perform some transformation on its elements (let's add one, again) in order to get a new number, say $M_1$.<br />
<br />
$$ \begin{matrix} M_1 & = & 0. & a_0 + 1 & a_1 + 1 & b_2 + 1 & c_3 + 1& d_4 + 1 & \cdots \end{matrix}$$<br />
However, note that $M_1$ must differ from $M_0$ now, as well as every other number in the set, by at least one digit. As such, $M_1$ must not yet exist in the set. We can add $M_1$ to the set, and repeat this process as many times as we want, but we'll always be able to produce a number outside of the set! We call a set with this fascinating property <i>uncountably infinite</i>.<br />
<br />
What does this mean? We can see that the set of integers is <i>countably</i> infinite, while the set of real numbers between 0 and 1 is <i>uncountably</i> infinite. We have successfully proven in this blog post that there are actually <b>more numbers between 0 and 1 than there are integers</b>!<br />
<br />
Cantor's Diagonalization Method has been used to prove several difficult problems in Mathematics, including the <a href="http://en.wikipedia.org/wiki/Church-Turing_theorem">Church-Turing Theorem</a> and <a href="http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems">Gödel's Incompleteness Theorems</a>. All three of these theorems have had major effects on the nature of Mathematics, so you can see that Cantor's Diagonalization Method can be quite useful!<br />
<br />
If you have any questions, or if anything was unclear, please leave a comment!<br />
<br />
Until next time,<br />
<br />
BenAnonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com3tag:blogger.com,1999:blog-786816577681924169.post-51761743513803047182012-12-06T10:52:00.003-05:002012-12-07T00:32:54.537-05:00Graphs and Topological Sorting in the Functional Paradigm<h3>What is a Graph?</h3><div><span style="font-family: Arial, Helvetica, sans-serif;">From <i><a href="http://en.wikipedia.org/wiki/Graph_(mathematics)" target="_blank">Wikipedia</a></i>: </span><br />
<blockquote class="tr_bq"><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;">In </span><a href="http://en.wikipedia.org/wiki/Mathematics" style="background-color: white; background-image: none; color: #0b0080; font-family: sans-serif; font-size: 13px; line-height: 19.200000762939453px; text-decoration: initial;" title="Mathematics">mathematics</a><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;">, a </span><b style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;">graph</b><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;"> is a representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called </span><span style="background-color: white; font-family: sans-serif; font-size: 13px; line-height: 19.200000762939453px;"><a href="http://en.wikipedia.org/wiki/Vertex_(graph_theory)" style="background-image: none; color: #0b0080; text-decoration: initial;" title="Vertex (graph theory)">vertices</a></span><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;">, and the links that connect some pairs of vertices are called </span><span style="background-color: white; font-family: sans-serif; font-size: 13px; line-height: 19.200000762939453px;">edges</span><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;">.</span></blockquote><span style="font-family: inherit;">Simply put, a graph is just a bunch of points with links between them. A road map is a simple example: roads being edges, and intersections being vertices. </span> In fact, <a href="http://maps.google.com/" target="_blank">Google maps</a> uses graphs for just this purpose! Graphs are widely used in a wide variety of places. <a href="http://www.facebook.com/" target="_blank">Facebook</a> uses graphs to model your friend connections and likes. In fact, the entire internet is just a giant graph; websites act as vertices, with hyperlinks as edges. Graphs are highly useful structures, as they can be used to model many different types of situations, and as such, they will be the focus of this blog post. I am going to discuss one way to represent a graph in the Haskell programming language, and how to functionally solve a common problem using graphs.<br />
<br />
Graphs are often represented visually like this:<br />
<span style="font-family: inherit;"><br />
</span></div><table class="graph" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://2.bp.blogspot.com/-WS-YS-sS1Yw/UL_BNs1BumI/AAAAAAAAAEY/ZwGmaHAtcBI/s1600/ABCDEF.png" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img class="graph" border="0" height="245" src="http://2.bp.blogspot.com/-WS-YS-sS1Yw/UL_BNs1BumI/AAAAAAAAAEY/ZwGmaHAtcBI/s400/ABCDEF.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Graph representing abstract data</td></tr>
</tbody></table><br />
<span style="font-family: Arial, Helvetica, sans-serif;">This graph links the first six letters of the alphabet in an arbitrary way. This data doesn't really mean anything, but it will serve as a simple foray into the world of graphs, and provides an initial graph to work towards representing in Haskell.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br />
</span> <span style="font-family: Arial, Helvetica, sans-serif;">Let's get right to it; here's the data structure we'll be using, along with some convenience methods:</span><br />
<br />
<script src="https://gist.github.com/4219938.js"> </script><br />
First we define the actual <span class="kt" style="color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">Graph</span><span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;"> </span><span class="n" style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">a</span> data type: It's simply a set vertices and edges in the form of 2-tuples (The tuple <span style="font-family: Courier New, Courier, monospace;">(a, b)</span> connects vertex <span style="font-family: Courier New, Courier, monospace;">a</span> to vertex <span style="font-family: Courier New, Courier, monospace;">b</span>), which fits our definition. I've also defined the <span class="nf" style="color: #990000; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">removeEdge</span><span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;"> </span>method, which does just what you'd expect. The <span class="nf" style="color: #990000; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">outbound</span><span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;"> </span>and <span class="nf" style="color: #990000; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">inbound</span><span class="nf" style="color: #990000; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-size: 12px; font-weight: bold; line-height: 16.766666412353516px; margin: 0px; padding: 0px; white-space: pre;"> </span>methods find the outbound and inbound connections to any point in the graph, respectively. They make use of the polymorphic <span class="nf" style="color: #990000; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">connections</span><span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;"> </span>method in order to get this done in a small amount of code. Finally, the <span style="color: #555555; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;">Graph </span>module exports the relevant functions at the top of the file.<br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br />
Now that we've got our framework in order, we can go ahead and build the graph we mentioned above:</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br />
</span> <script src="https://gist.github.com/4219915.js"> </script><br />
We import the <span class="kt" style="color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">Graph</span><span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;"> </span>module and define a simple <span style="color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 16.78333282470703px; white-space: pre;">Letter </span>data type, then build our Graph from it. The set of vertices are the letters <span class="kt" style="background-color: white; color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-size: 12px; font-weight: bold; line-height: 16.78333282470703px; margin: 0px; padding: 0px; white-space: pre;">A,</span><span style="background-color: white; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-size: 12px; line-height: 16.78333282470703px; white-space: pre;"> </span><span class="kt" style="background-color: white; color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-size: 12px; font-weight: bold; line-height: 16.78333282470703px; margin: 0px; padding: 0px; white-space: pre;">B,</span><span style="background-color: white; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-size: 12px; line-height: 16.78333282470703px; white-space: pre;"> </span><span class="kt" style="background-color: white; color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-size: 12px; font-weight: bold; line-height: 16.78333282470703px; margin: 0px; padding: 0px; white-space: pre;">C,</span><span style="background-color: white; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-size: 12px; line-height: 16.78333282470703px; white-space: pre;"> </span><span class="kt" style="background-color: white; color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-size: 12px; font-weight: bold; line-height: 16.78333282470703px; margin: 0px; padding: 0px; white-space: pre;">D,</span><span style="background-color: white; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-size: 12px; line-height: 16.78333282470703px; white-space: pre;"> </span><span class="kt" style="background-color: white; color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-size: 12px; font-weight: bold; line-height: 16.78333282470703px; margin: 0px; padding: 0px; white-space: pre;">E, </span>and<span style="background-color: white; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-size: 12px; line-height: 16.78333282470703px; white-space: pre;"> </span><span class="kt" style="background-color: white; color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-size: 12px; font-weight: bold; line-height: 16.78333282470703px; margin: 0px; padding: 0px; white-space: pre;">F</span>, and the edges are modeled as above.<br />
<br />
Now that we know how to build graphs, we can start modeling more important information with them.<br />
<h3><br />
</h3><h3>Modeling Actual Scenarios using Graphs</h3><div><span style="font-family: Arial, Helvetica, sans-serif;">Suppose some of the characters from NBC's <i><a href="http://www.nbc.com/parks-and-recreation/" target="_blank">Parks and Recreation</a> </i>have just finished competing in a dance competition, and we know the following about their rankings:</span><br />
<br />
<span style="font-family: Arial, Helvetica, sans-serif;">Leslie beat April.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;">April beat Ann.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;">Ron beat April.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;">Ron beat Ann.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;">April beat Andy.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;">Leslie beat Ron.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;">Andy beat Jerry.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;">Ron beat Andy.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;">Ann beat Jerry.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;">Leslie beat Andy.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;">Ann beat Andy.</span></div><div><br />
<span style="font-family: Arial, Helvetica, sans-serif;">This is a little hard to understand, so why don't we model it as a graph to make it a little more readable? </span>Each person can be represented as a vertex, with outgoing edges representing connections to the people they beat.<br />
<div><br />
</div><span style="font-family: Arial, Helvetica, sans-serif;"><br />
</span></div><div class="separator" style="clear: both; text-align: center;"></div><table class="graph" align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://4.bp.blogspot.com/-coJ1uHjEo94/UMC_E4j2EPI/AAAAAAAAAE0/fMKyRGqMfqU/s1600/PandR.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img class="graph" border="0" height="370" src="http://4.bp.blogspot.com/-coJ1uHjEo94/UMC_E4j2EPI/AAAAAAAAAE0/fMKyRGqMfqU/s400/PandR.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">A graph of dance competition results</td></tr>
</tbody></table><br />
It would be nice to be able to be able to read scenarios like this from a text file containing the important data and parse it into a graph. Let's go ahead and set up a function to do this for us, so we don't have to hard-code each and every graph that we want to use:<br />
<br />
Here's our data file, with a list of space-separated connections, one on each line:<br />
<br />
<script src="https://gist.github.com/4225498.js"> </script><br />
<br />
<br />
And our parsing function:<br />
<br />
<script src="https://gist.github.com/4219922.js"> </script><br />
The <span class="nf" style="color: #990000; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">graphFromFile</span> function takes a <span style="color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 16.78333282470703px; white-space: pre;">String </span>and returns an <span class="kt" style="color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">IO</span><span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;"> </span><span class="p" style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">(</span><span class="kt" style="color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">Graph</span><span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;"> </span><span class="kt" style="color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">String).</span> The function reads a file, parses it into two important pieces: <span class="n" style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">verts</span><span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;"> </span>(the set of all unique strings in the file, or, our vertices) and <span class="n" style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">conns</span><span class="n" style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.766666412353516px; margin: 0px; padding: 0px; white-space: pre;"> </span>(the set of connections between strings in the file). It then builds a Graph from this data, wraps it in the <span class="kt" style="color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">IO</span><span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;"> </span>monad with <span class="n" style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">return</span>, and gives it back.<br />
<br />
Now you might have been wondering from the beginning of this section what the ranking from the dance competition was (maybe you even figured it out on your own!). How do we do this programmatically, using our graph?<br />
<br />
<h3>Enter Topological Sort</h3>Again, from <i><a href="http://en.wikipedia.org/wiki/Topological_sort" target="_blank">Wikipedia</a>:</i><br />
<blockquote class="tr_bq"><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;">In </span><a href="http://en.wikipedia.org/wiki/Computer_science" style="background-color: white; background-image: none; color: #0b0080; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px; text-decoration: initial;" title="Computer science">computer science</a><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;">, a </span><b style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;">topological sort</b><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;"> of a </span><a href="http://en.wikipedia.org/wiki/Directed_graph" style="background-color: white; background-image: none; color: #0b0080; font-family: sans-serif; font-size: 13px; line-height: 19.200000762939453px; text-decoration: initial;" title="Directed graph">directed graph</a><span style="background-color: white; font-family: sans-serif; font-size: 13px; line-height: 19.200000762939453px;"> <i>is a linear ordering of its </i></span><a href="http://en.wikipedia.org/wiki/Vertex_(graph_theory)" style="background-color: white; background-image: none; color: #0b0080; font-family: sans-serif; font-size: 13px; line-height: 19.200000762939453px; text-decoration: initial;" title="Vertex (graph theory)">vertices</a><span style="background-color: white; font-family: sans-serif; font-size: 13px; line-height: 19.200000762939453px;"> <i>such that, for every edge </i></span><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;">uv</span><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;">, </span><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;">u</span><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;"> comes before </span><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;">v</span><span style="background-color: white; font-family: sans-serif; font-size: 13px; font-style: italic; line-height: 19.200000762939453px;"> in the ordering.</span></blockquote>In our case, this just means that each person must come before <i>all </i>of the people that he or she beat in the competition, in the ordering.<br />
<br />
The basic procedure for topological sort is as follows:<br />
<span style="font-family: Courier New, Courier, monospace;"><br />
</span> <span style="font-family: Courier New, Courier, monospace;">L = {} --sorted list</span><br />
<span style="font-family: Courier New, Courier, monospace;">S = Set of vertices with no incoming connections</span><br />
<span style="font-family: Courier New, Courier, monospace;">while S is not empty:</span><br />
<span style="font-family: Courier New, Courier, monospace;"> for each vertex v in S with no incoming connections:</span><br />
<span style="font-family: Courier New, Courier, monospace;"> push v to L</span><br />
<span style="font-family: Courier New, Courier, monospace;"> for each edge e from v to u:</span><br />
<span style="font-family: Courier New, Courier, monospace;"> remove e from graph</span><br />
<span style="font-family: Courier New, Courier, monospace;"> if u has no more incoming connections:</span><br />
<span style="font-family: Courier New, Courier, monospace;"> push u to S</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br />
</span> <span style="font-family: Courier New, Courier, monospace;">if edges still exist in the graph:</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"> error: there is at least one cycle in the graph</span><br />
<span style="font-family: 'Courier New', Courier, monospace;"><br />
</span> <span style="font-family: 'Courier New', Courier, monospace;">else return L</span><br />
<br />
If you do not understand this, I urge you to work through topologically sorting a graph on paper first; it's not too tough to understand once you've done it on paper, but can get a little confusing in psuedocode.<br />
<br />
The problem with this algorithm is that you see a ton of loops -- control structures that we do not have in Haskell. Therefore, we must rely on recursion, folds, and maps to achieve what we want to do. Here's how it looks:<br />
<br />
<br />
<script src="https://gist.github.com/4219925.js"> </script><br />
Our <span class="nf" style="color: #990000; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">tsort</span> function first finds the elements in the graph with no incoming edges using the function <span class="n" style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">noInbound</span><span class="n" style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.766666412353516px; margin: 0px; padding: 0px; white-space: pre;">.</span> We pass this into a sub-routine <span style="color: #990000; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 22.383333206176758px; white-space: pre;">tsort'</span> that takes a sorted list <span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;">l,</span> a list of vertices with no incoming connections <span class="p" style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">(</span><span class="n" style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">n</span><span class="kt" style="color: #445588; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">:</span><span class="n" style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">s</span><span class="p" style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 1.4em; margin: 0px; padding: 0px; white-space: pre;">)</span>, and a graph <span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;">g</span>.<br />
<br />
We operate on the first element of the set of vertices with no incoming connections <span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;">n</span>, finding <span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;">outEdges</span> (the outgoing edges from n), and <span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;">outNodes</span> (the nodes that <span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.766666412353516px; white-space: pre;">n</span> points to). We build a new graph <span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;">g'</span> with the <span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;">outEdges</span> removed, and find the nodes in <span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;">g'</span> with no inbound connections, and add them to <span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;">s</span>.<br />
<br />
We then recursively call <span style="color: #990000; font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; font-weight: bold; line-height: 22.383333206176758px; white-space: pre;">tsort'</span> with these new parameters (and prepend our current <span style="font-family: 'Bitstream Vera Sans Mono', 'Courier New', monospace; line-height: 16.78333282470703px; white-space: pre;">n</span> to the sorted list), until there are no more nodes to check. At this point, if the edge list in the graph is empty, all is well and we return the list of sorted elements. Otherwise, an error is thrown stating that there is at least one cycle in the graph.<br />
<br />
Now that we've got that, we're ready to find out how everyone ranked in the dance competition!<br />
<br />
<br />
<script src="https://gist.github.com/4219931.js"> </script><br />
This produces the output:<br />
<span style="font-family: Courier New, Courier, monospace;">["Leslie", "Ron", "April", "Ann", "Andy", "Jerry"]</span><br />
<br />
(Of course Jerry lost.)<br />
<br />
<h3>Conclusion</h3>As you can see, Graphs are very useful data structures. They can be used to model a huge variety of things (see how many more you can come up with, they're everywhere!). Topological sort in particular is a pretty remarkable algorithm, and can be applied in many different situations from the one above. For example, finding paths through college courses with prerequisites. It's even used in UNIX systems to schedule processes according to their dependencies.<br />
<br />
Hope you enjoyed the post! Until next time,<br />
<br />
Ben<br />
Anonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com0tag:blogger.com,1999:blog-786816577681924169.post-90254515170231637982012-10-09T11:12:00.002-04:002012-12-07T00:30:43.820-05:00"Memorizing" the Unit Circle<div>I, like many others I'm sure, was told that I needed to memorize the unit circle while studying Pre-calculus in High School. This looks like a <i>very</i> daunting task at first glance, and it caused me a lot of frustration the first time I learned it.</div><div><br />
</div><div>I was taught to memorize them straight. I don't know why, because there's a much, much, better way to go about it. I'm going to start with the full unit circle and widdle down "memorization" to the bare minimum. Once you can start to see the reality of what the Unit Circle is, it becomes way easier to interpret.</div><div><br />
</div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Unit_circle_angles_color.svg/600px-Unit_circle_angles_color.svg.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="400" src="http://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Unit_circle_angles_color.svg/600px-Unit_circle_angles_color.svg.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The Unit Circle</td></tr>
</tbody></table>First off, the unit circle is just a circle of radius 1. Knowing this, we can determine that its circumference is $c = 2\pi r = 2\pi 1 = 2\pi$ radians. Points on the unit circle are easy to find knowing that the circumference is just $2\pi$. We just have to figure out what fraction of $2\pi$ our target angle is, and locate that section on the circle.<br />
<br />
So what's our goal? We need to be able to extract the trig functions from the unit circle:<br />
<div>$$sin\theta, cos\theta, tan\theta, csc\theta, sec\theta, tan\theta$$</div><div><div><div>at each interval of $\frac{\pi}{6}$, or $30˚$, and each interval of $\frac{\pi}{4}$, or $45˚$.<br />
<div><br />
</div><div>To do this, we need to know a little bit about the way that the coordinate system on the unit circle works. At any given point on the unit circle, we can make a triangle starting from the center of the circle to said point that rests on the x axis. The hypotenuse of this triangle will <i>always </i>be $1$, simply by the definition of the unit circle. We know that $sin = \frac{opposite}{hypotenuse}$ and $cos = \frac{adjacent}{hypotenuse}$ for any angle on a triangle. We have noted that our $hypotenuse$ will <i>always</i> be $1$, so the $sin$ of any angle on the unit circle will simply be the $\frac{opposite}{1}$, or the length of the opposite side, otherwise known as our $y$ coordinate. Similarly, $cos = \frac{adjacent}{1}$, or the length of the adjacent side: our $x$ coordinate.</div><div><br />
</div><div>Knowing this, the cases of $0\pi, \frac{\pi}{2}, \pi, $ and $\frac{3\pi}{2}$ become trivial -- All we need to do is point out which coordinate is $0$, and which one is $1$, and we have both $cos$ and $sin$.</div></div></div></div><div><br />
</div><div>So, what about the rest of them? These are the only three fractions that I like to keep in mind when dealing with the unit circle angles. Commit these to memory: </div><div>$$\frac{1}{2}, \frac{\sqrt2}{2}, \frac{\sqrt3}{2}$$</div><div><br />
</div><div>These (and their negations) will be our $cos$ and $sin$ values for any "special" point on the unit circle, and as such, they are all we need to remember (the rest of the trig functions can be derived from these values).</div><div><br />
</div><div>Let's first just deal with the first quadrant angles, $\frac{\pi}{6}, \frac{\pi}{4}, \frac{\pi}{3}$. The first thing that I want to do is order the fractions above from smallest to largest. I've actually written them in the correct order; so I won't bother writing them out again. Now, let's think about this for a second. In the first quadrant, out of our three points, where is $sin$ (our $y$ coordinate) the smallest? We start at $0$, and our $y$ value gets closer and closer to $1$ as the angle increases. This means that the smallest angle of our three ($\frac{\pi}{6}$) gets the smallest $sin$ value. Following this convention, we can say that our middle angle ($\frac{\pi}{4}$) gets the middle $sin$ value ($\frac{\sqrt2}{2}$), and our largest angle ($\frac{\pi}{3}$) gets the largest $sin$ value ($\frac{\sqrt3}{2}$). </div><div><br />
</div><div>But wait! Didn't we say that our $cos$ value is simply the $y$ coordinate? Yes, and as such, this idea can be applied to the $cos$ values as well. $cos$ ($x$) is decreasing as we move from $0$ to $2\pi$ on our unit circle, though, so as angles increase, $cos$ decreases. Apply the logic from before, and we have:</div><div> $$cos \frac{\pi}{6} = \frac{\sqrt3}{2}, cos \frac{\pi}{4} = \frac{\sqrt2}{2}, cos \frac{\pi}{3} = \frac{1}{2}$$</div><div><br />
</div><div>Knowing this, you know the rest of the values on the unit circle. Why? Because we can see where the $x$ or $y$ coordinates are negative, and it is obvious which one is larger than the other at any point. For example, take $\frac{5\pi}{6}$. Here, we can see that the $x$ coordinate is negative, but the $y$ coordinate is positive. So, we have a positive $sin$ and a negative $cos$. The length of the $y$ side is clearly shorter than the length of the $x$ side, so we can see that $sin \frac{5\pi}{6} = \frac{1}{2}$ and $cos \frac{5\pi}{6} = -\frac{\sqrt3}{2}$. Note: At intervals of $\frac{\pi}{4}$, we will always have the same ratio for both $sin$ and $cos$: $\frac{sqrt2}{2}$. It's just a matter of getting the signs correct!</div><div><br />
</div><div>So, what about the rest of the trig functions? Well, let's start with $tan$. We know that $tan\theta = \frac{opposite}{adjacent}$, right? Well, our $adjacent$ side on the unit circle is just $cos$. Our $opposite$ side is just $sin$. Therefore, on the unit circle, $tan\theta = \frac{sin\theta}{cos\theta}$. Since we can get $sin$ and $cos$, we can just divide them out and get our $tan$ value. Simple.</div><div><br />
</div><div>$sec\theta$, $csc\theta$, and $cot\theta$ then become trivial. All we need to do is take the reciprocals of their counterparts ($cos\theta$, $sec\theta$, and $tan\theta$ respectively). $\frac{1}{2}$ becomes $2$, $\frac{\sqrt2}{2}$ becomes $\sqrt2$, and so on.</div><div><br />
</div><div>And that's all of the trig functions for the "essential points" on the unit circle. All that is truly necessary is the recalling of three simple fractions and a few key concepts, and the whole thing becomes easy.</div><div><br />
</div><div>Hope this helps!</div><div><br />
</div><div>-Ben</div>Anonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com0tag:blogger.com,1999:blog-786816577681924169.post-87646043932103293082012-08-15T19:30:00.000-04:002012-12-07T00:31:07.751-05:00Haskell: Implementing a Fractional Data Type and Investigating the Expansion of the Square Root of 2<span style="font-size: large;">A couple of weeks ago, I completed <a href="http://projecteuler.net/problem=57" target="_blank">Project Euler #57: Investigating the Expansion of the Square Root of 2</a>. I found the problem really interesting, since it required me to write up my own fractional operations (addition, division, etc.) Today, I decided that I wanted to take my minimally defined fractional library and make it a more full-featured one. First, I'll first walk through the building of the data type and implementing fractional operations, and then I'll get to my solution of the Project Euler problem.</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">First thing's first. A <b style="font-family: "Courier New",Courier,monospace;">Fraction</b> is defined as a numerator and a denominator. My fractions consist of only Integers, and here's how the data type is defined:</span><br />
<span style="font-size: large;"><br />
</span> <script src="https://gist.github.com/3364011.js?file=frac.hs"></script><span style="font-size: large;"><br />
</span> <span style="font-size: large;"><br />
</span> <span style="font-size: large;">I wanted fractions to show up in the form <b>x / y</b>, so that is what the instance of <b style="font-family: "Courier New",Courier,monospace;">Show</b><span style="font-family: "Courier New",Courier,monospace;"> </span>I defined does.</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">So, now that we have a data type, what can we do with it? Here's a list of common functions that I think are necessary in the definition of a fraction: Addition, Subtraction, Multiplication, Division, Exponentiation, Simplification, Negation, getting the Numerator, and getting the Denominator.</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">Let's start with the simple ones:</span><br />
<span style="font-size: large;"><br />
</span> <script src="https://gist.github.com/3364033.js?file=numDemon.hs"></script><span style="font-size: large;"><br />
</span> <span style="font-size: large;"><br />
</span> <span style="font-size: large;">Those are are <b style="font-family: "Courier New",Courier,monospace;">numerator</b><span style="font-family: "Courier New",Courier,monospace;"> </span>and <b style="font-family: "Courier New",Courier,monospace;">denominator</b><span style="font-family: "Courier New",Courier,monospace;"> </span>functions. We simply take the first or second argument of the <b style="font-family: "Courier New",Courier,monospace;">Frac</b><span style="font-family: "Courier New",Courier,monospace;"> </span>in order to get the parameter that we need, and disregard the other one (using<b> <span style="font-family: "Courier New",Courier,monospace;">_</span></b>) since it's unused.</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">Simplifying is also simple enough. We just need to divide the numerator and the denominator by the greatest common divisor of the two. Since Haskell gives us a <b style="font-family: "Courier New",Courier,monospace;">GCD</b><span style="font-family: "Courier New",Courier,monospace;"> </span>function, this is pretty darn simple. Here's how it's implemented:</span><br />
<span style="font-size: large;"><br />
</span> <script src="https://gist.github.com/3364060.js?file=simplify.hs"></script><span style="font-size: large;"><br />
</span> <span style="font-size: large;"><br />
</span> <span style="font-size: large;">Easy! We just make a new fraction out of the divided values. The function<b> <span style="font-family: "Courier New",Courier,monospace;">`quot`</span></b> is basically just integer division that truncates the result towards 0. The second half of that is unimportant in this instance, since we're dividing by the <b style="font-family: "Courier New",Courier,monospace;">GCD </b>of the numbers and the result will always be an integer value.</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">Okay, so we have a couple of functions. Great! But, what about implementing addition, subtraction, etc? Well, basically what we want to do here is define a couple of instances of numeric types for our Fractional data type. </span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">The first instance we need to derive is <b style="font-family: "Courier New",Courier,monospace;">Num</b>, which has a few operations that we want: </span><br />
<span style="font-size: large;"><br />
</span> <script src="https://gist.github.com/3364121.js?file=FracNum.hs"></script><span style="font-size: large;"><br />
</span> <span style="font-size: large;"><br />
</span> <span style="font-size: large;">The three "common" operators (<span style="font-family: "Courier New",Courier,monospace;">+,</span><b style="font-family: "Courier New",Courier,monospace;"> -</b><span style="font-family: "Courier New",Courier,monospace;">,</span><b style="font-family: "Courier New",Courier,monospace;"> *</b>) are defined here, which means that we can now evaluate expressions such as <b style="font-family: "Courier New",Courier,monospace;">Frac 1 2 * Frac 1 2</b>. Cool, right? Those three operations are fairly self-explanatory, and the code (hopefully) isn't too tough to follow. There are also three other function definitions here, that maybe aren't quite as clear. The function <b style="font-family: "Courier New",Courier,monospace;">negate</b><span style="font-family: "Courier New",Courier,monospace;"> </span>simply turns a negative fraction positive, or a positive fraction negative. The function <b style="font-family: "Courier New",Courier,monospace;">abs</b><span style="font-family: "Courier New",Courier,monospace;"> </span>takes the absolute value of the fraction. This is fairly simple; we just use a function that maps <b style="font-family: "Courier New",Courier,monospace;">abs</b><span style="font-family: "Courier New",Courier,monospace;"> </span>(Integer absolute value) over the numerator and denominator of the fraction. The last is <b style="font-family: "Courier New",Courier,monospace;">signum</b>, which looks probably the most complicated, but all it actually does is tells us whether the <b style="font-family: "Courier New",Courier,monospace;">Fraction </b>is less than, greater than, or equal to 0 (returning <span style="font-family: "Courier New",Courier,monospace;">-1</span>, <span style="font-family: "Courier New",Courier,monospace;">1</span>, and<span style="font-family: "Courier New",Courier,monospace;"> 0</span>, respectively).</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">Cool, so since we got all of those functions out of <b style="font-family: "Courier New",Courier,monospace;">Num</b>, where can we find the rest? We're missing <b>/</b>, so we'll make our <b style="font-family: "Courier New",Courier,monospace;">Fraction</b><span style="font-family: "Courier New",Courier,monospace;"> </span>an instance of <b style="font-family: "Courier New",Courier,monospace;">Fractional</b>. Seems appropriate, right?</span><br />
<span style="font-size: large;"><br />
</span> <script src="https://gist.github.com/3364265.js?file=FracFrac.hs"></script><span style="font-size: large;"><br />
</span> <span style="font-size: large;"><br />
</span> <span style="font-size: large;">Cool, we get division out of that, which is simple enough! We just take the reciprocal of the second fraction, and multiply the two. This may look a little funky, so I'll explain that last. </span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;"><br />
</span> <span style="font-size: large;">The other two functions defined here are <b style="font-family: "Courier New",Courier,monospace;">recip</b> and <b style="font-family: "Courier New",Courier,monospace;">fromRational</b>. <b style="font-family: "Courier New",Courier,monospace;">recip</b> simply flips the numerator and denominator in a <b style="font-family: "Courier New",Courier,monospace;">Fraction</b>, and this is easily handled with pattern matching. <b style="font-family: "Courier New",Courier,monospace;">fromRational</b> takes a rational number (which is provided the <b style="font-family: "Courier New",Courier,monospace;">numerator</b> and <b style="font-family: "Courier New",Courier,monospace;">denominator</b> functions) and turns it into a <b style="font-family: "Courier New",Courier,monospace;">Fraction</b>. Knowing what the <b style="font-family: "Courier New",Courier,monospace;">numerator</b> and <b style="font-family: "Courier New",Courier,monospace;">denominator</b> functions are, this function is incredibly trivial.</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">Okay, so about that division function. Our division appears to take only one argument, but it actually takes two. <b style="font-family: "Courier New",Courier,monospace;">(*) f f'</b> is just syntactic sugar for<span style="font-family: "Courier New",Courier,monospace;"> </span><b style="font-family: "Courier New",Courier,monospace;">f * f'</b>. We want to compose the function <b style="font-family: "Courier New",Courier,monospace;">f*</b> with the function <b style="font-family: "Courier New",Courier,monospace;">recip f'</b>, so we use the function <b style="font-family: "Courier New",Courier,monospace;">(*)</b>, apply it to <b style="font-family: "Courier New",Courier,monospace;">f</b>, and then apply that to the function <b style="font-family: "Courier New",Courier,monospace;">recip</b>, which is then called on the second argument of the function. This kind of function is hard to read for a lot of people, but it definitely comes more naturally with Haskell practice.</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;"><br />
</span> <span style="font-size: large;">Alright! We've got plenty of functions at our disposal now, so what's next? Well, we want to be able to compare <b style="font-family: "Courier New",Courier,monospace;">Fractions</b>, so let's go ahead and make it an instance of<b> <span style="font-family: "Courier New",Courier,monospace;">Eq</span> </b>and <b style="font-family: "Courier New",Courier,monospace;">Ord</b>, which allow us to check equivalency and order, respectively.</span><br />
<span style="font-size: large;"><br />
</span> <script src="https://gist.github.com/3364345.js?file=EqOrd.hs"></script><span style="font-size: large;"><br />
</span> <span style="font-size: large;"><br />
</span> <span style="font-size: large;">There's a lot of functions that are similar in structure to our <b>/</b> function from earlier, so understanding what is happening with those will make these much easier to understand.</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">Starting with <b style="font-family: "Courier New",Courier,monospace;">Eq</b>, we have two functions, <b style="font-family: "Courier New",Courier,monospace;">/=</b> (not equals) and <b style="font-family: "Courier New",Courier,monospace;">==</b>. <b style="font-family: "Courier New",Courier,monospace;">==</b> simply checks to see if the simplified version of <b style="font-family: "Courier New",Courier,monospace;">f</b> and the simplified version of <b style="font-family: "Courier New",Courier,monospace;">f'</b> have the same numerators and denominators. <b style="font-family: "Courier New",Courier,monospace;">/=</b> basically just returns the opposite of <b style="font-family: "Courier New",Courier,monospace;">==</b> by calling <b style="font-family: "Courier New",Courier,monospace;">not</b> on the result.</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;"><b style="font-family: "Courier New",Courier,monospace;">Ord</b> isn't too tough either. First we have <b style="font-family: "Courier New",Courier,monospace;">compare</b>, which returns a comparator (<b style="font-family: "Courier New",Courier,monospace;">LT</b>, <b style="font-family: "Courier New",Courier,monospace;">GT</b>, or <b style="font-family: "Courier New",Courier,monospace;">EQ</b>) based on the relationship between two <b style="font-family: "Courier New",Courier,monospace;">Fractions</b>. The inequality functions are all designed around this function. The <b style="font-family: "Courier New",Courier,monospace;">max</b> and <b style="font-family: "Courier New",Courier,monospace;">min</b> functions are simple, and designed around our inequality functions.</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">So, what's left? I decided I wanted to experiment, so I decided to also make <b style="font-family: "Courier New",Courier,monospace;">Fraction</b> an instance of <b style="font-family: "Courier New",Courier,monospace;"><a href="http://learnyouahaskell.com/functors-applicative-functors-and-monoids#monoids">Monoid</a></b>, and give our <b style="font-family: "Courier New",Courier,monospace;">Fraction</b> a simpler constructor. Here's the rest!</span><br />
<span style="font-size: large;"><br />
</span> <script src="https://gist.github.com/3364418.js?file=MonoidConstructor.hs"></script><span style="font-size: large;"><br />
</span> <span style="font-size: large;"><br />
</span> <span style="font-size: large;">The instance of <b style="font-family: "Courier New",Courier,monospace;">Monoid</b> defines a couple of functions: <b style="font-family: "Courier New",Courier,monospace;">mempty</b>, <b style="font-family: "Courier New",Courier,monospace;">mappend</b>, and <b style="font-family: "Courier New",Courier,monospace;">mconcat</b>. <b style="font-family: "Courier New",Courier,monospace;">mempty</b> is the minimal value for the <b style="font-family: "Courier New",Courier,monospace;">Monoid</b>.<b> </b>I chose 0 (which gets automatically boxed into a <b style="font-family: "Courier New",Courier,monospace;">Fraction</b>). <b style="font-family: "Courier New",Courier,monospace;">mappend</b> is a combiner function, and I thought that addition of fractions fit this bill well enough, so I simply gave it an alias. <b style="font-family: "Courier New",Courier,monospace;">mconcat</b> concatenates a list of fractions with some function, and in our case, sums the entire list.</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">Our type constructor (<b style="font-family: "Courier New",Courier,monospace;">%</b>) takes two integers and boxes them up into a <b style="font-family: "Courier New",Courier,monospace;">Fraction</b>, which is then simplified. Easy enough.</span><br />
<br />
<span style="font-size: large;">One final note on all of this. You may have noticed that exponentiation (<b style="font-family: "Courier New",Courier,monospace;">^</b>) isn't implemented here. But, it actually is! Turns out, any data type that has a <b style="font-family: "Courier New",Courier,monospace;">Num</b><span style="font-family: "Courier New",Courier,monospace;"> </span> instance defined (like our <b style="font-family: "Courier New",Courier,monospace;">Fraction</b>) can use the <b>^</b> operator. So things like <b style="font-family: "Courier New",Courier,monospace;">(1 % 2)^2</b> actually get evaluated properly. (In this case, to <b style="font-family: "Courier New",Courier,monospace;">1 % 4</b>).</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">All right! Let's use this library to solve <a href="http://projecteuler.net/problem=57" target="_blank">Project Euler #57</a>! Knowing how to use the <b style="font-family: "Courier New",Courier,monospace;">Fraction</b> library, this should be relatively easy to follow. Here we go:</span><br />
<span style="font-size: large;"><br />
</span> <script src="https://gist.github.com/3364532.js?file=Euler057.hs"></script><span style="font-size: large;"><br />
</span> <span style="font-size: large;"><br />
</span> <span style="font-size: large;">Fairly simple. We directly implement the function and run it on each iteration, building a list as we go. We then filter our list so that the only entries left are the ones that have more digits in the numerator than the denominator. Lastly, we evaluate the length of that list, which gives us the answer.</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">Pretty neat, huh? Here's the full <b style="font-family: "Courier New",Courier,monospace;">Fraction.hs</b> source file:</span><br />
<br />
<script src="https://gist.github.com/3364744.js?file=Fraction.hs"></script><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">Until next time!</span><br />
<span style="font-size: large;"><br />
</span> <span style="font-size: large;">Ben</span><br />
<span style="font-size: large;"><br />
</span>Anonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com1tag:blogger.com,1999:blog-786816577681924169.post-27824806480208773452012-08-05T13:52:00.000-04:002012-12-07T00:31:20.955-05:00My first real code golf program!I've always been interested in <a href="http://en.wikipedia.org/wiki/Code_golf">Code golf</a>, which essentially boils down to creating the shortest possible program that completes some task.<br />
<br />
I finally got around to completing one of these challenges, and though I wasn't really that close to winning, it was fun to mess around with it it was one of the shorter <a href="http://en.wikipedia.org/wiki/Haskell_%28programming_language%29">Haskell</a> solutions!<br />
<br />
So, the challenge I attempted was <a href="http://www.reddit.com/r/tinycode/comments/x41tf/how_about_a_challenge_4_find_the_longest_common/" target="_blank">Reddit's Tiny Code Challenge #4</a>, asking for the shortest program that finds the longest identical subsequence in a string. <br />
<br />
Directly from the challenge page:<br />
<blockquote class="tr_bq">For example:<br />
<code>aaabbbbccc aabccdcdd -> aab, bcc</code><br />
<code>adeaabbbbccc aabccdedcdd -> aab, bcc</code><br />
<code>abcdef ghijk -> nothing</code><br />
<code>abcdef fghijk -> f</code></blockquote>So, here was my solution in Haskell:<br />
<br />
<script src="https://gist.github.com/3265911.js?file=tc04.hs"></script><br />
Let's break this down into steps, since it probably looks like a bunch of mumbo-jumbo!<br />
<br />
<script src="https://gist.github.com/3266149.js?file=tc04Comments.hs"></script><br />
<br />
<br />
And there you have it! 193 characters of Haskell code got us a pretty cool program.<br />
<br />
Here's a little bit of output:<span style="font-family: "Courier New",Courier,monospace; font-size: x-small;"> </span><br />
<blockquote class="tr_bq"><blockquote class="tr_bq"><span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;">>tc04.exe</span> <code>"aaabbbbccc" "aabccdcdd"</code></span><br />
<div style="font-family: "Courier New",Courier,monospace;"><span style="font-size: small;">>"bcc"</span></div><div style="font-family: "Courier New",Courier,monospace;"><span style="font-size: small;">>tc04.exe "abcdef" "ghijk"</span></div><div style="font-family: "Courier New",Courier,monospace;"><span style="font-size: small;">>tc04.exe "abcdef" "fghijk"</span></div><div style="font-family: "Courier New",Courier,monospace;"><span style="font-size: small;">>"f"</span></div><div style="font-family: "Courier New",Courier,monospace;"><span style="font-size: small;">>tc04.exe "fhqwhgads" "where are all the dragons?"</span></div><span style="font-family: "Courier New",Courier,monospace; font-size: xx-small;"><span style="font-size: x-small;"><span style="font-size: small;">>"wh"</span> </span></span></blockquote></blockquote>Cool! :)<br />
<br />
-BenAnonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com0tag:blogger.com,1999:blog-786816577681924169.post-39473650145541629002012-07-17T00:59:00.001-04:002012-12-07T00:31:31.575-05:00Introducing fhck, a brainf*ck interpreter written in Haskell!If you haven't heard of <a href="http://en.wikipedia.org/wiki/Brainfuck">brainf*ck</a>, you should <i>totally</i> check it out, because it's probably the coolest programming language of them all!<br />
<br />
Also, probably one of the simplest...<br />
<br />
That's why I decided to write an interpreter for it!<br />
<br />
This is the product of about 3 days of work, give or take, but the sessions were long and I put a lot into it.<br />
<br />
If you're a Haskeller reading this, please feel free to critique it (I'm sure it could be improved in many places)!<br />
<br />
If you're not, please feel free to check it out anyway! I encourage everyone to play around with brainfuck a little bit because it's actually a lot of fun.<br />
<br />
If you're not familiar with the language, a quick look through brainfuck's <a href="http://en.wikipedia.org/wiki/Brainfuck">Wikipedia</a> page should help you to understand what's going on in brainfuck (it's not too complex).<br />
<br />
With the interpreter, you can write a file, say <b>thisisbf.b</b>, containing the classic "Hello, world!" brainfuck program directly from the wikipedia page: <br />
<br />
<script src="https://gist.github.com/3127236.js">
</script><br />
and pass it to the interpreter:<br />
<br />
on Windows:<br />
<blockquote>$ build\windows\fhck.exe <b>thisisbrainfuck.b</b></blockquote>or Linux (or presumably Mac OSX, though I haven't tried): <br />
<blockquote>$ build/linux/fhck <b>thisisbrainfuck.b</b></blockquote>...and it should print "Hello, world!" to your console!<br />
<br />
Neat, right? (I think so!)<br />
<br />
Download link/source is located here: <a href="https://github.com/5outh/fhck">fhck 1.0</a><br />
<br />
Enjoy!Anonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com0tag:blogger.com,1999:blog-786816577681924169.post-17734992098734883252012-07-11T16:59:00.004-04:002012-12-07T00:31:43.525-05:0099 Haskell Problems #13: Run-length Encoding<span style="font-family: Arial,Helvetica,sans-serif;">I've been working on </span><a href="http://www.haskell.org/haskellwiki/H-99:_Ninety-Nine_Haskell_Problems" style="font-family: Arial,Helvetica,sans-serif;" target="_blank">The Ninety-Nine Haskell Problems</a><span style="font-family: Arial,Helvetica,sans-serif;"> </span><span style="font-family: Arial,Helvetica,sans-serif;">lately, and I've come across a particular one that seems to be practical, and was a lot of fun to implement!</span><br />
<br />
<span style="font-family: Arial,Helvetica,sans-serif;">The 99 Problems start out with a <b>lot</b> of list-based exercises, and eventually you're asked to build up to a point where you can implement a function that performs <a href="http://en.wikipedia.org/wiki/Run-length_encoding" target="_blank">Run-length encoding</a> on a <span style="font-family: "Courier New",Courier,monospace;">String</span>. Basically what this means is, if we have a string, say <span style="font-family: "Courier New",Courier,monospace;">"aabbcccd"</span>, we'd group together the adjacent, identical characters, count them, and then output the characters along with their counts in a new list.</span><br />
<br />
<span style="font-family: Arial,Helvetica,sans-serif;">Thus, the previous example <span style="font-family: "Courier New",Courier,monospace;">"aabbcccd"</span> would output something like this: <span style="font-family: "Courier New",Courier,monospace;">a2b2c3d</span></span><br />
<br />
<span style="font-family: Arial,Helvetica,sans-serif;">A couple of the 99 Problems ask you to implement this indirectly, meaning, actually group the identical characters into sub-lists and count the length of those lists. This is fairly trivial, making use of Haskell's </span><span style="font-family: Arial,Helvetica,sans-serif;">built-in</span><span style="font-family: Arial,Helvetica,sans-serif;"> function <i style="font-family: "Courier New",Courier,monospace;">group</i><b>, </b>which takes a list and separates it in exactly the manner we would need in order to get sub-lists of adjacent identical values.</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;"><br />
</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;">The real fun came in <a href="http://www.haskell.org/haskellwiki/99_questions/11_to_20#Problem_13" target="_blank">Problem 13</a>, where it asks for a <i>direct</i> implementation of the run-length encoding algorithm, meaning, we're no longer allowed to split up the groups in the way that we were before. Additionally, the problem asks that we use a data wrapper on each ending value so we are able to discern <span style="font-family: "Courier New",Courier,monospace;">Single</span> values (example in above: d) vs <span style="font-family: "Courier New",Courier,monospace;">Multiple</span> values (ex: a2).</span><br />
<br />
<span style="font-family: Arial,Helvetica,sans-serif;">Here's what I came up with:</span><br />
<br />
<script src="https://gist.github.com/3093214.js"> </script><br />
<br />
<span style="font-family: Arial,Helvetica,sans-serif;">Let's take a look at this.</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;"><br />
</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;">So, first I defined a new data type called Count that can be either a <span style="font-family: "Courier New",Courier,monospace;">Single</span> that contains a character, or a<span style="font-family: "Courier New",Courier,monospace;"> Multiple</span> that contains a character and it's count (as an <span style="font-family: "Courier New",Courier,monospace;">Int</span>)</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;"><u></u></span><br />
<span style="font-family: Arial,Helvetica,sans-serif;">What <i style="font-family: "Courier New",Courier,monospace;">encodeDirect</i> does is actually parses a list of <span style="font-family: "Courier New",Courier,monospace;">Char</span>s (which, in Haskell, can be represented as a <span style="font-family: "Courier New",Courier,monospace;">String</span>, like <span style="font-family: "Courier New",Courier,monospace;">"aabbcccd"</span>) into a list that looks something like this:</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;"><br />
</span><br />
<div style="font-family: "Courier New",Courier,monospace;">[Multiple 2 a, Multiple 2 b, Multiple 3 c, Single d]</div><span style="font-family: Arial,Helvetica,sans-serif;"><br />
</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;">The procedure is as follows:</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;"><br />
</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;">First, we use encode every character in our input set by using a <i style="font-family: "Courier New",Courier,monospace;">foldr </i>and an <i style="font-family: "Courier New",Courier,monospace;">encode</i> function in order to get a list that contains <span style="font-family: "Courier New",Courier,monospace;">2-tuples</span> with our character as the second value, and its count as the first. ( <span style="font-family: "Courier New",Courier,monospace;"> [(2, 'a'), (2, 'b') ... ]</span> )</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;"><br />
</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;">The encode function might look a little cryptic, but broken down, it makes sense. First, if we have an empty resultant list of <span style="font-family: "Courier New",Courier,monospace;">Count</span>s, we need to put the first character we encounter in the resultant list. Once we have a resultant list (no matter how small), we are able to <i style="font-family: "Courier New",Courier,monospace;">encode</i> the other values by following some logic:</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;">1. If the first character value in the resultant list matches what we are currently trying <i style="font-family: "Courier New",Courier,monospace;">encode</i>, we simply need to step up the count on that entry.</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;">2. Otherwise, we need to add the new character to the front of the list with a count of 1.</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;"><br />
</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;">When the <i style="font-family: "Courier New",Courier,monospace;">foldr</i> is complete, we have a nice list that looks just like how I described previously.</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;"><br />
</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;">Now, to get everything wrapped up into a <span style="font-family: "Courier New",Courier,monospace;">Count </span>declaration, we simply map the <i style="font-family: "Courier New",Courier,monospace;">toCount </i>function over the list we just generated. The<i style="font-family: "Courier New",Courier,monospace;"> toCount</i> function takes one of our <span style="font-family: "Courier New",Courier,monospace;">2-tuple</span> values and creates a <span style="font-family: "Courier New",Courier,monospace;">Single</span> value out of it if its count is equivalent to 1, otherwise it packs it into a <span style="font-family: "Courier New",Courier,monospace;">Multiple </span>value.</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;"><br />
</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;">Once this is mapped, we have our resultant list!</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;"><br />
</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;"><i style="font-family: "Courier New",Courier,monospace;">encodeDirect</i> </span><span style="font-family: Arial,Helvetica,sans-serif;">"aabbcccd" = </span><span style="font-family: Arial,Helvetica,sans-serif;"><span style="font-family: "Courier New",Courier,monospace;">[Multiple 2 a, Multiple 2 b, Multiple 3 c, Single d] </span></span><br />
<br />
<span style="font-family: Arial,Helvetica,sans-serif;">PS:I picked up a bit of new syntax from a video I watched last night, located here: <a href="http://www.youtube.com/watch?v=mtvoOIsN-GU" target="_blank">Sokoban Live Coding.</a></span><span style="font-family: Arial,Helvetica,sans-serif;"> I learned a lot from it. If you're interested in Haskell, check it out.</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;"><br />
</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;">Until next time!</span><br />
<span style="font-family: Arial,Helvetica,sans-serif;"><br />
5outh</span>Anonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com0tag:blogger.com,1999:blog-786816577681924169.post-19587064152290411252012-04-03T02:49:00.003-04:002012-12-07T00:31:53.982-05:00Functional Sorting in Haskell<span style="font-family: Verdana, sans-serif;">Sorting is a fairly major topic of study when it comes to programming, and there are <a href="http://en.wikipedia.org/wiki/Sorting_algorithm">tons of ways to do it.</a> I don't know how interesting these algorithms are to other people, but they have always been an interest of mine. I think they're neat because they illustrate that there can be several ways to tackle even the simplest of tasks (which, in my opinion, is one of the things that makes programming so fun).</span><br />
<div><span style="font-family: Verdana, sans-serif;"><br />
</span></div><div><span style="font-family: Verdana, sans-serif;">Since I'm always looking for new things to try, I've decided to take a few of the common sorting algorithms and implement them on my own in <a href="http://www.haskell.org/haskellwiki/Haskell">Haskell</a>. For those of you who aren't familiar with it, here's a brief overview.</span></div><div><span style="font-family: Verdana, sans-serif;"><br />
</span></div><div><span style="font-family: Verdana, sans-serif;">Most programming languages (Java, C++, Python, Ruby, Javascript, etc) are defined as <i>imperative</i>, which basically means that programs are executed line-by-line. Many of the aforementioned languages are also defined as <i>object-oriented</i>, meaning that virtually everything is a part of an <i>object</i>. I won't get into the details about <i><a href="http://en.wikipedia.org/wiki/Object-oriented_programming">OOP</a></i> here, since we're talking about Haskell, but you can read about it if you'd like. Haskell differs from these languages by conforming to a paradigm in which everything is defined as a <i>function</i>. Objects are not present here, and iterative steps don't quite work in the same way -- nothing is being executed line-by-line -- all instructions are defined in functions. This is a rather mind-blowing concept, but it's extremely cool once you can get a mental grasp on it.</span></div><div><span style="font-family: Verdana, sans-serif;"><br />
</span></div><div><span style="font-family: Verdana, sans-serif;">Back to the point of the blog post. I'll be covering how to implement three sorting algorithms in a functional manner: <a href="http://en.wikipedia.org/wiki/Bubble_sort">Bubble Sort</a>, <a href="http://en.wikipedia.org/wiki/Insertion_sort">Insertion Sort</a>, and finally, <a href="http://en.wikipedia.org/wiki/Quicksort">Quicksort</a>. If you don't have a background in Haskell, this might all come off as programming jargon, but if you're looking for an interesting new look at these algorithms you've seen a billion times implemented imperatively, or are interested in picking up Haskell as a hobby or something, I'd recommend reading on.</span></div><div><span style="font-family: Verdana, sans-serif;"><br />
</span></div><div><span style="font-family: Verdana, sans-serif;"><b>Bubble Sort:</b></span></div><div><span style="font-family: Verdana, sans-serif;">The bubble sort algorithm is as follows:</span></div><div><span style="font-family: Verdana, sans-serif;">1. Take an array's first two elements (we'll call the first one x, and the second one y)</span></div><div><span style="font-family: Verdana, sans-serif;">2. If x is less than y, leave those elements alone. If not, swap y with x, so that the array now reads</span></div><div><span style="font-family: Verdana, sans-serif;">[y, x, (the rest of the array)]</span></div><div><span style="font-family: Verdana, sans-serif;">3. Repeat this for each element in the array, swapping as it goes along.</span></div><div><span style="font-family: Verdana, sans-serif;">4. Check to see if the list is sorted. If not, rerun the algorithm on the result of the last iteration of the function.</span></div><div><span style="font-family: Verdana, sans-serif;">5. When list is sorted, return the result.</span></div><div><span style="font-family: Verdana, sans-serif;"><br />
</span></div><div><span style="font-family: Verdana, sans-serif;">Here it is in Haskell:</span> <span style="font-family: Verdana, sans-serif;"><br />
</span> <br />
<div><script src="https://gist.github.com/2289680.js?file=gistfile1.hs">
</script> </div><span style="font-family: Verdana, sans-serif;">Rather long, but effective. Bubble Sort isn't the most efficient sorting algorithm, especially since it has to do all of that checking if it's already sorted. I'm not a big fan of this one.</span><br />
<span style="font-family: Verdana, sans-serif;"><br />
</span> <span style="font-family: Verdana, sans-serif;"><b>Insertion Sort:</b></span><br />
<span style="font-family: Verdana, sans-serif;">Insertion sort is pretty simple to follow. We start with an array, as always, and then follow these steps:</span><br />
<span style="font-family: Verdana, sans-serif;">1. Pop the first element of the array off of the array, and populate a new array with it.</span><br />
<span style="font-family: Verdana, sans-serif;">2. For each element after the first in the array, insert it at it's proper sorted location in the array.</span><br />
<span style="font-family: Verdana, sans-serif;">3. Return the final list of sorted numbers.</span><br />
<span style="font-family: Verdana, sans-serif;"><br />
</span> <span style="font-family: Verdana, sans-serif;">Let's see what this looks like in Haskell:</span><br />
<br />
<script src="https://gist.github.com/2289711.js?file=gistfile1.hs">
</script> <span style="font-family: Verdana, sans-serif;">How elegant is that? This could take many lines in an imperative language, but we make use of Haskell's recursive <i>foldr</i> method to populate our sorted list, and the appropriately named function <i>insert</i> taken from the <b>Data.List</b> package helps us to populate it in the exact manner we're looking for.</span><br />
<span style="font-family: Verdana, sans-serif;"><br />
</span> <span style="font-family: Verdana, sans-serif;"><b>Quicksort:</b></span><br />
<span style="font-family: Verdana, sans-serif;">The Quicksort algorithm can be pretty intimidating, especially at first glance. This is because it makes use of <a href="http://en.wikipedia.org/wiki/Recursion_(computer_science)">recursion</a> to accomplish it's sorting, which is a particularly tough concept to fully understand when it comes to programming. The instructions for Quicksort look a little something like this:</span><br />
<span style="font-family: Verdana, sans-serif;">1. Choose any point in the array as a "pivot" point.</span><br />
<span style="font-family: Verdana, sans-serif;">2. Create two new arrays, one populated with the numbers in the array less than the pivot, and another with the numbers greater than the pivot.</span><br />
<span style="font-family: Verdana, sans-serif;">3. Recursively call Quicksort on both of the lists, until these lists (inevitably) turn up empty, at which point the function returns an empty list.</span><br />
<span style="font-family: Verdana, sans-serif;">4. At this point, the recursion unwinds itself, and we concatenate the recursively sorted arrays together.</span> <span style="font-family: Verdana, sans-serif;">(I would recommend <a href="http://en.wikipedia.org/wiki/Quicksort">reading up on this algorithm</a> if the above instructions do not make sense; I am not the best at explaining things)</span><br />
<span style="font-family: Verdana, sans-serif;"><br />
</span> <span style="font-family: Verdana, sans-serif;">Sounds complicated, right? Here's a Haskell implementation:</span><br />
<span style="font-family: Verdana, sans-serif;"><br />
</span></div><script src="https://gist.github.com/2289792.js?file=gistfile1.hs">
</script> <span style="font-family: Verdana, sans-serif;">What? It only takes <i>five lines </i>to implement Quicksort? This is why Haskell is so cool to me. Compare this with something like, say, a <a href="http://gauss.ececs.uc.edu/Courses/C321/html/quicksort.java.html">Java</a> implementation, and you'll see what I mean. It's just so simple! We're simply defining quickSort as a quickSorted list of smaller numbers concatenated with a singleton list containing a pivot, concatenated with a quickSorted list of larger numbers. Easy to read, though the algorithm may seem very complicated.</span><br />
<br />
<span style="font-family: Verdana, sans-serif;">Hope you enjoyed the read!</span><br />
<span style="font-family: Verdana, sans-serif;"><br />
</span> <span style="font-family: Verdana, sans-serif;">-Ben</span>Anonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com1tag:blogger.com,1999:blog-786816577681924169.post-68743281609822234792012-03-21T17:23:00.002-04:002012-12-07T00:32:06.346-05:00<span style="background-color: white; color: #333333; font-family: 'Trebuchet MS', sans-serif; line-height: 20px; text-align: left;">Hey! [Insert obligatory first post statement here]</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><br />
</span> <span style="font-family: 'Trebuchet MS', sans-serif;"><span style="background-color: white; color: #333333; line-height: 20px; text-align: left;">I've been messing around with </span><a href="http://unity3d.com/" style="background-color: white; color: #999999; line-height: 20px; text-align: left; text-decoration: none;">Unity3d</a><span style="background-color: white; color: #333333; line-height: 20px; text-align: left;"> for the past week or so, and I have to say, it's very fun and simple to use.</span></span> <span style="background-color: white; color: #333333; font-family: 'Trebuchet MS', sans-serif; line-height: 20px; text-align: left;"><br />
</span><br />
<span style="background-color: white; color: #333333; font-family: 'Trebuchet MS', sans-serif; line-height: 20px; text-align: left;">That said, one of the first things that I thought to do after watching a bunch of tutorials and reading into various sample scripts was to implement an intuitive third person camera interface. I've seen several tutorials regarding how to move around using the WASD keys and the like, but not much regarding how to piece together a nice third person camera system. So, I decided to go ahead and make one. </span><br />
<span style="background-color: white; color: #333333; font-family: 'Trebuchet MS', sans-serif; line-height: 20px; text-align: left;"><br />
</span> <span style="font-family: 'Trebuchet MS', sans-serif;"><span style="background-color: white; color: #333333; line-height: 20px; text-align: left;">Please keep in mind that I am a beginner</span><i style="background-color: white; color: #333333; line-height: 20px; text-align: left;">. </i><span style="background-color: white; color: #333333; line-height: 20px; text-align: left;">There may be code issues here when things start getting more complicated, but this does work fine with a character on a flat plane (and should work for inclines mostly). This covers camera panning and zooming, as well as character movement with respect to the camera.</span></span> <span style="background-color: white; color: #333333; font-family: 'Trebuchet MS', sans-serif; line-height: 20px; text-align: left;"></span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><span style="background-color: white; color: #333333; line-height: 20px; text-align: left;">The first thing that we need to do is handle panning around the player character. I created a sphere object (as our player character), gave it the <b>Rigidbody </b>property, and created a basic floor out of a cube for our player to run around on. I gave the scene a <b>Point Light</b></span> object to see everything better, and then started the scripting.</span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Luckily, Unity3d has a standard asset script that gives us basic mouse-based camera control. The script is called M<b>ouseOrbit.js, </b>and can be found by searching through the Standard Assets or at <b>Standard Assets > Scripts > Camera Scripts > MouseOrbit</b>. This script basically takes a target as a parameter (in our case, the sphere), and circles around that target based on mouse controls. </span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">I thought that this should be tweaked in a couple of ways, so here's what I changed about it:</span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">1. Only rotate around the target object when the right mouse is held down ( this seems to be how most third-person RPGs do things these days ).</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><br />
2. Implement a zoom function using the mouse wheel!</span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">I won't get into the details of how I did this, I'll just post my <b>modified MouseOrbit.js</b> file. It should be rather easy to follow:</span><br />
<br />
<script src="https://gist.github.com/3094373.js"> </script><br />
<span style="font-family: 'Trebuchet MS', sans-serif;"><br />
</span><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">With that script attached to our M<b>ain Camera</b> object, we should be able to perform all of our cool new functions. Zooming can be done by scrolling in and out, and circular panning around our sphere (assuming that the sphere is attached to the script as the target) will only happen if the Right Mouse button is held down.</span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Now that that is working, the obvious next step would be to be able to move our character around, so that's exactly what I decided to do!</span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">We can create a new javascript (I named mine <b>MoveCharacter.js</b>) to attach to our character to perform movement relative to the camera.</span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Moving our object with respect to the camera is a bit tricky, as you'll see. Initially I thought this would be as simple as adding to Z to move forward, subtracting from Z to move backward, and so on. However, this will only move our character in one direction, <i>regardless </i>of the camera's position. This means that, even if our camera is facing west, our <i>character </i> will still only move north when we press the 'w' key. This is clearly a problem (but we'll fix it)!</span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">We need to perform a little trigonometry to get our sphere moving in the proper direction. I had a little bit of help from the community over at <a href="http://stackoverflow.com/">Stack Overflow</a> with this one. As it turns out, moving forward in space can be done like so:</span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;"> First, we take the <b>x</b> and <b>z</b> coordinates of our object with the <b>Sin</b> and <b>Cos</b> values of our current rotation and place them into a new vector <b>(Sin(rotation), 0, Cos(rotation) )</b>. This is our displacement vector, which adjusts for the rotation of our object.</span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Second, we take this displacement vector and perform our movement functions on it -- In our case, we want to multiply it by our <b>speed</b> value and adjust it for slower computers using our <b>delta time</b>. </span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Lastly, we take this new displacement vector, adjusted for rotation and applied speed, and we add it to our position in space.</span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">The resultant code for moving forward using the 'w' key can be implemented inside of our <b>update</b> function as follows:</span><br />
<br />
<script src="https://gist.github.com/3094378.js"> </script><br />
<span style="font-size: x-small;"><br />
</span><br />
<span style="font-family: Arial, Helvetica, sans-serif; font-size: x-small;">Note: the xDisplacement, yDisplacement, and displacement variables must be defined before we can use them!</span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Moving backwards is basically the same, except we want to subtract our displacement instead of adding it. The code for moving backwards is as simple as mapping our input key to "s" instead of "w" and replacing line 7 in the above code with:</span><br />
<br />
<pre class="brush: javascript">transform.position -= displacement;
</pre><br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Moving left and right, however, is a little bit more tricky, but it's nothing unmanageable. Basically all that we need to do is add 90 degrees to our angle, and follow the same basic instructions as before. If you look at a Cartesian plane and assess what we're doing so far, this makes perfect sense. What we're essentially doing is pretending that our object is actually facing directly to the right of its actual orientation, and moving forward and backward based on that rotation. This moves our character left and right. </span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">That's basically everything that this script does (there are different speeds for moving in different directions, but that's easy to grasp in the code), so I'll just go ahead and post the full <b>MoveCharacter.js </b>script for you here:</span><br />
<br />
<script src="https://gist.github.com/3094384.js"> </script><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Attaching this script to your <b>main character </b>object (whatever it may be) will allow movement based upon its rotation. </span><br />
<br />
<span style="font-family: 'Trebuchet MS', sans-serif;">Hope you enjoyed this! If you have any questions or suggestions or anything, just post a comment!</span>Anonymoushttp://www.blogger.com/profile/06806017873801457510noreply@blogger.com0