tag:blogger.com,1999:blog-65452878671252560632024-02-19T09:22:27.458-06:00Philosophy of ProgrammingOn the Philosophy of Programming.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comBlogger155125tag:blogger.com,1999:blog-6545287867125256063.post-4096339403376689182016-03-12T10:34:00.000-06:002016-03-12T10:34:08.240-06:00How I Learned to Love Loosely Coupled Test Data"<i><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">Play fast and loose with faith? So jest with heaven,</span></i><br />
<i><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">Make such unconstant children of ourselves</span></i>"<br />
-- Shakespeare, King John<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=3&SC=1&IdPlay=15#166957">Act III, Scene I, Lines 242-243</a><br />
<br />
For C# development, I love to use <a href="http://autofac.org/">AutoFac</a>! I find that AutoFac allows me to change the design of my code without having to worry about decencies. The last thing I want to have to do while refactoring my design is fix a bunch of broken unit tests. Typically if find that I have to support hard coded test setup for the system under test, when I change the signature of the constructor I'll also need to change all the test setups related to the class (this is often the case in code in which I was not the original author). This can become very annoying, since the test cases often do not really care about the setup of the system under test.<br />
<br />
If you are using a decency injection framework like AutoFac you really need to pair the loose coupling of your production code decencies with loose coupling of the setup of your system under test. Loose coupling of the setup of your system under test is exactly what a <a href="https://en.wikipedia.org/wiki/Test_fixture">test fixture</a> is for.<br />
<br />
Personally I love <a href="https://github.com/AutoFixture/AutoFixture">AutoFixture</a> for C# development! AutoFixture does all the hard work of creating a test fixture for you, all you have to do is walk up to it and ask it for what you want.<br />
<br />
If you are using AutoFac or some other IoC framework in your system under test, more likely than not, you are using a mocking framework like <a href="https://github.com/moq/moq4">Moq</a> or <a href="https://www.hibernatingrhinos.com/oss/rhino-mocks">Rhino Mocks</a>. Well, AutoFixture has you covered by allowing you to use an <a href="http://blog.ploeh.dk/2010/08/19/AutoFixtureasanauto-mockingcontainer/">auto mocking</a> plugin for <a href="https://www.nuget.org/packages/AutoFixture.AutoMoq">Moq</a>, <a href="https://www.nuget.org/packages/AutoFixture.AutoRhinoMocks">Rhino Mocks</a>, or whatever. By using auto mocking along with AutoFixture you are able to create a system under test with all the decencies already mocked out.<br />
<br />
With AutoFixture creating the system under test for you, you can freely change the signature of your constructor for your system under test without the need to change any of the setup for the test cases!<br />
<br />
Say we have the following:<br />
<br />
<script src="https://gist.github.com/MikeMKH/c97b8a26983b74fba4a2.js"></script><br />
<br />
The above is a fairly common example of C# application that I work with.<br />
<br />
We see that we are testing using two different test classes, one using AutoFixture and one not. If we uncomment out the ILog decency in the System class we would break the test setup in the test class ProgramTestsWithoutAutoFixture, but the test class SystemTestsWithAutoFixture would continue to work! For such a simple example this might not matter, but with larger code bases this can become an issue.<br />
<br />
By using AutoFixture with Moq we are pairing the same loosely coupling of the creation of our system under test with the loosely coupling we get for our decencies in our production code using AutoFac. Truly one can say, AutoFac <a href="http://mathworld.wolfram.com/Iff.html">iff</a> AutoFixture with Moq.<br />
<br />Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-91171856703949109042016-02-21T14:33:00.002-06:002016-02-21T14:33:23.132-06:00Unquote, App.config, and You"<i><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">What curious eye doth quote deformities?</span></i>"<br />
-- Shakespeare, Romeo and Juliet<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=1&SC=4&IdPlay=32#228883">Act I, Scene IV, Line 31</a><br />
<br />
I've started using <a href="http://www.swensensoftware.com/unquote">Unquote</a> for my assertions with <a href="http://fsharp.org/">F#</a> <a href="https://xunit.github.io/">xUnit</a> tests. I find that its step-by-step failure messages really help in figuring out what is going on.<br />
<br />
One thing that really throw me when I first used it was the <span style="font-family: Courier New, Courier, monospace;">System.MissingMethodException</span> exception that Unquote was throwing at runtime. Luckily I was able to find this <a href="http://stackoverflow.com/a/13847458/2370606">StackOverflow answer</a>. It seems that you need to do a binding redirect for FSharp.Core, so you'll need to set up an App.config file in your test project like this example of the <a href="http://comp-phil.blogspot.com/search/label/coin_changer">Coin Changer kata</a> (using <a href="http://comp-phil.blogspot.com/2016/01/mapfold-or-set-phasers-to-fun.html">MapFold</a>).<br />
<br />
<script src="https://gist.github.com/MikeMKH/39ff4d02f2e11d034f17.js"></script><br />
<br />
Happy coding.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-83504056670962442042016-02-15T11:38:00.001-06:002016-02-15T11:38:43.187-06:00Behold the Power of Mutation!"<span style="font-family: "helvetica neue" , "arial" , "helvetica" , sans-serif;"><i>And – ere a man hath power to say ‘ Behold!’ –</i></span>"<br />
-- Shakespeare, A Midsummer Night's Dream<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=1&SC=1&IdPlay=4#125606">Act I, Scene I, Line 147</a><br />
<br />
One of the things I found very interesting in the Pluralsight class <a href="https://app.pluralsight.com/library/courses/csharp-with-jon-skeet/table-of-contents">"Exploring C# 6 with Jon Skeet"</a> was that the new <a href="https://msdn.microsoft.com/en-us/library/dn961160.aspx">interpolated strings</a> works with expressions. Since C# is a mutable language we can easily abuse this!<br />
<br />
<script src="https://gist.github.com/MikeMKH/a32ac7aeeea3017967d1.js"></script><br />
<br />
In the above C# REPL we see that we can we can have all kinds of fun as long as we have an expression in our <a href="https://github.com/dotnet/roslyn/wiki/New-Language-Features-in-C%23-6#string-interpolation">interpolated string</a>.<br />
<br />
Example:<br />
<br />
<span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"><span style="font-family: "courier new" , "courier" , monospace;">var intValue = 0;</span></span><br />
<span style="font-family: "courier new" , "courier" , monospace;"><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">var stringValue = $"{</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">((Func<int>)(() => { intValue++; return intValue; }))()</int></span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">}"</span></span><br />
<br />
As long as the expression has a ToString value it will work. Note, stringValue will only increment intValue once and after that it will always give the same result, but it is fun nonetheless.<br />
<br />
Remember, never under estimate the power to abuse mutable languages!Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-34381725276976837342016-02-06T17:58:00.004-06:002016-02-06T17:59:25.911-06:00Item and Slice F#"<i><span style="font-family: "helvetica neue" , "arial" , "helvetica" , sans-serif;">Slice, I say. Pauca, pauca. Slice! That's my humour.</span></i>"<br />
-- Shakespeare, The Merry Wives of Windsor<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=1&SC=1&IdPlay=29#216294">Act I, Scene I, Line 125</a><br />
<br />
I've been working my way through <a href="http://davefancher.com/">Dave Fancher's</a> excellent <a href="https://www.nostarch.com/fsharp">Book of F#</a> and found an interesting example of indexing and slicing arrays in F#. Since programming is a full contact sport, here is my take on indexing and slicing in F#.<br />
<br />
<script src="https://gist.github.com/MikeMKH/3963b7d4b905a8c62f69.js"></script><br />
<br />
We have a constructor for a type called Word which takes a string and separates it into words.<br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;"><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">type Words(sentence </span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">:</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> string)</span></span><br />
<br />
We implement an index with the Item member.<br />
<span style="font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="font-family: "courier new" , "courier" , monospace;"><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">member</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> </span><span class="pl-smi" style="background-color: white; box-sizing: border-box; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">x.Item</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">(</span><span class="pl-v" style="background-color: white; box-sizing: border-box; color: #ed6a43; font-size: 12px; line-height: 16.8px; white-space: pre;">i</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">) </span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">=</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> words.</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">[</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">i</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">]</span></span><br />
<br />
This allows us to access the words of the string given.<br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;"><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">Words(sentence).</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">[</span><span style="background-color: white; color: #0086b3; font-size: 12px; line-height: 16.8px; white-space: pre;">1</span><span style="background-color: white; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">]</span></span><br />
<br />
We also implement an array slice with the GetSlice member.<br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;"><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">member</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> </span><span class="pl-smi" style="background-color: white; box-sizing: border-box; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">x.GetSlice</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">(</span><span class="pl-v" style="background-color: white; box-sizing: border-box; color: #ed6a43; font-size: 12px; line-height: 16.8px; white-space: pre;">s</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> : </span><span class="pl-v" style="background-color: white; box-sizing: border-box; color: #ed6a43; font-size: 12px; line-height: 16.8px; white-space: pre;">int</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> </span><span class="pl-v" style="background-color: white; box-sizing: border-box; color: #ed6a43; font-size: 12px; line-height: 16.8px; white-space: pre;">option</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">, </span><span class="pl-v" style="background-color: white; box-sizing: border-box; color: #ed6a43; font-size: 12px; line-height: 16.8px; white-space: pre;">e</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> : </span><span class="pl-v" style="background-color: white; box-sizing: border-box; color: #ed6a43; font-size: 12px; line-height: 16.8px; white-space: pre;">int</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> </span><span class="pl-v" style="background-color: white; box-sizing: border-box; color: #ed6a43; font-size: 12px; line-height: 16.8px; white-space: pre;">option</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">)</span></span><br />
<br />
This allows us to slice the array (substring it) of words in the string given.<br />
<span style="font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="font-family: "courier new" , "courier" , monospace;"><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">Words(sentence).</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">[</span><span style="background-color: white; color: #0086b3; font-size: 12px; line-height: 16.8px; white-space: pre;">1</span><span class="pl-smi" style="background-color: white; box-sizing: border-box; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">..</span><span style="background-color: white; color: #0086b3; font-size: 12px; line-height: 16.8px; white-space: pre;">2</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">]</span></span><br />
<br />
We can go one better than built in slice by allow for range in the slice to be bigger than the number of words.<br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;"><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">let</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> </span><span class="pl-smi" style="background-color: white; box-sizing: border-box; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">longer</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> </span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">=</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> </span><span class="pl-c1" style="background-color: white; box-sizing: border-box; color: #0086b3; font-size: 12px; line-height: 16.8px; white-space: pre;">100</span></span><br />
<span style="font-family: "courier new" , "courier" , monospace;"><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">Words(sentence).</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">[</span><span class="pl-c1" style="background-color: white; box-sizing: border-box; color: #0086b3; font-size: 12px; line-height: 16.8px; white-space: pre;">0.</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">.longer</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">]</span></span><br />
<br />
In order to allow for this we have to check to see if the end is greater than the number of words.<br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;"><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">if</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> e </span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">></span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> words.Length </span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">then</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> words.</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">[</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">s</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">..]</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> </span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">else</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> words.</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">[</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">s</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">..</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">e</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">]</span></span><br />
<br />
and<br />
<span style="font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="font-family: "courier new" , "courier" , monospace;"><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">if</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> e </span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">></span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> words.Length </span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">then</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> words </span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">else</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;"> words.</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">[..</span><span style="background-color: white; color: #333333; font-size: 12px; line-height: 16.8px; white-space: pre;">e</span><span class="pl-k" style="background-color: white; box-sizing: border-box; color: #a71d5d; font-size: 12px; line-height: 16.8px; white-space: pre;">]</span></span><br />
<br />
I hope I have shown that F# has some very nice support for objects.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-65194695533849671812016-01-24T15:24:00.001-06:002016-01-24T15:30:24.661-06:00FizzBuzz and the Roman Numeral Kata are the Same Thing!"<i><span style="font-family: "helvetica neue" , "arial" , "helvetica" , sans-serif;">The same, sir.</span></i>"<br />
<div>
-- Shakespeare, Coriolanus</div>
<div>
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=4&SC=3&IdPlay=3#123739">Act IV, Scene III, Line 7</a><br />
<div>
<br /></div>
<div>
As Homer Simpson pointed out, "Coke and Pepsi are the same thing!"<br />
<iframe allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/lfTl8-hyXJE" width="420"></iframe><br />
<br />
Similarly I plan to show that the <a href="http://rosettacode.org/wiki/FizzBuzz">FizzBuzz</a> and <a href="http://www.rosettacode.org/wiki/Roman_numerals/Encode">Roman Numeral</a> katas are the same thing! </div>
<div>
<br /></div>
<div>
First let's look at the rules of FizzBuzz.</div>
<div>
<br /></div>
<div>
<span style="font-family: "courier new" , "courier" , monospace;">f(x : int) : string</span></div>
<div>
<span style="font-family: "courier new" , "courier" , monospace;"> <i>if 3 | x and 5 | x then "FizzBuzz"</i><br /> if 3 | x then "Fizz"<br /> if 5 | x then "Buzz"<br /> default string x</span><br />
<br />
<span style="font-size: xx-small;">*note, 3 | x reads 3 divides x, in other words x / 3 does not have a remainder</span><br />
<br />
In general we see that we have two (or three) rules and a default value, we are translating from the domain into the codomain following a set of rules, in other words we have a <a href="http://mathworld.wolfram.com/Function.html">function</a>.</div>
</div>
<div>
<br /></div>
<div>
<script src="https://gist.github.com/MikeMKH/12272aa3ec3fe0a0ab84.js"></script></div>
<div>
<br /></div>
<div>
How about the Roman Numeral kata?</div>
<div>
<br /></div>
<div>
<i><span style="font-family: "courier new" , "courier" , monospace;">f(x : int) : string</span></i></div>
<div>
<i><span style="font-family: "courier new" , "courier" , monospace;"> fold</span></i></div>
<div>
<i><span style="font-family: "courier new" , "courier" , monospace;"> roman-numerals : (int, string)</span></i></div>
<div>
<i><span style="font-family: "courier new" , "courier" , monospace;"> lambda((x : int, m : string),</span></i></div>
<div>
<i><span style="font-family: "courier new" , "courier" , monospace;"> (k : int, v : string)) : (int, string)</span></i></div>
<div>
<i><span style="font-family: "courier new" , "courier" , monospace;"> while k | x then (x / k, concat m v)</span></i></div>
<div>
<i><span style="font-family: "courier new" , "courier" , monospace;"> (x, default string) : (int, string)</span></i></div>
<div>
<br /></div>
<div>
Again we see a list of rules for translation.</div>
<div>
<br /></div>
<div>
<script src="https://gist.github.com/MikeMKH/44410661b961180ab43f.js"></script></div>
<div>
<br /></div>
<div>
The only real difference to FizzBuzz is the fold across the rules, but we've hinted at this in the FizzBuzz description above. We stated that FizzBuzz has two (or three) rules, we can rewrite it using a fold with just the two rules using the fold to cover the "and" case.</div>
<div>
<br /></div>
<div>
<script src="https://gist.github.com/MikeMKH/72eb49b82d57d54bdcf2.js"></script></div>
<div>
<br /></div>
<div>
We see the FizzBuzz and Roman Numeral as having the same shape which we use in the generalization in the "2 version". Thus using the same function with a set of rules, a defaulting function, and a seed we create both the FizzBuzz and Roman Numeral kata from the same general function!</div>
Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-67223786961627229652016-01-18T10:50:00.002-06:002016-01-18T10:55:29.998-06:00MapFold OR Set Phasers to Fun"<span style="font-family: "helvetica neue" , "arial" , "helvetica" , sans-serif;"><i>Back to our brother of England.</i></span>"<br />
-- Shakespeare, Henry V<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=2&SC=4&IdPlay=38#254510">Act II, Scene IV, Line 115.1</a><br />
<br />
One of the things I love about functional programming is you can tell a lot about how a function works by just looking at its type signature. In <a href="https://github.com/fsharp/FSharpLangDesign/blob/master/FSharp-4.0/ListSeqArrayAdditions.md">F# 4.0</a> there is a new function to work with collections, here is it type signature:<br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;">('State -> 'T -> 'U * 'State) -> 'State -> C<'T> -> C<'U> * 'State</span><br />
<br />
What do you think it does?<br />
<br />
That's right this is a <a href="https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/list.fs#L86">MapFold</a>. Looking at <a href="https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/list.fs#L86">its full definition</a> we see the following:<br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;">let mapFold<'T,'State,'Result> </span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> (f:'State -> 'T -> 'Result * 'State) acc list =</span><br />
<br />
How does this work?<br />
<br />
Looking at F#'s unit tests we see the <a href="https://github.com/fsharp/fsharp/blob/8f02ecb0b79947e67e6a0ef9c482d167baf17696/src/fsharp/FSharp.Core.Unittests/FSharp.Core/Microsoft.FSharp.Collections/ListProperties.fs#L632">following test name</a>:<br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;">let ``mapFold works like map + fold`` () =</span><br />
<br />
MapFold works like a map with a fold to maintain state. I know what you are thinking maintaining state is bad, that's why functional programming is easier to reason about. This is very true, but this is not a mutable state, this is an evolving state.<br />
<br />
Let us look at an example, the <a href="http://comp-phil.blogspot.com/2014/05/the-form-of-katas.html">Coin Changer kata</a>:<br />
<br />
<script src="https://gist.github.com/MikeMKH/69cb3ff0f2dc857c44ef.js"></script><br />
<br />
The Coin Changer kata simulates one of those machines which give you back coins at a store. It takes a list of coin values and the amount of change to be given.<br />
<br />
The Coin Changer kata is interesting since it has two things going on at the same time: 1) state and 2) list processing. In the Coin Changer kata you must maintain the amount of change you have left to give along with the amount of each coin to be given back. An example would be 99 cents with an US register, you would get back 3 quarters, 2 dimes, 0 nickels, and 4 pennies.<br />
<br />
How would this example of 99 cents with an US register work with MapFold?<br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;">changeFor [25; 10; 5; 1] 99</span><br />
<br />
We'll use <span style="font-family: "courier new" , "courier" , monospace;">s</span> to hold the state, <span style="font-family: "courier new" , "courier" , monospace;">r</span> to hold the result, and <span style="font-family: "courier new" , "courier" , monospace;">x</span> to hold the current coin value we are looking at .<br />
<br />
Processing the first value: <span style="font-family: "courier new" , "courier" , monospace;">x = 25, s = 99, r = [] </span>resulting in <span style="font-family: "courier new" , "courier" , monospace;">s = 24, r = [3]</span><br />
Second value: <span style="font-family: "courier new" , "courier" , monospace;">x = 10, s = 24, r = [3] </span>resulting in <span style="font-family: "courier new" , "courier" , monospace;">s = 4, r = [3; 2]</span><br />
Third: <span style="font-family: "courier new" , "courier" , monospace;">x = 5, s = 4, r = [3; 2] </span>resulting in <span style="font-family: "courier new" , "courier" , monospace;">s = 4, r = [3; 2; 0]</span><br />
Last: <span style="font-family: "courier new" , "courier" , monospace;">x = 1, s = 4, r = [3; 2; 0] </span>resulting in <span style="font-family: "courier new" , "courier" , monospace;">s = 0, r = [3; 2; 0; 4]</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"><br /></span>
There you have it, step-by-step through the Coin Changer kata using MapFold.<br />
<br />
Guess what the source code to MapFold looks for the most part like what we just experienced. Here it is:<br />
<br />
<script src="http://gist-it.appspot.com/https://github.com/fsharp/fsharp/blob/a62def585754e61e128f9e09a6f0e18e7e07084c/src/absil/illib.fs?slice=326:341"></script><br />
<br />
We see that it loops through each member of the collection, applying the function given against the state and current member. Once there are no more members it returns a tuple of the result along with the state. For the Coin Changer kata we do not care about the state (maybe we could use it verify that we have 0 cents) so we just drop it and get the result using <span style="font-family: "courier new" , "courier" , monospace;">fst</span>.<br />
<br />
There you have it the Coin Changer kata and MapFold seem to be made for each other.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-46587740758426998832016-01-10T16:58:00.001-06:002016-01-10T16:58:24.647-06:00Data Structures Matters"<i><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">I see thee yet, in form as palpable</span></i>"<br />
-- Shakespeare, Macbeth<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=2&SC=1&IdPlay=13#160004">Act II, Scene I, Line 31 </a><br />
<br />
One of the katas we like to use at work while interviewing candidates is the <a href="http://comp-phil.blogspot.com/2015/03/roman-numeral-kata-in-one-line-with-c.html">Roman Numeral kata</a>. It is a simple kata in which you create a function which takes an integer and gives you back a string representing the roman numeral representation of the number. It is fairly simple to explain but is deep enough to get a good idea of how the person works.<br />
<br />
Here is a possible solution to the Roman Numeral kata in C#.<br />
<br />
<script src="https://gist.github.com/MikeMKH/a4d8892023e219756db4.js"></script><br />
<br />
Looking at this solution we see a few things. The solution is using <a href="https://github.com/dotnet/roslyn/wiki/New-Language-Features-in-C%23-6">C# 6.0</a> syntax but beyond that we see three major things.<br />
<br />
<ol>
<li>translation are being applied using the higher order function <a href="http://comp-phil.blogspot.com/2012/12/the-last-of-big-3-higher-order.html">Fold</a> (in C# <a href="http://www.dotnetperls.com/aggregate">Aggregate</a>)</li>
<li>mutation of the input value is used to maintain state through iterations</li>
<li>translations are held in a <a href="http://www.dotnetperls.com/dictionary">Dictionary</a></li>
</ol>
<div>
Let us look at the <a href="https://xlinux.nist.gov/dads/HTML/dictionary.html">Dictionary data structure</a> which is the main focus of this post. In general a Dictionary is not ordered, now some implementations are ordered in the order in which the key value pairs are inserted (this is the case with the <a href="http://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,74">C# implementation</a>), but this is not a property of the Dictionary data structure (see also the <a href="https://xlinux.nist.gov/dads/HTML/dictionary.html">NIST entry</a>).</div>
<div>
<br /></div>
<div>
Here is a possible solution to the Roman Numeral kata in Clojure.</div>
<div>
<br /></div>
<div>
<script src="https://gist.github.com/MikeMKH/2ebf1d1959321dfd0211.js"></script></div>
<div>
<br /></div>
<div>
Looking at this solution we see a few things.</div>
<div>
<ol>
<li>translations are being applied using the higher order function <a href="http://comp-phil.blogspot.com/2012/12/the-last-of-big-3-higher-order.html">Fold</a> (in Clojure <a href="https://clojuredocs.org/clojure.core/reduce">reduce</a>) </li>
<li><a href="https://clojuredocs.org/clojure.core/hash-map">hash maps</a> are used to maintain state through iterations</li>
<li>translations are held in a <a href="https://clojuredocs.org/clojure.core/vector">vector</a> of vectors</li>
</ol>
</div>
<div>
We see that we cannot use a Dictionary (called maps in Clojure) to hold the translation. Clojure's HashMap uses <a href="http://lampwww.epfl.ch/papers/idealhashtrees.pdf">Phil Bagwell's Hash Array Mapped Trie</a> which makes no claim about order, <a href="http://clojure.org/data_structures#Data Structures-Collections-Clojure collection hashes">in fact we see</a> that maps (and sets) are unordered while vectors (lists and seq) are ordered. Since our algorithm requires that the translations be in the order we insert them we must use a data structure which preserves this order. Thus we must used something that is ordered like a <a href="https://clojuredocs.org/clojure.core/vector">vector</a>.</div>
<div>
<br /></div>
<div>
How about F#? Here is a possible solution to the Roman Numeral kata in F#.</div>
<div>
<br /></div>
<div>
<script src="https://gist.github.com/MikeMKH/44410661b961180ab43f.js"></script></div>
<div>
<br /></div>
<div>
Looking at this solution we see a few things.</div>
<div>
<ol>
<li>translations are being applied using the higher order function <a href="http://comp-phil.blogspot.com/2012/12/the-last-of-big-3-higher-order.html">Fold</a> (using F#'s <a href="https://msdn.microsoft.com/en-us/library/ee353894.aspx">List.fold</a>)</li>
<li><a href="http://fsharpforfunandprofit.com/posts/tuples/">tuples</a> are used to maintain state through iterations</li>
<li>translations are held in a <a href="https://msdn.microsoft.com/en-us/library/dd233224.aspx">List</a></li>
</ol>
</div>
<div>
For the same reasons that we found in the Clojure solution we cannot use a Dictionary (called a <a href="https://msdn.microsoft.com/en-us/library/ee353686.aspx">Map</a> in F#) since they are ordered by F#'s generic comparison and not in the ordered in which they were inserted. Luckily we can use a <a href="https://msdn.microsoft.com/en-us/library/dd233224.aspx">List</a> which is ordered.</div>
<div>
<br /></div>
<div>
There you have it, the Roman Numeral kata in three different languages. Despite being a simple kata we have learned something about the Dictionary data structure, mainly that it does not have an order and thus should not be used in cases in which order matters.</div>
Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-41761908715711277982016-01-02T16:05:00.003-06:002016-01-02T16:05:33.953-06:00Discoveries in 2015"<i><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">So Jove, the Olympian Lord of Thunder, hied him to the bed in which he always slept; and when he had got on to it he went to sleep, with Juno of the golden throne by his side.</span></i>"<br />
-- The Iliad, Homer<br />
<a href="http://classics.mit.edu/Homer/iliad.1.i.html">Book 1</a><br />
<br />
My discoveries in 2015 of things that I've enjoyed (idea from Michael Fogus' <a href="http://blog.fogus.me/2015/12/29/the-best-things-and-stuff-of-2015/">Best Things and Stuff of 2015</a>). Order is just ordered of discovery.<br />
<h4>
Programming Languages</h4>
<br />
<ul>
<li><a href="http://www.idris-lang.org/">Idris</a></li>
</ul>
<br />
<h4>
Non-Fiction Books</h4>
<br />
<ul>
<li><a href="https://www.hackettpublishing.com/zhuangzi-the-essential-writings">Zhuangzi: The Essential Writings</a> by Zhuangzi</li>
<li><a href="https://pragprog.com/book/cjclojure/mastering-clojure-macros">Mastering Clojure Macros: Write Cleaner, Faster, Smarter Code</a> by Colin Jones</li>
<li><a href="https://en.wikipedia.org/wiki/Against_Method">Against Method</a> by Paul Feyerabend</li>
<li><a href="http://www.cambridge.org/US/academic/subjects/computer-science/programming-languages-and-applied-logic/type-theory-and-formal-proof-introduction">Type Theory and Formal Proof: An Introduction</a> by Rob Nederpelt and Herman Geuvers</li>
</ul>
<br />
<h4>
Fiction Books</h4>
<br />
<ul>
<li><a href="https://en.wikipedia.org/wiki/The_Adventures_of_Sherlock_Holmes">The Adventures of Sherlock Holmes</a> by Arthur Conan Doyle</li>
<li><a href="https://en.wikipedia.org/wiki/David_Copperfield">David Copperfield</a> by Charles Dickens</li>
<li><a href="https://en.wikipedia.org/wiki/Dracula">Dracula</a> by Bram Stoker</li>
<li><a href="https://en.wikipedia.org/wiki/Cousin_Bette">La Cousine Bette</a> by Honoré de Balzac</li>
<li><a href="https://en.wikipedia.org/wiki/The_Charterhouse_of_Parma">La Chartreuse de Parme</a> by Stendhal</li>
</ul>
<br />
<h4>
White Papers</h4>
<br />
<ul>
<li><a href="http://www.cs.nott.ac.uk/~gmh/fold.pdf">"A tutorial on the universality and expressiveness of fold"</a> by Graham Hutton</li>
<li><a href="http://eprints.eemcs.utwente.nl/7281/01/db-utwente-40501F46.pdf">"Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire"</a> by Erik Meijer, Maarten Fokkinga, Ross Paterson</li>
</ul>
<h4>
Music</h4>
<div>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Balzac_(band)">Balzac</a></li>
<li><a href="https://en.wikipedia.org/wiki/Dave_Hause">Dave Hause</a></li>
<li><a href="https://en.wikipedia.org/wiki/Masked_Intruder">Masked Intruder</a></li>
<li><a href="https://en.wikipedia.org/wiki/The_Menzingers">The Menzingers</a></li>
<li><a href="https://en.wikipedia.org/wiki/God_Is_an_Astronaut">GOD Is an Astronaut</a></li>
<li><a href="https://en.wikipedia.org/wiki/Maybeshewill">maybeshewill</a></li>
</ul>
</div>
<br />
<h4>
My Top 5 Most Popular Blog Posts of 2015</h4>
<br />
<ul>
<li><a href="http://comp-phil.blogspot.com/2015/05/intro-to-higher-order-functions.html">Intro to Higher Order Functions</a></li>
<li><a href="http://comp-phil.blogspot.com/2015/08/think-about-length-or-how-fold-can-do.html">Think About Length OR How Fold Can Do Everything, Even Count</a></li>
<li><a href="http://comp-phil.blogspot.com/2015/07/always-bet-on-math.html">Always Bet on Math</a></li>
<li><a href="http://comp-phil.blogspot.com/2015/08/bro-do-you-even-fizzbuzz.html">Bro, Do You Even FizzBuzz?!?</a></li>
<li><a href="http://comp-phil.blogspot.com/2015/06/mark-antony-shall-we-give-sign-of.html">One Data Structure to Rule Them All</a></li>
</ul>
<h4>
Most Enjoyable Conferences</h4>
<div>
Presented at: <a href="http://www.midwest.io/">Midwest.io</a></div>
<div>
Attended: <a href="http://www.thestrangeloop.com/">Strange Loop</a></div>
<div>
Location (Portland): <a href="http://clojurewest.org/">Clojure/West</a></div>
Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-25040104584564304922015-12-13T12:30:00.002-06:002015-12-13T12:30:25.577-06:00Round and Round We Go OR How to Stop Circular References in AutoFixture"<i><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">That many things, having full reference</span></i>"<br />
-- Shakespeare, Henry V<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=1&SC=2&IdPlay=38#253712">Act I, Scene II, Line 205</a><br />
<br />
I love to use <a href="http://comp-phil.blogspot.com/2015/12/autofixture-for-win.html">AutoFixture</a> to setup the the arrange part of my tests. I find that working without worrying about the arrange allows me to focus more on the task at hand. A possible downside of working this way is that <a href="https://github.com/AutoFixture/AutoFixture">AutoFixture</a> is mindlessly setting up all the test data.<br />
<br />
Having AutoFixture setup your test data is fine when working with green field classes but when working with legacy code and third party code you getting into cases in which you have circular references. What do I mean? Compare the following:<br />
<br />
Case 1:<br />
<br />
class A has members with type B<br />type B has member with type C<br />type C is a primitive<br />
<br />
Case 2:<br />
<br />
class X has members with type Y<br />
type Y has member with type Z<br />
type Z has member with type X<br />
<br />
In case 1 we have a termination point with type C, AutoFixture can happily go about and create an instance of A and populate all the members in the hierarchy with data.<br />
<br />
In case 2 we do not have a termination point, Z has a member of type X which a member of type Y which a member of type Z which goes back to X and so on. Case 2 has a circular reference and AutoFixture is unable to give us back an instance of X without going into an endless loop. Luckily AutoFixture is smart enough to figure out that it is in an endless loop and will error out telling us about the issue.<br />
<br />
What do we do if we have a class like X in legacy code or third party code? We'll we can tell AutoFixture that we will have classes like X but that it is fine to just terminate the repeating hierarchy with a null or empty. We use the following to do that:<br />
<br />
<script src="https://gist.github.com/MikeMKH/b16352ebcafb4f480f5b.js"></script><br />
<br />
I normally put this in my TestInitialize for the test class of the offender, but I can see putting in the arrange of a test class if you are mixing old and new. There you have it, a way to use AutoFixture with dirty old classes.<br />
<br />
<br />Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-87512952822107580582015-12-06T11:00:00.002-06:002015-12-06T11:00:36.158-06:00AutoFixture for the Win"<i><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">What have I kept back?</span></i>"<br />
-- Shakespeare, Antony and Cleopatra<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=5&SC=2&IdPlay=8#111930">Act V, Scene II, Line 147.2</a><br />
<br />
Anyone who has paired with me while working in C# knows that I am addicted to <a href="https://github.com/AutoFixture/AutoFixture">AutoFixture</a>. Now I do not try to add it to everything that I am working, but usually it finds its way into whatever I am working on. Why? Simply put, using AutoFixture allows me to focus on the task at hand.<br />
<br />
Here is a quick example:<br />
<br />
<script src="https://gist.github.com/MikeMKH/77794c97aa2974a8d802.js"></script><br />
<br />
In this example I am implementing the higher order function Map using the higher order function Fold (see my <a href="http://comp-phil.blogspot.com/2015/01/reducing-map-to-reduce-or-all-you-need.html">other post</a> if this interested you).<br />
<br />
What do you not see in the tests? The setting up of the test data.<br />
<br />
Why? It is not important to the task at hand. We do not need it to test the behavior of Map. Map takes a collection and a function and <b>applies</b> the function against every member of the collection producing a new collection. What we want to verify is the <b>applies</b> part, which only requires a collection and a function, the actual members of the collection (and the function) do not matter for this verification.<br />
<br />
Staying focus on the task at hand is the power of a test fixture and having someone else implement the test fixture for you is even better. Using <a href="https://www.nuget.org/packages/AutoFixture.Xunit2">AutoFixture with xUnit</a> you really do not need to think about setting up test data at all and that is good thing.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-51991197375855102212015-11-28T16:08:00.001-06:002015-11-28T16:08:05.052-06:00Axioms of Equal in Clojure"<i><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">In quantity equals not one of yours.</span></i>"<br />
-- Shakespeare, Henry IV Part I<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=3&SC=1&IdPlay=33#234486">Act III, Scene I, Line 93</a><br />
<br />
In <a href="https://mitpress.mit.edu/books/little-prover">The Little Prover</a> we find the following Axioms of Equal:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">(dethm equal-same (x) </span><br />
<span style="font-family: Courier New, Courier, monospace;"> (equal (equal x x) 't))</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;">(dethm equal-swap (x y) </span><br />
<span style="font-family: Courier New, Courier, monospace;"> (equal (equal x y) (equal y x)))</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;">(dethm equal-if (x y)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> (if (equal x y</span><br />
<span style="font-family: Courier New, Courier, monospace;"> (equal x y)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> 't)))</span><br />
<br />
I learn best by doing, so I showed myself these axioms in Clojure.<br />
<br />
<script src="https://gist.github.com/MikeMKH/c5fa50bae3dc714fc705.js"></script><br />
<br />
Looking at <span style="font-family: Courier New, Courier, monospace;">equal-same</span> we see that if we have something which is the same then those values are equal. Nothing shocking, unless you are using reference equivalence which we are not.<br />
<br />
Next we look at <span style="font-family: Courier New, Courier, monospace;">equal-swap</span> which states that equivalence is <a href="http://mathworld.wolfram.com/Commutative.html">commutative</a> meaning <span style="font-family: Courier New, Courier, monospace;">x = y</span> is the same as <span style="font-family: Courier New, Courier, monospace;">y = x</span>. Again nothing shocking.<br />
<br />
Last we look at <span style="font-family: Courier New, Courier, monospace;">equal-if</span> which states that if something is equal once it will be equal again. Note that this assumes that values are immutable which they are (for the most part) in Clojure. This axiom is rather interesting when paired with lazy evaluation, as we see with the following:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">(is (true? </span><br />
<span style="font-family: Courier New, Courier, monospace;"> (if (= :yep :yep) </span><br />
<span style="font-family: Courier New, Courier, monospace;"> (= :yep :yep) </span><br />
<span style="font-family: Courier New, Courier, monospace;"> (throw </span><br />
<span style="font-family: Courier New, Courier, monospace;"> (IllegalStateException. "How the hell did we get here?")))))</span><br />
<br />
When the statement is evaluated we do not have the Exception thrown! This is a great benefit of the <a href="http://clojure.org/special_forms#if">if special form</a> in Clojure. We do see this awesomeness has limits:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">(let [x (repeat 42)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> y x]</span><br />
<span style="font-family: Courier New, Courier, monospace;"> (is (true? </span><br />
<span style="font-family: Courier New, Courier, monospace;"> (if (= x y)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> (= x y)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> false)))) </span><br />
<br />
but fails when the infinite sequence is not the same "reference"<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">(let [x (repeat 42) </span><br />
<span style="font-family: Courier New, Courier, monospace;"> y (repeat 42)]</span><br />
<span style="font-family: Courier New, Courier, monospace;"> (is (true?</span><br />
<span style="font-family: Courier New, Courier, monospace;"> (if (= x y)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> (= x y)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> false)))))</span><br />
<br />
Despite the second example of comparing with an infinite sequence not finishing, the if special form is awesome and shows the power of the <span style="font-family: Courier New, Courier, monospace;">equal-if</span> axiom paired with lazy evaluation.<br />
<br />
These axioms are very powerful and I would argue are more useful than tests. If this interests you I would recommend reading <a href="http://www.amazon.com/Little-Prover-Daniel-P-Friedman/dp/0262527952/ref=sr_1_1?ie=UTF8&qid=1447612965&sr=8-1&keywords=the+little+prover">The Little Prover</a> or working your way through the <a href="http://www.cs.utexas.edu/users/moore/acl2/v7-1/combined-manual/index.html?topic=ACL2____A_02Flying_02Tour_02of_02ACL2">flying tour of ACL2</a>.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-71581826811129319522015-11-22T15:21:00.003-06:002015-11-22T15:25:30.933-06:00Axioms of If in Clojure"<i><span style="font-family: "helvetica neue" , "arial" , "helvetica" , sans-serif;">How if I answer no?</span></i>"<br />
-- Shakespeare, Hamlet<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=5&SC=2&IdPlay=2#119921">Act V, Scene II, Line 167</a><br />
<br />
In <a href="https://mitpress.mit.edu/books/little-prover">The Little Prover</a> we find the following Axioms of If:<br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;">(dethm if-true (x y)</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> (equal (if 't x y) x))</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="font-family: "courier new" , "courier" , monospace;">(dethm if-false (x y)</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> (equal (if 'nil x y) y)</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="font-family: "courier new" , "courier" , monospace;">(dethm if-same (x y)</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> (equal (if x y y) y)</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="font-family: "courier new" , "courier" , monospace;">(dethm if-nest-A (x y z)</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> (if x</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> (equal (if x y z) y)</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> 't))</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="font-family: "courier new" , "courier" , monospace;">(dethm if-nest-E (x y z)</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> (if x</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> 't</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> (equal (if x y z) z)))</span><br />
<br />
The way I learn best is by <strike>trying</strike> doing, so I showed myself these axioms in Clojure.<br />
<br />
<script src="https://gist.github.com/MikeMKH/462ba6709e7a9c3b561c.js"></script><br />
<br />
Looking at <span style="font-family: "courier new" , "courier" , monospace;">if-true</span> we see that if we have a true <span style="font-family: "courier new" , "courier" , monospace;"><i>premise</i></span> that we always take the <span style="font-family: "courier new" , "courier" , monospace;"><i>answer</i></span> part of the <span style="font-family: "courier new" , "courier" , monospace;">if</span>.<br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;">(if <i>premise</i> <i>answer</i> <i>else</i>)</span><br />
<br />
This is not a shock to anyone, but is very useful.<br />
<br />
Moving on we see <span style="font-family: "courier new" , "courier" , monospace;">if-false</span> states that if we have a false <i><span style="font-family: "courier new" , "courier" , monospace;">premise</span></i> that we always take the <i><span style="font-family: "courier new" , "courier" , monospace;">else</span></i> part of the <span style="font-family: "courier new" , "courier" , monospace;">if</span>. Again nothing shocking but very useful.<br />
<br />
Next we see <span style="font-family: "courier new" , "courier" , monospace;">if-same</span> which states that if the <i><span style="font-family: "courier new" , "courier" , monospace;">answer</span></i> and <i><span style="font-family: "courier new" , "courier" , monospace;">else</span></i> are the same then the <i><span style="font-family: "courier new" , "courier" , monospace;">premise</span></i> does not matter. This makes complete logical sense, but I'll admit I never really thought of it before.<br />
<br />
Now let us look at <span style="font-family: "courier new" , "courier" , monospace;">if-nest-A</span> which states that if the condition is true in the <i><span style="font-family: "courier new" , "courier" , monospace;">premise</span></i> then it must be true in the <i><span style="font-family: "courier new" , "courier" , monospace;">answer</span></i> part. This is very awesome, we can now eliminate code by simply looking for redundant ifs. We see this in the following:<br />
<span style="font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="font-family: inherit;">given <b>x</b> is true </span><br />
<span style="font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="font-family: "courier new" , "courier" , monospace;">(if <b>x</b> </span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> (if <b>x</b> :yep :nope)</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> :nope)))))</span><br />
<br />
We see that we have the<span style="font-family: "courier new" , "courier" , monospace;">(if <i>what-ever</i></span> in the outside which matches the <span style="font-family: "courier new" , "courier" , monospace;">(if </span><i style="font-family: 'Courier New', Courier, monospace;">what-ever</i> in the <i><span style="font-family: "courier new" , "courier" , monospace;">answer</span></i> part thus we can eliminate it pulling it up (in the code above the <span style="font-family: "courier new" , "courier" , monospace;">:yep</span>), since if the <i><span style="font-family: "courier new" , "courier" , monospace;">premise</span></i> is true on the outside it is true on the inside. This axiom is very useful in refactoring code and I figured it out for myself a long time ago and find myself using it all the time, it is nice to know that it has a solid theoretical basis.<br />
<br />
Last we see the anti of <span style="font-family: "courier new" , "courier" , monospace;">if-nest-A</span>, <span style="font-family: "courier new" , "courier" , monospace;">if-nest-E</span>. <span style="font-family: Courier New, Courier, monospace;">if-nest-E</span> states that if the condition is false in the <i><span style="font-family: Courier New, Courier, monospace;">premise</span></i> then it must be false in the <i><span style="font-family: Courier New, Courier, monospace;">else</span></i> part. We see this in the following:<br />
<br />
<span style="font-family: inherit;">given <b>x</b> is false</span><br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;">(if <b>x</b></span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> :nope</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> (if <b>x</b> :nope :yep))</span><br />
<br />
We see that we have the <span style="font-family: "courier new" , "courier" , monospace;">(if <i>what-ever</i></span> in the outside which matches the <span style="font-family: "courier new" , "courier" , monospace;">(if </span><i style="font-family: 'Courier New', Courier, monospace;">what-ever</i> in the <i><span style="font-family: "courier new" , "courier" , monospace;">else</span></i> part thus we can eliminate it pulling it up (in the code above the <span style="font-family: "courier new" , "courier" , monospace;">:yep</span>), since if the <i><span style="font-family: "courier new" , "courier" , monospace;">premise</span></i> is false on the outside it is false on the inside. Again, this is very useful in eliminating code.<br />
<br />
These axioms are very powerful and I would argue are more useful than tests. If this interests you I would recommend reading <a href="http://www.amazon.com/Little-Prover-Daniel-P-Friedman/dp/0262527952/ref=sr_1_1?ie=UTF8&qid=1447612965&sr=8-1&keywords=the+little+prover">The Little Prover</a> or working your way through the <a href="http://www.cs.utexas.edu/users/moore/acl2/v7-1/combined-manual/index.html?topic=ACL2____A_02Flying_02Tour_02of_02ACL2">flying tour of ACL2</a>.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-83001522624066348042015-11-15T12:48:00.002-06:002015-11-15T12:48:12.919-06:00Axioms of Cons in Clojure"<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;"><i>Why then, build me thy fortunes upon the basis</i></span>"<br />
-- Shakespeare, Twelfth Night<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=3&SC=2&IdPlay=21#188141">Act III, Scene II, Line 31</a><br />
<br />
I recently finished <a href="http://the-little-prover.github.io/">The Little Prover</a>. In <a href="https://mitpress.mit.edu/books/little-prover">The Little Prover</a> we find the following Axioms of Con:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">(dethm atom/cons (x y) </span><br />
<span style="font-family: Courier New, Courier, monospace;"> (equal (atom (cons x y)) 'nil)</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;">(dethm car/cons (x y)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> (equal (car (cons x y)) x))</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;">(dethm cdr/cons (x y)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> (equal (cdr (cons x y)) y))</span><br />
<span style="font-family: Courier New, Courier, monospace;"><br /></span>
<span style="font-family: Courier New, Courier, monospace;">(dethm cons/car+cdr (x)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> (if (atom x)</span><br />
<span style="font-family: Courier New, Courier, monospace;"> 't</span><br />
<span style="font-family: Courier New, Courier, monospace;"> (equal (cons (car x) (cdr x)) x)))</span><br />
<br />
The way I learn best is by <a href="http://comp-phil.blogspot.com/2015/11/showing-map-distributes-over-functional.html">showing myself</a> that something makes sense, so I went through showing myself these axioms in Clojure.<br />
<br />
<script src="https://gist.github.com/MikeMKH/33c91d143b645d07f4e1.js"></script><br />
<br />
Looking at <span style="font-family: Courier New, Courier, monospace;">atom/cons</span> in the code above we see that Clojure does not have <span style="font-family: Courier New, Courier, monospace;"><a href="https://classes.soe.ucsc.edu/cmps112/Spring03/languages/scheme/SchemeTutorialB.html">atom</a></span> but <span style="font-family: Courier New, Courier, monospace;">(complement sequential?)</span> is close enough if we are working with sequential collections so we'll use that. Using the definition that an <span style="font-family: Courier New, Courier, monospace;">atom</span> is not a sequential collection we see in the code above that <span style="font-family: Courier New, Courier, monospace;">cons</span> "always" yields not an <span style="font-family: Courier New, Courier, monospace;">atom</span>.<br />
<br />
Next looking at <span style="font-family: Courier New, Courier, monospace;">car/cons</span> in the code above we see that using <span style="font-family: Courier New, Courier, monospace;"><a href="https://clojuredocs.org/clojure.core/first">first</a></span> (Clojure's <span style="font-family: Courier New, Courier, monospace;"><a href="http://www.dotnetperls.com/cons-car-cdr-cadr-scheme">car</a></span>) on a <span style="font-family: Courier New, Courier, monospace;"><a href="https://clojuredocs.org/clojure.core/cons">cons</a></span> "always" yields the head of the sequential collection, which makes prefect sense since that is what one expects from <span style="font-family: Courier New, Courier, monospace;">first</span>.<br />
<br />
The other side of <span style="font-family: Courier New, Courier, monospace;">car/cons</span> is <span style="font-family: Courier New, Courier, monospace;">cdr/cons</span>. Looking at the code above we see that using <span style="font-family: Courier New, Courier, monospace;"><a href="https://clojuredocs.org/clojure.core/rest">rest</a></span> (Clojure's <span style="font-family: Courier New, Courier, monospace;"><a href="http://www.dotnetperls.com/cons-car-cdr-cadr-scheme">cdr</a></span>) on a <span style="font-family: Courier New, Courier, monospace;">cons</span> "always" yields the tail of the sequential collection, which again makes prefect sense since that is what one expects from <span style="font-family: Courier New, Courier, monospace;">rest</span>.<br />
<br />
Last we look at <span style="font-family: Courier New, Courier, monospace;">cons/car+cdr</span>. Looking at the code we see that if we do not have an <span style="font-family: Courier New, Courier, monospace;">atom</span> that <span style="font-family: Courier New, Courier, monospace;"><a href="https://clojuredocs.org/clojure.core/first">first</a></span> and <span style="font-family: Courier New, Courier, monospace;"><a href="https://clojuredocs.org/clojure.core/rest">rest</a></span> (Clojure's <a href="http://www.dotnetperls.com/cons-car-cdr-cadr-scheme"><span style="font-family: Courier New, Courier, monospace;">car</span> and <span style="font-family: Courier New, Courier, monospace;">cdr</span></a>) together yield the sequential collection, which again is what one would expect.<br />
<br />
So what does any of this give us? We now have a firm foundation on which to define other theorems and proofs about our statements using these axioms as our basis. This is very powerful and I would argue that this is better having tests.<br />
<br />
If this interests you I would recommend reading <a href="http://www.amazon.com/Little-Prover-Daniel-P-Friedman/dp/0262527952/ref=sr_1_1?ie=UTF8&qid=1447612965&sr=8-1&keywords=the+little+prover">The Little Prover</a> or working your way through the <a href="http://www.cs.utexas.edu/users/moore/acl2/v7-1/combined-manual/index.html?topic=ACL2____A_02Flying_02Tour_02of_02ACL2">flying tour of ACL2</a>.<br />
<br />Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-67585163855975954562015-11-08T15:34:00.003-06:002015-11-08T15:34:11.521-06:00Showing Map Distributes Over Functional Composition OR Fun With Clojure"<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;"><i>Here by the cheeks I'll drag thee up and down.</i></span>"<br />
-- Shakespeare, Henry VI Part 1<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=1&SC=3&IdPlay=25#201376">Act I, Scene III, Line 51</a><br />
<br />
I love to try things out for myself. Whenever I am trying to understand idea I need to show myself that the idea is valid. Sometimes I will just accept something, but if I really want to understand it I will show myself that it makes sense.<br />
<br />
While rereading Dr. Hutton's paper "<a href="http://www.cs.nott.ac.uk/~pszgmh/fold.pdf">A tutorial on the universality and expressiveness of fold</a>", I came back across the following statement, "the map operator distributes over function composition". Being the kind of person which likes to show things to myself I figured I'd show myself this idea in Clojure as part of <a href="http://comp-phil.blogspot.com/2013/10/a-kata-day.html">my daily kata</a>.<br />
<br />
<script src="https://gist.github.com/MikeMKH/bf72c8b35cd31526a93d.js"></script><br />
<br />
Looking at the code above we see the following:<br />
<br />
<ul>
<li>map f · map g = map (f · g)</li>
<li>r/map f · r/map g = r/map (f · g)</li>
<li>reduction f · reduction g = reduction (f · g)</li>
</ul>
<br />
So what does this give us? Having this property we are allowed to improve the performance of our code by composing a series of transformation against a collection to a single transformation of the collection dragged through a series of composed functions. In fact this is the whole idea behind <a href="https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html">streams</a>.<br />
<br />
Taken straight from <a href="http://www.oracle.com/technetwork/articles/java/ma14-java-se-8-streams-2177646.html">Raoul-Gabriel Urma's article in Java Magazine</a>, "[i]n a nutshell, collections are about data and streams are about computations." Thinking about processing as a series of computation we see how we can naturally think about composing our computations together and then drag the data through using a higher order function like map to preform the series of transformations in one pass.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-36629973377553251402015-10-18T11:30:00.003-05:002015-10-18T11:30:29.586-05:00On the Fusion Property of Fold"<i><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">If I break time, or flinch in property</span></i>"<br />
-- Shakespeare, All's Well That Ends Well<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=2&SC=1&IdPlay=30#221142">Act II, Scene I, Line 187</a><br />
<br />
In <a href="http://www.cs.nott.ac.uk/~pszgmh/">Dr. Hutton's</a> excellent paper, <a href="http://www.cs.nott.ac.uk/~pszgmh/fold.pdf">"A tutorial on the universality and expressiveness of fold"</a>, he gives the following definition of the fusion property of Fold:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">h · fold g w = fold f v</span><br />
<br />
Great, but what does this mean to me? Well if we go on in the paper we find the following application of the fusion property of Fold:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">(+1) · sum = fold (+) 1</span><br />
<br />
Interesting, we see that adding 1 to the sum (defined as, <span style="font-family: Courier New, Courier, monospace;">fold (+) 0</span>) of a collection is the same as folding over that collection with 1 as the seed value. Further down in the paper we see that we can simplify and generalize the application above as:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">(⊕ a) · fold (⊕) b = fold (⊕) (b ⊕ a)</span><br />
<br />
Now this is really cool. We can apply an <a href="https://en.wikipedia.org/wiki/Associative_property">associative</a> <a href="https://en.wikipedia.org/wiki/Binary_operation">binary operation</a> with a value against the results of folding that operation against a collection is the same as applying that binary operation with a value against the seed.<br />
<br />
As an aside, an associative binary operation is an operation which takes two values from the same type and outputs a value of that type, examples would be <span style="font-family: Courier New, Courier, monospace;">+</span>, <span style="font-family: Courier New, Courier, monospace;">-</span>, <span style="font-family: Courier New, Courier, monospace;">*</span>, <span style="font-family: Courier New, Courier, monospace;">/</span>, <span style="font-family: Courier New, Courier, monospace;">min</span>, <span style="font-family: Courier New, Courier, monospace;">max</span>, ... We say an operation is associative if and only if:<br />
<br />
<span style="font-family: 'Courier New', Courier, monospace;">a ⊕ b = b</span><span style="font-family: 'Courier New', Courier, monospace;"> ⊕ a</span><br />
<br />
This means addition is associative while subtraction is not (2 - 1 != 1 - 2, but 2 + 1 = 1 + 2).<br />
<br />
How about looking at some examples of the fusion property?<br />
<br />
First we'll look at examples in Clojure.<br />
<br />
<script src="https://gist.github.com/MikeMKH/4a17be267d04a2607e44.js"></script><br />
<br />
We see in the Clojure example that we are using <a href="https://clojuredocs.org/clojure.core/reduce">reduce</a> to fold over a collection of integers (integers are easier to use in examples but this idea is not limited to integers) applying an associative binary operation against each member. We see that applying the operation with a value against the result is the same as applying that operation and value against the seed.<br />
<br />
Next we'll look at examples in ECMAScript 2015 (JavaScript) using <a href="https://facebook.github.io/immutable-js/">Immutable.js</a>.<br />
<br />
<script src="https://gist.github.com/MikeMKH/e6f5d1f281b2c314b3ea.js"></script><br />
<br />
We see in the ECMAScript example that we are using <a href="https://facebook.github.io/immutable-js/docs/#/List/reduce">Immutable's reduce</a> to fold over a List of integers (again this could be applied against any type) applying the associative binary operation against the members. Like the Clojure example we see that applying the operation with a value against the result is the same as applying that operation and value against the seed.<br />
<br />
We can go further with this idea but I feel this is a good overview of the concept.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-88324277201210238782015-10-11T10:08:00.003-05:002015-10-11T10:11:52.805-05:00Folding Up the Coin Changer Kata"<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;"><i>Whate'er the course, the end is the renown.</i></span>"<br />
-- Shakespeare, All's Well That Ends Well<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=4&SC=4&IdPlay=30#223402">Act IV Scene IV, Line 36</a><br />
<br />
<h4>
Coin Changer Kata</h4>
<br />
The <a href="http://comp-phil.blogspot.com/2014/08/functional-programming-all-things-or.html">Coin Changer</a> <a href="http://comp-phil.blogspot.com/2014/05/the-form-of-katas.html">kata</a> has three things which make it a good kata.<br />
<br />
<ol>
<li>easy to understand</li>
<li>rich set of features</li>
<li>lots of realistic possible implementations</li>
</ol>
Even in today's cashless society, most people understand the idea of handing someone over some money and get change back. This handing back of change requires the breaking down of the change over coins of different denominations. Finding which coins to hand back has lots of possible implementations which translate over to things which programmers do every day.<br />
<br />
The user story is very simple:<br />
<br />
Given a collection of coins of different denominational value<br />
When an amount of change is given<br />
Then it will give back the number of coins for each denomination needed using the least amount of coins possible<br />
<br />
A type signature for the function needed could look like the following:<br />
<br />
changeFor(coins: int[], amount: int): int[]<br />
<br />
We are expecting an array of integers which have different denomination of coins (in the US something like: [25, 10, 5, 1]) and the amount of change needed (something like: 99) giving a resulting array of integers showing how many of each denomination (something like: [3, 2, 0, 4]).<br />
<br />
What would we need to be able to do this kata using just Fold?<br />
<br />
We'll need to use a tuple (or something like one) to manage the state of the amount of change needed and the resulting array of integers.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiqZIJIWTvs3UkMREVOJfdbBcikeFgky_Mi0t3EYGWaPKjUcrz-cHmbaFBSJmJEYndnc02hpS5Zp36V0m2N6ZDVo8TmgeQpc6PfxUUcGEoW57bo_KEM7gIcIwYajZoqhYLaI65FPfqIa1af/s1600/Screen+Shot+2015-10-05+at+4.20.12+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiqZIJIWTvs3UkMREVOJfdbBcikeFgky_Mi0t3EYGWaPKjUcrz-cHmbaFBSJmJEYndnc02hpS5Zp36V0m2N6ZDVo8TmgeQpc6PfxUUcGEoW57bo_KEM7gIcIwYajZoqhYLaI65FPfqIa1af/s320/Screen+Shot+2015-10-05+at+4.20.12+PM.png" width="278" /></a></div>
<br />
Now lets look at an example using a typical full US register with quarters, dimes, nickels, and pennies. We'll look at getting change for 99 cents.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJosNL51AMcfmDGhgcxQ_9J2qH5icf0T5_63Cd0z1_ed3REDgWqmq6QQe1icqTNYIKfeCxLIBcmk51QL0rbg1hR4ICFJaUmcJW1JJiF3CkkWfjuQ4JF4CM5Hts6ZZ0MWwNgEQD5FcyKxlQ/s1600/Screen+Shot+2015-10-05+at+5.12.14+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="218" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJosNL51AMcfmDGhgcxQ_9J2qH5icf0T5_63Cd0z1_ed3REDgWqmq6QQe1icqTNYIKfeCxLIBcmk51QL0rbg1hR4ICFJaUmcJW1JJiF3CkkWfjuQ4JF4CM5Hts6ZZ0MWwNgEQD5FcyKxlQ/s320/Screen+Shot+2015-10-05+at+5.12.14+PM.png" width="320" /></a></div>
<br />
First Memorize has (99, empty) and X has 25 giving the result of (24, [3]).<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhHpRHGrHwakAMKvlqFGlGmBBqABJb6j5EW8kDQRfSwIhs_L6G5XY2WHO4F-TlTd01Ysfa8G2S8-NK2u9OpfAPXlz2OCMwq0HayZgB6hNO0O-OvbcI0JzNDCZHQKejEzbbn3lCfyrLEpNYz/s1600/Screen+Shot+2015-10-05+at+5.13.07+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="218" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhHpRHGrHwakAMKvlqFGlGmBBqABJb6j5EW8kDQRfSwIhs_L6G5XY2WHO4F-TlTd01Ysfa8G2S8-NK2u9OpfAPXlz2OCMwq0HayZgB6hNO0O-OvbcI0JzNDCZHQKejEzbbn3lCfyrLEpNYz/s320/Screen+Shot+2015-10-05+at+5.13.07+PM.png" width="320" /></a></div>
<br />
Next Memorize has (24, [3]) and X has 10 giving the result of (4, [3, 2]).<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIRBwbjTDxr2kJQ_4Vtk5rJEkMAIuN_dGn6NUQld0iF1TMmgLUVVOzgZdDHRLByvy4GiUPgr6cfuwb9ZF-GMzpbKUAA6dH3Q2FknKZ3TtN3JVoMfMYcALFK3G3X6mnJQ4U2PuEvdNOCWL5/s1600/Screen+Shot+2015-10-05+at+5.13.20+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="218" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIRBwbjTDxr2kJQ_4Vtk5rJEkMAIuN_dGn6NUQld0iF1TMmgLUVVOzgZdDHRLByvy4GiUPgr6cfuwb9ZF-GMzpbKUAA6dH3Q2FknKZ3TtN3JVoMfMYcALFK3G3X6mnJQ4U2PuEvdNOCWL5/s320/Screen+Shot+2015-10-05+at+5.13.20+PM.png" width="320" /></a></div>
<br />
Then Memorize has (4, [3, 2]) and X has 5 giving the result of (4, [3, 2, 0]).<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi89R8FcGp6PUiYzAD3kRq8fol6xnaJ0K2X-8j2O9K_5VfropfhyphenhyphendbffIq1Iw6dqySqNqndKIEJDa0j7wpYRuernGYeBb02HZ9h6ybWit8ma2BJqbVWSoZ7KhbMoWoDONcV7F61D3TTGbkL/s1600/Screen+Shot+2015-10-05+at+5.13.35+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="217" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi89R8FcGp6PUiYzAD3kRq8fol6xnaJ0K2X-8j2O9K_5VfropfhyphenhyphendbffIq1Iw6dqySqNqndKIEJDa0j7wpYRuernGYeBb02HZ9h6ybWit8ma2BJqbVWSoZ7KhbMoWoDONcV7F61D3TTGbkL/s320/Screen+Shot+2015-10-05+at+5.13.35+PM.png" width="320" /></a></div>
<br />
Last Memorize has (4, [3, 2, 0]) and X has 1 giving the result of (0, [3, 2, 0, 4]).<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgBYsTtVUD7ubRVURimRp17G_kqQlrf1oUydYgo0IeZx8gAoNNCed-3pOLdZS1Icxwf8WaafeTLRJm-RSERSiTXDcJcH39NNDqG0MIDXoxXx4j3___7QXPV6aHwWCc4wmevakaqviWawxJp/s1600/Screen+Shot+2015-10-05+at+5.13.50+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="216" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgBYsTtVUD7ubRVURimRp17G_kqQlrf1oUydYgo0IeZx8gAoNNCed-3pOLdZS1Icxwf8WaafeTLRJm-RSERSiTXDcJcH39NNDqG0MIDXoxXx4j3___7QXPV6aHwWCc4wmevakaqviWawxJp/s320/Screen+Shot+2015-10-05+at+5.13.50+PM.png" width="320" /></a></div>
<br />
Finally obtaining the tuple item with the resulting array of integers to get the change.<br />
<br />
<h4>
Clojure</h4>
<br />
<script src="https://gist.github.com/MikeMKH/92684eeeeacffa4b9fb1.js"></script><br />
<br />
We see with the Clojure code that we seed with a <a href="http://clojure.github.io/clojure/clojure.core-api.html#clojure.core/hash-map">map</a> with a key for the :amount and one for the :result. We fold over the coins using <a href="https://clojuredocs.org/clojure.core/reduce">reduce</a> <a href="https://clojurebridge.github.io/community-docs/docs/clojure/destructuring/">destructing</a> the memoize value into the amount and result. We then just calculate the new amount using: amount % coin, follow by inserting the number of coins we get using: amount / coin. We use <a href="https://clojuredocs.org/clojure.core/cons">cons</a> to show off the coolness that is the <a href="https://clojuredocs.org/clojure.core/-%3E%3E">thread-last macro</a> (at least that is why I think I coded it this way, it was a little bit ago that I did the gist and I cannot remember why I code with cons over conj).<br />
<br />
<h4>
C#</h4>
<br />
<script src="https://gist.github.com/MikeMKH/e3da77484fdc7251ea1b.js"></script>
<br />
We see with the C# code that we seed using a <a href="http://www.dotnetperls.com/tuple">Tuple</a> (which I think has very ugly syntax in C#). We then fold over the coins using <a href="http://www.dotnetperls.com/aggregate">aggregate</a> just like the Clojure code above. We calculate the changer results and place them into a new Tuple which we return as the memoize.<br />
<br />
<h4>
ECMAScript 2015</h4>
<br />
<script src="https://gist.github.com/MikeMKH/95235d1688254e3346a7.js"></script>
<br />
In this ECAMScript 2015 example we use <a href="https://lodash.com/docs#reduce">lodash's foldl</a> to fold over the coins just like the two examples above. The seed value is a simple JavaScript object with the members of amount and result given. We are a bit dirty and mutate the memoize on each call with the changer results but we could argue that this is still "pure" since the mutation happens to an item which is created and used only in side the function.<br />
<br />
<h4>
ECMAScript 2015 and <a href="https://facebook.github.io/immutable-js/">Immutable.js</a></h4>
<br />
<script src="https://gist.github.com/MikeMKH/7e97a29a7290b3071550.js"></script><br />
Last we look at <a href="https://facebook.github.io/immutable-js/">Facebook's open source Immutable.js</a>. We create an <a href="https://facebook.github.io/immutable-js/docs/#/List">immutable List</a> with the coins which we use to fold over the values using <a href="https://facebook.github.io/immutable-js/docs/#/List/reduce">reduce</a>. The seed value we give it is a simple JavaScript array with an <a href="https://facebook.github.io/immutable-js/docs/#/List">immutable List</a> to hold the results and the amount passed in. We could use an <a href="https://facebook.github.io/immutable-js/docs/#/Map">immutable Map</a> if we wanted to keep it purely immutable. Like this:<br />
<br />
<script src="https://gist.github.com/MikeMKH/22b6ab4f849dc775b6b0.js"></script><br />
<br />
I am not a huge fan of stringly typed accessors, but I understand why they use them. Both ways are good and would really come down to to performance and readability.<br />
<br />
<h4>
The End</h4>
<br />
Thus ends our tour of All You Need is Fold, but this is not the end of the uses of Fold, for <a href="http://www.cs.nott.ac.uk/~gmh/fold.pdf">Fold is universal</a>.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-56500431332185044222015-10-04T20:24:00.001-05:002015-10-04T20:24:06.879-05:00Fold the Zip Up"<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;"><i>They fell together all, as by consent.</i></span>"<br />
-- Shakespeare, The Tempest<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=2&SC=1&IdPlay=12#157362">Act II, Scene I, Line 207</a><br />
<br />
<h4>
Zip</h4>
<br />
Zip can be thought of as the more generic form of <a href="http://comp-phil.blogspot.com/2015/01/reducing-map-to-reduce-or-all-you-need.html">Map</a>. Think of Zip as applying a function against each member of the collections given to it, thus mapping more than one collection to another collection. It is a lot easier to see than to explain in words.<br />
<br />
I believe Zip2 would get the following definition:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">zip2 :: (α → β → γ) → ([α] → [β] → [γ])</span><br />
<span style="font-family: Courier New, Courier, monospace;">zip2 f = fold (λx y xs ys → f x y : xs ys) [ ]</span><br />
<br />
This would be if we limit Zip to being used on 2 collections (this is mine definition, <a href="http://www.cs.nott.ac.uk/~pszgmh/">Dr. Graham Hutton</a> has nothing to do with this definition, blame me if it is wrong).<br />
<br />
Folding a Zip we'll need a collection to seed with then we just apply the given function against each member from each collection concatenating it with the seed, just as we did with <a href="http://comp-phil.blogspot.com/2015/09/folding-into-map.html">Map</a>.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihdys8mwW05BEveKxKq-XpzPj-yJkHPkDZyVuGRbJVFFZI_63H5rz2e_Fp0tXThCQr1rcI9QsiDtkMcwYHs-JWluOwVmwgJEZBwu2U5XX4WpcagncfLjmIww4_N_YFe_1pNDm8uxUImEkt/s1600/Screen+Shot+2015-10-04+at+5.33.29+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="270" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEihdys8mwW05BEveKxKq-XpzPj-yJkHPkDZyVuGRbJVFFZI_63H5rz2e_Fp0tXThCQr1rcI9QsiDtkMcwYHs-JWluOwVmwgJEZBwu2U5XX4WpcagncfLjmIww4_N_YFe_1pNDm8uxUImEkt/s320/Screen+Shot+2015-10-04+at+5.33.29+PM.png" width="320" /></a></div>
<br />
<br />
Next we'll look at a simple example adding the members of two collections together.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiZUKSqfvOaq12nbBOcmwuNuHDRVMT4oURSrcvwj7MZ9R2idEg_-O81nNyA8_J2x6Aw02pauqu1spUtQC7sQJ2E1boVGZASNYPJQBJBqLXIj0YA3dLjfcz55cqs5iUddvfhSSi8fvkHWr-1/s1600/Screen+Shot+2015-10-04+at+5.54.59+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiZUKSqfvOaq12nbBOcmwuNuHDRVMT4oURSrcvwj7MZ9R2idEg_-O81nNyA8_J2x6Aw02pauqu1spUtQC7sQJ2E1boVGZASNYPJQBJBqLXIj0YA3dLjfcz55cqs5iUddvfhSSi8fvkHWr-1/s320/Screen+Shot+2015-10-04+at+5.54.59+PM.png" width="250" /></a></div>
<br />
First Memoize has nothing and X has 1 while Y has 10 giving the result of 11.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhLeAlFr5CtBb4c2eB-BRkFXGYLfrdbKr1UCEcwqVfI-wwITQQvkMkmeRHJSx4o4RhZQgsoiKgCl6igUjJ1hJCkTyOcZvr2Xaijtx7_kNUJXsMbodj_KoAXeHAK-S9s9ADn3-zhxNQRhsEY/s1600/Screen+Shot+2015-10-04+at+5.55.13+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="306" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhLeAlFr5CtBb4c2eB-BRkFXGYLfrdbKr1UCEcwqVfI-wwITQQvkMkmeRHJSx4o4RhZQgsoiKgCl6igUjJ1hJCkTyOcZvr2Xaijtx7_kNUJXsMbodj_KoAXeHAK-S9s9ADn3-zhxNQRhsEY/s320/Screen+Shot+2015-10-04+at+5.55.13+PM.png" width="320" /></a></div>
<br />
Next Memoize has 11 and X has 2 while Y has 20 giving the result of 11, 22.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjmwrB7Hj_t6d3ZE1UjTyq-AmIAwQwcQ9Spa2nICG_9pGcrnBuS4_lziw832rAedMyM63yFIo995r6gD7dP_F5YJK2nGDIyIPz6eF759_TwwrYNWWIqNRwThv01sm5tKSi8HBVRmtloBDeW/s1600/Screen+Shot+2015-10-04+at+7.47.22+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="245" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjmwrB7Hj_t6d3ZE1UjTyq-AmIAwQwcQ9Spa2nICG_9pGcrnBuS4_lziw832rAedMyM63yFIo995r6gD7dP_F5YJK2nGDIyIPz6eF759_TwwrYNWWIqNRwThv01sm5tKSi8HBVRmtloBDeW/s320/Screen+Shot+2015-10-04+at+7.47.22+PM.png" width="320" /></a></div>
<br />
Lets see some code examples.<br />
<br />
<h4>
Clojure</h4>
<br />
<script src="https://gist.github.com/MikeMKH/49857215df5e1bdf1829.js"></script><br />
<br />
With Clojure we do not have to worry about the number of collection we'll give our Zip function since we can use <a href="http://www.braveclojure.com/do-things/#3_3_3__Destructuring">destructing</a> to say and everything else. We can then apply <a href="https://clojuredocs.org/clojure.core/map">map</a> to create a <a href="https://clojuredocs.org/clojure.core/vector">vector</a> containing all the elements next to each other, we'll see this is common in the other languages since the implementation of <a href="https://clojuredocs.org/clojure.core/reduce">reduce</a> is only design to work with a single collection. From here it is just like Map except that we need to use <a href="https://clojuredocs.org/clojure.core/apply">apply</a> since are members are a collection themselves.<br />
<br />
<h4>
C#</h4>
<br />
<script src="https://gist.github.com/MikeMKH/26ce963e370bd5614472.js"></script><br />
<br />
With C# we have to specify the number of collection we are going to Zip, in this case we'll do two. We need to <a href="http://www.dotnetperls.com/zip">Zip</a> the members from the two collections together into a <a href="http://www.dotnetperls.com/tuple">Tuple</a> (which is a bit of cheating but I can find no other way to do it with LINQ). From there it is just like Map. With this implementation we do have a limitation in that the two collections must be the same size, since to get around that would be a bit of work and we rather have a readable implementation than perfect code.<br />
<br />
<h4>
ECMAScript 2015</h4>
<br />
<script src="https://gist.github.com/MikeMKH/ea7148f3f8abe3750894.js"></script><br />
<br />
In ECMAScript 2015 (also known as JavaScript ES6), we see an implementation similar to the C# code except we use lodash's <a href="https://lodash.com/docs#zip">zip</a> to place the members in a single collection (lodash's <a href="https://lodash.com/docs#zipWith">zipWith</a> is like LINQ's <a href="http://www.dotnetperls.com/zip">Zip</a>). From there it is just like Map. With this implementation like the C# implementation we have a limitation in that the two collections must be the same size, and again the work around would be a lot of work so we'll error on keeping the code readable.<br />
<br />
<h4>
Done</h4>
<br />
There you have it showing once again that all you need is Zip.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-88713305118066767222015-09-20T14:46:00.003-05:002015-09-20T14:58:38.205-05:00The Cloud-Capped Towers OR AutoFixture"<i><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">The cloud-capped towers, the gorgeous palaces,<br />The solemn temples, the great globe itself,<br />Yea, all which it inherit, shall dissolve,<br />And, like this insubstantial pageant faded,<br /><br />Leave not a rack behind. We are such stuff</span></i>"<br />
-- Shakespeare, The Tempest<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=4&SC=1&IdPlay=12#158576">Act IV, Scene I, Lines 152 -156</a><br />
<br />
In my day-to-day work I do a lot of .Net programming. It seem at some point in each of the applications I am either enhancing or creating I ended including <a href="https://twitter.com/ploeh">Mark Seemann's</a> <a href="https://github.com/AutoFixture/AutoFixture">AutoFixture</a> (if it is not already in use). AutoFixture is an easy way to create a <a href="http://blog.ploeh.dk/2009/03/16/FixtureObject/">fixture object</a>. A fixture object is an object which centralizes your helper methods in your test code, like methods which create your system under test and help generate test data.<br />
<br />
Fixture objects are great and I often find myself wanting one in my day-to-day work, but I am lazy. Since I am lazy I do not want to go to all the trouble of creating my own fixture object, to quote Homer Simpson, "Can't someone else do it". Luckily in the .Net realm someone already has, Mark Seemann. <a href="http://blog.ploeh.dk/2009/05/15/AutoFixtureAsFixtureObject/">AutoFixture</a> lets you get the best of all worlds, you get a fixture object and you do not have to write the framework around it! (working with it for a few years now, I can say it is well thought out and not a big hair ball, see also <a href="http://www.infoq.com/presentations/Simple-Made-Easy">Simple Made Easy</a> for the full reference)<br />
<br />
How about some examples? (taken from the <a href="https://github.com/AutoFixture/AutoFixture/wiki/Cheat-Sheet">AutoFixture cheat sheet</a> and rewritten using <a href="https://github.com/xunit/xunit">xUnit</a>)<br />
<br />
<script src="https://gist.github.com/MikeMKH/bd19a33a6a46b5c244b5.js"></script><br />
<br />
We see in the above lots of wonderful things.<br />
<ul>
<li>We can walk up to the fixture object and ask it for some test data. </li>
<li>We can use the AutoData attribute and ask for test data. </li>
<li>We can register implementation for abstract types. </li>
<li>We can create collections of test data.</li>
<li>We can build specific test data saying what attributes we care about and letting the fixture object set up the rest.</li>
<li>We can even have a do method to allow for modification outside of the object we are having the fixture object create (this is not good design but sometimes it is needed).</li>
</ul>
As I work more with AutoFixture I find more and more uses for it.<br />
<br />
Another framework I use a lot in my day-to-day .Net programming is <a href="https://github.com/Moq/moq4">Moq</a>. Guess what, AutoFixture can be uses as an <a href="http://blog.ploeh.dk/2010/08/19/AutoFixtureasanauto-mockingcontainer/">auto-mocking container with Moq</a> (and it has plugins for other mocking frameworks too).<br />
<br />
Yet another example. (using MS Test taken from an overview of AutoFixture I did at work recently)<br />
<br />
<script src="https://gist.github.com/MikeMKH/cef3018b60044484a9ed.js"></script><br />
<br />
We see in this example that we had a simple class called Echo which got top hatted into having logging and a backup added to it. The interactions with the logger and back-upper need to be tested, luckily we can tell the fixture object that we would like to get spy objects for the logger and back-upper. These spies from AutoFixture are Moq mocks which allows us to verify that the behaviors we want.<br />
<br />
By using AutoFixture and Moq we can meet all the "needs" of Top Hats everywhere.<br />
<br />
(The term Top Hats comes from <a href="https://cleancoders.com/episode/clean-code-episode-7/show">Uncle Bob's Clean Coder series episode 7</a>, in which there is a scene with an Architect talking about choosing an IDE and Database for a project hence the term Top Hat and top hatting to describe this type of "architecture".)<br />
<br />
I find that AutoFixture allows me to simplify my test code (simple as discussed in <a href="http://www.infoq.com/presentations/Simple-Made-Easy">Simple Made Easy</a>) and allows me to stay focus on what I am actually trying to test.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-17517108455294273892015-09-13T11:33:00.002-05:002015-09-13T11:37:10.040-05:00Filter, Guarding You From Fold"You and your ways; whose wraths to guard you from,"<br />
<div>
-- Shakespeare, The Tempest</div>
<div>
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=3&SC=3&IdPlay=12#158314">Act III, Scene III, Line 80</a></div>
<div>
<br /></div>
<h3>
Filter</h3>
<div>
<br /></div>
<div>
Filter is a lot like a higher order functional bouncer, it prevents undesirable elements from getting into the resulting collection. </div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg-dzjn08-_EAbP6zHnjeA8tvVKKozRjvhDM2E4ls04HEp0giHX17bW7PQkomnRx54kK9wuNYWTi1_ZsfMj4icilJbCUoF4ji3VvbgFe_ORrhIwsnRw6leB3LXNzQibfBrPONQUuzzA0RUr/s1600/Filtering.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="206" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg-dzjn08-_EAbP6zHnjeA8tvVKKozRjvhDM2E4ls04HEp0giHX17bW7PQkomnRx54kK9wuNYWTi1_ZsfMj4icilJbCUoF4ji3VvbgFe_ORrhIwsnRw6leB3LXNzQibfBrPONQUuzzA0RUr/s320/Filtering.png" width="320" /></a></div>
<br />
A simple example would be a filtering with a function which says if a value is odd or not.<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiDCYob6tuf_64UWYna76GBT4-TeUWiTCHYxBoyTxjsOXC8ABO2hZMGTkNDOHE9xlyHKjjmIIeAjHI4Pqhol0k6W2P5lUMG44gVMOplcF6nX8VNqe8jqQyVge422R3dVwdzn_tx1yKmj3Du/s1600/Odd.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="123" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiDCYob6tuf_64UWYna76GBT4-TeUWiTCHYxBoyTxjsOXC8ABO2hZMGTkNDOHE9xlyHKjjmIIeAjHI4Pqhol0k6W2P5lUMG44gVMOplcF6nX8VNqe8jqQyVge422R3dVwdzn_tx1yKmj3Du/s320/Odd.png" width="320" /></a></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
In <a href="http://www.cs.nott.ac.uk/~gmh/">Dr. Hutton's</a> excellent paper, "<a href="http://www.cs.nott.ac.uk/~gmh/fold.pdf">A tutorial on the universality and expressiveness of fold</a>", he gives the following definition of Filter in terms of Fold:</div>
<div>
<br /></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">filter :: (α → Bool) → ([α] → [α])</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;">filter p = fold (λx xs → if p x then x : xs else xs) [ ]</span></div>
<div>
<br /></div>
<div>
From the definition above, we see that Filter is just Map but with a predicate clause stating if the element should be placed in the resulting collection or not.</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjOM7EFlrIx8tDKnN8h9A0J41QuhJSOHchcQbiHpr5GfN1uzxdLEqfHf9RzJuL-cNj_iVWIgf7Ig2UtJ0hAJXCH71eZ_LJwFF3samfubRJrESIzuIaVs61pNOF7Q7FWoIIrcFPyncZ2ZNuk/s1600/Screen+Shot+2015-09-13+at+11.23.27+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="279" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjOM7EFlrIx8tDKnN8h9A0J41QuhJSOHchcQbiHpr5GfN1uzxdLEqfHf9RzJuL-cNj_iVWIgf7Ig2UtJ0hAJXCH71eZ_LJwFF3samfubRJrESIzuIaVs61pNOF7Q7FWoIIrcFPyncZ2ZNuk/s320/Screen+Shot+2015-09-13+at+11.23.27+AM.png" width="320" /></a></div>
<div>
<br /></div>
<div>
Let us look at an example using my name Mike and a function which will check if a character is lower case.</div>
<div>
<br /></div>
<div>
(similar to <a href="http://comp-phil.blogspot.com/2015/09/folding-into-map.html">Map last time</a>)</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEie2qxxzeS4Nof3WxX5nO2TndzUceBRyezTXzY-wFocQhHsTM-PM24CvOw9Q47KZKY3S0P-majp6tP3efRLykJwc5kX5a2YdBfBWAWHrEaFUaeDG3rfcEC0YqwN34gJ4d7veVWZRencFcC7/s1600/Screen+Shot+2015-09-13+at+11.23.53+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="219" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEie2qxxzeS4Nof3WxX5nO2TndzUceBRyezTXzY-wFocQhHsTM-PM24CvOw9Q47KZKY3S0P-majp6tP3efRLykJwc5kX5a2YdBfBWAWHrEaFUaeDG3rfcEC0YqwN34gJ4d7veVWZRencFcC7/s320/Screen+Shot+2015-09-13+at+11.23.53+AM.png" width="320" /></a></div>
<div>
<br /></div>
<div>
First Memoize has nothing and X has M.</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguuMGaTbCg26absYUmPtDq0bUab8ixPMvPDDNAP8WIhVa7r268YYf-o_xkFBP6N9fe7IVp19WNFSfbcZqXfoDRMQt1c_S6e2VOhiHg2_B1b1Q6tRKdIkUtGEOjGeM5fgBpK3QmV2dtv3di/s1600/Screen+Shot+2015-09-13+at+11.24.05+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="224" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguuMGaTbCg26absYUmPtDq0bUab8ixPMvPDDNAP8WIhVa7r268YYf-o_xkFBP6N9fe7IVp19WNFSfbcZqXfoDRMQt1c_S6e2VOhiHg2_B1b1Q6tRKdIkUtGEOjGeM5fgBpK3QmV2dtv3di/s320/Screen+Shot+2015-09-13+at+11.24.05+AM.png" width="320" /></a></div>
<div>
<br /></div>
<div>
Next Memoize still has nothing (since M is upper case) and X has i.</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhC2-TlP9IRLowB6szYFsbR1o-uHt6gVlMWD4XKGyza9rK3aqUCW1bt81x0F0FVQ-9n5Gczpq8UVFLJGnQs_qSxxo8lcV_fR4Vmj1HMSyOI0k-a4tDVFa_iPIJ4_zDiQng8bqeY8lNmW9CZ/s1600/Screen+Shot+2015-09-13+at+11.24.17+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="261" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhC2-TlP9IRLowB6szYFsbR1o-uHt6gVlMWD4XKGyza9rK3aqUCW1bt81x0F0FVQ-9n5Gczpq8UVFLJGnQs_qSxxo8lcV_fR4Vmj1HMSyOI0k-a4tDVFa_iPIJ4_zDiQng8bqeY8lNmW9CZ/s320/Screen+Shot+2015-09-13+at+11.24.17+AM.png" width="320" /></a></div>
<div>
<br /></div>
<div>
Now Memoize has i and X has k.</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg33tGXFTqy2yVeFWkq4jFKNgNKznVr0oZedYEXEUuVXmxTqx3rTdTqSAR2VBZA0Y9PIqHZ7nKROzzk3oNeHVZlExrPfCM2-yzSGFGDMDJvzNZ3gnDzp3G6EaIg0N4c6Lc7MyghK9GwvTxq/s1600/Screen+Shot+2015-09-13+at+11.24.39+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="262" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg33tGXFTqy2yVeFWkq4jFKNgNKznVr0oZedYEXEUuVXmxTqx3rTdTqSAR2VBZA0Y9PIqHZ7nKROzzk3oNeHVZlExrPfCM2-yzSGFGDMDJvzNZ3gnDzp3G6EaIg0N4c6Lc7MyghK9GwvTxq/s320/Screen+Shot+2015-09-13+at+11.24.39+AM.png" width="320" /></a></div>
<div>
<br /></div>
<div>
Then Memoize has i and k while X has e.</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjozArBr_6C2o0RTkLDd_uUIT6AXoYs7ggrvCKmJnFggLBf4Juw7xrOjYPGfvXVcXdNLWidWAMoYbXatcm2NlyF_dho5QXJiEwXeG5_LbuLiqNw-wevKroOViVlA_F1GfynaiqOoxwMjyIA/s1600/Screen+Shot+2015-09-13+at+11.24.52+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="260" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjozArBr_6C2o0RTkLDd_uUIT6AXoYs7ggrvCKmJnFggLBf4Juw7xrOjYPGfvXVcXdNLWidWAMoYbXatcm2NlyF_dho5QXJiEwXeG5_LbuLiqNw-wevKroOViVlA_F1GfynaiqOoxwMjyIA/s320/Screen+Shot+2015-09-13+at+11.24.52+AM.png" width="320" /></a></div>
<div>
<br /></div>
<div>
Now the Filter will return the result of "ike".</div>
<div>
<br /></div>
<div>
Now what we all came to see, some code examples.</div>
<div>
<br /></div>
<h3>
Clojure</h3>
<div>
<br /></div>
<div>
<script src="https://gist.github.com/MikeMKH/e3e02ab5d85dcff9ff95.js"></script></div>
<div>
<br /></div>
<div>
In Clojure we can use the <a href="https://clojuredocs.org/clojure.core/reduce">reduce</a> function to move through the collection checking the predicate condition with the <a href="https://clojuredocs.org/clojure.core/if">if</a> macro guard against undesirable elements.</div>
<div>
<br /></div>
<h3>
C#</h3>
<div>
<br /></div>
<div>
<script src="https://gist.github.com/MikeMKH/33cbe392d962510b0a6f.js"></script></div>
<div>
<br /></div>
<div>
With the C# code we'll need to create some type of collection with the seed value which will allow us to add elements to it, we'll use the collection class of <a href="http://www.dotnetperls.com/list">List</a>. We'll simply iterate through the collection using <a href="http://www.dotnetperls.com/aggregate">Aggregate</a> and add elements to the memoize List if they pass the predicate clause.</div>
<div>
<br /></div>
<h3>
ECMAScript 2015</h3>
<div>
<br /></div>
<div>
<script src="https://gist.github.com/MikeMKH/eac8a3fff99b955524a3.js"></script></div>
<div>
<br /></div>
<div>
In the code above that we'll use the build in JavaScript array method of <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/push">push</a> to add an element which gets past the guarding predicate function to the array at the end. We are simply move through the collection we are filtering, pushing elements into the memoize array.</div>
<div>
<br /></div>
<h3>
Fin</h3>
<div>
<br /></div>
<div>
There you have it we are able to keep the riffraff elements out using Fold. </div>
Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-85753507369401961152015-09-07T14:37:00.002-05:002015-09-07T14:46:06.285-05:00Folding into Map"<i><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">I have forgot the map.</span></i>"<br />
-- Shakespeare, Henry IV Part I<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=3&SC=1&IdPlay=33#234371">Act III, Scene I, Line 5</a><br />
<br />
<h3>
Map</h3>
<br />
Map is the first of the big three <a href="http://comp-phil.blogspot.com/2013/03/higher-order-functions.html">Higher Order Function</a> we will looking at Folding using <a href="http://www.cs.nott.ac.uk/~gmh/">Dr. Hutton's</a> excellent paper, "<a href="http://www.cs.nott.ac.uk/~gmh/fold.pdf">A tutorial on the universality and expressiveness of fold</a>", as a guide. The idea of a <a href="http://comp-phil.blogspot.com/2013/05/maps-filters-and-folding-oh-my-or-yet.html">Map</a> is simple, you have a collection which you wish to apply some translation function against every member of the collection.<br />
<br />
We can look at a few simple examples, the first of which would be the identity function.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdmMqNhx5a3ezHRttc6Seev8tYaBd3Ke4G8adm_Nl1b5oWFdjkaWB-cijQ8mh80KN_1SOEq2E11dS_tT7R6PHg0bTNpASeIB2Hothj3a-NFtMXL61DTQg5VTnnqTAJIx4wvQD-TR9E_F8t/s1600/Identity.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="123" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdmMqNhx5a3ezHRttc6Seev8tYaBd3Ke4G8adm_Nl1b5oWFdjkaWB-cijQ8mh80KN_1SOEq2E11dS_tT7R6PHg0bTNpASeIB2Hothj3a-NFtMXL61DTQg5VTnnqTAJIx4wvQD-TR9E_F8t/s320/Identity.png" width="320" /></a></div>
<br />
Next we can look at a constant function which maps turtle for any value given to it.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjx_52wlPm2EVFqpGmRrh-BdDcl7wjfZowhs-9Ay9jE5VmSbQcuNcx3CmkbUl3Ui7YX-ARzBPOqjoLXAK2-FTw75iWtal2PBsy9fCCPdGNliSOlG_8Zd2Yzp7DwoZ16DLmvcu9X8uBD2CTP/s1600/Turtles.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="118" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjx_52wlPm2EVFqpGmRrh-BdDcl7wjfZowhs-9Ay9jE5VmSbQcuNcx3CmkbUl3Ui7YX-ARzBPOqjoLXAK2-FTw75iWtal2PBsy9fCCPdGNliSOlG_8Zd2Yzp7DwoZ16DLmvcu9X8uBD2CTP/s320/Turtles.png" width="320" /></a></div>
<br />
Last we can look at a function which shifts everything given to it.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiAJ9lJuSUNxOF3SSr1f5jsxPMUD5HH1ve7tlV6b2TAfrWCtubtqZbTBZP3JUPxm98Rdw2yG2_N8FhgF48yRm4heGSKFXEZoTyvi1_Pa92WpX4Sw9vx0lpJlhlDclkuWdASyXzA8kp2OJA1/s1600/Shift.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="123" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiAJ9lJuSUNxOF3SSr1f5jsxPMUD5HH1ve7tlV6b2TAfrWCtubtqZbTBZP3JUPxm98Rdw2yG2_N8FhgF48yRm4heGSKFXEZoTyvi1_Pa92WpX4Sw9vx0lpJlhlDclkuWdASyXzA8kp2OJA1/s320/Shift.png" width="320" /></a></div>
<br />
All of this these functions have something in common, they all apply a function against every single member of the collection they are given, thus the resulting collection is the exact same size as the collection given to it.<br />
<br />
We can now look at how we would <a href="http://comp-phil.blogspot.com/2015/01/reducing-map-to-reduce-or-all-you-need.html">implement Map using a Fold</a>. We see that Dr. Hutton gives Map the following definition:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">map :: (α → β) → ([α] → [β])</span><br />
<span style="font-family: Courier New, Courier, monospace;">map f = fold (λx xs → f x : xs) [ ]</span><br />
<br />
Folding a Map we'll need a collection to seed with then we just apply the given function against each member concatenating it with the seed.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgOKuY3FRMP33uZv9WXi9Q1dqCkXldCpJjlJgXvP5HOdTeS7QpJNaQg5Zlhr5CSXx2gZB8Vz8nuMiVlr6RtIDVbjcThbJqZJzToiQ3MKuzZPS0W34DrIRuWpOoukp4xYcRMoAT7XzEoic6R/s1600/Screen+Shot+2015-09-07+at+1.54.00+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="275" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgOKuY3FRMP33uZv9WXi9Q1dqCkXldCpJjlJgXvP5HOdTeS7QpJNaQg5Zlhr5CSXx2gZB8Vz8nuMiVlr6RtIDVbjcThbJqZJzToiQ3MKuzZPS0W34DrIRuWpOoukp4xYcRMoAT7XzEoic6R/s320/Screen+Shot+2015-09-07+at+1.54.00+PM.png" width="320" /></a></div>
<br />
(similar to <a href="http://comp-phil.blogspot.com/2015/08/displanting-function-or-folding-reverse.html">Reverse from last time</a>)<br />
<br />
Let us look at an example of upper casing Mike.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh9fKi1EbEM41H1qBdo_rBDdBObfIAZ6TGAtcXoGpp9HtAe8dMouai-ZTgSHUKsujzz72F2BJ8juIUCuuegXNuU2w2Pm02dkCy0GWs3Tm2MP6yuiOTQ2JQuq8dKPS274QpGwHuJtKLFOP0w/s1600/Screen+Shot+2015-09-07+at+2.12.26+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="215" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh9fKi1EbEM41H1qBdo_rBDdBObfIAZ6TGAtcXoGpp9HtAe8dMouai-ZTgSHUKsujzz72F2BJ8juIUCuuegXNuU2w2Pm02dkCy0GWs3Tm2MP6yuiOTQ2JQuq8dKPS274QpGwHuJtKLFOP0w/s320/Screen+Shot+2015-09-07+at+2.12.26+PM.png" width="320" /></a></div>
<br />
First Memoize has nothing and X has M.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg-6isZBkBVisGVz2Z0ITEZwlU0f6-hVBSMpAGaw9mun0KWCF8UOq5JYwjH4QqdtwT9DHRJMPm41yQFoYWbr6XQcmJwpajV7LvrmhuFtqBHwK2_foBWyxxjhg3UcLugZSwf2r9Z4ojqC3Bd/s1600/Screen+Shot+2015-09-07+at+2.13.01+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="224" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg-6isZBkBVisGVz2Z0ITEZwlU0f6-hVBSMpAGaw9mun0KWCF8UOq5JYwjH4QqdtwT9DHRJMPm41yQFoYWbr6XQcmJwpajV7LvrmhuFtqBHwK2_foBWyxxjhg3UcLugZSwf2r9Z4ojqC3Bd/s320/Screen+Shot+2015-09-07+at+2.13.01+PM.png" width="320" /></a></div>
<br />
Second Memoize has M and X has i.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj7fmJt3D8y3_TXTjp6oqCCGn91FfKrATSF8Nvcl_40t6QdzrlO1Ez9EnyA_ia0LEbnIj-_O7G31oV9lSH3Kvo6diEhiMwcl8ATrZT2GmGD6t6zA1VjHZpb2tyrgAW8izui7G9agYfh2Xxm/s1600/Screen+Shot+2015-09-07+at+2.13.21+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="262" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj7fmJt3D8y3_TXTjp6oqCCGn91FfKrATSF8Nvcl_40t6QdzrlO1Ez9EnyA_ia0LEbnIj-_O7G31oV9lSH3Kvo6diEhiMwcl8ATrZT2GmGD6t6zA1VjHZpb2tyrgAW8izui7G9agYfh2Xxm/s320/Screen+Shot+2015-09-07+at+2.13.21+PM.png" width="320" /></a></div>
<br />
Third time Memoize has MI and X has k.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEicNfCvUeKH8N2bXtdEj83RFfR_jYggbC-3ibBvyc2GTGbZNDR7TrCMVRZR4GRPyjvg8-cdtHJyeZJwalej_jQyFp4oX1DNDd6cSC3UJkmNxPU-wn8XtcG_KOEqazU5U2Jj-uLLvKLTIyl1/s1600/Screen+Shot+2015-09-07+at+2.14.05+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="261" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEicNfCvUeKH8N2bXtdEj83RFfR_jYggbC-3ibBvyc2GTGbZNDR7TrCMVRZR4GRPyjvg8-cdtHJyeZJwalej_jQyFp4oX1DNDd6cSC3UJkmNxPU-wn8XtcG_KOEqazU5U2Jj-uLLvKLTIyl1/s320/Screen+Shot+2015-09-07+at+2.14.05+PM.png" width="320" /></a></div>
<br />
Finally Memoize has MIK and X has e.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhA4ldl1_k5isZo8uYYoGkYLe9pIzJbAJXCTdtTkQk7KYsWVRZ-lWqVzvqY8A2PBvRRQFRbTH1h1b5gcDGslFr8Ld6MWYE0tZdqBq3jJE9qXjzKAUBZFthgGM0Gv3iO3s5_IqHooe5GCt7p/s1600/Screen+Shot+2015-09-07+at+2.14.24+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="265" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhA4ldl1_k5isZo8uYYoGkYLe9pIzJbAJXCTdtTkQk7KYsWVRZ-lWqVzvqY8A2PBvRRQFRbTH1h1b5gcDGslFr8Ld6MWYE0tZdqBq3jJE9qXjzKAUBZFthgGM0Gv3iO3s5_IqHooe5GCt7p/s320/Screen+Shot+2015-09-07+at+2.14.24+PM.png" width="320" /></a></div>
<br />
Giving the final result of MIKE. Now let us look at some code examples.<br />
<br />
<h3>
Clojure</h3>
<br />
<script src="https://gist.github.com/MikeMKH/a1abcb11c7e409d6e652.js"></script><br />
<br />
In Clojure we use the <a href="https://clojuredocs.org/clojure.core/reduce">reduce</a> function to Fold. We give the reduce a seed of an empty collection and use <a href="https://clojuredocs.org/clojure.core/conj">conj</a> to join applying the function given with the resulting collection.<br />
<br />
<h3>
C#</h3>
<br />
<script src="https://gist.github.com/MikeMKH/cc079648a97a2920ab76.js"></script><br />
<br />
With C# we use the <a href="http://www.dotnetperls.com/aggregate">aggregate</a> LINQ function to Fold. We give the aggregate a List and add the result of applying each member of the given collection against the function we are mapping with.<br />
<br />
<h3>
ECMAScript 2015</h3>
<br />
<script src="https://gist.github.com/MikeMKH/6a8e7bbe6ea86bfaee01.js"></script><br />
<br />
Using ECMAScript 2015 (aka JavaScript), we use <a href="https://lodash.com/docs#reduce">lodash's foldl</a> to Fold. We give the foldl an empty array and push the result of applying the function given against the member we are mapping against.<br />
<br />
<h3>
To End All</h3>
<br />
There you have it by folding with an empty collection and applying the given function against each member adding the result against the seed and you have a Map.<br />
<br />
<br />Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-56946867885391785092015-08-29T16:05:00.003-05:002015-08-29T16:05:49.865-05:00Displanting a Function OR Folding a Reverse"<i><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">Displant a town, reverse a prince's doom</span></i>"<br />
-- Shakespeare, Romeo and Juliet<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=3&SC=3&IdPlay=32#230673">Act III, Scene III, Line 60</a><br />
<br />
<h3>
Reverse</h3>
<br />
The interesting thing about the Reverse function is that it is not really doing anything. With a small clerical error in a visit and recombine function you have reverse.<br />
<br />
In <a href="http://www.cs.nott.ac.uk/~gmh/">Dr. Hutton's</a> excellent paper, <a href="http://www.cs.nott.ac.uk/~gmh/fold.pdf">"A tutorial on the universality and expressiveness of fold"</a>, the following definition is given for reversing:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">reverse :: [α] → [α]</span><br />
<span style="font-family: Courier New, Courier, monospace;">reverse = fold (λx xs → xs ++ [x]) [ ]</span><br />
<br />
We see that we concat the memoize with the member, in that order, thus reversing the collection.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi1NBjgFnIwnqHWtVz-KgI-eXN7fa1DtV88etLkWQM_SnDLK61i1jhTyOljon0FcpTRLbzZTVpXTXho8XYsfTLJK4HQUoIU9he48BnhFtWWeJ1RBUpPFAmcaxB9b21Ot9VbaNOttczE-W0c/s1600/Screen+Shot+2015-08-29+at+3.40.45+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="271" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi1NBjgFnIwnqHWtVz-KgI-eXN7fa1DtV88etLkWQM_SnDLK61i1jhTyOljon0FcpTRLbzZTVpXTXho8XYsfTLJK4HQUoIU9he48BnhFtWWeJ1RBUpPFAmcaxB9b21Ot9VbaNOttczE-W0c/s320/Screen+Shot+2015-08-29+at+3.40.45+PM.png" width="320" /></a></div>
<br />
Since I like advertising myself, let us go through an example with my name (someone has to advertise for me).<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi5hmZf3yI0pzd7MdXIe4J8Ec61bfhYIpwHpuJgGQkUPnkvlg1kafKv65107bv7fm6bN2Zu29QJM-QWNmT2KKQGmvQwhianlCsoqEJj2CLAcADJaKWQRb2kFYWhIrwrMNN13DVFy3pbmH3v/s1600/Screen+Shot+2015-08-29+at+3.53.42+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="280" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi5hmZf3yI0pzd7MdXIe4J8Ec61bfhYIpwHpuJgGQkUPnkvlg1kafKv65107bv7fm6bN2Zu29QJM-QWNmT2KKQGmvQwhianlCsoqEJj2CLAcADJaKWQRb2kFYWhIrwrMNN13DVFy3pbmH3v/s320/Screen+Shot+2015-08-29+at+3.53.42+PM.png" width="320" /></a></div>
<br />
First time the Memoize has nothing and X has M.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhnfXHAamLVBzNyjQSwRf8G0WsVsYBSG-tw_op1mSdC9xRXIi5gI-z-NtFVxUjcVuX2gqmkjGiaifeGHmUxILQbBGlz5XKKIyhasI0vpjoXU-e0qzcLitFDrwvzuxrwTDKLBIHn9RHXh1GD/s1600/Screen+Shot+2015-08-29+at+3.56.17+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="224" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhnfXHAamLVBzNyjQSwRf8G0WsVsYBSG-tw_op1mSdC9xRXIi5gI-z-NtFVxUjcVuX2gqmkjGiaifeGHmUxILQbBGlz5XKKIyhasI0vpjoXU-e0qzcLitFDrwvzuxrwTDKLBIHn9RHXh1GD/s320/Screen+Shot+2015-08-29+at+3.56.17+PM.png" width="320" /></a></div>
<br />
Second time the Memoize has M and X is i.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg7CnPyeZhGNg5V9UOo7gwvvlZnOZvG0fkEaxaXbqHg-VCPJrps56PtXZCr9QUGRFc0krdMrkidonPdZqDTgh7zqa2J8qSxLZprmbNctXUxkf7VpqzSU05IZamWeZhT2BVrKwYiit61UExM/s1600/Screen+Shot+2015-08-29+at+3.57.24+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="222" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg7CnPyeZhGNg5V9UOo7gwvvlZnOZvG0fkEaxaXbqHg-VCPJrps56PtXZCr9QUGRFc0krdMrkidonPdZqDTgh7zqa2J8qSxLZprmbNctXUxkf7VpqzSU05IZamWeZhT2BVrKwYiit61UExM/s320/Screen+Shot+2015-08-29+at+3.57.24+PM.png" width="320" /></a></div>
<br />
Third time Memoize has i and M and X has k.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhcK3_2GwPyIecF0NTzLq_gPqJE2lDfIdrv-nj0XRpbK2pvAeGe_bzemfoyrMksF9GPeLHRLVNOm9y39nzzNnBUcmoeTvQG8TPiCDyka6vVJjqCykW05EE3t26zlDplQW9LwJRF9SZriAJM/s1600/Screen+Shot+2015-08-29+at+3.58.46+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="222" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhcK3_2GwPyIecF0NTzLq_gPqJE2lDfIdrv-nj0XRpbK2pvAeGe_bzemfoyrMksF9GPeLHRLVNOm9y39nzzNnBUcmoeTvQG8TPiCDyka6vVJjqCykW05EE3t26zlDplQW9LwJRF9SZriAJM/s320/Screen+Shot+2015-08-29+at+3.58.46+PM.png" width="320" /></a></div>
<br />
Fourth time Memoize has k, i, and M while X has e.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgmscPvY6jnLLaDPxYV22vs6FCtsl5HAQM5F1ohb1dQoB_slqkvVGX9Gw6k8FIHrLs5kjUe-mja44y8mjKyCq-MFuaaZv76blZA-FiAO2qKXsVXGO-29ye_j3ESav5u0h9cnIDsuyXvCJhx/s1600/Screen+Shot+2015-08-29+at+4.00.18+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="223" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgmscPvY6jnLLaDPxYV22vs6FCtsl5HAQM5F1ohb1dQoB_slqkvVGX9Gw6k8FIHrLs5kjUe-mja44y8mjKyCq-MFuaaZv76blZA-FiAO2qKXsVXGO-29ye_j3ESav5u0h9cnIDsuyXvCJhx/s320/Screen+Shot+2015-08-29+at+4.00.18+PM.png" width="320" /></a></div>
<br />
Leaving us with ekiM.<br />
<br />
Let us look at some code examples.<br />
<br />
<h3>
Clojure</h3>
<br />
<script src="https://gist.github.com/MikeMKH/5ee165039dcc374bc673.js"></script><br />
<br />
We see with the Clojure code we are using the <a href="https://clojuredocs.org/clojure.core/cons">cons function</a> to place the current member in the front of the memoize. We do this for the whole collection thus giving us the collection in reverse.<br />
<br />
<h3>
C#</h3>
<br />
<script src="https://gist.github.com/MikeMKH/b644fd7cdbd0e69fe5b9.js"></script><br />
<br />
With the C# code we see that we need to create something to contain the resulting collection, in this case we'll create a <a href="http://www.dotnetperls.com/ilist">List</a>. We create the reversed collection in an immutable way by creating a new List every time in the lambda.<br />
<br />
<h3>
ECMAScript 2015</h3>
<br />
<script src="https://gist.github.com/MikeMKH/23c01915912d11a01d0d.js"></script><br />
<br />
With JavaScript (ECMAScript 2015) we us the <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/unshift">unshift</a> method on the array. Since unshift returns the length of the array after the member is added to the head of the array (which I totally did not expect) we need to manually return the memoize after applying unshift.<br />
<br />
<h3>
Fin</h3>
<br />
There you have it again, yet another function which can be created using Fold. Showing once again that all you need is Fold.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-71456999229940551352015-08-23T11:06:00.004-05:002015-08-26T19:04:23.522-05:00Think About Length OR How Fold Can Do Everything, Even Count<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;"><i>"Leave nothing out for length, and make us think"</i></span><br />
-- Shakespeare, Coriolanus<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=2&SC=2&IdPlay=3#121921">Act II, Scene II, Line 47</a><br />
<br />
<h3>
How Long is It?</h3>
I am not sure why but before I start reading a chapter or watching something I've recorded I almost always check to see how long it is. Today's post will be using Fold to find the length of a collection. In <a href="http://www.cs.nott.ac.uk/~gmh/">Dr. Hutton's</a> excellent paper, <a href="http://www.cs.nott.ac.uk/~gmh/fold.pdf">"A tutorial on the universality and expressiveness of fold"</a>, the following definition is given for finding the length:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">length :: [α] → Int</span><br />
<span style="font-family: Courier New, Courier, monospace;">length = fold (λx n → 1 + n) 0</span><br />
<br />
We see with this definition we do nothing with the current member of the collection (x above) and instead only act on the memoize (n above).<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi2JEjYZTNdoVVJYZ8zMxMhCXGGydqdlqJrmrvnbw4dak1SnHx4Y4D4rbRzc18m_M3JRXydTubU_MzUAIequtydf7XAS9_0aXiM0UnweaYyH40f3im0043Lc4l1k1IcQ9be102j-RxUqJdf/s1600/Screen+Shot+2015-08-23+at+10.39.20+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="285" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi2JEjYZTNdoVVJYZ8zMxMhCXGGydqdlqJrmrvnbw4dak1SnHx4Y4D4rbRzc18m_M3JRXydTubU_MzUAIequtydf7XAS9_0aXiM0UnweaYyH40f3im0043Lc4l1k1IcQ9be102j-RxUqJdf/s320/Screen+Shot+2015-08-23+at+10.39.20+AM.png" width="320" /></a></div>
<br />
In the simple example below we will see that the string "Mike" has 4 characters in it.<br />
<br />
At the start we have a Seed of 0 and a collection with the members M, i, k, and e.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjD3HT96SoOxeGHVp2zNvtyYQNVkiMrCksS1MpwL4D546Fugjk06E3o0WCuYgmdTizGyTtHBXz_EBf3B7BPCpDEafaDt4p1eLJ_Qb45PqyeCR4GWQDirSq2lUS_675IuamNHgsBv_2psc1I/s1600/Screen+Shot+2015-08-23+at+10.42.59+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="268" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjD3HT96SoOxeGHVp2zNvtyYQNVkiMrCksS1MpwL4D546Fugjk06E3o0WCuYgmdTizGyTtHBXz_EBf3B7BPCpDEafaDt4p1eLJ_Qb45PqyeCR4GWQDirSq2lUS_675IuamNHgsBv_2psc1I/s320/Screen+Shot+2015-08-23+at+10.42.59+AM.png" width="320" /></a></div>
<br />
First time Memoize has 0 in it and X has M.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEghJm_HhaO9lvDXk6nEAmsXCsDzZuvtu9ppIcojucKGreEAxOp07OVSel96nqpVLWQnNfXFAdOED3h-Fi_jP_IgZZ1DaE79TxKabK94LFkzrsJRSLgFsIY1mTqs0T4pK6RPJKpQGkOpBiDw/s1600/Screen+Shot+2015-08-23+at+10.46.09+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="228" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEghJm_HhaO9lvDXk6nEAmsXCsDzZuvtu9ppIcojucKGreEAxOp07OVSel96nqpVLWQnNfXFAdOED3h-Fi_jP_IgZZ1DaE79TxKabK94LFkzrsJRSLgFsIY1mTqs0T4pK6RPJKpQGkOpBiDw/s320/Screen+Shot+2015-08-23+at+10.46.09+AM.png" width="320" /></a></div>
<br />
Second time Memoize has 1 in it and X has i.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_jyCE6WOOxp-71V4ETxsAvdl69mo6oClah3jLMlVkYRfCG9WY4oWoN-8_8-chnmwY5Mz9e2lAA4PtA-6qNnX6GDpA9Nl7sfW0FGEb7FZmWvYL29upg18fvhRXxMaq6M_iG0Pw9UkFEuZk/s1600/Screen+Shot+2015-08-23+at+10.48.46+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="266" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_jyCE6WOOxp-71V4ETxsAvdl69mo6oClah3jLMlVkYRfCG9WY4oWoN-8_8-chnmwY5Mz9e2lAA4PtA-6qNnX6GDpA9Nl7sfW0FGEb7FZmWvYL29upg18fvhRXxMaq6M_iG0Pw9UkFEuZk/s320/Screen+Shot+2015-08-23+at+10.48.46+AM.png" width="320" /></a></div>
Third time Memoize has 2 in it and X has the letter k.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgWaZLzpEafhnc7puIinctkm-fXt5VBPo-YOa-jmxLRFGoWzJgjyPVZ2kll6cgiWf7-H5z053gR7V9PmclnzX75cG-kX2aXS1gJmj6YhhqMfg0kHprUk3Lj6x3GmdA8K-vTbtIcaLDFfT7c/s1600/Screen+Shot+2015-08-23+at+10.50.24+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="270" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgWaZLzpEafhnc7puIinctkm-fXt5VBPo-YOa-jmxLRFGoWzJgjyPVZ2kll6cgiWf7-H5z053gR7V9PmclnzX75cG-kX2aXS1gJmj6YhhqMfg0kHprUk3Lj6x3GmdA8K-vTbtIcaLDFfT7c/s320/Screen+Shot+2015-08-23+at+10.50.24+AM.png" width="320" /></a></div>
Last time Memoize has 3 and X has e.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhA65aGxmrgH0Z3Vzj05tb_tZOvdMrhZILptbNEAL73Bu4bcj79kyT319426RbsfSWkLs49t0MaAoX4XUxewjthgrgsSM_TmIhbe1XKQGffH0uu-Bmd_jYiWej_VHRuCkm2yHrbX_X7mFu4/s1600/Screen+Shot+2015-08-23+at+10.52.09+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="269" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhA65aGxmrgH0Z3Vzj05tb_tZOvdMrhZILptbNEAL73Bu4bcj79kyT319426RbsfSWkLs49t0MaAoX4XUxewjthgrgsSM_TmIhbe1XKQGffH0uu-Bmd_jYiWej_VHRuCkm2yHrbX_X7mFu4/s320/Screen+Shot+2015-08-23+at+10.52.09+AM.png" width="320" /></a></div>
There you have it (maybe I should have used my sister Kim name instead). Let us see some code.<br />
<br />
<h3>
Clojure</h3>
<script src="https://gist.github.com/MikeMKH/ca9725b78f05851bf2d2.js"></script><br />
We see in the clojure example that function we give the <a href="https://clojuredocs.org/clojure.core/reduce">reduce</a> must have two parameters, so we call the second one _ to denote that it is not used.<br />
<br />
<h3>
C#</h3>
<script src="https://gist.github.com/MikeMKH/d2011c7bc4ad842fe835.js"></script><br />
With the C# code the lambda we give <a href="http://www.dotnetperls.com/aggregate">Aggregate</a> has two values of which we give the second one the name of _ to denote not using it.<br />
<br />
<h3>
JavaScript (ECMAScript 2015)</h3>
<script src="https://gist.github.com/MikeMKH/2b9a5c5cbaa39f61a66f.js"></script><br />
With ECMAScript 2015 we use <a href="https://lodash.com/docs#reduce">lodash's foldl</a> and see that the lambda only has to have one value which is the memoize.<br />
<br />
<h3>
Fin</h3>
There you have it counting with Fold, showing that you need is Fold.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-42581823927914816002015-08-16T16:45:00.003-05:002015-08-16T16:50:02.570-05:00If True or False I Know Not"<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;"><i>I idly heard; if true or false I know not.</i></span>"<br />
<div>
-- Shakespeare, King John<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=4&SC=2&IdPlay=15#167793">Act IV, Scene II, Line 124</a><br />
<br />
<h3>
Welcome Back</h3>
<br />
This is the next in the series of post on <a href="http://www.cs.nott.ac.uk/~gmh/">Dr. Graham Hutton's</a> excellent paper, <a href="http://www.cs.nott.ac.uk/~gmh/fold.pdf">"A tutorial on the universality and expressiveness of fold"</a>, this time around we'll look at Oring. Dr. Hutton has given Oring the following definition:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">or :: [Bool] → Bool</span><br />
<span style="font-family: Courier New, Courier, monospace;">or = fold (∨) False</span><br />
<br />
The idea is that we Fold an Or function with a seed value of False. If one of the members of the collection is True we Or it with False giving us True, else if none of the members of the collection are True we will end up with the value of False.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEitvVY_-tCWj9tqMK0OVIxPQsc59jeCFvOFW-SLH0Rpw8QJkGjvjjrKVU9ZRp4Q_eOrQBnK8iNuGKmoXGc3Rzf6OwDIFp-4gokZIUQKokUOULNnI5b4uQyS24H4Ud5SO7c1Wit0RIy-stVQ/s1600/Screen+Shot+2015-08-16+at+4.21.56+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="277" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEitvVY_-tCWj9tqMK0OVIxPQsc59jeCFvOFW-SLH0Rpw8QJkGjvjjrKVU9ZRp4Q_eOrQBnK8iNuGKmoXGc3Rzf6OwDIFp-4gokZIUQKokUOULNnI5b4uQyS24H4Ud5SO7c1Wit0RIy-stVQ/s320/Screen+Shot+2015-08-16+at+4.21.56+PM.png" width="320" /></a></div>
<br />
In the simple example below we'll see that if we have a single value of True then the end result will be True.<br />
<br />
At the start we have a Seed value of False with collection containing False, True, and False.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjI_WP3VXaJMVC7p3OsgJe9LTttLQCWMUHtvk3xTMCwpVR_WXF_kQ-oYAJxpu155iO05wihfBUjSwAAi1g5Mx3pFb8V9ig-XvO3LXFw6nS6RC4iyJTT4MonrtfMRDXqb99OXGe8HB1trtAj/s1600/Screen+Shot+2015-08-16+at+4.39.54+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjI_WP3VXaJMVC7p3OsgJe9LTttLQCWMUHtvk3xTMCwpVR_WXF_kQ-oYAJxpu155iO05wihfBUjSwAAi1g5Mx3pFb8V9ig-XvO3LXFw6nS6RC4iyJTT4MonrtfMRDXqb99OXGe8HB1trtAj/s320/Screen+Shot+2015-08-16+at+4.39.54+PM.png" width="287" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
First time the Memorize has False and X has False.</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjaO57RDprCKhRE584tDwqaSjrG5q1Ahg6J4bba06RUWOPb_HaztIEP3FO3ynWndDOB908BcLuY8kqhBry5T5WuW5CVOuva1zwD8rsQWFpUutLQ0OngM0sUsGi-axrty9PD0xK4J4O_DgWQ/s1600/Screen+Shot+2015-08-16+at+4.40.11+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="255" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjaO57RDprCKhRE584tDwqaSjrG5q1Ahg6J4bba06RUWOPb_HaztIEP3FO3ynWndDOB908BcLuY8kqhBry5T5WuW5CVOuva1zwD8rsQWFpUutLQ0OngM0sUsGi-axrty9PD0xK4J4O_DgWQ/s320/Screen+Shot+2015-08-16+at+4.40.11+PM.png" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Second time the Memorize has False and X has True.</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgUMrOkJCZiC6bj3M3zyDDZqcPIgt55HqhaY8aREjqYxj6MLzBm9F9Emf8_Aau6A_ITFzt6v_dPCK055CdPewR0I-vDqYrO6zuCXnX0CPm8yy2ftKkVQ-TEuXF5m3RhNKv-5E2ylwxA51Gb/s1600/Screen+Shot+2015-08-16+at+4.40.27+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="259" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgUMrOkJCZiC6bj3M3zyDDZqcPIgt55HqhaY8aREjqYxj6MLzBm9F9Emf8_Aau6A_ITFzt6v_dPCK055CdPewR0I-vDqYrO6zuCXnX0CPm8yy2ftKkVQ-TEuXF5m3RhNKv-5E2ylwxA51Gb/s320/Screen+Shot+2015-08-16+at+4.40.27+PM.png" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Third time the Memorize has True and X has False giving use the finally value of True.</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9gJNlyCffJ6NU7Kqd5lj5GdrtDunlqJknLW56duMCSPHyNHriPf7gRNiHzCBr7g3nJOgX0DUq9tfiRlgCMCUCs94Iv4obpedKu54orunUWnA-TQZkctkOIZcMuDw_ful3XWpewzfb8fPj/s1600/Screen+Shot+2015-08-16+at+4.40.39+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="260" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9gJNlyCffJ6NU7Kqd5lj5GdrtDunlqJknLW56duMCSPHyNHriPf7gRNiHzCBr7g3nJOgX0DUq9tfiRlgCMCUCs94Iv4obpedKu54orunUWnA-TQZkctkOIZcMuDw_ful3XWpewzfb8fPj/s320/Screen+Shot+2015-08-16+at+4.40.39+PM.png" width="320" /></a></div>
<br />
<br />
Let us now look at this in sweet, sweet code.<br />
<br />
<h3>
Clojure</h3>
<script src="https://gist.github.com/MikeMKH/24ddbee5a9ebf4437408.js"></script><br />
<br />
In the Clojure code that we use the <a href="https://clojuredocs.org/clojure.core/or">or macro</a> and a seed value of false in order to create an Oring function using the higher order function of <a href="https://clojuredocs.org/clojure.core/reduce">reduce</a>. Since reduce is expecting a function and not a macro we need to create a lambda function to wrap the or macro.<br />
<br />
<h3>
C#</h3>
<script src="https://gist.github.com/MikeMKH/e6c8cf7f12a5144a45cc.js"></script><br />
<br />
We see in the C# code that we can use the <a href="http://www.dotnetperls.com/aggregate">LINQ aggregate method</a> on the collection we are folding. We give the aggregate a seed value of false and in the lambda we simply takes the memorize and the current member and or them.<br />
<br />
<h3>
JavaScript (ECMAScript 2015)</h3>
<script src="https://gist.github.com/MikeMKH/d2f32f97b9b3822d867d.js"></script><br />
<br />
Using <a href="https://lodash.com/docs#reduce">lodash's foldl function</a> along with <a href="http://babeljs.io/">Babel.js</a> we are able to create an Oring function by folding over the collection and passing it to a lambda function which ors the current member of the collection with the memorize value. We give a seed value of false thus causing the initial value of the memorize to be false.<br />
<br />
<h3>
Until Next Time</h3>
<br />
There you have it an Oring function using nothing but Fold. Thus "proving" that all you need is Fold.<br />
<br />
<br /></div>
Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-21100095109080056522015-08-09T13:23:00.002-05:002015-08-09T13:24:18.659-05:00Approaching the Fold"<i><span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;">Approach the fold and cull th' infected forth</span></i>"<br />
-- Shakespeare, Timon of Athens<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=5&SC=4&IdPlay=17#175623">Act V, Scene IV, Line 43</a><br />
<br />
<h3>
Welcome</h3>
<br />
In <a href="http://www.cs.nott.ac.uk/~gmh/">Graham Hutton's</a> excellent paper, "<a href="http://www.cs.nott.ac.uk/~gmh/fold.pdf">A tutorial on the universality and expressiveness of fold</a>", the first function that is looked at is And. Dr. Hutton gives And the following definition:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;">and :: [Bool] → Bool</span><br />
<span style="font-family: Courier New, Courier, monospace;">and = fold (∧) True</span><br />
<br />
The idea being that we give Fold an And function with a seed value of True. If one of the members of the collection given is False the Anding it with True will yield a value of False and thus the end result will be False. If no member of the collection given is False then the end result will be True.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkq-2URvhQc_56xPyfS5644DyAZ9c4G3J9tQZ4egDsH7srPmQgZD5T15OhYaiylgrjGevLHI2qNKCPBbDld7dnjNQQM7gLmUW7nlwiL9HsrISJcsvzxrjV19pyJ3XUYh7qQkd1SGtwoOA6/s1600/Screen+Shot+2015-08-09+at+1.07.06+PM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="279" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkq-2URvhQc_56xPyfS5644DyAZ9c4G3J9tQZ4egDsH7srPmQgZD5T15OhYaiylgrjGevLHI2qNKCPBbDld7dnjNQQM7gLmUW7nlwiL9HsrISJcsvzxrjV19pyJ3XUYh7qQkd1SGtwoOA6/s320/Screen+Shot+2015-08-09+at+1.07.06+PM.png" width="320" /></a></div>
<br />
Let us look at this in code.<br />
<br />
<h3>
Clojure</h3>
<br />
<script src="https://gist.github.com/MikeMKH/f33fc540f461206b71f4.js"></script><br />
<br />
To create an Anding function we'll use <a href="https://clojuredocs.org/clojure.core/reduce">reduce</a> along with the <a href="https://clojuredocs.org/clojure.core/and">and</a> macro with a seed of true. Since and is a macro, we'll need to wrap it in a function in order to be able to use it in reduce.<br />
<br />
<h3>
C#</h3>
<br />
<script src="https://gist.github.com/MikeMKH/eb498fb74d106bd57237.js"></script><br />
<br />
We'll use the <a href="http://www.dotnetperls.com/aggregate">LINQ function Aggregate</a> along && and a value of true to create an Anding function.<br />
<br />
<h3>
JavaScript</h3>
<br />
<script src="https://gist.github.com/MikeMKH/1e80f099ee412deae897.js"></script><br />
<br />
We see that by using <a href="https://lodash.com/docs#reduce">lodash's foldl</a> function with && and the value true we can create an Anding function.<br />
<br />
<h3>
ECMAScript 2015</h3>
<br />
<script src="https://gist.github.com/MikeMKH/164d8ebc89bcfecbe480.js"></script><br />
<br />
Since we live in the future, we'll use <a href="http://babeljs.io/">Babel</a> to allow us to use <a href="http://www.ecma-international.org/ecma-262/6.0/">ECMAScript 2015</a>. We see again that by using <a href="https://lodash.com/docs#reduce">lodash's foldl</a> with && along with the value true we now have an Anding function.<br />
<br />
<h3>
Fin</h3>
<br />
There you have it the And function using Fold, showing once again that all you need is Fold.Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.comtag:blogger.com,1999:blog-6545287867125256063.post-61657718498303847502015-08-02T13:52:00.002-05:002015-08-09T12:38:33.444-05:00Bro, Do You Even FizzBuzz?!?"<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;"><i>Do you bite your thumb at us, sir?</i></span>"<br />
-- Shakespeare, Romeo and Juliet<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=1&SC=1&IdPlay=32#228273">Act I, Scene I, Line 43</a><br />
<br />
FizzBuzz as an interview <a href="http://comp-phil.blogspot.com/2014/05/the-form-of-katas.html">kata</a> has been getting a lot of bad press lately. Part of the bad press has been around having to use <a href="http://mathworld.wolfram.com/Modulus.html">modulus</a> in the solution. I am not sure how people have been explaining FizzBuzz in interviews, but you do not have to know anything about the mod operator in order to solve the problem.<br />
<br />
Here is a solution in Clojure which does not use modulus.<br />
<br />
<script src="https://gist.github.com/MikeMKH/23377c87a5d9780c8a74.js"></script><br />
<br />
This solution is using <a href="https://clojuredocs.org/clojure.core/cycle">cycles</a> and <a href="http://comp-phil.blogspot.com/2015/01/on-zipping.html">zip</a>. The odds are low of someone knowing how to use cycle and zip but not knowing modulus. The point is that you do not need to know about modulus to do the kata.<br />
<br />
In interviews I do, I'll tell the person about modulus if they get stuck. The point of using a kata in an interview is to make sure that person who <a href="http://blog.codinghorror.com/why-cant-programmers-program/">claims to be a programmer can actually program</a> and that you can work with the person.<br />
<br />
Still if the whole modulus thing has you worried, try the <a href="http://comp-phil.blogspot.com/2015/03/roman-numeral-kata-in-one-line-with-c.html">Roman Numeral kata</a>.<br />
<br />
Here is a solution in C# I did few minutes before an interview on Thursday (pro-tip, always make sure you can do the kata in short amount of time before you ask someone else to do it in an interview).<br />
<br />
<script src="https://gist.github.com/MikeMKH/d0b89556b496b82832c3.js"></script><br />
<br />
Again, the goal of the interview kata should be to see if the person can actually program and to see what they are like to work with.<br />
<br />
"<span style="font-family: Helvetica Neue, Arial, Helvetica, sans-serif;"><i>No, sir, I do not bite my thumb at you, sir. But<br />I bite my thumb, sir.</i></span>"<br />
<div>
-- Shakespeare, Romeo and Juliet<br />
<a href="http://www.shakespeareswords.com/Plays.aspx?Ac=1&SC=1&IdPlay=32#228286">Act I, Scene I, Lines 49-50</a><br />
<br />
<br /></div>
Mike Harrishttp://www.blogger.com/profile/14085354666808996894noreply@blogger.com