ploeh blog https://blog.ploeh.dk danish software design en-us Mark Seemann Mon, 11 Nov 2019 09:16:21 UTC Mon, 11 Nov 2019 09:16:21 UTC Diamond rock https://blog.ploeh.dk/2019/11/11/diamond-rock/ Mon, 11 Nov 2019 09:15:00 UTC <div id="post"> <p> <em>A diamond kata implementation written in Rockstar</em> </p> <p> I've <a href="/2015/01/10/diamond-kata-with-fscheck">previously written about the diamond kata</a>, which has become one of my favourite programming exercises. I wanted to take the <a href="https://codewithrockstar.com">Rockstar</a> language out for a spin, and it seemed a good candidate problem. </p> <h3 id="ab491bf89ae945f48821fe7b324febeb"> Rockstar <a href="#ab491bf89ae945f48821fe7b324febeb" title="permalink">#</a> </h3> <p> If you're not aware of the Rockstar programming language, it started with a tweet from <a href="http://paulstovell.com">Paul Stovell</a>: <blockquote> <p> "To really confuse recruiters, someone should make a programming language called Rockstar." </p> <footer><cite><a href="https://twitter.com/paulstovell/status/1013960369465782273">Paul Stovell</a></cite></footer> </blockquote> This inspired <a href="http://www.dylanbeattie.net">Dylan Beattie</a> to create the Rockstar programming language. The language's <a href="https://codewithrockstar.com">landing page</a> already sports an <a href="/2015/08/03/idiomatic-or-idiosyncratic">idiomatic</a> implementation of the <a href="http://codingdojo.org/kata/FizzBuzz">FizzBuzz kata</a>, so I had to pick another exercise. The <a href="http://claysnow.co.uk/recycling-tests-in-tdd">diamond kata</a> was a natural choice for me. </p> <h3 id="c17e0b1d17f04d19b9e965ad531f10d9"> Lyrics <a href="#c17e0b1d17f04d19b9e965ad531f10d9" title="permalink">#</a> </h3> <p> I'll start with the final result. What follows here are the final lyrics to <em>Diamond rock</em>. As you'll see, it starts with a short prologue after which it settles into a repetitive pattern. I imagine that this might make it useful for audience participation, in the anthem rock style of e.g. <a href="https://en.wikipedia.org/wiki/We_Will_Rock_You">We Will Rock You</a>. </p> <p> After 25 repetitions the lyrics change. I haven't written music to any of them, but I imagine that this essentially transitions into another song, just like <em>We Will Rock You</em> traditionally moves into <a href="https://en.wikipedia.org/wiki/We_Are_the_Champions">We Are the Champions</a>. The style of the remaining lyrics does, however, suggest something musically more complex than a rock anthem. </p> <p> <pre>Your memory says&nbsp;&nbsp; The way says A Despair takes your hope The key is nothing Your courage is a tightrope Let it be without it If your hope is your courage Let the key be the way Build your courage up If your hope is your courage The key says B Build your courage up If your hope is your courage The key says C Build your courage up If your hope is your courage The key says D Build your courage up If your hope is your courage The key says E Build your courage up If your hope is your courage The key says F Build your courage up If your hope is your courage The key says G Build your courage up If your hope is your courage The key says H Build your courage up If your hope is your courage The key says I Build your courage up If your hope is your courage The key says J Build your courage up If your hope is your courage The key says K Build your courage up If your hope is your courage The key says L Build your courage up If your hope is your courage The key says M Build your courage up If your hope is your courage The key says N Build your courage up If your hope is your courage The key says O Build your courage up If your hope is your courage The key says P Build your courage up If your hope is your courage The key says Q Build your courage up If your hope is your courage The key says R Build your courage up If your hope is your courage The key says S Build your courage up If your hope is your courage The key says T Build your courage up If your hope is your courage The key says U Build your courage up If your hope is your courage The key says V Build your courage up If your hope is your courage The key says W Build your courage up If your hope is your courage The key says X Build your courage up If your hope is your courage The key says Y Build your courage up If your hope is your courage The key says Z Give back the key Dream takes a tightrope Your hope's start'n'stop While Despair taking your hope ain't a tightrope Build your hope up Give back your hope Raindrop is a wintercrop Light is a misanthrope Let it be without raindrop Darkness is a kaleidoscope Let it be without raindrop Diamond takes your hour, love, and your day If love is the way Let your sorrow be your hour without light Put your sorrow over darkness into flight Put your memory of flight into motion Put it with love, and motion into the ocean Whisper the ocean If love ain't the way Let ray be your day of darkness without light Let your courage be your hour without darkness, and ray Put your courage over darkness into the night Put your memory of ray into action Let satisfaction be your memory of the night Let alright be satisfaction with love, action, love, and satisfaction Shout alright Listen to the wind Let flight be the wind Let your heart be Dream taking flight Let your breath be your heart of darkness with light Your hope's stop'n'start While your hope is lower than your heart Let away be Despair taking your hope Diamond taking your breath, away, and your hope Build your hope up Renown is southbound While your hope is as high as renown Let away be Despair taking your hope Diamond taking your breath, away, and your hope Knock your hope down</pre> </p> <p> Not only do these look like lyrics, but it's also an executable program! </p> <h3 id="994b9a9d46dc467383c528a17dc99f65"> Execution <a href="#994b9a9d46dc467383c528a17dc99f65" title="permalink">#</a> </h3> <p> If you want to run the program, you can copy the text and paste it into <a href="https://codewithrockstar.com/online">the web-based Rockstar interpreter</a>; that's what I did. </p> <p> When you <em>Rock!</em> the lyrics, the interpreter will prompt you for an input. There's no instructions or input validation, but <em>the only valid input is the letters</em> <code>A</code> to <code>Z</code>, and <em>only in upper case</em>. If you type anything else, I don't know what'll happen, but most likely it'll just enter an infinite loop, and you'll have to reboot your computer. </p> <p> If you input, say, <code>E</code>, the output will be the expected diamond figure: </p> <p> <pre> A B B C C D D E E D D C C B B A </pre> </p> <p> When you paste the code, be sure to include everything. There's significant whitespace in those lyrics; I'll explain later. </p> <h3 id="12f2c388f5c8499594a3bf90f37e07f4"> Readable code <a href="#12f2c388f5c8499594a3bf90f37e07f4" title="permalink">#</a> </h3> <p> As the Rockstar documentation strongly implies, <em>singability</em> is more important than readability. You can, however, write more readable Rockstar code, and that's what I started with: </p> <p> <pre>Space says&nbsp;&nbsp; LetterA says A GetLetter takes index If index is 0 Give back LetterA If index is 1 retVal says B Give back retVal If index is 2 retVal says C Give back retVal GetIndex takes letter Index is 0 While GetLetter taking Index ain't letter Build Index up Give back Index PrintLine takes width, l, lidx If l is LetterA Let completeSpaceCount be width minus 1 Let paddingCount be completeSpaceCount over 2 Let padding be Space times paddingCount Let line be padding plus l plus padding Say line Else Let internalSpaceSize be lidx times 2 minus 1 Let filler be Space times internalSpaceSize Let totalOuterPaddingSize be width minus 2, internalSpaceSize Let paddingSize be totalOuterPaddingSize over 2 Let padding be Space times paddingSize Let line be padding plus l, filler, l, padding Say line Listen to input Let idx be GetIndex taking input Let width be idx times 2 plus 1 Let counter be 0 While counter is lower than idx Let l be GetLetter taking counter PrintLine taking width, l, counter Build counter up While counter is as high as 0 Let l be GetLetter taking counter PrintLine taking width, l, counter Knock counter down</pre> </p> <p> This prototype only handled the input letters <code>A</code>, <code>B</code>, and <code>C</code>, but it was enough to verify that the algorithm worked. I've done the diamond kata several times before, so I only had to find the most imperative implementation on my hard drive. It wasn't too hard to translate to Rockstar. </p> <p> Although Rockstar supports mainstream quoted strings like <code>"A"</code>, <code>"B"</code>, and so on, you can see that I went straight for <em>poetic string literals</em>. Before I started persisting Rockstar code to a file, I experimented with the language using the online interpreter. I wanted the program to look as much like rock lyrics as I could, so I didn't want to have too many statements like <code>Shout "FizzBuzz!"</code> in my code. </p> <h3 id="1ae1c1c329894b438bc934097090901b"> Obscuring space <a href="#1ae1c1c329894b438bc934097090901b" title="permalink">#</a> </h3> <p> My first concern was whether I could obscure the space character. Using a poetic string literal, I could: </p> <p> <pre>Space says&nbsp;&nbsp;</pre> </p> <p> The rules of poetic string literals is that everything between <code>says&nbsp;</code> and the newline character becomes the value of the string variable. So there's an extra space after <code>says&nbsp;</code>! </p> <p> After I renamed all the variables and functions, that line became: </p> <p> <pre>Your memory says&nbsp;&nbsp;</pre> </p> <p> Perhaps it isn't an unprintable character, but it <em>is</em> unsingable. </p> <h3 id="d1ae4568cc104312a3c20fe8019ccb18"> No else <a href="#d1ae4568cc104312a3c20fe8019ccb18" title="permalink">#</a> </h3> <p> The keyword <code>Else</code> looks conspicuously like a programming construct, so I wanted to get rid of that as well. That was easy, because I could just invert the initial <code>if</code> condition: </p> <p> <pre>If l ain't LetterA</pre> </p> <p> This effectively switches between the two alternative code blocks. </p> <h3 id="cbaa9c218905453bb3df2155b9e9b822"> Obscuring letter indices <a href="#cbaa9c218905453bb3df2155b9e9b822" title="permalink">#</a> </h3> <p> I also wanted to obscure the incrementing index values <code>1</code>, <code>2</code>, <code>3</code>, etcetera. Since the indices are monotonically increasing, I realised that I could use a counter and increment it: </p> <p> <pre>number is 0 If index is number Let retVal be LetterA Build number up If index is number retVal says B Build number up If index is number retVal says C</pre> </p> <p> The function initialises <code>number</code> to <code>0</code> and assigns a value to <code>retVal</code> if the input <code>index</code> is also <code>0</code>. </p> <p> If not, it increments the <code>number</code> (so that it's now <code>1</code>) and again compares it to <code>index</code>. This sufficiently obscures the indices, but if there's a way to hide the letters of the alphabet, I'm not aware of it. </p> <p> After I renamed the variables, the code became: </p> <p> <pre>Your courage is a tightrope Let it be without it If your hope is your courage Let the key be the way Build your courage up If your hope is your courage The key says B Build your courage up If your hope is your courage The key says C</pre> </p> <p> There's one more line of code in the final lyrics, compared to the above snippet. The line <code>Let it be without it</code> has no corresponding line of code in the readable version. What's going on? </p> <h3 id="aef4cf50f4484327b37cd61995c74d99"> Obscuring numbers <a href="#aef4cf50f4484327b37cd61995c74d99" title="permalink">#</a> </h3> <p> Like poetic string literals, Rockstar also supports <em>poetic number literals</em>. Due to its modulo-ten-based system, however, I found it difficult to come up with a good ten-letter word that fit the song's lyrical theme. I <em>could</em> have done something like this to produce the number <code>0</code>: </p> <p> <pre>Your courage is barbershop</pre> </p> <p> or some other ten-letter word. My problem was that regardless of what I chose, it didn't sound good. Some article like <code>a</code> or <code>the</code> would sound better, but that would change the value of the poetic number literal. <code>a tightrope</code> is the number <em>19</em>, because <code>a</code> has one letter, and <code>tightrope</code> has nine. </p> <p> There's a simple way to produce <em>0</em> from any number: just subtract the number from itself. That's what <code>Let it be without it</code> does. I could also have written it as <code>Let your courage be without your courage</code>, but I chose to take advantage of Rockstar's <em>pronoun</em> feature instead. I'd been looking for an opportunity to include the phrase <a href="https://en.wikipedia.org/wiki/Let_It_Be_(Beatles_song)">Let It Be</a> ever since I learned about the <code>Let x be y</code> syntax. </p> <p> The following code snippet initialises the variable <code>Your courage</code> to <code>19</code>, but on the next line subtracts 19 from 19 and updates the variable so that its value is now <code>0</code>. </p> <p> <pre>Your courage is a tightrope Let it be without it</pre> </p> <p> I had the same problem with initialising the numbers <em>1</em> and <em>2</em>, so further down I resorted to similar tricks: </p> <p> <pre>Raindrop is a wintercrop Light is a misanthrope Let it be without raindrop Darkness is a kaleidoscope Let it be without raindrop </pre> </p> <p> Here I had the additional constraint that I wanted the words to rhyme. The rhymes are a continuation of the previous lines' <code>up</code> and <code>hope</code>, so I struggled to come up with a ten-letter word that rhymes with <code>up</code>; <code>wintercrop</code> was the best I could do. <code>a wintercrop</code> is <em>10</em>, and the strategy is to define <code>Light</code> and <code>Darkness</code> as <em>11</em> and <em>12</em>, and then subtract <em>10</em> from both. At the first occurrence of <code>Let it be without raindrop</code>, <code>it</code> refers to <code>Light</code>, whereas the second time <code>it</code> refers to <code>Darkness</code>. </p> <h3 id="46b60c0d25e54f9599e5bd40b7e88d80"> Lyrical theme <a href="#46b60c0d25e54f9599e5bd40b7e88d80" title="permalink">#</a> </h3> <p> Once I had figured out how to obscure strings and numbers, it was time to rename all the readable variables and function names into idiomatic Rockstar. </p> <p> At first, I thought that I'd pattern my lyrics after <a href="https://en.wikipedia.org/wiki/Shine_On_You_Crazy_Diamond">Shine On You Crazy Diamond</a>, but I soon ran into problems with the keyword <code>taking</code>. I found it difficult to find words that would naturally succeed <code>taking</code>. Some options I thought of were: <ul> <li>taking the bus</li> <li>taking a chance</li> <li>taking hold</li> <li>taking flight</li> <li>taking time</li> </ul> Some of these didn't work for various reasons. In Rockstar <code>times</code> is a keyword, and apparently <code>time</code> is reserved as well. At least, the online interpreter choked on it. </p> <p> <code>Taking a chance</code> sounded <a href="https://en.wikipedia.org/wiki/Take_a_Chance_on_Me">too much like ABBA</a>. <code>Taking hold</code> created the derived problem that I had to initialise and use a variable called <code>hold</code>, and I couldn't make that work. </p> <p> <code>Taking flight</code>, on the other hand, turned out to provide a fertile opening. </p> <p> I soon realised, though, that my choice of words pulled the lyrical theme away from idiomatic Rockstar vocabulary. While I do get the <a href="https://en.wikipedia.org/wiki/Livin%27_on_a_Prayer">Tommy and Gina</a> references, I didn't feel at home in that poetic universe. </p> <p> On the other hand, I thought that the words started to sound like <a href="https://en.wikipedia.org/wiki/Yes_(band)">Yes</a>. I've listened to a lot of Yes. The lyrics are the same kind of lame and vapid as what was taking form in my editor. I decided to go in that direction. </p> <p> Granted, this is no longer idiomatic Rockstar, since it's more <a href="https://en.wikipedia.org/wiki/Progressive_rock">prog rock</a> than <a href="https://en.wikipedia.org/wiki/Glam_metal">hair metal</a>. I invoke creative license. </p> <p> Soon I also conceived of the extra ambition that I wanted the verses to rhyme. Here, it proved fortunate that the form <code>let x be y</code> is interchangeable with the form <code>put y into x</code>. Some words, like <em>darkness</em>, are difficult to rhyme with, so it helps that you can hide them within a <code>put y into x</code> form. </p> <p> Over the hours(!) I worked on this, a theme started to emerge. I'm particularly fond of the repeated motifs like: </p> <p> <pre>Your hope's start'n'stop</pre> </p> <p> which rhymes with <code>up</code>, but then later it appears again as </p> <p> <pre>Your hope's stop'n'start</pre> </p> <p> which rhymes with <code>heart</code>. Both words, by the way, represent the number <em>0</em>, since there's ten letters when you ignore the single quotes. </p> <h3 id="234366a7cb1a4998813719845f3c08d7"> Conclusion <a href="#234366a7cb1a4998813719845f3c08d7" title="permalink">#</a> </h3> <p> I spent more time on this that I suppose I ought to, but once I got started, it was hard to stop. I found the translation from readable code into 'idiomatic' Rockstar at least as difficult as writing working software. There's a lesson there, I believe. </p> <p> Rockstar is still a budding language, so I did miss a few features, chief among which would be <em>arrays</em>, but I'm not sure how one would make arrays sufficiently rock'n'roll. </p> <p> A unit testing framework would also be nice. </p> <p> If you liked this article, please <a href="https://www.linkedin.com/in/ploeh/">endorse my <em>Rockstar</em> skills on LinkedIn</a> so that we can <em>"confuse recruiters."</em> </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/11/11/diamond-rock The 80/24 rule https://blog.ploeh.dk/2019/11/04/the-80-24-rule/ Mon, 04 Nov 2019 06:51:00 UTC <div id="post"> <p> <em>Write small blocks of code. How small? Here's how small.</em> </p> <p> One of the most common questions I get is this: </p> <p> <em>If you could give just one advice to programmers, what would it be?</em> </p> <p> That's easy: </p> <p> <em>Write small blocks of code.</em> </p> <p> Small methods. Small functions. Small procedures. </p> <p> How small? </p> <h3 id="849d07675e3a4c5681641eb0c67dfafb"> Few lines of code <a href="#849d07675e3a4c5681641eb0c67dfafb" title="permalink">#</a> </h3> <p> You can't give a universally good answer to that question. Among other things, it depends on the programming language in question. Some languages are much denser than others. The densest language I've ever encountered is <a href="https://en.wikipedia.org/wiki/APL_(programming_language)">APL</a>. </p> <p> Most mainstream languages, however, seem to be verbose to approximately the same order of magnitude. My experience is mostly with C#, so I'll use that (and similar languages like Java) as a starting point. </p> <p> When I write C# code, I become uncomfortable when my method size approaches fifteen or twenty lines of code. C# is, however, a fairly wordy language, so it sometimes happens that I have to allow a method to grow larger. My limit is probably somewhere around 25 lines of code. </p> <p> That's an arbitrary number, but if I have to quote a number, it would be around that size. Since it's arbitrary anyway, let's make it <em>24</em>, for reasons that I'll explain later. </p> <p> The maximum line count of a C# (or Java, or JavaScript, etc.) method, then, should be 24. </p> <p> To repeat the point from before, this depends on the language. I'd consider a 24-line <a href="https://www.haskell.org">Haskell</a> or <a href="https://fsharp.org">F#</a> function to be so huge that if I received it as a pull request, I'd reject it <a href="/2015/01/15/10-tips-for-better-pull-requests">on the grounds of size</a> alone. </p> <h3 id="8506ebcba585459b9739d84a7bcad758"> Narrow line width <a href="#8506ebcba585459b9739d84a7bcad758" title="permalink">#</a> </h3> <p> Most languages allow for flexibility in layout. For example, C-based languages use the <code>;</code> character as a delimiter. This enables you to write more than one statement per line: </p> <p> <pre><span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">foo</span>&nbsp;=&nbsp;32;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">bar</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">foo</span>&nbsp;+&nbsp;10;&nbsp;<span style="color:#2b91af;">Console</span>.<span style="color:#74531f;">WriteLine</span>(<span style="font-weight:bold;color:#1f377f;">bar</span>);</pre> </p> <p> You could attempt to avoid the 24-line-height rule by writing wide lines. That would, however, be to defeat the purpose. </p> <p> The purpose of writing small methods is to nudge yourself towards writing readable code; code that fits in your brain. The smaller, the better. </p> <p> For completeness sake, let's institute a maximum line width as well. If there's any accepted industry standard for maximum line width, it's 80 characters. I've used that maximum for years, and it's a good maximum. </p> <p> Like all other programmers, other people's code annoys me. The most common annoyance is that people write too wide code. </p> <p> This is probably because most programmers have drunk the Cool Aid that bigger screens make you more productive. When you code on a big screen, you don't notice how wide your lines become. </p> <p> There's many scenarios where wide code is problematic: <ul> <li>When you're comparing changes to a file side-by-side. This often happens when you review pull requests. Now you have only half of your normal screen width.</li> <li>When you're looking at code on a smaller device.</li> <li>When you're getting old, or are otherwise visually impaired. After I turned 40, I discovered that I found it increasingly difficult to see small things. I still use a 10-point font for programming, but I foresee that this will not last much longer.</li> <li>When you're <a href="https://en.wikipedia.org/wiki/Mob_programming">mob programming</a> you're limited to the size of the shared screen.</li> <li>When you're sharing your screen via the web, for remote pair programming or similar.</li> <li>When you're presenting code at meetups, user groups, conferences, etc.</li> </ul> What most programmers need, I think, is just a <a href="https://en.wikipedia.org/wiki/Nudge_theory">nudge</a>. In Visual Studio, for example, you can install the <a href="https://marketplace.visualstudio.com/items?itemName=PaulHarrington.EditorGuidelines">Editor Guidelines</a> extension, which will display one or more vertical guidelines. You can configure it as you'd like, but I've mine set to 80 characters, and bright red: </p> <p> <img src="/content/binary/vertical-guideline-at-80-characters.png" alt="Screen shot of editor with code, showing red vertical line at 80 characters."> </p> <p> Notice the red dotted vertical line that cuts through <code>universe</code>. It tells me where the 80 character limit is. </p> <h3 id="d94a52940215425e9cb19492d9f51a41"> Terminal box <a href="#d94a52940215425e9cb19492d9f51a41" title="permalink">#</a> </h3> <p> The 80-character limit has a long and venerable history, but what about the 24-line limit? While both are, ultimately, arbitrary, both fit the size of the popular <a href="https://en.wikipedia.org/wiki/VT100">VT100</a> terminal, which had a display resolution of 80x24 characters. </p> <p> A box of 80x24 characters thus reproduces the size of an old terminal. Does this mean that I suggest that you should write programs on terminals? No, people always misunderstand this. That should be the maximum size of a method. On larger screens, you'd be able to see multiple small methods at once. For example, you could view a unit test and its target in a split screen configuration. </p> <p> The exact sizes are arbitrary, but I think that there's something fundamentally right about such continuity with the past. </p> <p> I've been using the 80-character mark as a soft limit for years. I tend to stay within it, but I occasionally decide to make my code a little wider. I haven't paid quite as much attention to the number of lines of my methods, but only for the reason that I know that I tend to write methods shorter than that. Both limits have served me well for years. </p> <h3 id="e5301bcefd8f444487906af03df293b0"> Example <a href="#e5301bcefd8f444487906af03df293b0" title="permalink">#</a> </h3> <p> Consider this example: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">ActionResult</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Post</span>(<span style="color:#2b91af;">ReservationDto</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">dto</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">validationMsg</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Validator</span>.<span style="color:#74531f;">Validate</span>(<span style="font-weight:bold;color:#1f377f;">dto</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">if</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">validationMsg</span>&nbsp;!=&nbsp;<span style="color:#a31515;">&quot;&quot;</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#74531f;">BadRequest</span>(<span style="font-weight:bold;color:#1f377f;">validationMsg</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Mapper</span>.<span style="color:#74531f;">Map</span>(<span style="font-weight:bold;color:#1f377f;">dto</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">reservations</span>&nbsp;=&nbsp;Repository.<span style="font-weight:bold;color:#74531f;">ReadReservations</span>(<span style="font-weight:bold;color:#1f377f;">reservation</span>.Date); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">accepted</span>&nbsp;=&nbsp;maîtreD.<span style="font-weight:bold;color:#74531f;">CanAccept</span>(<span style="font-weight:bold;color:#1f377f;">reservations</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">if</span>&nbsp;(!<span style="font-weight:bold;color:#1f377f;">accepted</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#74531f;">StatusCode</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">StatusCodes</span>.Status500InternalServerError, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#a31515;">&quot;Couldn&#39;t&nbsp;accept.&quot;</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">id</span>&nbsp;=&nbsp;Repository.<span style="font-weight:bold;color:#74531f;">Create</span>(<span style="font-weight:bold;color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Ok</span>(<span style="font-weight:bold;color:#1f377f;">id</span>); }</pre> </p> <p> This method is 18 lines long, which includes the method declaration, curly brackets and blank lines. It easily stays within the 80-character limit. Note that I've deliberately formatted the code so that it behaves. You can see it in this fragment: </p> <p> <pre><span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#74531f;">StatusCode</span>( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">StatusCodes</span>.Status500InternalServerError, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#a31515;">&quot;Couldn&#39;t&nbsp;accept.&quot;</span>);</pre> </p> <p> Most people write it like this: </p> <p> <pre><span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#74531f;">StatusCode</span>(<span style="color:#2b91af;">StatusCodes</span>.Status500InternalServerError,&nbsp;<span style="color:#a31515;">&quot;Couldn&#39;t&nbsp;accept.&quot;</span>);</pre> </p> <p> That doesn't look bad, but I've seen much worse examples. </p> <p> Another key to writing small methods is to call other methods. The above <code>Post</code> method doesn't look like much, but significant functionality could be hiding behind <code>Validator.Validate</code>, <code>Repository.ReadReservations</code>, or <code>maîtreD.CanAccept</code>. I hope that you agree that each of these objects and methods are named well enough to give you an idea about their purpose. </p> <h3 id="ca4e5a8403244f93a95c2736cdaf7eee"> Code that fits in your brain <a href="#ca4e5a8403244f93a95c2736cdaf7eee" title="permalink">#</a> </h3> <p> As I describe in my <a href="https://cleancoders.com/episode/humane-code-real-episode-1/show">Humane Code</a> video, the human brain can only keep track of <a href="https://en.wikipedia.org/wiki/The_Magical_Number_Seven,_Plus_or_Minus_Two">about seven things</a>. I think that this rule of thumb applies to the way we read and interpret code. If you need to understand and keep track of more than seven separate things at the same time, the code becomes harder to understand. </p> <p> This could explain why small methods are good. They're only good, however, if they're self-contained. When you look at a method like the above <code>Post</code> method, you'll be most effective if you don't need to have a deep understanding of how each of the dependencies work. If this is true, the method only juggles about five dependencies: <code>Validator</code>, <code>Mapper</code>, <code>Repository</code>, <code>maîtreD</code>, and its own base class (which provides the methods <code>BadRequest</code>, <code>StatusCode</code>, and <code>Ok</code>). Five dependencies is fewer than seven. </p> <p> Another way to evaluate the cognitive load of a method is to measure its <a href="https://en.wikipedia.org/wiki/Cyclomatic_complexity">cyclomatic complexity</a>. The <code>Post</code> method's cyclomatic complexity is <em>3</em>, so that should be easily within the brain's capacity. </p> <p> These are all heuristics, so read this for inspiration, not as law. They've served me well for years, though. </p> <h3 id="1c2120e143784dde8e520026b67651d4"> Conclusion <a href="#1c2120e143784dde8e520026b67651d4" title="permalink">#</a> </h3> <p> You've probably heard about the <em>80/20 rule</em>, also known as the <a href="https://en.wikipedia.org/wiki/Pareto_principle">Pareto principle</a>. Perhaps the title lead you to believe that this article was a misunderstanding. I admit that I went for an arresting title; perhaps a more proper name is the <em>80x24 rule</em>. </p> <p> The exact numbers can vary, but I've found a maximum method size of 80x24 characters to work well for C#. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="cbdf43b5551242efa330a163f01119ca"> <div class="comment-author">Jiehong</div> <div class="comment-content"> <p> As a matter of fact, <em>terminals</em> had 80 characters lines, because <a href="https://en.wikipedia.org/wiki/Punched_card#/media/File:FortranCardPROJ039.agr.jpg">IBM punch cards</a>, representing only 1 line, had 80 symbols (even though only the first 72 were used at first). However, I don't know why terminals settled for 24 lines! In Java, which is similar to C# in term of verbosity, Clean Code tend to push towards 20-lines long functions or less. One of the danger to make functions even smaller is that many more functions can create many indirections, and that becomes harder to keep track within our brains. </p> </div> <div class="comment-date">2019-11-04 11:13 UTC</div> </div> <div class="comment" id="7fc45f8fd537ba9907ad73daa2c85b52"> <div class="comment-author">Terrell</div> <div class="comment-content"> <p> Some additional terminal sizing history in Mike Hoye's recent similarly-named post: <a href="http://exple.tive.org/blarg/2019/10/23/80x25/">http://exple.tive.org/blarg/2019/10/23/80x25/</a> Spoiler - Banknotes! </p> </div> <div class="comment-date">2019-11-04 13:25 UTC</div> </div> </div> <hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/11/04/the-80-24-rule A basic Haskell solution to the robot journeys coding exercise https://blog.ploeh.dk/2019/10/28/a-basic-haskell-solution-to-the-robot-journeys-coding-exercise/ Mon, 28 Oct 2019 04:34:00 UTC <div id="post"> <p> <em>This article shows an idiomatic, yet beginner-friendly Haskell solution to a coding exercise.</em> </p> <p> <a href="https://twitter.com/mikehadlow/status/1186332184086495233">Mike Hadlow tweeted</a> a coding exercise that involves parsing and evaluating instruction sets. <a href="https://www.haskell.org">Haskell</a> excels at such problems, so I decided to give it a go. Since this was only an exercise for the fun of it, I didn't want to set up a complete Haskell project. Rather, I wanted to write one or two <code>.hs</code> files that I could interact with via <em>GHCi</em>. This means no lenses, monad transformers, or other fancy libraries. </p> <p> Hopefully, this makes the code friendly to Haskell beginners. It shows what I consider <a href="/2015/08/03/idiomatic-or-idiosyncratic">idiomatic</a>, but basic Haskell, solving a problem of moderate difficulty. </p> <h3 id="79b308125b2d4bcc9df79f7c6569a6e9"> The problem <a href="#79b308125b2d4bcc9df79f7c6569a6e9" title="permalink">#</a> </h3> <p> <a href="https://github.com/mikehadlow/Journeys">Mike Hadlow has a detailed description of the exercise</a>, but in short, you're given a file with a set of instructions that look like this: </p> <p> <pre>1 1 E RFRFRFRF 1 1 E</pre> </p> <p> The first and last lines describe the position and orientation of a robot. The first line, for example, describes a robot at position (1, 1) facing east. A robot can face in one of the four normal directions of the map: north, east, south, and west. </p> <p> The first line gives the robot's start position, and the last line the <em>expected</em> end position. </p> <p> The middle line is a set of instructions to the robot. It can turn left or right, or move forward. </p> <p> The exercise is to evaluate whether journeys are valid; that is, whether the robot's end position matches the expected end position if it follows the commands. </p> <h3 id="cf43d781d49545c38e30f487867e904f"> Imports <a href="#cf43d781d49545c38e30f487867e904f" title="permalink">#</a> </h3> <p> I managed to solve the exercise with a single <code>Main.hs</code> file. Here's the module declaration and the required imports: </p> <p> <pre><span style="color:blue;">module</span>&nbsp;Main&nbsp;<span style="color:blue;">where</span> <span style="color:blue;">import</span>&nbsp;Data.Foldable <span style="color:blue;">import</span>&nbsp;Data.Ord <span style="color:blue;">import</span>&nbsp;Text.Read&nbsp;(<span style="color:#2b91af;">readPrec</span>) <span style="color:blue;">import</span>&nbsp;Text.ParserCombinators.ReadP <span style="color:blue;">import</span>&nbsp;Text.ParserCombinators.ReadPrec&nbsp;(<span style="color:#2b91af;">readPrec_to_P</span>,&nbsp;<span style="color:#2b91af;">minPrec</span>)</pre> </p> <p> These imports are only required to support parsing of input. Once parsed, you can evaluate each journey using nothing but the functions available in the standard <code>Prelude</code>. </p> <h3 id="8329bba327f54dbfb8474f9102ba8662"> Types <a href="#8329bba327f54dbfb8474f9102ba8662" title="permalink">#</a> </h3> <p> Haskell is a statically typed language, so it often pays to define some types. Granted, the exercise hardly warrants all of these types, but as an example of idiomatic Haskell, I think that this is still good practice. After all, Haskell types are easy to declare. Often, they are one-liners: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;Direction&nbsp;=&nbsp;North&nbsp;|&nbsp;East&nbsp;|&nbsp;South&nbsp;|&nbsp;West&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> The <code>Direction</code> type enumerates the four corners of the world. </p> <p> <pre><span style="color:blue;">data</span>&nbsp;Robot&nbsp;=&nbsp;Robot&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;robotPosition&nbsp;::&nbsp;(Integer,&nbsp;Integer) &nbsp;&nbsp;,&nbsp;robotDirection&nbsp;::&nbsp;Direction&nbsp;} &nbsp;&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> The <code>Robot</code> record type represents the state of a robot: its position and the direction it faces. </p> <p> You'll also need to enumerate the commands that you can give a robot: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;Command&nbsp;=&nbsp;TurnLeft&nbsp;|&nbsp;TurnRight&nbsp;|&nbsp;MoveForward&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> Finally, you can also define a type for a <code>Journey</code>: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;Journey&nbsp;=&nbsp;Journey&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;journeyStart&nbsp;::&nbsp;Robot &nbsp;&nbsp;,&nbsp;journeyCommands&nbsp;::&nbsp;[Command] &nbsp;&nbsp;,&nbsp;journeyEnd&nbsp;::&nbsp;Robot&nbsp;} &nbsp;&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> These are all the types required for solving the exercise. </p> <h3 id="5ada3f24aa4e4858892855ae076f457b"> Parsing <a href="#5ada3f24aa4e4858892855ae076f457b" title="permalink">#</a> </h3> <p> The format of the input file is simple enough that it could be done in an ad-hoc fashion using <code>lines</code>, <code>word</code>, <code>read</code>, and a few other low-level functions. While the format barely warrants the use of parser combinators, I'll still use some to showcase the power of that approach. </p> <p> Since one of my goals is to implement the functionality using a single <code>.hs</code> file, I can't pull in external parser combinator libraries. Instead, I'll use the built-in <code>ReadP</code> module, which I've often found sufficient to parse files like the present exercise input file. </p> <p> First, you're going to have to be able to parse numbers, which can be done using the <code>Read</code> type class. You'll need, however, to be able to compose <code>Integer</code> parsers with other <code>ReadP</code> parsers. </p> <p> <pre><span style="color:#2b91af;">parseRead</span>&nbsp;::&nbsp;<span style="color:blue;">Read</span>&nbsp;a&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;<span style="color:blue;">ReadP</span>&nbsp;a parseRead&nbsp;=&nbsp;readPrec_to_P&nbsp;readPrec&nbsp;minPrec</pre> </p> <p> This turns every <code>Read</code> instance value into a <code>ReadP</code> value. (I admit that I wasn't sure which precedence number to use, but <code>minPrec</code> seems to work.) </p> <p> Next, you need a parser for <code>Direction</code> values: </p> <p> <pre><span style="color:#2b91af;">parseDirection</span>&nbsp;::&nbsp;<span style="color:blue;">ReadP</span>&nbsp;<span style="color:blue;">Direction</span> parseDirection&nbsp;= &nbsp;&nbsp;choice&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;char&nbsp;<span style="color:#a31515;">&#39;N&#39;</span>&nbsp;&gt;&gt;&nbsp;<span style="color:blue;">return</span>&nbsp;North, &nbsp;&nbsp;&nbsp;&nbsp;char&nbsp;<span style="color:#a31515;">&#39;E&#39;</span>&nbsp;&gt;&gt;&nbsp;<span style="color:blue;">return</span>&nbsp;East, &nbsp;&nbsp;&nbsp;&nbsp;char&nbsp;<span style="color:#a31515;">&#39;S&#39;</span>&nbsp;&gt;&gt;&nbsp;<span style="color:blue;">return</span>&nbsp;South, &nbsp;&nbsp;&nbsp;&nbsp;char&nbsp;<span style="color:#a31515;">&#39;W&#39;</span>&nbsp;&gt;&gt;&nbsp;<span style="color:blue;">return</span>&nbsp;West&nbsp;]</pre> </p> <p> Notice how declarative this looks. The <code>choice</code> function combines a list of other parsers. When an individual parser in that list encounters the <code>'N'</code> character, it'll parse it as <code>North</code>, <code>'E'</code> as <code>East</code>, and so on. </p> <p> You can now parse an entire <code>Robot</code> using the <code>Applicative</code> <code>&lt;*&gt;</code> and <code>&lt;*</code> operators. </p> <p> <pre><span style="color:#2b91af;">parseRobot</span>&nbsp;::&nbsp;<span style="color:blue;">ReadP</span>&nbsp;<span style="color:blue;">Robot</span> parseRobot&nbsp;= &nbsp;&nbsp;(\x&nbsp;y&nbsp;d&nbsp;-&gt;&nbsp;Robot&nbsp;(x,&nbsp;y)&nbsp;d)&nbsp;&lt;$&gt; &nbsp;&nbsp;(parseRead&nbsp;&lt;*&nbsp;char&nbsp;<span style="color:#a31515;">&#39;&nbsp;&#39;</span>)&nbsp;&lt;*&gt; &nbsp;&nbsp;(parseRead&nbsp;&lt;*&nbsp;char&nbsp;<span style="color:#a31515;">&#39;&nbsp;&#39;</span>)&nbsp;&lt;*&gt; &nbsp;&nbsp;&nbsp;parseDirection</pre> </p> <p> The <code>&lt;*&gt;</code> operator combines two parsers by using the output of both of them, whereas the <code>&lt;*</code> combines two parsers by running both of them, but discarding the output of the right-hand parser. A good mnemonic is that the operator points to the parser that produces an output. Here', the <code>parseRobot</code> function uses the <code>&lt;*</code> operator to require that each number is followed by a space. The space, however, is just a delimiter, so you throw it away. </p> <p> <code>parseRead</code> parses any <code>Read</code> instance. Here, the <code>parseRobot</code> function uses it to parse each <code>Integer</code> in a robot's position. It also uses <code>parseDirection</code> to parse the robot's direction. </p> <p> Similar to how you can parse directions, you can also parse the commands: </p> <p> <pre><span style="color:#2b91af;">parseCommand</span>&nbsp;::&nbsp;<span style="color:blue;">ReadP</span>&nbsp;<span style="color:blue;">Command</span> parseCommand&nbsp;= &nbsp;&nbsp;choice&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;char&nbsp;<span style="color:#a31515;">&#39;L&#39;</span>&nbsp;&gt;&gt;&nbsp;<span style="color:blue;">return</span>&nbsp;TurnLeft, &nbsp;&nbsp;&nbsp;&nbsp;char&nbsp;<span style="color:#a31515;">&#39;R&#39;</span>&nbsp;&gt;&gt;&nbsp;<span style="color:blue;">return</span>&nbsp;TurnRight, &nbsp;&nbsp;&nbsp;&nbsp;char&nbsp;<span style="color:#a31515;">&#39;F&#39;</span>&nbsp;&gt;&gt;&nbsp;<span style="color:blue;">return</span>&nbsp;MoveForward]</pre> </p> <p> Likewise, similar to how you parse a single robot, you can now parse a journey: </p> <p> <pre><span style="color:#2b91af;">parseJourney</span>&nbsp;::&nbsp;<span style="color:blue;">ReadP</span>&nbsp;<span style="color:blue;">Journey</span> parseJourney&nbsp;= &nbsp;&nbsp;Journey&nbsp;&lt;$&gt; &nbsp;&nbsp;(parseRobot&nbsp;&lt;*&nbsp;string&nbsp;<span style="color:#a31515;">&quot;\n&quot;</span>)&nbsp;&lt;*&gt; &nbsp;&nbsp;(many&nbsp;parseCommand&nbsp;&lt;*&nbsp;string&nbsp;<span style="color:#a31515;">&quot;\n&quot;</span>)&nbsp;&lt;*&gt; &nbsp;&nbsp;&nbsp;parseRobot</pre> </p> <p> The only new element compared to <code>parseRobot</code> is the use of the <code>many</code> parser combinator, which looks for zero, one, or many <code>Command</code> values. </p> <p> This gives you a way to parse a complete journey, but the input file contains many of those, separated by newlines and other whitespace: </p> <p> <pre><span style="color:#2b91af;">parseJourneys</span>&nbsp;::&nbsp;<span style="color:blue;">ReadP</span>&nbsp;[<span style="color:blue;">Journey</span>] parseJourneys&nbsp;=&nbsp;parseJourney&nbsp;`sepBy`&nbsp;skipSpaces</pre> </p> <p> Finally, you can parse a multi-line string into a list of journeys: </p> <p> <pre><span style="color:#2b91af;">parseInput</span>&nbsp;::&nbsp;<span style="color:#2b91af;">String</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;[<span style="color:blue;">Journey</span>] parseInput&nbsp;=&nbsp;<span style="color:blue;">fst</span>&nbsp;.&nbsp;minimumBy&nbsp;(comparing&nbsp;<span style="color:blue;">snd</span>)&nbsp;.&nbsp;readP_to_S&nbsp;parseJourneys</pre> </p> <p> When you run <code>readP_to_S</code>, it'll produce a list of alternatives, as there's more than one way to interpret the file according to <code>parseJourneys</code>. Each alternative is presented as a tuple of the parse result and the remaining (or unconsumed) string. I'm after the alternative that consumes as much of the input file as possible (which turns out to be all of it), so I use <code>minimumBy</code> to find the tuple that has the smallest second element. Then I return the first element of that tuple. </p> <p> Play around with <code>readP_to_S parseJourneys</code> in GHCi if you want all the details. </p> <h3 id="34135daae9634db2885e28382760d1fd"> Evaluation <a href="#34135daae9634db2885e28382760d1fd" title="permalink">#</a> </h3> <p> Haskell beginners may still find operators like <code>&lt;*&gt;</code> cryptic, but they're essential to parser combinators. Evaluation of the journeys is, in comparison, simple. </p> <p> You can start by defining a function to turn right: </p> <p> <pre><span style="color:#2b91af;">turnRight</span>&nbsp;::&nbsp;<span style="color:blue;">Robot</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Robot</span> turnRight&nbsp;r@(Robot&nbsp;_&nbsp;North)&nbsp;=&nbsp;r&nbsp;{&nbsp;robotDirection&nbsp;=&nbsp;East&nbsp;} turnRight&nbsp;r@(Robot&nbsp;_&nbsp;&nbsp;East)&nbsp;=&nbsp;r&nbsp;{&nbsp;robotDirection&nbsp;=&nbsp;South&nbsp;} turnRight&nbsp;r@(Robot&nbsp;_&nbsp;South)&nbsp;=&nbsp;r&nbsp;{&nbsp;robotDirection&nbsp;=&nbsp;West&nbsp;} turnRight&nbsp;r@(Robot&nbsp;_&nbsp;&nbsp;West)&nbsp;=&nbsp;r&nbsp;{&nbsp;robotDirection&nbsp;=&nbsp;North&nbsp;}</pre> </p> <p> There's more than one way to write a function that rotates one direction to the right, but I chose one that I found most readable. It trades clarity for verbosity by relying on simple pattern matching. I hope that it's easy to understand for Haskell beginners, and perhaps even for people who haven't seen Haskell code before. </p> <p> The function to turn left uses the same structure: </p> <p> <pre><span style="color:#2b91af;">turnLeft</span>&nbsp;::&nbsp;<span style="color:blue;">Robot</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Robot</span> turnLeft&nbsp;r@(Robot&nbsp;_&nbsp;North)&nbsp;=&nbsp;r&nbsp;{&nbsp;robotDirection&nbsp;=&nbsp;West&nbsp;} turnLeft&nbsp;r@(Robot&nbsp;_&nbsp;&nbsp;West)&nbsp;=&nbsp;r&nbsp;{&nbsp;robotDirection&nbsp;=&nbsp;South&nbsp;} turnLeft&nbsp;r@(Robot&nbsp;_&nbsp;South)&nbsp;=&nbsp;r&nbsp;{&nbsp;robotDirection&nbsp;=&nbsp;East&nbsp;} turnLeft&nbsp;r@(Robot&nbsp;_&nbsp;&nbsp;East)&nbsp;=&nbsp;r&nbsp;{&nbsp;robotDirection&nbsp;=&nbsp;North&nbsp;}</pre> </p> <p> The last command you need to implement is moving forward: </p> <p> <pre><span style="color:#2b91af;">moveForward</span>&nbsp;::&nbsp;<span style="color:blue;">Robot</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Robot</span> moveForward&nbsp;(Robot&nbsp;(x,&nbsp;y)&nbsp;North)&nbsp;=&nbsp;Robot&nbsp;(x,&nbsp;y&nbsp;+&nbsp;1)&nbsp;North moveForward&nbsp;(Robot&nbsp;(x,&nbsp;y)&nbsp;&nbsp;East)&nbsp;=&nbsp;Robot&nbsp;(x&nbsp;+&nbsp;1,&nbsp;y)&nbsp;East moveForward&nbsp;(Robot&nbsp;(x,&nbsp;y)&nbsp;South)&nbsp;=&nbsp;Robot&nbsp;(x,&nbsp;y&nbsp;-&nbsp;1)&nbsp;South moveForward&nbsp;(Robot&nbsp;(x,&nbsp;y)&nbsp;&nbsp;West)&nbsp;=&nbsp;Robot&nbsp;(x&nbsp;-&nbsp;1,&nbsp;y)&nbsp;West</pre> </p> <p> The <code>moveForward</code> function also pattern-matches on the direction the robot is facing, this time to increment or decrement the <code>x</code> or <code>y</code> coordinate as appropriate. </p> <p> You can now evaluate all three commands: </p> <p> <pre><span style="color:#2b91af;">evalCommand</span>&nbsp;::&nbsp;<span style="color:blue;">Command</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Robot</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Robot</span> evalCommand&nbsp;&nbsp;&nbsp;TurnRight&nbsp;=&nbsp;turnRight evalCommand&nbsp;&nbsp;&nbsp;&nbsp;TurnLeft&nbsp;=&nbsp;turnLeft evalCommand&nbsp;MoveForward&nbsp;=&nbsp;moveForward</pre> </p> <p> The <code>evalCommand</code> pattern-matches on all three <code>Command</code> cases and returns the appropriate function for each. </p> <p> You can now evaluate whether a <code>Journey</code> is valid: </p> <p> <pre><span style="color:#2b91af;">isJourneyValid</span>&nbsp;::&nbsp;<span style="color:blue;">Journey</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Bool</span> isJourneyValid&nbsp;(Journey&nbsp;s&nbsp;cs&nbsp;e)&nbsp;=&nbsp;<span style="color:blue;">foldl</span>&nbsp;(<span style="color:blue;">flip</span>&nbsp;evalCommand)&nbsp;s&nbsp;cs&nbsp;==&nbsp;e</pre> </p> <p> The <code>isJourneyValid</code> function pattern-matches the constituent values out of <code>Journey</code>. I named the <code>journeyStart</code> value <code>s</code> (for <em>start</em>), the <code>journeyCommands</code> value <code>cs</code> (for <em>commands</em>), and the <code>journeyEnd</code> value <code>e</code> (for <em>end</em>). </p> <p> The <code>evalCommand</code> function evaluates a single <code>Command</code>, but a <code>Journey</code> contains many commands. You'll need to evaluate the first command to find the position from which you evaluate the second command, and so on. Imperative programmers would use a <em>for loop</em> for something like that, but in functional programming, a <em>fold</em>, in this case from the left, is how it's done. </p> <p> <code>foldl</code> requires you to supply an initial state <code>s</code> as well as the list of commands <code>cs</code>. The entire <code>foldl</code> expression produces a final <code>Robot</code> state that you can compare against the expected end state <code>e</code>. </p> <h3 id="6267cc3a03594d0fb21cd7cc61430eb0"> Execution <a href="#6267cc3a03594d0fb21cd7cc61430eb0" title="permalink">#</a> </h3> <p> Load the input file, parse it, and evaluate each journey in the <code>main</code> function: </p> <p> <pre><span style="color:#2b91af;">main</span>&nbsp;::&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;() main&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;input&nbsp;&lt;-&nbsp;parseInput&nbsp;&lt;$&gt;&nbsp;<span style="color:blue;">readFile</span>&nbsp;<span style="color:#a31515;">&quot;input.txt&quot;</span> &nbsp;&nbsp;<span style="color:blue;">mapM_</span>&nbsp;<span style="color:blue;">print</span>&nbsp;$&nbsp;isJourneyValid&nbsp;&lt;$&gt;&nbsp;input</pre> </p> <p> I just load the <code>Main.hs</code> file in GHCi and run the <code>main</code> function: </p> <p> <pre>Prelude&gt; :load Main.hs [1 of 1] Compiling Main ( Main.hs, interpreted ) Ok, one module loaded. *Main&gt; main True True True</pre> </p> <p> I used the same input file as Mike Hadlow, and it turns out that all journeys are valid. That's not what I'd expected from an exercise like this, so I cloned and ran Mike's solution as well, and it seems that it arrives at the same result. </p> <h3 id="683ea9809a774338b16aed1ad41e1984"> Conclusion <a href="#683ea9809a774338b16aed1ad41e1984" title="permalink">#</a> </h3> <p> Haskell is a great language for small coding exercises that require parsing and interpretation. In this article, I demonstrated one solution to the <em>robot journeys</em> coding exercise. My goal was to show some beginner-friendly, but still idiomatic Haskell code. </p> <p> Granted, the use of parser combinators is on the verge of being overkill, but I wanted to show an example; Haskell examples are scarce, so I hope it's helpful. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/10/28/a-basic-haskell-solution-to-the-robot-journeys-coding-exercise A red-green-refactor checklist https://blog.ploeh.dk/2019/10/21/a-red-green-refactor-checklist/ Mon, 21 Oct 2019 06:49:00 UTC <div id="post"> <p> <em>A simple read-do checklist for test-driven development.</em> </p> <p> I recently read <a href="https://amzn.to/35Wk5yD">The Checklist Manifesto</a>, a book about the power of checklists. That may sound off-putting and tedious, but I actually <a href="https://www.goodreads.com/review/show/2949987528">found it inspiring</a>. It explains how checklists empower skilled professionals to focus on difficult problems, while preventing avoidable mistakes. </p> <p> Since I read the book with the intent to see if there were ideas that we could apply in software development, I thought about checklists one might create for software development. Possibly the simplest checklist is one that describes the <em>red-green-refactor</em> cycle of test-driven development. </p> <h3 id="530e04dfea574602952023fa218d8a7c"> Types of checklists <a href="#530e04dfea574602952023fa218d8a7c" title="permalink">#</a> </h3> <p> As the book describes, there's basically two types of checklists: <ul> <li><strong>Do-confirm.</strong> With such a checklist, you perform a set of tasks, and then subsequently, at a sufficient <em>pause point</em> go through the checklist to verify that you remembered to perform all the tasks on the list.</li> <li><strong>Read-do.</strong> With this type of checklist, you read each item for instructions and then perform the task. Only when you've performed the task do you move on to the next item on the list.</li> </ul> I find it most intuitive to describe the red-green-refactor cycle as a <em>read-do</em> list. I did, however, find it expedient to include a <em>do-confirm</em> sub-list for one of the overall steps. </p> <p> This list is, I think, mostly useful if you're still learning test-driven development. It can be easily internalised. As such, I offer this for inspiration, and as a learning aid. </p> <h3 id="05b38ebc9c0c419b9a146be976578bd2"> Red-green-refactor checklist <a href="#05b38ebc9c0c419b9a146be976578bd2" title="permalink">#</a> </h3> <p> Read each of the steps in the list and perform the task. <ol> <li>Write a failing test. <ul> <li>Did you run the test?</li> <li>Did it fail?</li> <li>Did it fail because of an assertion?</li> <li>Did it fail because of the <em>last</em> assertion?</li> </ul> </li> <li>Make all tests pass by doing the simplest thing that could possibly work.</li> <li>Consider the resulting code. Can it be improved? If so, do it, but make sure that all tests still pass.</li> <li>Repeat</li> </ol> Perhaps the most value this checklist provides isn't so much the overall <em>read-do</em> list, but rather the subordinate <em>do-confirm</em> list associated with the first step. </p> <p> I regularly see people write failing tests as an initial step. The reason the test fails, however, is because the implementation throws an exception. </p> <h3 id="24a066fa0b9b401687d47b92473d63d0"> Improperly failing tests <a href="#24a066fa0b9b401687d47b92473d63d0" title="permalink">#</a> </h3> <p> Consider, as an example, the first test you might write when doing the <a href="https://en.wikipedia.org/wiki/Fizz_buzz">FizzBuzz</a> kata. </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">One</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#2b91af;">FizzBuzz</span>.<span style="color:#74531f;">Convert</span>(1); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Equal</span>(<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> I wrote this test first (i.e. before the 'production' code) and used Visual Studio's refactoring tools to generate the implied type and method. </p> <p> When I run the test, it fails. </p> <p> Further investigation, however, reveals that the test fails when <code>Convert</code> is called: </p> <p> <pre>Ploeh.Katas.FizzBuzzKata.FizzBuzzTests.One Source: FizzBuzzTests.cs line: 11 Duration: 8 ms Message: System.NotImplementedException : The method or operation is not implemented. Stack Trace: at FizzBuzz.Convert(Int32 i) in FizzBuzz.cs line: 9 at FizzBuzzTests.One() in FizzBuzzTests.cs line: 13 </pre> </p> <p> This is hardly surprising, since this is the current 'implementation': </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">string</span>&nbsp;<span style="color:#74531f;">Convert</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">i</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">throw</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">NotImplementedException</span>(); }</pre> </p> <p> This is what the subordinate <em>do-confirm</em> checklist is for. Did the test fail because of an assertion? In this case, the answer is no. </p> <p> This means that you're not yet done with the <em>read</em> phase. </p> <h3 id="97295029364d4cd7ace15be9c9f8dc64"> Properly failing tests <a href="#97295029364d4cd7ace15be9c9f8dc64" title="permalink">#</a> </h3> <p> You can address the issue by changing the <code>Convert</code> method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">string</span>&nbsp;<span style="color:#74531f;">Convert</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">i</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:#a31515;">&quot;&quot;</span>; }</pre> </p> <p> This causes the test to fail because of an assertion: </p> <p> <pre> Ploeh.Katas.FizzBuzzKata.FizzBuzzTests.One Source: FizzBuzzTests.cs line: 11 Duration: 13 ms Message: Assert.Equal() Failure ↓ (pos 0) Expected: 1 Actual: ↑ (pos 0) Stack Trace: at FizzBuzzTests.One() in FizzBuzzTests.cs line: 14 </pre> </p> <p> Not only does the test fail because of an assertion - it fails because of the last assertion (since there's only one assertion). This completes the <em>do-confirm</em> checklist, and you're now ready to make the simplest change that could possibly work: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">string</span>&nbsp;<span style="color:#74531f;">Convert</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">i</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>; }</pre> </p> <p> This passes the test suite. </p> <h3 id="bdb785a78ebf475c95c64197274268c7"> Conclusion <a href="#bdb785a78ebf475c95c64197274268c7" title="permalink">#</a> </h3> <p> It's important to see tests fail. Particularly, it's important to see tests fail for the reason you expect them to fail. You'd be surprised how often you inadvertently write an <a href="/2019/10/14/tautological-assertion">assertion that can never fail</a>. </p> <p> Once you've seen the test fail for the proper reason, make it pass. </p> <p> Finally, refactor the code if necessary. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="99be0da15a164d5782afdef808300828"> <div class="comment-author">Tyson Williams</div> <div class="comment-content"> <p> I remember the first time that I realized that I did the red step wrong because my test didn't fail for the intended reason (i.e. it didn't fail because of an assertion). Before that, I didn't realize that I needed to This is a nice programming checklist. Thanks for sharing it :) </p> <blockquote> 3. Consider the resulting code. Can it be improved? If so, do it, but make sure that all tests still pass. </blockquote> <blockquote> Finally, refactor the code if necessary. </blockquote> <p> If I can be a <a href="https://blog.ploeh.dk/2019/10/07/devils-advocate/">Devil's advocate</a> for a moment, then I would say that code can always be improved and few things are necessary. In all honesty though, I think the refactoring step is the most interesting. All three steps include aspects of science and art, but I think the refactor step includes the most of both. On the one hand, it is extremely creative and full of judgement calls about what code should be refactored and what properties the resulting code should have. On the other hand, much of the work of how to (properly) refactor is laid out in books like <a href="https://www.amazon.com/Refactoring-Improving-Existing-Addison-Wesley-Signature/dp/0134757599">Martin Fowler's Refacoring</a> and is akin to algebraic manipulations of an algebraic formula. </p> <p> In other words, I feel like there is room to expand on this checklist in the refactor step. Do you have any thoughts about you might expand it? </p> </div> <div class="comment-date">2019-10-25 00:33 UTC</div> </div> <div class="comment" id="28976782c7984115a65d539eff3d0414"> <div class="comment-author"><a href="/">Mark Seemann</a></div> <div class="comment-content"> <p> Tyson, thank you for writing. I agree that the <em>refactoring</em> step is both important and compelling. I can't, however, imagine how a checklist would be useful. </p> <p> The point of <em>The Checklist Manifesto</em> is that checklists help identify avoidable mistakes. A checklist isn't intended to describe an algorithm, but rather to make sure that crucial steps aren't forgotten. </p> <p> Another important point from <em>The Checklist Manifesto</em> is that a checklist is only effective if it's not too big. A checklist that tries to cover every eventuality isn't useful, because then people don't follow it. </p> <p> As you write, refactoring is a big topic, covered by several books. All the creativity and experience that goes into refactoring doesn't seem like something that can easily be expressed as an effective checklist. </p> <p> I don't mind being proven wrong, though, so by all means give it a go. </p> </div> <div class="comment-date">2019-10-25 21:51 UTC</div> </div> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/10/21/a-red-green-refactor-checklist Tautological assertion https://blog.ploeh.dk/2019/10/14/tautological-assertion/ Mon, 14 Oct 2019 18:39:00 UTC <div id="post"> <p> <em>It's surprisingly easy to write a unit test assertion that never fails.</em> </p> <p> Recently I was mob programming with a pair of <a href="https://idq.dk">IDQ</a>'s programmers. We were starting a new code base, using test-driven development (TDD). This was the first test we wrote: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">async</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;<span style="font-weight:bold;color:#74531f;">HandleObserveUnitStatusStartsSaga</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">subscribers</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">List</span>&lt;<span style="color:#2b91af;">Guid</span>&gt;&nbsp;{&nbsp;<span style="color:#2b91af;">Guid</span>.<span style="color:#74531f;">Parse</span>(<span style="color:#a31515;">&quot;{4D093799-9CCC-4135-8CB3-8661985A5853}&quot;</span>)&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">StatusPolicy</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Data&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">StatusPolicyData</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;UnitId&nbsp;=&nbsp;123, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Subscribers&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">subscribers</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">subscriber</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Guid</span>.<span style="color:#74531f;">Parse</span>(<span style="color:#a31515;">&quot;{003C5527-7747-4C7A-980E-67040DB738C3}&quot;</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">message</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ObserveUnitStatus</span>(123,&nbsp;<span style="font-weight:bold;color:#1f377f;">subscriber</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">context</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">TestableMessageHandlerContext</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">await</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">sut</span>.<span style="font-weight:bold;color:#74531f;">Handle</span>(<span style="font-weight:bold;color:#1f377f;">message</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">context</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Contains</span>(<span style="font-weight:bold;color:#1f377f;">subscriber</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">sut</span>.Data.Subscribers); }</pre> </p> <p> This unit test uses <a href="https://xunit.net">xUnit.net</a> 2.4.0 and <a href="https://particular.net/nservicebus">NServiceBus</a> 7.1.10 on .NET Core 2.2. The System Under Test (SUT) is intended to be an NServiceBus Saga that monitors a resource for status changes. If a <em>unit</em> changes status, the Saga will alert its subscribers. </p> <p> The test verifies that when a new subscriber wishes to observe a unit, then its ID is added to the policy's list of subscribers. </p> <p> The test induced us to implement <code>Handle</code> like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Handle</span>(<span style="color:#2b91af;">ObserveUnitStatus</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">message</span>,&nbsp;<span style="color:#2b91af;">IMessageHandlerContext</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">context</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Data.Subscribers.<span style="font-weight:bold;color:#74531f;">Add</span>(<span style="font-weight:bold;color:#1f377f;">message</span>.SubscriberId); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#2b91af;">Task</span>.CompletedTask; }</pre> </p> <p> Following the <em>red-green-refactor</em> cycle of TDD, this seemed an appropriate implementation. </p> <h3 id="8182b3c72b2940b98195f41b7a1193e8"> Enter the Devil <a href="#8182b3c72b2940b98195f41b7a1193e8" title="permalink">#</a> </h3> <p> I often use the <a href="/2019/10/07/devils-advocate">Devil's advocate</a> technique to figure out what to do next, so I made this change to the <code>Handle</code> method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Handle</span>(<span style="color:#2b91af;">ObserveUnitStatus</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">message</span>,&nbsp;<span style="color:#2b91af;">IMessageHandlerContext</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">context</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Data.Subscribers.<span style="font-weight:bold;color:#74531f;">Clear</span>(); &nbsp;&nbsp;&nbsp;&nbsp;Data.Subscribers.<span style="font-weight:bold;color:#74531f;">Add</span>(<span style="font-weight:bold;color:#1f377f;">message</span>.SubscriberId); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#2b91af;">Task</span>.CompletedTask; }</pre> </p> <p> The change is that the method first deletes all existing subscribers. This is obviously wrong, but it passes all tests. That's no surprise, since I intentionally introduced the change to make us improve the test. </p> <h3 id="55331957e1de4691bb182c2aae614f4e"> False negative <a href="#55331957e1de4691bb182c2aae614f4e" title="permalink">#</a> </h3> <p> We had to write a new test, or improve the existing test, so that the defect I just introduced would be caught. I suggested an improvement to the existing test: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">async</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;<span style="font-weight:bold;color:#74531f;">HandleObserveUnitStatusStartsSaga</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">subscribers</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">List</span>&lt;<span style="color:#2b91af;">Guid</span>&gt;&nbsp;{&nbsp;<span style="color:#2b91af;">Guid</span>.<span style="color:#74531f;">Parse</span>(<span style="color:#a31515;">&quot;{4D093799-9CCC-4135-8CB3-8661985A5853}&quot;</span>)&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">StatusPolicy</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Data&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">StatusPolicyData</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;UnitId&nbsp;=&nbsp;123, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Subscribers&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">subscribers</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">subscriber</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Guid</span>.<span style="color:#74531f;">Parse</span>(<span style="color:#a31515;">&quot;{003C5527-7747-4C7A-980E-67040DB738C3}&quot;</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">message</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ObserveUnitStatus</span>(123,&nbsp;<span style="font-weight:bold;color:#1f377f;">subscriber</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">context</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">TestableMessageHandlerContext</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">await</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">sut</span>.<span style="font-weight:bold;color:#74531f;">Handle</span>(<span style="font-weight:bold;color:#1f377f;">message</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">context</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Contains</span>(<span style="font-weight:bold;color:#1f377f;">subscriber</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">sut</span>.Data.Subscribers); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Superset</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">expectedSubset</span>:&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HashSet</span>&lt;<span style="color:#2b91af;">Guid</span>&gt;(<span style="font-weight:bold;color:#1f377f;">subscribers</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>:&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HashSet</span>&lt;<span style="color:#2b91af;">Guid</span>&gt;(<span style="font-weight:bold;color:#1f377f;">sut</span>.Data.Subscribers)); }</pre> </p> <p> The only change is the addition of the last assertion. </p> <p> Smugly I asked the keyboard driver to run the tests, anticipating that it would now fail. </p> <p> It passed. </p> <p> We'd just managed to write a <a href="http://xunitpatterns.com/false%20negative.html">false negative</a>. Even though there's a defect in the code, the test still passes. I was nonplussed. None of us expected the test to pass, yet it does. </p> <p> It took us a minute to figure out what was wrong. Before you read on, try to figure it out for yourself. Perhaps it's immediately clear to you, but it took three people with decades of programming experience a few minutes to spot the problem. </p> <h3 id="6f985240963a40d8af913e251b3b86bf"> Aliasing <a href="#6f985240963a40d8af913e251b3b86bf" title="permalink">#</a> </h3> <p> The problem is <a href="https://en.wikipedia.org/wiki/Aliasing_(computing)">aliasing</a>. While named differently, <code>subscribers</code> and <code>sut.Data.Subscribers</code> is the same object. Of course one is a subset of the other, since a set is considered to be a subset of itself. </p> <p> The assertion is tautological. It can never fail. </p> <h3 id="9e8ec91f731e4f67aceefbebb76799d4"> Fixing the problem <a href="#9e8ec91f731e4f67aceefbebb76799d4" title="permalink">#</a> </h3> <p> It's surprisingly easy to write tautological assertions when working with mutable state. This regularly happens to me, perhaps a few times a month. Once you've realised that this has happened, however, it's easy to address. </p> <p> <code>subscribers</code> shouldn't change during the test, so make it immutable. </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">async</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;<span style="font-weight:bold;color:#74531f;">HandleObserveUnitStatusStartsSaga</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Guid</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">subscribers</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#2b91af;">Guid</span>.<span style="color:#74531f;">Parse</span>(<span style="color:#a31515;">&quot;{4D093799-9CCC-4135-8CB3-8661985A5853}&quot;</span>)&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">StatusPolicy</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Data&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">StatusPolicyData</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;UnitId&nbsp;=&nbsp;123, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Subscribers&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">subscribers</span>.<span style="font-weight:bold;color:#74531f;">ToList</span>() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">subscriber</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Guid</span>.<span style="color:#74531f;">Parse</span>(<span style="color:#a31515;">&quot;{003C5527-7747-4C7A-980E-67040DB738C3}&quot;</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">message</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ObserveUnitStatus</span>(123,&nbsp;<span style="font-weight:bold;color:#1f377f;">subscriber</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">context</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">TestableMessageHandlerContext</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">await</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">sut</span>.<span style="font-weight:bold;color:#74531f;">Handle</span>(<span style="font-weight:bold;color:#1f377f;">message</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">context</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Contains</span>(<span style="font-weight:bold;color:#1f377f;">subscriber</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">sut</span>.Data.Subscribers); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Superset</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">expectedSubset</span>:&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HashSet</span>&lt;<span style="color:#2b91af;">Guid</span>&gt;(<span style="font-weight:bold;color:#1f377f;">subscribers</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>:&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HashSet</span>&lt;<span style="color:#2b91af;">Guid</span>&gt;(<span style="font-weight:bold;color:#1f377f;">sut</span>.Data.Subscribers)); }</pre> </p> <p> An array strictly isn't immutable, but declaring it as <code>IEnumerable&lt;Guid&gt;</code> hides the mutation capabilities. The test now has to copy <code>subscribers</code> to a list before assigning it to the policy's data. This anti-aliases <code>subscribers</code> from <code>sut.Data.Subscribers</code>, and causes the test to fail. After all, there's a defect in the <code>Handle</code> method. </p> <p> You now have to remove the offending line: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Handle</span>(<span style="color:#2b91af;">ObserveUnitStatus</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">message</span>,&nbsp;<span style="color:#2b91af;">IMessageHandlerContext</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">context</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Data.Subscribers.<span style="font-weight:bold;color:#74531f;">Add</span>(<span style="font-weight:bold;color:#1f377f;">message</span>.SubscriberId); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#2b91af;">Task</span>.CompletedTask; }</pre> </p> <p> This makes the test pass. </p> <h3 id="fd8e8ab5e7314ebbadc4775741af11fa"> Summary <a href="#fd8e8ab5e7314ebbadc4775741af11fa" title="permalink">#</a> </h3> <p> This article shows an example where I was surprised by aliasing. An assertion that I thought would fail turned out to be a false negative. </p> <p> You can easily make the mistake of writing a test that always passes. If you haven't tried it, you may think that you're too smart to do that, but it regularly happens to me. Other TDD practitioners have told me that it also happens to them. </p> <p> This is the reason that the <em>red-green-refactor</em> process encourages you to run each new test <em>and see it fail</em>. If you haven't seen it fail, you don't know if you've avoided a tautology. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/10/14/tautological-assertion Devil's advocate https://blog.ploeh.dk/2019/10/07/devils-advocate/ Mon, 07 Oct 2019 15:00:00 UTC <div id="post"> <p> <em>How do you know when you have enough test cases. The Devil's Advocate technique can help you decide.</em> </p> <p> When I review unit tests, I often utilise a technique I call <em>Devil's Advocate</em>. I do the same whenever I consider if I have a sufficient number of test cases. The first time I explicitly named the technique was, I think, in my <a href="/outside-in-tdd">Outside-in TDD Pluralsight course</a>, in which I also discuss the so-called <em>Gollum style</em> variation. I don't think, however, that I've ever written an article explicitly about this topic. The current text attempts to rectify that omission. </p> <h3 id="a66b04a5812b4a84ba3a60a8609e58be"> Coverage <a href="#a66b04a5812b4a84ba3a60a8609e58be" title="permalink">#</a> </h3> <p> Programmers new to unit testing often struggle with identifying useful test cases. I sometimes see people writing redundant unit tests, while, on the other hand, forgetting to add important test cases. How do you know which test cases to add, and how do you know when you've added enough? </p> <p> I may return to the first question in another article, but in this, I wish to address the second question. How do you know that you have a sufficient set of test cases? </p> <p> You may think that this is a question of turning on code coverage. Surely, if you have <a href="/2015/11/16/code-coverage-is-a-useless-target-measure">100% code coverage</a>, that's sufficient? </p> <p> It's not. Consider this simple class: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">capacity</span>) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Capacity&nbsp;=&nbsp;<span style="color:#1f377f;">capacity</span>; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">int</span>&nbsp;Capacity&nbsp;{&nbsp;<span style="color:blue;">get</span>;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;<span style="color:#74531f;">CanAccept</span>(<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&nbsp;<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;<span style="color:#1f377f;">reservation</span>) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;=&nbsp;<span style="color:#1f377f;">reservations</span>.<span style="color:#74531f;">Sum</span>(<span style="color:#1f377f;">r</span>&nbsp;=&gt;&nbsp;<span style="color:#1f377f;">r</span>.Quantity); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(Capacity&nbsp;&lt;&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;+&nbsp;<span style="color:#1f377f;">reservation</span>.Quantity) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">false</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">true</span>; &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> This class implements the (simplified) decision logic for an online restaurant reservation system. The <code>CanAccept</code> method has a cyclomatic complexity of 2, so it should be easy to cover with a pair of unit tests: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptWithNoPriorReservations</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;4 &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>:&nbsp;10); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>[0],&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">True</span>(<span style="color:#1f377f;">actual</span>); } [<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptOnInsufficientCapacity</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;4 &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>:&nbsp;10); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;{&nbsp;Quantity&nbsp;=&nbsp;7&nbsp;}&nbsp;}, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">False</span>(<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> These two tests together completely cover the <code>CanAccept</code> method: </p> <p> <img src="/content/binary/coverage-of-can-accept-method.png" alt="Screen shot showing that the CanAccept method is 100% covered."> </p> <p> You'd think that this is a sufficient number of test cases of the method, then. </p> <h3 id="0ac61ef87e3f4e738475e97179242db5"> As the Devil reads the Bible <a href="#0ac61ef87e3f4e738475e97179242db5" title="permalink">#</a> </h3> <p> In Scandinavia we have an idiom that <a href="https://www.kentbeck.com">Kent Beck</a> (who's worked with Norwegian companies) has also encountered: <blockquote> <p> "TIL: "like the devil reads the Bible"--meaning someone who carefully reads a book to subvert its intent" </p> <footer><cite><a href="https://twitter.com/kentbeck/status/651817458857320449">Kent Beck</a></cite></footer> </blockquote> We have the same saying in Danish, and the Swedes also use it. </p> <p> If you think of a unit test suite as an executable specification, you may consider if you can follow the specification to the letter while intentionally introduce a defect. You can easily do that with the above <code>CanAccept</code> method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;<span style="color:#74531f;">CanAccept</span>(<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&nbsp;<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;<span style="color:#1f377f;">reservation</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;=&nbsp;<span style="color:#1f377f;">reservations</span>.<span style="color:#74531f;">Sum</span>(<span style="color:#1f377f;">r</span>&nbsp;=&gt;&nbsp;<span style="color:#1f377f;">r</span>.Quantity); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(Capacity&nbsp;&lt;=&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;+&nbsp;<span style="color:#1f377f;">reservation</span>.Quantity) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">false</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">true</span>; }</pre> </p> <p> This still passes both tests, and still has a code coverage of 100%, yet it's 'obviously' wrong. </p> <p> Can you spot the difference? </p> <p> Instead of a <em>less-than</em> comparison, it now uses a <em>less-than-or-equal</em> comparison. You could easily, inadvertently, make such a mistake while programming. It belongs in the category of <em>off-by-one errors</em>, which is one of the most common type of bugs. </p> <p> This is, in a nutshell, the Devil's Advocate technique. The intent isn't to break the software by sneaking in defects, but to explore how effectively the test suite detects bugs. In the current (simplified) example, the effectiveness of the test suite isn't impressive. </p> <h3 id="d6e4c657adec4cc1bb6d10af351a415f"> Add test cases <a href="#d6e4c657adec4cc1bb6d10af351a415f" title="permalink">#</a> </h3> <p> The problem introduced by the Devil's Advocate is an edge case. If the reservation under consideration fits the restaurant's remaining capacity, but entirely consumes it, the <code>MaîtreD</code> class should still accept it. Currently, however, it doesn't. </p> <p> It'd seem that the obvious solution is to 'fix' the unit test: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptWithNoPriorReservations</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;10 &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>:&nbsp;10); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>[0],&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">True</span>(<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> Changing the requested <code>Quantity</code> to <code>10</code> does, indeed, cause the test to fail. </p> <h3 id="26be7b38248c4dcba5134eb4529d8214"> Beyond mutation testing <a href="#26be7b38248c4dcba5134eb4529d8214" title="permalink">#</a> </h3> <p> Until this point, you may think that the Devil's Advocate just looks like <em>an ad-hoc, informally-specified, error-prone, manual version of half of <a href="https://en.wikipedia.org/wiki/Mutation_testing">mutation testing</a></em>. So far, the change I made above could also have been made during mutation testing. </p> <p> What I sometimes do with the Devil's Advocate technique is to experiment with other, less heuristically driven changes. For instance, based on my knowledge of the existing test cases, it's not too difficult to come up with this change: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;<span style="color:#74531f;">CanAccept</span>(<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&nbsp;<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;<span style="color:#1f377f;">reservation</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;=&nbsp;<span style="color:#1f377f;">reservations</span>.<span style="color:#74531f;">Sum</span>(<span style="color:#1f377f;">r</span>&nbsp;=&gt;&nbsp;<span style="color:#1f377f;">r</span>.Quantity); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(<span style="color:#1f377f;">reservation</span>.Quantity&nbsp;!=&nbsp;10) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">false</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">true</span>; }</pre> </p> <p> That's an even simpler implementation than the original, but obviously wrong. </p> <p> This should prompt you to add at least one other test case: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(&nbsp;4)] [<span style="color:#2b91af;">InlineData</span>(10)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptWithNoPriorReservations</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">quantity</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">quantity</span> &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>:&nbsp;10); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>[0],&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">True</span>(<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> Notice that I converted the test to a parametrised test. This breaks the Devil's latest attempt, while the original implementation passes all tests. </p> <p> The Devil, not to be outdone, now switches tactics and goes after the <code>reservations</code> instead: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;<span style="color:#74531f;">CanAccept</span>(<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&nbsp;<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;<span style="color:#1f377f;">reservation</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;!<span style="color:#1f377f;">reservations</span>.<span style="color:#74531f;">Any</span>(); }</pre> </p> <p> This still passes all tests, including the new test case. This indicates that you'll need to add at least one test case with existing reservations, but where there's still enough capacity to accept another reservation: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptWithOnePriorReservation</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;4 &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>:&nbsp;10); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;{&nbsp;Quantity&nbsp;=&nbsp;4&nbsp;}&nbsp;}, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">True</span>(<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> This new test fails, prompting you to correct the implementation of <code>CanAccept</code>. The Devil, however, can do this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;<span style="color:#74531f;">CanAccept</span>(<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&nbsp;<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;<span style="color:#1f377f;">reservation</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;=&nbsp;<span style="color:#1f377f;">reservations</span>.<span style="color:#74531f;">Sum</span>(<span style="color:#1f377f;">r</span>&nbsp;=&gt;&nbsp;<span style="color:#1f377f;">r</span>.Quantity); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;!=&nbsp;7; }</pre> </p> <p> This is still not correct, but passes all tests. It does, however, look like you're getting closer to a proper implementation. </p> <h3 id="9b955ad4a2084823a9eeb668415eb696"> Reverse Transformation Priority Premise <a href="#9b955ad4a2084823a9eeb668415eb696" title="permalink">#</a> </h3> <p> If you find this process oddly familiar, it's because it resembles the <a href="https://blog.cleancoder.com/uncle-bob/2013/05/27/TheTransformationPriorityPremise.html">Transformation Priority Premise</a> (TPP), just reversed. <blockquote> <p> “As the tests get more specific, the code gets more generic.” </p> <footer><cite><a href="https://blog.cleancoder.com/uncle-bob/2013/05/27/TheTransformationPriorityPremise.html">Robert C. Martin</a></cite></footer> </blockquote> </p> <p> When I test-drive code, I often try to follow the TPP, but when I review code with tests, the code and the tests are already in place, and it's my task to assess both. </p> <p> Applying the Devil's Advocate review technique to <code>CanAccept</code>, it seems as though I'm getting closer to a proper implementation. It does, however, require more tests. As your next move you may, for instance, consider parametrising the test case that verifies what happens when capacity is insufficient: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(7)] [<span style="color:#2b91af;">InlineData</span>(8)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptOnInsufficientCapacity</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;4 &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>:&nbsp;10); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;{&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;}&nbsp;}, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">False</span>(<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> That doesn't help much, though, because this passes all tests: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;<span style="color:#74531f;">CanAccept</span>(<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&nbsp;<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;<span style="color:#1f377f;">reservation</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;=&nbsp;<span style="color:#1f377f;">reservations</span>.<span style="color:#74531f;">Sum</span>(<span style="color:#1f377f;">r</span>&nbsp;=&gt;&nbsp;<span style="color:#1f377f;">r</span>.Quantity); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;&lt;&nbsp;7; }</pre> </p> <p> Compared to the initial, 'desired' implementation, there's at least two issues with this code: <ul> <li>It doesn't consider <code>reservation.Quantity</code></li> <li>It doesn't take into account the <code>Capacity</code> of the restaurant</li> </ul> This indicates that you're going to have to add more test cases, varying both <code>reservation.Quantity</code> and <code>Capacity</code>. The happy-path test cases already varies <code>reservation.Quantity</code> a bit, but <code>CanAcceptOnInsufficientCapacity</code> does not, so perhaps you can follow the TPP by varying <code>reservation.Quantity</code> in that method as well: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(&nbsp;1,&nbsp;10)] [<span style="color:#2b91af;">InlineData</span>(&nbsp;2,&nbsp;&nbsp;9)] [<span style="color:#2b91af;">InlineData</span>(&nbsp;3,&nbsp;&nbsp;8)] [<span style="color:#2b91af;">InlineData</span>(&nbsp;4,&nbsp;&nbsp;7)] [<span style="color:#2b91af;">InlineData</span>(&nbsp;4,&nbsp;&nbsp;8)] [<span style="color:#2b91af;">InlineData</span>(&nbsp;5,&nbsp;&nbsp;6)] [<span style="color:#2b91af;">InlineData</span>(&nbsp;6,&nbsp;&nbsp;5)] [<span style="color:#2b91af;">InlineData</span>(10,&nbsp;&nbsp;1)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptOnInsufficientCapacity</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">quantity</span>,&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">quantity</span> &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>:&nbsp;10); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;{&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;}&nbsp;}, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">False</span>(<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> This makes it harder for the Devil to come up with a malevolent implementation. Harder, but not impossible. </p> <p> It seems clear that since all test cases still use a hard-coded capacity, it ought to be possible to write an implementation that ignores the <code>Capacity</code>, but at this point I don't see a simple way to avoid looking at <code>reservation.Quantity</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;<span style="color:#74531f;">CanAccept</span>(<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&nbsp;<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;<span style="color:#1f377f;">reservation</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;=&nbsp;<span style="color:#1f377f;">reservations</span>.<span style="color:#74531f;">Sum</span>(<span style="color:#1f377f;">r</span>&nbsp;=&gt;&nbsp;<span style="color:#1f377f;">r</span>.Quantity); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;+&nbsp;<span style="color:#1f377f;">reservation</span>.Quantity&nbsp;&lt;&nbsp;11; }</pre> </p> <p> This implementation passes all the tests. The last batch of test cases forced the Devil to consider <code>reservation.Quantity</code>. This strongly implies that if you vary <code>Capacity</code> as well, the proper implementation out to emerge. </p> <h3 id="e3ed81c93d5847039ea53e7acd978d99"> Diminishing returns <a href="#e3ed81c93d5847039ea53e7acd978d99" title="permalink">#</a> </h3> <p> What happens, then, if you add just one test case with a different <code>Capacity</code>? </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(&nbsp;1,&nbsp;10,&nbsp;10)] [<span style="color:#2b91af;">InlineData</span>(&nbsp;2,&nbsp;&nbsp;9,&nbsp;10)] [<span style="color:#2b91af;">InlineData</span>(&nbsp;3,&nbsp;&nbsp;8,&nbsp;10)] [<span style="color:#2b91af;">InlineData</span>(&nbsp;4,&nbsp;&nbsp;7,&nbsp;10)] [<span style="color:#2b91af;">InlineData</span>(&nbsp;4,&nbsp;&nbsp;8,&nbsp;10)] [<span style="color:#2b91af;">InlineData</span>(&nbsp;5,&nbsp;&nbsp;6,&nbsp;10)] [<span style="color:#2b91af;">InlineData</span>(&nbsp;6,&nbsp;&nbsp;5,&nbsp;10)] [<span style="color:#2b91af;">InlineData</span>(10,&nbsp;&nbsp;1,&nbsp;10)] [<span style="color:#2b91af;">InlineData</span>(&nbsp;1,&nbsp;&nbsp;1,&nbsp;&nbsp;1)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptOnInsufficientCapacity</span>( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">quantity</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">capacity</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">quantity</span> &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;{&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;}&nbsp;}, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">False</span>(<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> Notice that I just added one test case with a <code>Capacity</code> of <code>1</code>. </p> <p> You may think that this is about where the Devil ought to capitulate, but not so. This passes all tests: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;<span style="color:#74531f;">CanAccept</span>(<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&nbsp;<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;<span style="color:#1f377f;">reservation</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">foreach</span>&nbsp;(<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">r</span>&nbsp;<span style="color:#8f08c4;">in</span>&nbsp;<span style="color:#1f377f;">reservations</span>) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;=&nbsp;<span style="color:#1f377f;">r</span>.Quantity; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">break</span>; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;+&nbsp;<span style="color:#1f377f;">reservation</span>.Quantity&nbsp;&lt;=&nbsp;Capacity; }</pre> </p> <p> Here you may feel the urge to protest. So far, all the Devil's Advocate implementations have been objectively <em>simpler</em> than the 'desired' implementation because it has involved fewer elements and has had a lower or equivalent <a href="https://en.wikipedia.org/wiki/Cyclomatic_complexity">cyclomatic complexity</a>. This new attempt to circumvent the specification seems more complex. </p> <p> It's also seems clearly ill-intentioned. Recall that the intent of the Devil's Advocate technique isn't to 'cheat' the unit tests, but rather to explore how well the test describe the desired behaviour of the system. The motivation is that it's easy to make off-by-one errors like inadvertently use <code>&lt;=</code> instead of <code>&lt;</code>. It doesn't seem quite as reasonable that a well-intentioned programmer accidentally would leave behind an implementation like the above. </p> <p> You can, however, make it <em>look</em> less complicated: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;<span style="color:#74531f;">CanAccept</span>(<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&nbsp;<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;<span style="color:#1f377f;">reservation</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;=&nbsp;<span style="color:#1f377f;">reservations</span>.<span style="color:#74531f;">Select</span>(<span style="color:#1f377f;">r</span>&nbsp;=&gt;&nbsp;<span style="color:#1f377f;">r</span>.Quantity).<span style="color:#74531f;">FirstOrDefault</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;+&nbsp;<span style="color:#1f377f;">reservation</span>.Quantity&nbsp;&lt;=&nbsp;Capacity; }</pre> </p> <p> You could argue that this still looks intentionally wrong, but I've seen much code that looks like this. It seems to me that there's a kind of programmer who seems generally uncomfortable thinking in collections; they seem to subconsciously gravitate towards code that deals with singular objects. Code that attempts to get 'the' value out of a collection is, unfortunately, not that uncommon. </p> <p> Still, you might think that at this point, you've added enough test cases. That's reasonable. </p> <p> The Devil's Advocate technique isn't an <em>algorithm</em>; it has no deterministic exit criterion. It's just a heuristic that I use to explore the quality of tests. There comes a point where subjectively, I judge that the test cases <em>sufficiently</em> describe the desired behaviour. </p> <p> You may find that we've reached that point now. You could, for example, argue that in order to calculate <code>reservedSeats</code>, <code>reservations.Sum(r =&gt; r.Quantity)</code> is simpler than <code>reservations.Select(r =&gt; r.Quantity).FirstOrDefault()</code>. I'd be inclined to agree. </p> <p> There's diminishing returns to the Devil's Advocate technique. Once you find that the gains from insisting on intentionally pernicious implementations are smaller than the effort required to add more test cases, it's time to stop and commit to the test cases now in place. </p> <h3 id="609ddb35ae364efbbfb7965a646d857e"> Test case variability <a href="#609ddb35ae364efbbfb7965a646d857e" title="permalink">#</a> </h3> <p> Tests specify desired behaviour. If the tests contain less variability than the code they cover, then how can you be certain that the implementation code is correct? </p> <p> The discussion now moves into territory where I usually exercise a great deal of judgement. Read the following for inspiration, not as rigid instructions. My intent with the following is not to imply that you must always go to like extremes, but simply to demonstrate what you <em>can</em> do. Depending on circumstances (such as the cost of a defect in production), I may choose to do the following, and sometimes I may choose to skip it. </p> <p> If you consider the original implementation of <code>CanAccept</code> at the top of the article, notice that it works with <code>reservations</code> of indefinite size. If you think of <code>reservations</code> as a finite collection, it can contain zero, one, two, ten, or hundreds of elements. Yet, no test case goes beyond a single existing reservation. This is, I think, a disconnect. The tests come not even close to the degree of variability that the method can handle. If this is a piece of mission-critical software, that could be a cause for concern. </p> <p> You should add some test cases where there's two, three, or more existing reservations. People often don't do that because it seems that you'd now have to write a test method that exercises one or more test cases with two existing reservations: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptWithTwoPriorReservations</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;4 &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>:&nbsp;10); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;{&nbsp;Quantity&nbsp;=&nbsp;4&nbsp;},&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;{&nbsp;Quantity&nbsp;=&nbsp;1&nbsp;}&nbsp;}, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">True</span>(<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> While this method now covers the two-existing-reservations test case, you need one to cover the three-existing-reservations test case, and so on. This seems repetitive, and probably bothers you at more than one level: <ul> <li>It's just plain tedious to have to add that kind of variability</li> <li>It seems to violate the <a href="https://en.wikipedia.org/wiki/Don%27t_repeat_yourself">DRY principle</a></li> </ul> I don't hold the DRY principle as an absolute that must always be followed, but it often indicates a maintainability problem. I think this is the case here, because the new <code>CanAcceptWithTwoPriorReservations</code> test method looks a lot like the previous <code>CanAcceptWithOnePriorReservation</code> method. If someone makes changes to the <code>MaîtreD</code> class, they would have to go and revisit all those test methods. </p> <p> What you can do instead is to parametrise the key values of the collection(s) in question. While you can't put collections of objects in <code>[InlineData]</code> attributes, you <em>can</em> put arrays of constants. For existing reservations, the key values are the quantities, so supply an array of integers as a test argument: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(&nbsp;4,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">int</span>[0])] [<span style="color:#2b91af;">InlineData</span>(10,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">int</span>[0])] [<span style="color:#2b91af;">InlineData</span>(&nbsp;4,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;4&nbsp;})] [<span style="color:#2b91af;">InlineData</span>(&nbsp;4,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;4,&nbsp;1&nbsp;})] [<span style="color:#2b91af;">InlineData</span>(&nbsp;2,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;2,&nbsp;1,&nbsp;3,&nbsp;2&nbsp;})] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptWhenCapacityIsSufficient</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">quantity</span>,&nbsp;<span style="color:blue;">int</span>[]&nbsp;<span style="color:#1f377f;">reservationQantities</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">quantity</span> &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>:&nbsp;10); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservations</span>&nbsp;=&nbsp;<span style="color:#1f377f;">reservationQantities</span>.<span style="color:#74531f;">Select</span>(<span style="color:#1f377f;">q</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;{&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">q</span>&nbsp;}); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>(<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">True</span>(<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> This single test method replaces the previous three 'happy path' test methods. The first four <code>[InlineData]</code> annotations reproduce the previous test cases, whereas the fifth <code>[InlineData]</code> annotation adds a new test case with four existing reservations. </p> <p> I gave the method a new name to better reflect the more general nature of it. </p> <p> Notice that the <code>CanAcceptWhenCapacityIsSufficient</code> method uses <code>Select</code> to turn the array of integers into a collection of <code>Reservation</code> objects. </p> <p> You may think that I cheated, since I didn't supply any other values, such as the <code>Date</code> property, to the existing reservations. This is easily addressed: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(&nbsp;4,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">int</span>[0])] [<span style="color:#2b91af;">InlineData</span>(10,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">int</span>[0])] [<span style="color:#2b91af;">InlineData</span>(&nbsp;4,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;4&nbsp;})] [<span style="color:#2b91af;">InlineData</span>(&nbsp;4,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;4,&nbsp;1&nbsp;})] [<span style="color:#2b91af;">InlineData</span>(&nbsp;2,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;2,&nbsp;1,&nbsp;3,&nbsp;2&nbsp;})] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptWhenCapacityIsSufficient</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">quantity</span>,&nbsp;<span style="color:blue;">int</span>[]&nbsp;<span style="color:#1f377f;">reservationQantities</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">date</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:#1f377f;">date</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">quantity</span> &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>:&nbsp;10); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservations</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">reservationQantities</span>.<span style="color:#74531f;">Select</span>(<span style="color:#1f377f;">q</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;{&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">q</span>,&nbsp;Date&nbsp;=&nbsp;<span style="color:#1f377f;">date</span>&nbsp;}); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>(<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">True</span>(<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> The only change compared to before is that <code>date</code> is now a variable assigned not only to <code>reservation</code>, but also to all the <code>Reservation</code> objects in <code>reservations</code>. </p> <h3 id="0564ebd7cafc44f4ba6ad017e3f0d0ce"> Towards property-based testing <a href="#0564ebd7cafc44f4ba6ad017e3f0d0ce" title="permalink">#</a> </h3> <p> Looking at a test method like <code>CanAcceptWhenCapacityIsSufficient</code> it should bother you that the <code>capacity</code> is still hard-coded. Why don't you make that a test argument as well? </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(10,&nbsp;&nbsp;4,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">int</span>[0])] [<span style="color:#2b91af;">InlineData</span>(10,&nbsp;10,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">int</span>[0])] [<span style="color:#2b91af;">InlineData</span>(10,&nbsp;&nbsp;4,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;4&nbsp;})] [<span style="color:#2b91af;">InlineData</span>(10,&nbsp;&nbsp;4,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;4,&nbsp;1&nbsp;})] [<span style="color:#2b91af;">InlineData</span>(10,&nbsp;&nbsp;2,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;2,&nbsp;1,&nbsp;3,&nbsp;2&nbsp;})] [<span style="color:#2b91af;">InlineData</span>(20,&nbsp;10,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;2,&nbsp;2,&nbsp;2,&nbsp;2&nbsp;})] [<span style="color:#2b91af;">InlineData</span>(20,&nbsp;&nbsp;4,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;2,&nbsp;2,&nbsp;4,&nbsp;1,&nbsp;3,&nbsp;3&nbsp;})] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptWhenCapacityIsSufficient</span>( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">capacity</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">quantity</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>[]&nbsp;<span style="color:#1f377f;">reservationQantities</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">date</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:#1f377f;">date</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">quantity</span> &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservations</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">reservationQantities</span>.<span style="color:#74531f;">Select</span>(<span style="color:#1f377f;">q</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;{&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">q</span>,&nbsp;Date&nbsp;=&nbsp;<span style="color:#1f377f;">date</span>&nbsp;}); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>(<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">True</span>(<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> The first five <code>[InlineData]</code> annotations just reproduce the test cases that were already present, whereas the bottom two annotations are new test cases with another <code>capacity</code>. </p> <p> How do I come up with new test cases? It's easy: In the happy-path case, the sum of existing reservation quantities, plus the requested quantity, must be less than or equal to the <code>capacity</code>. </p> <p> It sometimes helps to slightly reframe the test method. If you allow the collection of existing reservations to be the most variable element in the test method, you can express the other values relative to that input. For example, instead of supplying the <code>capacity</code> as an absolute number, you can express a test case's capacity in relation to the existing reservations: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(6,&nbsp;&nbsp;4,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">int</span>[0])] [<span style="color:#2b91af;">InlineData</span>(0,&nbsp;10,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">int</span>[0])] [<span style="color:#2b91af;">InlineData</span>(2,&nbsp;&nbsp;4,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;4&nbsp;})] [<span style="color:#2b91af;">InlineData</span>(1,&nbsp;&nbsp;4,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;4,&nbsp;1&nbsp;})] [<span style="color:#2b91af;">InlineData</span>(0,&nbsp;&nbsp;2,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;2,&nbsp;1,&nbsp;3,&nbsp;2&nbsp;})] [<span style="color:#2b91af;">InlineData</span>(2,&nbsp;10,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;2,&nbsp;2,&nbsp;2,&nbsp;2&nbsp;})] [<span style="color:#2b91af;">InlineData</span>(1,&nbsp;&nbsp;4,&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;2,&nbsp;2,&nbsp;4,&nbsp;1,&nbsp;3,&nbsp;3&nbsp;})] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptWhenCapacityIsSufficient</span>( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">capacitySurplus</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">quantity</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>[]&nbsp;<span style="color:#1f377f;">reservationQantities</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">date</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:#1f377f;">date</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">quantity</span> &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;=&nbsp;<span style="color:#1f377f;">reservationQantities</span>.<span style="color:#74531f;">Sum</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">capacity</span>&nbsp;=&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;+&nbsp;<span style="color:#1f377f;">quantity</span>&nbsp;+&nbsp;<span style="color:#1f377f;">capacitySurplus</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservations</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">reservationQantities</span>.<span style="color:#74531f;">Select</span>(<span style="color:#1f377f;">q</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;{&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">q</span>,&nbsp;Date&nbsp;=&nbsp;<span style="color:#1f377f;">date</span>&nbsp;}); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>(<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">True</span>(<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> Notice that the value supplied as a test argument is now named <code>capacitySurplus</code>. This represents the surplus capacity for each test case. For example, in the first test case, the <code>capacity</code> was previously supplied as the absolute number <code>10</code>. The requested quantity is <code>4</code>, and since there's no prior reservations in that test case, the capacity surplus, after accepting the reservation, is <code>6</code>. </p> <p> Likewise, in the second test case, the requested quantity is <code>10</code>, and since the absolute capacity is also <code>10</code>, when you reframe the test case, the surplus capacity, after accepting the reservation, is <code>0</code>. </p> <p> This seems odd if you aren't used to it. You'd probably intuitively think of a restaurant's <code>Capacity</code> as 'the most absolute' number, in that it's often a number that originates from physical constraints. </p> <p> When you're looking for test cases, however, you aren't looking for test cases for a particular restaurant. You're looking for test cases for an arbitrary restaurant. In other words, you're looking for test inputs that belong to the same <em>equivalence class</em>. </p> <h3 id="174e2338027e4f3ca0b84dd0fb6adc5f"> Property-based testing <a href="#174e2338027e4f3ca0b84dd0fb6adc5f" title="permalink">#</a> </h3> <p> I haven't explicitly stated this yet, but both the <code>capacity</code> and each reservation <code>Quantity</code> should be a positive number. This should really have been <a href="/2015/01/19/from-primitive-obsession-to-domain-modelling">captured as a proper domain object</a>, but I chose to keep these values as primitive integers in order to not complicate the example too much. </p> <p> If you look at the test parameters for the latest incarnation of <code>CanAcceptWhenCapacityIsSufficient</code>, you may now observe the following: <ul> <li><code>capacitySurplus</code> can be an arbitrary non-negative number</li> <li><code>quantity</code> can be an arbitrary positive number</li> <li><code>reservationQantities</code> can be an arbitrary array of positive numbers, including the empty array</li> </ul> This isn't too hard to express with, say, <a href="https://fscheck.github.io/FsCheck">FsCheck</a> (2.14.0): </p> <p> <pre>[<span style="color:#2b91af;">Property</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">CanAcceptWhenCapacityIsSufficient</span>( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">NonNegativeInt</span>&nbsp;<span style="color:#1f377f;">capacitySurplus</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">PositiveInt</span>&nbsp;<span style="color:#1f377f;">quantity</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">PositiveInt</span>[]&nbsp;<span style="color:#1f377f;">reservationQantities</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">date</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(2018,&nbsp;8,&nbsp;30); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;<span style="color:#1f377f;">date</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">quantity</span>.Item &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;=&nbsp;<span style="color:#1f377f;">reservationQantities</span>.<span style="color:#74531f;">Sum</span>(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;<span style="color:#1f377f;">x</span>.Item); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">capacity</span>&nbsp;=&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;+&nbsp;<span style="color:#1f377f;">quantity</span>.Item&nbsp;+&nbsp;<span style="color:#1f377f;">capacitySurplus</span>.Item; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">MaîtreD</span>(<span style="color:#1f377f;">capacity</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservations</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">reservationQantities</span>.<span style="color:#74531f;">Select</span>(<span style="color:#1f377f;">q</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;{&nbsp;Quantity&nbsp;=&nbsp;<span style="color:#1f377f;">q</span>.Item,&nbsp;Date&nbsp;=&nbsp;<span style="color:#1f377f;">date</span>&nbsp;}); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#1f377f;">sut</span>.<span style="color:#74531f;">CanAccept</span>(<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#1f377f;">reservation</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">True</span>(<span style="color:#1f377f;">actual</span>); }</pre> </p> <p> This refactoring takes advantage of FsCheck's built-in wrapper types <code>NonNegativeInt</code> and <code>PositiveInt</code>. If you'd like an introduction to FsCheck, you could watch my <a href="/property-based-testing-intro">Introduction to Property-based Testing with F#</a> Pluralsight course. </p> <p> By default, FsCheck runs each property 100 times, so now, instead of seven test cases, you now have 100. </p> <h3 id="1eddf5bb91324b18880c78d1f1825ea6"> Limits to the Devil's Advocate technique <a href="#1eddf5bb91324b18880c78d1f1825ea6" title="permalink">#</a> </h3> <p> There's a limit to the Devil's Advocate technique. Unless you're working with <a href="/2015/02/23/property-based-testing-without-a-property-based-testing-framework">a problem where you can exhaust the entire domain of possible test cases</a>, your testing strategy is always going to be a sampling strategy. You run your automated tests with either hard-coded values or randomly generated values, but regardless, a test run isn't going to cover all possible input combinations. </p> <p> For example, a truly hostile Devil could make this change to the <code>CanAccept</code> method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;<span style="color:#74531f;">CanAccept</span>(<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&nbsp;<span style="color:#1f377f;">reservations</span>,&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;<span style="color:#1f377f;">reservation</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(<span style="color:#1f377f;">reservation</span>.Quantity&nbsp;==&nbsp;3953911) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">true</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;=&nbsp;<span style="color:#1f377f;">reservations</span>.<span style="color:#74531f;">Sum</span>(<span style="color:#1f377f;">r</span>&nbsp;=&gt;&nbsp;<span style="color:#1f377f;">r</span>.Quantity); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:#1f377f;">reservedSeats</span>&nbsp;+&nbsp;<span style="color:#1f377f;">reservation</span>.Quantity&nbsp;&lt;=&nbsp;Capacity; }</pre> </p> <p> Even if you increase the number of test cases that FsCheck generates to, say, 100,000, it's unlikely to find the poisonous branch. The chance of randomly generating a <code>quantity</code> of <em>exactly</em> <code>3953911</code> isn't that great. </p> <p> The Devil's Advocate technique doesn't guarantee that you'll have enough test cases to protect yourself against all sorts of odd defects. It does, however, still work well as an analysis tool to figure out if there's 'enough' test cases. </p> <h3 id="6ad7a48fd0c04f91af236d99f0722617"> Conclusion <a href="#6ad7a48fd0c04f91af236d99f0722617" title="permalink">#</a> </h3> <p> The Devil's Advocate technique is a heuristic you can use to evaluate whether more test cases would improve confidence in the test suite. You can use it to review existing (test) code, but you can also use it as inspiration for new test cases that you should consider adding. </p> <p> The technique is to deliberately implement the system under test incorrectly. The more incorrect you can make it, the more test cases you'll be likely to have to add. </p> <p> When there's only a few test cases, you can probably get away with a decidedly unsound implementation that still passes all tests. These are often simpler than the 'intended' implementation. In this phase of applying the heuristic, this clearly demonstrates the need for more test cases. </p> <p> At a later stage, you'll have to go deliberately out of your way to produce a wrong implementation that still passes all tests. When that happens, it may be time to stop. </p> <p> The intent of the technique is to uncover how many test cases you need to protect against common defects in the future. Thus, it's not a measure of <em>current</em> code coverage. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="fd53c72c360b42999b87c87649460e78"> <div class="comment-author">Tyson Williams</div> <div class="comment-content"> <blockquote> <p> When there's only a few test cases, you can probably get away with a decidedly unsound implementation that still passes all tests. These are often simpler than the 'intended' implementation. In this phase of applying the heuristic, this clearly demonstrates the need for more test cases. </p> <p> At a later stage, you'll have to go deliberately out of your way to produce a wrong implementation that still passes all tests. When that happens, it may be time to stop. </p> </blockquote> <p> I like to think of this behavior as a phrase transition. </p> <blockquote> Unless you're working with a problem where you can exhaust the entire domain of possible test cases, your testing strategy is always going to be a sampling strategy. </blockquote> <p> I agree with this in practice, but it is not always true in theory. A counter eaxample is <a href="https://en.wikipedia.org/wiki/Polynomial_interpolation">polynomial interpolation</a>. </p> <p> Normally we think of a polynomial in an indeterminate <code>x</code> of degree <code>n</code> as being specified by a list of <code>n + 1</code> coefficients, where the <code>i</code>th coefficient is the coefficient of <code>x<sup>i</sup></code>. Evaluating this polynomial given a value for <code>x</code> is easy; it just involves exponentiation, multiplication, and addition. Polynomial evaluation has a conceptual inverse called polynomial interpolation. In this direction, the input is evaluations at <code>n + 1</code> points in "general position" and the output is the <code>n + 1</code> coefficients. For example, a line is a polynomial of degree <code>1</code> and two points are in general position if they are not the same point. This is commonly expressed the phrase "Any two (distinct) points defines a line." Three points are in general position if they are not co-linear, where co-linear means that all three points are on the same line. In general, <code>n + 1</code> points are in general position if they are not all on the same polynomial of degree <code>n</code>. <p> <p> Anyway, here is the point. If a pure function is known to implement some polynomial of degree (at most) <code>n</code>, then even if the domain is infinite, there exists <code>n + 1</code> inputs such that it is sufficient to test this function for correctness on those inputs. </p> <p> This is why I think the phrase transition in the Devil's advocate testing is critical. There is some objective measure of complexity of the function under test (such as cyclomatic complexity), and we have an intuitive sense that a certain number of tests is sufficient for testing functions with that complexity. If the Devil is allowed to add monomials to the polynomial (or, heaven forbid, modify the implementation so that it is not a polynomial), then any finite number of tests can be circumvented. If instead the Devil is only allowed to modify the coefficients of the polynomial, then we have a winning strategy. </p> <blockquote> Here you may feel the urge to protest. So far, all the Devil's Advocate implementations have been objectively simpler than the 'desired' implementation because it has involved fewer elements and has had a lower or equivalent cyclomatic complexity. This new attempt to circumvent the specification seems more complex. </blockquote> <p> I think it would be exceedingly intersting if you can formally define what you mean here by "objectively". In the case of a polynomial (and speaking slightly roughly), changing the "first" nonzero coefficient to <code>0</code> decreases the complexity (i.e. the degree of the polynomial) while any other change to that coefficient or any change to any other coefficient maintains the complexity. </p> </div> <div class="comment-date">2019-10-25 01:32 UTC</div> </div> <div class="comment" id="cb15452b8c96429998efd50b67373da3"> <div class="comment-author"><a href="/">Mark Seemann</a></div> <div class="comment-content"> <p> Tyson, thank you for writing. What I meant by <em>objectively simpler</em> I partially explain in the same paragraph. I consider cyclomatic complexity one of hardly any useful measurements in software development. As I also imply in the article, I consider Robert C. Martin's <em>Transformation Priority Premise</em> to include a good ranking of code constructs, e.g. that using a constant is simpler than using a variable, and so on. </p> <p> I don't think you need to reach for polynomial interpolation in order to make your point. Just consider a function that returns a constant value, like this one: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">string</span>&nbsp;<span style="color:#74531f;">Foo</span>(<span style="color:blue;">int</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">i</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#a31515;">&quot;foo&quot;</span>; }</pre> </p> <p> You can make a similar argument about this function: You only need a single test value in order to demonstrate that it works as intended. I suppose you could view that as a zero-degree polynomial. </p> <p> Beyond what you think of as the <em>phase transition</em> I sometimes try to see what happens if I slightly <em>increase</em> the complexity of a function. For the <code>Foo</code> function, it could be a change like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">string</span>&nbsp;<span style="color:#74531f;">Foo</span>(<span style="color:blue;">int</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">i</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">if</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">i</span>&nbsp;&lt;&nbsp;-1000) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#a31515;">&quot;bar&quot;</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#a31515;">&quot;foo&quot;</span>; }</pre> </p> <p> Unless you just happened to pick a number less than <code>-1000</code> for your test value, your test will not discover such a change. </p> <p> Your argument attempts to guard against that sort of change by assuming that we can somehow 'forbid' a change from a polynomial to something irregular. Real code doesn't work that way. Real code is rarely a continuous function, but rather discrete. That's the reason we have a concept such as <em>edge case</em>, because code branches at discrete values. </p> <p> A polynomial is a single function, regardless of degree. Implemented in code, it'll have a cyclomatic complexity of 1. That may not even be worth testing, because you'd essentially only be reproducing the implementation code in your test. </p> <p> The purpose of the Devil's Advocate technique isn't to demonstrate correctness; that's what unit tests are for. The purpose of the Devil's Advocate technique is to critique the tests. </p> <p> In reality, I never imagine that some malicious developer gains access to the source code. On the other hand, we all make mistakes, and I try to imagine what a likely mistake might look like. </p> </div> <div class="comment-date">2019-10-26 3:57 UTC</div> </div> </div> <hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/10/07/devils-advocate 10x developers https://blog.ploeh.dk/2019/09/30/10x-developers/ Mon, 30 Sep 2019 06:56:00 UTC <div id="post"> <p> <em>Do 10x developers exist? I believe that they do, but not like you may think.</em> </p> <p> The notion that some software developers are ten times (10x) as productive as 'normal' developers is decades old. Once in a while, the discussion resurfaces. It's a controversial subject, but something I've been thinking about for years, so I thought that I'd share my perspective because I don't see anyone else arguing from this position. </p> <p> While I'll try to explain my reasoning, I'll make no attempt at passing this off as anything but my current, subjective viewpoint. Please leave a comment if you have something to add. </p> <h3 id="11f6ec960f694758892bff549eb79d59"> Perspective <a href="#11f6ec960f694758892bff549eb79d59" title="permalink">#</a> </h3> <p> Meet Yohan. You've probably had a colleague like him. He's one of those software developers who gets things done, who never says no when the business asks him to help them out, who always respond with a smile to any request. </p> <p> I've had a few colleagues like Yohan in my career. It can be enlightening overhearing non-technical stakeholders discuss software developers: </p> <p> <strong>Alice:</strong> Yohan is such a dear; he helped me out with that feature on the web site, you know... </p> <p> <strong>Bob:</strong> Yes, he's a real go-getter. All the other programmers just say no and look pissed when I approach them about anything. </p> <p> <strong>Alice:</strong> Yohan always says yes, and he gets things done. He's a real 10x developer. </p> <p> <strong>Bob:</strong> We're so lucky we have him... </p> <p> Overhearing such a conversation can be frustrating. Yohan is your colleague, and you've just about had enough of him. Yohan is one of those developers who'll surround all code with a <code>try-catch</code> block, because then there'll be no exceptions in production. Yohan will make changes directly to the production system and tell no-one. Yohan will copy and paste code. Yohan will put business logic in database triggers, or rewrite logs, or use email as a messaging system, or call, parse, and run HTML-embedded JavaScript code on back-end servers. All 'because it's faster and provides more business value.' </p> <p> Yohan is a 10x developer. </p> <p> You, and the rest of your team, get nothing done. </p> <p> You get nothing done because you waste all your time cleaning up the trail of garbage and technical debt Yohan leaves in his wake. </p> <p> Business stakeholders may view Yohan as being orders of magnitude more productive than other developers, because most programming work is invisible and intangible. Whether or not someone is a 10x developer is highly subjective, and depends on perspective. </p> <h3 id="57c36b775bca4e848cadf50182028191"> Context <a href="#57c36b775bca4e848cadf50182028191" title="permalink">#</a> </h3> <p> The notion that some people are orders of magnitude more productive than the 'baseline' programmer has other problems. It implicitly assumes that a 'baseline' programmer exists in the first place. Modern software development, however, is specialised. </p> <p> As an example, I've been doing test-driven, ASP.NET-based C# server-side enterprise development for decades. Drop me into a project with my favourite stack and watch me go. On the other hand, try asking me to develop a game for the Sony PlayStation, and watch me stall. </p> <p> Clearly, then, I'm a 10x developer, for the tautological reason that I'm much better at the things that I'm good at than the things I'm not good at. </p> <p> Even the greatest <a href="https://en.wikipedia.org/wiki/R_(programming_language)">R</a> developer is unlikely to be of much help on your next <a href="https://en.wikipedia.org/wiki/COBOL">COBOL</a> project. </p> <p> As always, context matters. You can be a great programmer in a particular context, and suck in another. </p> <p> This isn't limited to technology stacks. Some people prefer co-location, while others work best by themselves. Some people are detail-oriented, while others like to look at the big picture. Some people do their best work early in the morning, and others late at night. </p> <p> And some teams of 'mediocre' programmers outperform all-star teams. (This, incidentally, is a phenomenon also <a href="https://en.wikipedia.org/wiki/UEFA_Euro_1992">sometimes seen</a> in professional <a href="https://en.wikipedia.org/wiki/Association_football">Soccer</a>.) </p> <h3 id="34e113a19c8040b0bcb38f7abf1b532d"> Evidence <a href="#34e113a19c8040b0bcb38f7abf1b532d" title="permalink">#</a> </h3> <p> Unfortunately, as I explain in my <a href="https://cleancoders.com/video-details/humane-code-real-episode-1">Humane Code</a> video, I believe that you can't measure software development productivity. Thus, the notion of a 10x developer is subjective. </p> <p> The original idea, however, is decades old, and seems, at first glance, to originate in a 'study'. If you're curious about its origins, I can't recommend <a href="http://bit.ly/leprechauns-of-software-engineering">The Leprechauns of Software Engineering</a> enough. In that book, Laurent Bossavit explains just how insubstantial the evidence is. </p> <p> If the evidence is so weak, then why does the idea that 10x developers exist keep coming back? </p> <h3 id="6988798f60bf4622808b58a3e7f55bce"> 0x developers <a href="#6988798f60bf4622808b58a3e7f55bce" title="permalink">#</a> </h3> <p> I think that the reason that the belief is recurring is that (subjectively) <em>it seems so evident</em>. Barring confirmation bias, I'm sure everyone has encountered a team member that never seemed to get anything done. </p> <p> I know that I've certainly had that experience from time to time. </p> <p> The first job I had, I hated. I just couldn't muster any enthusiasm for the work, and I'd postpone and drag out as long as possible even the simplest task. That wasn't very mature, but I was 25 and it was my first job, and I didn't know how to handle the situation I found myself in. I'm sure that my colleagues back then found that I didn't pull my part. I didn't, and I'm not proud of it, but it's true. </p> <p> I believe now that I was in the wrong context. It wasn't that I was incapable of doing the job, but at that time in my career, I absolutely loathed it, and for that reason, I wasn't productive. </p> <p> Another time, I had a colleague who seemed incapable of producing anything that helped us achieve our goals. I was concerned that I'd <a href="https://en.wikipedia.org/wiki/Bozo_bit">flipped the bozo bit</a> on that colleague, so I started to collect evidence. Our Git repository had few commits from that colleague, and the few that I could find I knew had been made in collaboration with another team member. We shared an office, and I had a pretty good idea about who worked together with whom when. </p> <p> This colleague spent a lot of time talking to other people. Us, other stakeholders, or any hapless victim who didn't escape in time. Based on these meetings and discussions, we'd hear about all sorts of ideas for improvements for our code or development process, but nothing would be implemented, and rarely did it have any relevance to what we were trying to accomplish. </p> <p> I've met programmers who get nothing done more than once. Sometimes, like the above story, they're boisterous bluffs, but most often, they just sit quietly in their corner and fidget with who knows what. </p> <p> Based on the above, mind you, I'm not saying that these people are necessarily incompetent (although I suspect that some are). They might also just find themselves in a wrong context, like I did in my first job. </p> <p> It seems clear to me, then, that there's such a thing as a <em>0x developer</em>. This is a developer who gets zero times (0x) as much done as the 'average' developer. </p> <p> For that reason it seems evident to me that 10x developers exist. Any developer who regularly manages to get code deployed to production is not only ten times, but infinitely more productive than 0x developers. </p> <p> It gets worse, though. </p> <h3 id="fe07476743704027acab9c7b949bc3a4"> −nx developers <a href="#fe07476743704027acab9c7b949bc3a4" title="permalink">#</a> </h3> <p> Not only is it my experience that 0x developers exist, I also believe that I've met more than one <em>−nx developer</em>. These are developers who are <em>minus n times</em> 'more' productive than the 'baseline' developer. In other words, they are software developers who have negative productivity. </p> <p> I've never met anyone who I suspected of deliberately sabotaging our efforts; they always seem well-meaning, but some people can produce more mess than three colleagues can clean up. Yohan, above, is such an archetype. </p> <p> One colleague I had, long ago, was so bad that the rest of the team deliberately compartmentalised him/her. We'd ask him/her to work on an isolated piece of the system, knowing that (s)he would be assigned to another project after four months. We then secretly planned to throw away the code once (s)he was gone, and rewrite it. I don't know if that was the right decision, but since we had padded all other estimates accordingly, we made our deadlines without more than the usual overruns. </p> <p> If you accept the assertion that −nx developers exist, then clearly, anyone who gets anything done at all is an <em>∞x developer</em>. </p> <h3 id="8257729b743641d0afa1c2ddbfe1b0df"> Summary <a href="#8257729b743641d0afa1c2ddbfe1b0df" title="permalink">#</a> </h3> <p> 10x developers exist, but not in the way that people normally interpret the term. </p> <p> 10x developers exist because there's great variability in (perceived) productivity. Much of the variability is context-dependent, so it's less clear if some people are just 'better at programming' than others. Still, when we consider that people like <a href="https://en.wikipedia.org/wiki/Linus_Torvalds">Linus Torvalds</a> exist, it seems compelling that this might be the case. </p> <p> Most of the variability, however, I think correlates with environment. Are you working in a technology stack with which you're comfortable? Do you like what you're doing? Do you like your colleagues? Do you like your hours? Do you like your working environment? </p> <p> Still, even if we could control for all of those variables, we might still find that some people get stuff done, and some people don't. The people who get anything done are ∞x developers. </p> <p> Employers and non-technical start-up founders sometimes look for the 10x unicorns, just like they look for <em>rock star developers</em>. <blockquote> <p> "To really confuse recruiters, someone should make a programming language called Rockstar." </p> <footer><cite><a href="https://twitter.com/paulstovell/status/1013960369465782273">Paul Stovell</a></cite></footer> </blockquote> The above tweet inspired <a href="http://www.dylanbeattie.net">Dylan Beattie</a> to create <a href="https://codewithrockstar.com">the Rockstar programming language</a>. </p> <p> Perhaps we should also create a <em>10x</em> programming language, so that we could put <em>certified Rockstar programmer, 10x developer</em> on our resumes. </p> </div> <hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/09/30/10x-developers Unit testing wai applications https://blog.ploeh.dk/2019/09/23/unit-testing-wai-applications/ Mon, 23 Sep 2019 06:35:00 UTC <div id="post"> <p> <em>One way to unit test a wai application with the API provided by Network.Wai.Test.</em> </p> <p> I'm currently developing a REST API in <a href="https://www.haskell.org">Haskell</a> using <a href="https://haskell-servant.readthedocs.io">Servant</a>, and I'd like to test the HTTP API as well as the functions that I use to compose it. The Servant documentation, as well as the <em>servant</em> <a href="https://haskellstack.org">Stack</a> template, uses <a href="http://hackage.haskell.org/package/hspec">hspec</a> to drive the tests. </p> <p> I tried to develop my code with hspec, but I found it confusing and inflexible. It's possible that I only found it inflexible because I didn't understand it well enough, but I don't think you can argue with my experience of finding it confusing. </p> <p> I prefer a combination of <a href="https://hackage.haskell.org/package/HUnit">HUnit</a> and <a href="http://hackage.haskell.org/package/QuickCheck">QuickCheck</a>. It turns out that it's possible to test a <a href="http://hackage.haskell.org/package/wai">wai</a> application (including Servant) using only those test libraries. </p> <h3 id="1c7a7365bd0c425e85691625d00adcd0"> Testable HTTP requests <a href="#1c7a7365bd0c425e85691625d00adcd0" title="permalink">#</a> </h3> <p> When testing against the HTTP API itself, you want something that can simulate the HTTP traffic. That capability is provided by <a href="http://hackage.haskell.org/package/wai-extra/docs/Network-Wai-Test.html">Network.Wai.Test</a>. At first, however, it wasn't entirely clear to me how that library works, but I could see that the Servant-recommended <a href="http://hackage.haskell.org/package/hspec-wai/docs/Test-Hspec-Wai.html">Test.Hspec.Wai</a> is just a thin wrapper over <em>Network.Wai.Test</em> (notice how <a href="/2019/07/01/yes-silver-bullet">open source makes such research much easier</a>). </p> <p> It turns out that <em>Network.Wai.Test</em> enables you to run your tests in a <code>Session</code> monad. You can, for example, define a simple HTTP GET request like this: </p> <p> <pre><span style="color:blue;">import</span>&nbsp;<span style="color:blue;">qualified</span>&nbsp;Data.ByteString&nbsp;<span style="color:blue;">as</span>&nbsp;BS <span style="color:blue;">import</span>&nbsp;<span style="color:blue;">qualified</span>&nbsp;Data.ByteString.Lazy&nbsp;<span style="color:blue;">as</span>&nbsp;LBS <span style="color:blue;">import</span>&nbsp;Network.HTTP.Types <span style="color:blue;">import</span>&nbsp;Network.Wai <span style="color:blue;">import</span>&nbsp;Network.Wai.Test <span style="color:#2b91af;">get</span>&nbsp;::&nbsp;<span style="color:blue;">BS</span>.<span style="color:blue;">ByteString</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Session</span>&nbsp;<span style="color:blue;">SResponse</span> get&nbsp;url&nbsp;=&nbsp;request&nbsp;$&nbsp;setPath&nbsp;defaultRequest&nbsp;{&nbsp;requestMethod&nbsp;=&nbsp;methodGet&nbsp;}&nbsp;url </pre> </p> <p> This <code>get</code> function takes a <code>url</code> and returns a <code>Session SResponse</code>. It uses the <code>defaultRequest</code>, so it doesn't set any specific HTTP headers. </p> <p> For HTTP POST requests, I needed a function that'd POST a JSON document to a particular URL. For that purpose, I had to do a little more work: </p> <p> <pre><span style="color:#2b91af;">postJSON</span>&nbsp;::&nbsp;<span style="color:blue;">BS</span>.<span style="color:blue;">ByteString</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">LBS</span>.<span style="color:blue;">ByteString</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Session</span>&nbsp;<span style="color:blue;">SResponse</span> postJSON&nbsp;url&nbsp;json&nbsp;=&nbsp;srequest&nbsp;$&nbsp;SRequest&nbsp;req&nbsp;json &nbsp;&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;&nbsp;&nbsp;req&nbsp;=&nbsp;setPath&nbsp;defaultRequest &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;requestMethod&nbsp;=&nbsp;methodPost &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;requestHeaders&nbsp;=&nbsp;[(hContentType,&nbsp;<span style="color:#a31515;">&quot;application/json&quot;</span>)]}&nbsp;url</pre> </p> <p> This is a little more involved than the <code>get</code> function, because it also has to supply the <code>Content-Type</code> HTTP header. If you don't supply that header with the <code>application/json</code> value, your API is going to reject the request when you attempt to post a string with a JSON object. </p> <p> Apart from that, it works the same way as the <code>get</code> function. </p> <h3 id="d726d432f53b4817b5dc9716a2fabc36"> Running a test session <a href="#d726d432f53b4817b5dc9716a2fabc36" title="permalink">#</a> </h3> <p> The <code>get</code> and <code>postJSON</code> functions both return <code>Session</code> values, so a test must run in the <code>Session</code> monad. This is easily done with Haskell's <code>do</code> notation; you'll see an example of that later in the article. </p> <p> First, however, you'll need a way to run a <code>Session</code>. <em>Network.Wai.Test</em> provides a function for that, called <code>runSession</code>. Besides a <code>Session a</code> value, though, it also requires an <code>Application</code> value. </p> <p> In my test library, I already have an <code>Application</code>, although it's running in <code>IO</code> (for reasons that'll take another article to explain): </p> <p> <pre><span style="color:#2b91af;">app</span>&nbsp;::&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;<span style="color:blue;">Application</span></pre> </p> <p> With this value, you can easily convert any <code>Session a</code> to <code>IO a</code>: </p> <p> <pre><span style="color:#2b91af;">runSessionWithApp</span>&nbsp;::&nbsp;<span style="color:blue;">Session</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;a runSessionWithApp&nbsp;s&nbsp;=&nbsp;app&nbsp;&gt;&gt;=&nbsp;runSession&nbsp;s</pre> </p> <p> The next step is to figure out how to turn an <code>IO a</code> into a test. </p> <h3 id="febab39aa10d4d78bfd0bc4d3d45ca8a"> Running a property <a href="#febab39aa10d4d78bfd0bc4d3d45ca8a" title="permalink">#</a> </h3> <p> You can turn an <code>IO a</code> into a <code>Property</code> with either <code>ioProperty</code> or <code>idempotentIOProperty</code>. I admit that the documentation doesn't make the distinction between the two entirely clear, but <code>ioProperty</code> sounds like the safer choice, so that's what I went for here. </p> <p> With <code>ioProperty</code> you now have a <code>Property</code> that you can turn into a <code>Test</code> using <code>testProperty</code> from <a href="http://hackage.haskell.org/package/test-framework-quickcheck2/docs/Test-Framework-Providers-QuickCheck2.html">Test.Framework.Providers.QuickCheck2</a>: </p> <p> <pre><span style="color:#2b91af;">appProperty</span>&nbsp;::&nbsp;(<span style="color:blue;">Functor</span>&nbsp;f,&nbsp;<span style="color:blue;">Testable</span>&nbsp;prop,&nbsp;<span style="color:blue;">Testable</span>&nbsp;(f&nbsp;<span style="color:blue;">Property</span>)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&gt;&nbsp;TestName&nbsp;-&gt;&nbsp;f&nbsp;(Session&nbsp;prop)&nbsp;-&gt;&nbsp;Test appProperty&nbsp;name&nbsp;= &nbsp;&nbsp;testProperty&nbsp;name&nbsp;.&nbsp;<span style="color:blue;">fmap</span>&nbsp;(ioProperty&nbsp;.&nbsp;runSessionWithApp)</pre> </p> <p> The type of this function seems more cryptic than strictly necessary. What's that <code>Functor f</code> doing there? </p> <p> The way I've written the tests, each property receives input from QuickCheck in the form of function arguments. I could have given the <code>appProperty</code> function a more restricted type, to make it clearer what's going on: </p> <p> <pre><span style="color:#2b91af;">appProperty</span>&nbsp;::&nbsp;(<span style="color:blue;">Arbitrary</span>&nbsp;a,&nbsp;<span style="color:blue;">Show</span>&nbsp;a,&nbsp;<span style="color:blue;">Testable</span>&nbsp;prop) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&gt;&nbsp;TestName&nbsp;-&gt;&nbsp;(a&nbsp;-&gt;&nbsp;Session&nbsp;prop)&nbsp;-&gt;&nbsp;Test appProperty&nbsp;name&nbsp;= &nbsp;&nbsp;testProperty&nbsp;name&nbsp;.&nbsp;<span style="color:blue;">fmap</span>&nbsp;(ioProperty&nbsp;.&nbsp;runSessionWithApp)</pre> </p> <p> This is the same function, just with a more restricted type. It states that for any <code>Arbitrary a, Show a</code>, a test is a function that takes <code>a</code> as input and returns a <code>Session prop</code>. This restricts tests to take a single input value, which means that you'll have to write all those properties in tupled, uncurried form. You could relax that requirement by introducing a <code>newtype</code> and a type class with an instance that recursively enables curried functions. That's what <a href="http://hackage.haskell.org/package/hspec-wai/docs/Test-Hspec-Wai-QuickCheck.html">Test.Hspec.Wai.QuickCheck</a> does. I decided not to add that extra level of indirection, and instead living with having to write all my properties in tupled form. </p> <p> The <code>Functor f</code> in the above, relaxed type, then, is in actual use the Reader functor. You'll see some examples next. </p> <h3 id="0ebc8724e39149e88e5e71763b03d499"> Properties <a href="#0ebc8724e39149e88e5e71763b03d499" title="permalink">#</a> </h3> <p> You can now define some properties. Here's a simple example: </p> <p> <pre>appProperty&nbsp;<span style="color:#a31515;">&quot;responds&nbsp;with&nbsp;404&nbsp;when&nbsp;no&nbsp;reservation&nbsp;exists&quot;</span>&nbsp;$&nbsp;\rid&nbsp;-&gt;&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;actual&nbsp;&lt;-&nbsp;get&nbsp;$&nbsp;<span style="color:#a31515;">&quot;/reservations/&quot;</span>&nbsp;&lt;&gt;&nbsp;toASCIIBytes&nbsp;rid &nbsp;&nbsp;assertStatus&nbsp;404&nbsp;actual</pre> </p> <p> This is an inlined property, similar to how <a href="/2018/05/07/inlined-hunit-test-lists">I inline HUnit tests in test lists</a>. </p> <p> First, notice that the property is written as a lambda expression, which means that it fits the mould of <code>a -&gt; Session prop</code>. The input value <code>rid</code> (<em>reservationID</em>) is a <a href="http://hackage.haskell.org/package/uuid/docs/Data-UUID.html">UUID</a> value (for which an <code>Arbitrary</code> instance exists via <a href="http://hackage.haskell.org/package/quickcheck-instances">quickcheck-instances</a>). </p> <p> While the test runs in the <code>Session</code> monad, the <code>do</code> notation makes <code>actual</code> an <code>SResponse</code> value that you can then assert with <code>assertStatus</code> (from <em>Network.Wai.Test</em>). </p> <p> This property reproduces an interaction like this: </p> <p> <pre>&amp; curl -v http://localhost:8080/reservations/db38ac75-9ccd-43cc-864a-ce13e90a71d8 * Trying ::1:8080... * TCP_NODELAY set * Trying 127.0.0.1:8080... * TCP_NODELAY set * Connected to localhost (127.0.0.1) port 8080 (#0) &gt; GET /reservations/db38ac75-9ccd-43cc-864a-ce13e90a71d8 HTTP/1.1 &gt; Host: localhost:8080 &gt; User-Agent: curl/7.65.1 &gt; Accept: */* &gt; * Mark bundle as not supporting multiuse &lt; HTTP/1.1 404 Not Found &lt; Transfer-Encoding: chunked &lt; Date: Tue, 02 Jul 2019 18:09:51 GMT &lt; Server: Warp/3.2.27 &lt; * Connection #0 to host localhost left intact</pre> </p> <p> The important result is that the status code is <code>404 Not Found</code>, which is also what the property asserts. </p> <p> If you need more than one input value to your property, you have to write the property in tupled form: </p> <p> <pre>appProperty&nbsp;<span style="color:#a31515;">&quot;fails&nbsp;when&nbsp;reservation&nbsp;is&nbsp;POSTed&nbsp;with&nbsp;invalid&nbsp;quantity&quot;</span>&nbsp;$&nbsp;\ &nbsp;&nbsp;(ValidReservation&nbsp;r,&nbsp;NonNegative&nbsp;q)&nbsp;-&gt;&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;invalid&nbsp;=&nbsp;r&nbsp;{&nbsp;reservationQuantity&nbsp;=&nbsp;<span style="color:blue;">negate</span>&nbsp;q&nbsp;} &nbsp;&nbsp;actual&nbsp;&lt;-&nbsp;postJSON&nbsp;<span style="color:#a31515;">&quot;/reservations&quot;</span>&nbsp;$&nbsp;encode&nbsp;invalid &nbsp;&nbsp;assertStatus&nbsp;400&nbsp;actual</pre> </p> <p> This property still takes a single input, but that input is a tuple where the first element is a <code>ValidReservation</code> and the second element a <code>NonNegative Int</code>. The <a href="/2019/09/02/naming-newtypes-for-quickcheck-arbitraries">ValidReservation newtype wrapper</a> ensures that <code>r</code> is a valid reservation record. This ensures that the property only exercises the path where the reservation quantity is zero or negative. It accomplishes this by negating <code>q</code> and replacing the <code>reservationQuantity</code> with that negative (or zero) number. </p> <p> It then encodes (with <a href="http://hackage.haskell.org/package/aeson">aeson</a>) the <code>invalid</code> reservation and posts it using the <code>postJSON</code> function. </p> <p> Finally it asserts that the HTTP status code is <code>400 Bad Request</code>. </p> <h3 id="ae5b3f7b07634799ad2af0d9a2ac668c"> Summary <a href="#ae5b3f7b07634799ad2af0d9a2ac668c" title="permalink">#</a> </h3> <p> After having tried using <em>Test.Hspec.Wai</em> for some time, I decided to refactor my tests to QuickCheck and HUnit. Once I figured out how <em>Network.Wai.Test</em> works, the remaining work wasn't too difficult. While there's little written documentation for the modules, the types (as usual) act as documentation. Using the types, and looking a little at the underlying code, I was able to figure out how to use the test API. </p> <p> You write tests against <em>wai</em> applications in the <code>Session</code> monad. You can then use <code>runSession</code> to turn the <code>Session</code> into an <code>IO</code> value. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/09/23/unit-testing-wai-applications Picture archivist in F# https://blog.ploeh.dk/2019/09/16/picture-archivist-in-f/ Mon, 16 Sep 2019 05:59:00 UTC <div id="post"> <p> <em>A comprehensive code example showing how to implement a functional architecture in F#.</em> </p> <p> This article shows how to implement the <a href="/2019/08/26/functional-file-system">picture archivist architecture described in a previous article</a>. In short, the task is to move some image files to directories based on their date-taken metadata. The architectural idea is to load a directory structure from disk into an in-memory tree, manipulate that tree, and use the resulting tree to perform the desired actions: </p> <p> <img src="/content/binary/functional-file-system-interaction.png" alt="A functional program typically loads data, transforms it, and stores it again."> </p> <p> Much of the program will manipulate the tree data, which is immutable. </p> <p> The previous article showed how to implement the <a href="/2019/09/09/picture-archivist-in-haskell">picture archivist architecture in Haskell</a>. In this article, you'll see how to do it in <a href="https://fsharp.org">F#</a>. This is essentially a port of the <a href="https://www.haskell.org">Haskell</a> code. </p> <h3 id="949a876ffec843e09d4faa5ae1c1b4c5"> Tree <a href="#949a876ffec843e09d4faa5ae1c1b4c5" title="permalink">#</a> </h3> <p> You can start by defining a <a href="https://en.wikipedia.org/wiki/Rose_tree">rose tree</a>: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;Tree&lt;&#39;a,&nbsp;&#39;b&gt;&nbsp;=&nbsp;Node&nbsp;<span style="color:blue;">of</span>&nbsp;&#39;a&nbsp;*&nbsp;Tree&lt;&#39;a,&nbsp;&#39;b&gt;&nbsp;list&nbsp;|&nbsp;Leaf&nbsp;<span style="color:blue;">of</span>&nbsp;&#39;b</pre> </p> <p> If you wanted to, you could put all the <code>Tree</code> code in a reusable library, because none of it is coupled to a particular application, such as <a href="https://amzn.to/2V06Kji">moving pictures</a>. You could also write a comprehensive test suite for the following functions, but in this article, I'll skip that. </p> <p> Notice that this sort of tree explicitly distinguishes between internal and leaf nodes. This is necessary because you'll need to keep track of the directory names (the internal nodes), while at the same time you'll want to enrich the leaves with additional data - data that you can't meaningfully add to the internal nodes. You'll see this later in the article. </p> <p> While I typically tend to define F# types outside of modules (so that you don't have to, say, prefix the type name with the module name - <code>Tree.Tree</code> is so awkward), the rest of the tree code goes into a module, including two helper functions: </p> <p> <pre><span style="color:blue;">module</span>&nbsp;Tree&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;&#39;b&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;leaf&nbsp;=&nbsp;Leaf &nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;&#39;a&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;list&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;node&nbsp;x&nbsp;xs&nbsp;=&nbsp;Node&nbsp;(x,&nbsp;xs)</pre> </p> <p> The <code>leaf</code> function doesn't add much value, but the <code>node</code> function offers a curried alternative to the <code>Node</code> case constructor. That's occasionally useful. </p> <p> The rest of the code related to trees is also defined in the <code>Tree</code> module, but I'm going to present it formatted as free-standing functions. If you're confused about the layout of the code, the entire code base is <a href="https://github.com/ploeh/picture-archivist">available on GitHub</a>. </p> <p> The <a href="/2019/08/05/rose-tree-catamorphism">rose tree catamorphism</a> is this <code>cata</code> function: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;c&nbsp;list&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;(&#39;b&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;&#39;c</span> <span style="color:blue;">let</span>&nbsp;<span style="color:blue;">rec</span>&nbsp;cata&nbsp;fd&nbsp;ff&nbsp;=&nbsp;<span style="color:blue;">function</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;Leaf&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;ff&nbsp;x &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;Node&nbsp;(x,&nbsp;xs)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;xs&nbsp;|&gt;&nbsp;List.map&nbsp;(cata&nbsp;fd&nbsp;ff)&nbsp;|&gt;&nbsp;fd&nbsp;x</pre> </p> <p> In the corresponding Haskell implementation of this architecture, I called this function <code>foldTree</code>, so why not retain that name? The short answer is that the naming conventions differ between Haskell and F#, and while I favour learning from Haskell, I still want my F# code to be as <a href="/2015/08/03/idiomatic-or-idiosyncratic">idiomatic</a> as possible. </p> <p> While I don't enforce that client code <em>must</em> use the <code>Tree</code> module name to access the functions within, I prefer to name the functions so that they make sense when used with qualified access. Having to write <code>Tree.foldTree</code> seems redundant. A more idiomatic name would be <code>fold</code>, so that you could write <code>Tree.fold</code>. The problem with that name, though, is that <code>fold</code> usually implies a list-biased <em>fold</em> (corresponding to <code>foldl</code> in Haskell), and I'll actually need that name for that particular purpose later. </p> <p> So, <code>cata</code> it is. </p> <p> In this article, tree functionality is (with one exception) directly or transitively implemented with <code>cata</code>. </p> <h3 id="3f30722983ad47bd83c88cec4ba80983"> Filtering trees <a href="#3f30722983ad47bd83c88cec4ba80983" title="permalink">#</a> </h3> <p> It'll be useful to be able to filter the contents of a tree. For example, the picture archivist program will only move image files with valid metadata. This means that it'll need to filter out all files that aren't image files, as well as image files without valid metadata. </p> <p> It turns out that it'll be useful to supply a function that throws away <code>None</code> values from a tree of <code>option</code> leaves. This is similar to <a href="https://msdn.microsoft.com/en-us/visualfsharpdocs/conceptual/list.choose%5B't%2C'u%5D-function-%5Bfsharp%5D">List.choose</a>, so I call it <code>Tree.choose</code>: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b&nbsp;option)&nbsp;-&gt;&nbsp;Tree&lt;&#39;c,&#39;a&gt;&nbsp;-&gt;&nbsp;Tree&lt;&#39;c,&#39;b&gt;&nbsp;option</span> <span style="color:blue;">let</span>&nbsp;choose&nbsp;f&nbsp;=&nbsp;cata&nbsp;(<span style="color:blue;">fun</span>&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;List.choose&nbsp;id&nbsp;&gt;&gt;&nbsp;node&nbsp;x&nbsp;&gt;&gt;&nbsp;Some)&nbsp;(f&nbsp;&gt;&gt;&nbsp;Option.map&nbsp;Leaf)</pre> </p> <p> You may find the type of the function surprising. Why does it return a <code>Tree option</code>, instead of simply a <code>Tree</code>? </p> <p> While <code>List.choose</code> simply returns a list, it can do this because lists can be empty. This <code>Tree</code> type, on the other hand, can't be empty. If the purpose of <code>Tree.choose</code> is to throw away all <code>None</code> values, then how do you return a tree from <code>Leaf None</code>? </p> <p> You can't return a <code>Leaf</code> because you have no value to put in the leaf. Similarly, you can't return a <code>Node</code> because, again, you have no value to put in the node. </p> <p> In order to handle this edge case, then, you'll have to return <code>None</code>: </p> <p> <pre>&gt; let l : Tree&lt;string, int option&gt; = Leaf None;; val l : Tree&lt;string,int option&gt; = Leaf None &gt; Tree.choose id l;; val it : Tree&lt;string,int&gt; option = None</pre> </p> <p> If you have anything other than a <code>None</code> leaf, though, you'll get a proper tree, but wrapped in an <code>option</code>: </p> <p> <pre>&gt; Tree.node "Foo" [Leaf (Some 42); Leaf None; Leaf (Some 2112)] |&gt; Tree.choose id;; val it : Tree&lt;string,int&gt; option = Some (Node ("Foo",[Leaf 42; Leaf 2112]))</pre> </p> <p> While the resulting tree is wrapped in a <code>Some</code> case, the leaves contain unwrapped values. </p> <h3 id="32f46f2c16cf428abc39c3d79433caa6"> Bifunctor, functor, and folds <a href="#32f46f2c16cf428abc39c3d79433caa6" title="permalink">#</a> </h3> <p> Through its type class language feature, Haskell has formal definitions of <a href="/2018/03/22/functors">functors</a>, <a href="/2018/12/24/bifunctors">bifunctors</a>, and other types of <em>folds</em> (list-biased <a href="/2019/04/29/catamorphisms">catamorphisms</a>). F# doesn't have a similar degree of formalism, which means that while you can still implement the corresponding functionality, you'll have to rely on conventions to make the functions recognisable. </p> <p> It's straighforward to start with the bifunctor functionality: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b)&nbsp;-&gt;&nbsp;(&#39;c&nbsp;-&gt;&nbsp;&#39;d)&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;c&gt;&nbsp;-&gt;&nbsp;Tree&lt;&#39;b,&#39;d&gt;</span> <span style="color:blue;">let</span>&nbsp;bimap&nbsp;f&nbsp;g&nbsp;=&nbsp;cata&nbsp;(f&nbsp;&gt;&gt;&nbsp;node)&nbsp;(g&nbsp;&gt;&gt;&nbsp;leaf)</pre> </p> <p> This is, apart from the syntax differences, the same implementation as in Haskell. Based on <code>bimap</code>, you can also trivially implement <code>mapNode</code> and <code>mapLeaf</code> functions if you'd like, but you're not going to need those for the code in this article. You do need, however, a function that we could consider an alias of a hypothetical <code>mapLeaf</code> function: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;b&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;c&gt;</span> <span style="color:blue;">let</span>&nbsp;map&nbsp;f&nbsp;=&nbsp;bimap&nbsp;id&nbsp;f</pre> </p> <p> This makes <code>Tree</code> a functor. </p> <p> It'll also be useful to reduce a tree to a potentially more compact value, so you can add some specialised folds: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;c&nbsp;-&gt;&nbsp;&#39;a&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;(&#39;c&nbsp;-&gt;&nbsp;&#39;b&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;&#39;c</span> <span style="color:blue;">let</span>&nbsp;bifold&nbsp;f&nbsp;g&nbsp;z&nbsp;t&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;flip&nbsp;f&nbsp;x&nbsp;y&nbsp;=&nbsp;f&nbsp;y&nbsp;x &nbsp;&nbsp;&nbsp;&nbsp;cata&nbsp;(<span style="color:blue;">fun</span>&nbsp;x&nbsp;xs&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;flip&nbsp;f&nbsp;x&nbsp;&gt;&gt;&nbsp;List.fold&nbsp;(&gt;&gt;)&nbsp;id&nbsp;xs)&nbsp;(flip&nbsp;g)&nbsp;t&nbsp;z <span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;(&#39;b&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;&#39;c</span> <span style="color:blue;">let</span>&nbsp;bifoldBack&nbsp;f&nbsp;g&nbsp;t&nbsp;z&nbsp;=&nbsp;cata&nbsp;(<span style="color:blue;">fun</span>&nbsp;x&nbsp;xs&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;List.foldBack&nbsp;(&lt;&lt;)&nbsp;xs&nbsp;id&nbsp;&gt;&gt;&nbsp;f&nbsp;x)&nbsp;g&nbsp;t&nbsp;z</pre> </p> <p> In an attempt to emulate the F# naming conventions, I named the functions as I did. There are similar functions in the <code>List</code> and <code>Option</code> modules, for instance. If you're comparing the F# code with the Haskell code in the previous article, <code>Tree.bifold</code> corresponds to <code>bifoldl</code>, and <code>Tree.bifoldBack</code> corresponds to <code>bifoldr</code>. </p> <p> These enable you to implement folds over leaves only: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;c&nbsp;-&gt;&nbsp;&#39;b&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;&#39;c</span> <span style="color:blue;">let</span>&nbsp;fold&nbsp;f&nbsp;=&nbsp;bifold&nbsp;(<span style="color:blue;">fun</span>&nbsp;x&nbsp;_&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;x)&nbsp;f <span style="color:green;">//&nbsp;(&#39;b&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;&#39;c</span> <span style="color:blue;">let</span>&nbsp;foldBack&nbsp;f&nbsp;=&nbsp;bifoldBack&nbsp;(<span style="color:blue;">fun</span>&nbsp;_&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;x)&nbsp;f</pre> </p> <p> These, again, enable you to implement another function that'll turn out to be useful in this article: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;b&nbsp;-&gt;&nbsp;unit)&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;unit</span> <span style="color:blue;">let</span>&nbsp;iter&nbsp;f&nbsp;=&nbsp;fold&nbsp;(<span style="color:blue;">fun</span>&nbsp;()&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;f&nbsp;x)&nbsp;()</pre> </p> <p> The picture archivist program isn't going to explicitly need all of these, but transitively, it will. </p> <h3 id="8a9a50c69a2d461cac5bb87fa4cf3cd9"> Moving pictures <a href="#8a9a50c69a2d461cac5bb87fa4cf3cd9" title="permalink">#</a> </h3> <p> So far, all the code shown here could be in a general-purpose reusable library, since it contains no functionality specifically related to image files. The rest of the code in this article, however, will be specific to the program. I'll put the domain model code in another module that I call <code>Archive</code>. Later in the article, we'll look at how to load a tree from the file system, but for now, we'll just pretend that we have such a tree. </p> <p> The major logic of the program is to create a destination tree based on a source tree. The leaves of the tree will have to carry some extra information apart from a file path, so you can introduce a specific type to capture that information: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;PhotoFile&nbsp;=&nbsp;{&nbsp;File&nbsp;:&nbsp;FileInfo;&nbsp;TakenOn&nbsp;:&nbsp;DateTime&nbsp;}</pre> </p> <p> A <code>PhotoFile</code> not only contains the file path for an image file, but also the date the photo was taken. This date can be extracted from the file's metadata, but that's an impure operation, so we'll delegate that work to the start of the program. We'll return to that later. </p> <p> Given a source tree of <code>PhotoFile</code> leaves, though, the program must produce a destination tree of files: </p> <p> <pre><span style="color:green;">//&nbsp;string&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,PhotoFile&gt;&nbsp;-&gt;&nbsp;Tree&lt;string,FileInfo&gt;</span> <span style="color:blue;">let</span>&nbsp;moveTo&nbsp;destination&nbsp;t&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;dirNameOf&nbsp;(dt&nbsp;:&nbsp;DateTime)&nbsp;=&nbsp;sprintf&nbsp;<span style="color:#a31515;">&quot;%d-%02d&quot;</span>&nbsp;dt.Year&nbsp;dt.Month &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;groupByDir&nbsp;pf&nbsp;m&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;key&nbsp;=&nbsp;dirNameOf&nbsp;pf.TakenOn &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;dir&nbsp;=&nbsp;Map.tryFind&nbsp;key&nbsp;m&nbsp;|&gt;&nbsp;Option.defaultValue&nbsp;[] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Map.add&nbsp;key&nbsp;(pf.File&nbsp;::&nbsp;dir)&nbsp;m &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;addDir&nbsp;name&nbsp;files&nbsp;dirs&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Tree.node&nbsp;name&nbsp;(List.map&nbsp;Leaf&nbsp;files)&nbsp;::&nbsp;dirs &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;m&nbsp;=&nbsp;Tree.foldBack&nbsp;groupByDir&nbsp;t&nbsp;Map.empty &nbsp;&nbsp;&nbsp;&nbsp;Map.foldBack&nbsp;addDir&nbsp;m&nbsp;[]&nbsp;|&gt;&nbsp;Tree.node&nbsp;destination</pre> </p> <p> This <code>moveTo</code> function looks, perhaps, overwhelming, but it's composed of three conceptual steps: <ol> <li>Create a map of destination folders (<code>m</code>).</li> <li>Create a list of branches from the map (<code>Map.foldBack addDir m []</code>).</li> <li>Create a tree from the list (<code>Tree.node destination</code>).</li> </ol> The <code>moveTo</code> function starts by folding the input data into a map <code>m</code>. The map is keyed by the directory name, which is formatted by the <code>dirNameOf</code> function. This function takes a <code>DateTime</code> as input and formats it to a <code>YYYY-MM</code> format. For example, December 20, 2018 becomes <code>"2018-12"</code>. </p> <p> The entire mapping step groups the <code>PhotoFile</code> values into a map of the type <code>Map&lt;string,FileInfo list&gt;</code>. All the image files taken in April 2014 are added to the list with the <code>"2014-04"</code> key, all the image files taken in July 2011 are added to the list with the <code>"2011-07"</code> key, and so on. </p> <p> In the next step, the <code>moveTo</code> function converts the map to a list of trees. This will be the branches (or sub-directories) of the <code>destination</code> directory. Because of the desired structure of the destination tree, this is a list of shallow branches. Each node contains only leaves. </p> <p> <img src="/content/binary/shallow-photo-destination-directories.png" alt="Shallow photo destination directories."> </p> <p> The only remaining step is to add that list of branches to a <code>destination</code> node. This is done by piping (<code>|&gt;</code>) the list of sub-directories into <code>Tree.node destination</code>. </p> <p> Since this is a <a href="https://en.wikipedia.org/wiki/Pure_function">pure function</a>, it's <a href="/2015/05/07/functional-design-is-intrinsically-testable">easy to unit test</a>. Just create some test cases and call the function. First, the test cases. </p> <p> In this code base, I'm using <a href="https://xunit.github.io">xUnit.net</a> 2.4.1, so I'll first create a set of test cases as a test-specific class: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;MoveToDestinationTestData&nbsp;()&nbsp;<span style="color:blue;">as</span>&nbsp;this&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">inherit</span>&nbsp;TheoryData&lt;Tree&lt;string,&nbsp;PhotoFile&gt;,&nbsp;string,&nbsp;Tree&lt;string,&nbsp;string&gt;&gt;&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;photoLeaf&nbsp;name&nbsp;(y,&nbsp;mth,&nbsp;d,&nbsp;h,&nbsp;m,&nbsp;s)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;{&nbsp;File&nbsp;=&nbsp;FileInfo&nbsp;name;&nbsp;TakenOn&nbsp;=&nbsp;DateTime&nbsp;(y,&nbsp;mth,&nbsp;d,&nbsp;h,&nbsp;m,&nbsp;s)&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;(2018,&nbsp;11,&nbsp;9,&nbsp;11,&nbsp;47,&nbsp;17), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>,&nbsp;[Node&nbsp;(<span style="color:#a31515;">&quot;2018-11&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>])])) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;S&quot;</span>,&nbsp;[photoLeaf&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>&nbsp;(1972,&nbsp;6,&nbsp;6,&nbsp;16,&nbsp;15,&nbsp;0)]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;D&quot;</span>,&nbsp;[Node&nbsp;(<span style="color:#a31515;">&quot;1972-06&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>])])) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;S&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;L&quot;</span>&nbsp;(2002,&nbsp;10,&nbsp;12,&nbsp;17,&nbsp;16,&nbsp;15); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;J&quot;</span>&nbsp;(2007,&nbsp;4,&nbsp;21,&nbsp;17,&nbsp;18,&nbsp;19)]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;D&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2002-10&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;L&quot;</span>]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2007-04&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;J&quot;</span>])])) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;(2010,&nbsp;1,&nbsp;12,&nbsp;17,&nbsp;16,&nbsp;15); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;(2010,&nbsp;3,&nbsp;12,&nbsp;17,&nbsp;16,&nbsp;15); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>&nbsp;(2010,&nbsp;1,&nbsp;21,&nbsp;17,&nbsp;18,&nbsp;19)]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2010-01&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>;&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2010-03&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>])])) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;bar&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;(2010,&nbsp;1,&nbsp;12,&nbsp;17,&nbsp;16,&nbsp;15); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;(2010,&nbsp;3,&nbsp;12,&nbsp;17,&nbsp;16,&nbsp;15); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>&nbsp;(2010,&nbsp;1,&nbsp;21,&nbsp;17,&nbsp;18,&nbsp;19)]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;baz&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;d&quot;</span>&nbsp;(2010,&nbsp;3,&nbsp;1,&nbsp;2,&nbsp;3,&nbsp;4); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;e&quot;</span>&nbsp;(2011,&nbsp;3,&nbsp;4,&nbsp;3,&nbsp;2,&nbsp;1)])]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#a31515;">&quot;qux&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;qux&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2010-01&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>;&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2010-03&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>;&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;d&quot;</span>]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2011-03&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;e&quot;</span>])]))</pre> </p> <p> That looks like a lot of code, but is really just a list of test cases. Each test case is a triple of a source tree, a destination directory name, and an expected result (another tree). </p> <p> The test itself, on the other hand, is compact: </p> <p> <pre>[&lt;Theory;&nbsp;ClassData(typeof&lt;MoveToDestinationTestData&gt;)&gt;] <span style="color:blue;">let</span>&nbsp;``Move&nbsp;to&nbsp;destination``&nbsp;source&nbsp;destination&nbsp;expected&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;Archive.moveTo&nbsp;destination&nbsp;source &nbsp;&nbsp;&nbsp;&nbsp;expected&nbsp;=!&nbsp;Tree.map&nbsp;string&nbsp;actual</pre> </p> <p> The <code>=!</code> operator comes from <a href="https://github.com/SwensenSoftware/unquote">Unquote</a> and means something like <em>must equal</em>. It's an assertion that will throw an exception if <code>expected</code> isn't equal to <code>Tree.map string actual</code>. </p> <p> The reason that the assertion maps <code>actual</code> to a tree of strings is that <code>actual</code> is a <code>Tree&lt;string,FileInfo&gt;</code>, but <code>FileInfo</code> doesn't have structural equality. So either I had to implement a test-specific equality comparer for <code>FileInfo</code> (and for <code>Tree&lt;string,FileInfo&gt;</code>), or map the tree to something with proper equality, such as a <code>string</code>. I chose the latter. </p> <h3 id="abe95ba6865745bc9df8004079d8a250"> Calculating moves <a href="#abe95ba6865745bc9df8004079d8a250" title="permalink">#</a> </h3> <p> One pure step remains. The result of calling the <code>moveTo</code> function is a tree with the desired structure. In order to actually move the files, though, for each file you'll need to keep track of both the source path and the destination path. To make that explicit, you can define a type for that purpose: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;Move&nbsp;=&nbsp;{&nbsp;Source&nbsp;:&nbsp;FileInfo;&nbsp;Destination&nbsp;:&nbsp;FileInfo&nbsp;}</pre> </p> <p> A <code>Move</code> is simply a data structure. Contrast this with typical object-oriented design, where it would be a (possibly polymorphic) method on an object. In functional programming, you'll regularly model <em>intent</em> with a data structure. As long as intents remain data, you can easily manipulate them, and once you're done with that, you can run an interpreter over your data structure to perform the work you want accomplished. </p> <p> The unit test cases for the <code>moveTo</code> function suggest that file names are local file names like <code>"L"</code>, <code>"J"</code>, <code>"a"</code>, and so on. That was only to make the tests as compact as possible, since the function actually doesn't manipulate the specific <code>FileInfo</code> objects. </p> <p> In reality, the file names will most likely be longer, and they could also contain the full path, instead of the local path: <code>"C:\foo\bar\a.jpg"</code>. </p> <p> If you call <code>moveTo</code> with a tree where each leaf has a fully qualified path, the output tree will have the desired structure of the destination tree, but the leaves will still contain the full path to each source file. That means that you can calculate a <code>Move</code> for each file: </p> <p> <pre><span style="color:green;">//&nbsp;Tree&lt;string,FileInfo&gt;&nbsp;-&gt;&nbsp;Tree&lt;string,Move&gt;</span> <span style="color:blue;">let</span>&nbsp;calculateMoves&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;replaceDirectory&nbsp;(f&nbsp;:&nbsp;FileInfo)&nbsp;d&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;FileInfo&nbsp;(Path.Combine&nbsp;(d,&nbsp;f.Name)) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:blue;">rec</span>&nbsp;imp&nbsp;path&nbsp;=&nbsp;<span style="color:blue;">function</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;Leaf&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;{&nbsp;Source&nbsp;=&nbsp;x;&nbsp;Destination&nbsp;=&nbsp;replaceDirectory&nbsp;x&nbsp;path&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;Node&nbsp;(x,&nbsp;xs)&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;newNPath&nbsp;=&nbsp;Path.Combine&nbsp;(path,&nbsp;x) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Tree.node&nbsp;newNPath&nbsp;(List.map&nbsp;(imp&nbsp;newNPath)&nbsp;xs) &nbsp;&nbsp;&nbsp;&nbsp;imp&nbsp;<span style="color:#a31515;">&quot;&quot;</span></pre> </p> <p> This function takes as input a <code>Tree&lt;string,FileInfo&gt;</code>, which is compatible with the output of <code>moveTo</code>. It returns a <code>Tree&lt;string,Move&gt;</code>, i.e. a tree where the leaves are <code>Move</code> values. </p> <p> Earlier, I wrote that you can implement desired <code>Tree</code> functionality with the <code>cata</code> function, but that was a simplification. If you can implement the functionality of <code>calculateMoves</code> with <code>cata</code>, I don't know how. You can, however, implement it using explicit pattern matching and simple recursion. </p> <p> The <code>imp</code> function builds up a file path as it recursively negotiates the tree. All <code>Leaf</code> nodes are converted to a <code>Move</code> value using the leaf node's current <code>FileInfo</code> value as the <code>Source</code>, and the <code>path</code> to figure out the desired <code>Destination</code>. </p> <p> This code is still easy to unit test. First, test cases: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;CalculateMovesTestData&nbsp;()&nbsp;<span style="color:blue;">as</span>&nbsp;this&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">inherit</span>&nbsp;TheoryData&lt;Tree&lt;string,&nbsp;FileInfo&gt;,&nbsp;Tree&lt;string,&nbsp;(string&nbsp;*&nbsp;string)&gt;&gt;&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;(Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>),&nbsp;Leaf&nbsp;(<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>)) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;[Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>)]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;[Leaf&nbsp;(<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>))])) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;[Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>);&nbsp;Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>)]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(<span style="color:#a31515;">&quot;2&quot;</span>,&nbsp;Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>))])) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;b&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>)]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;c&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;3&quot;</span>)])]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>),&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(<span style="color:#a31515;">&quot;2&quot;</span>,&nbsp;Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>))]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>),&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(<span style="color:#a31515;">&quot;3&quot;</span>,&nbsp;Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;3&quot;</span>))])]))</pre> </p> <p> The test cases in this parametrised test are tuples of an input tree and the expected tree. For each test case, the test calls the <code>Archive.calculateMoves</code> function with <code>tree</code> and asserts that the <code>actual</code> tree is equal to the <code>expected</code> tree: </p> <p> <pre>[&lt;Theory;&nbsp;ClassData(typeof&lt;CalculateMovesTestData&gt;)&gt;] <span style="color:blue;">let</span>&nbsp;``Calculate&nbsp;moves``&nbsp;tree&nbsp;expected&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;Archive.calculateMoves&nbsp;tree &nbsp;&nbsp;&nbsp;&nbsp;expected&nbsp;=!&nbsp;Tree.map&nbsp;(<span style="color:blue;">fun</span>&nbsp;m&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(m.Source.ToString&nbsp;(),&nbsp;m.Destination.ToString&nbsp;()))&nbsp;actual</pre> </p> <p> Again, the test maps <code>FileInfo</code> objects to <code>strings</code> to support easy comparison. </p> <p> That's all the pure code you need in order to implement the desired functionality. Now you only need to write some code that loads a tree from disk, and imprints a destination tree to disk, as well as the code that composes it all. </p> <h3 id="bac6be79cf8c44a7b47923e2ec90d99f"> Loading a tree from disk <a href="#bac6be79cf8c44a7b47923e2ec90d99f" title="permalink">#</a> </h3> <p> The remaining code in this article is impure. You could put it in dedicated modules, but for this program, you're only going to need three functions and a bit of composition code, so you could also just put it all in the <code>Program</code> module. That's what I did. </p> <p> To load a tree from disk, you'll need a root directory, under which you load the entire tree. Given a directory path, you read a tree using a recursive function like this: </p> <p> <pre><span style="color:green;">//&nbsp;string&nbsp;-&gt;&nbsp;Tree&lt;string,string&gt;</span> <span style="color:blue;">let</span>&nbsp;<span style="color:blue;">rec</span>&nbsp;readTree&nbsp;path&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;File.Exists&nbsp;path &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">then</span>&nbsp;Leaf&nbsp;path &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;dirsAndFiles&nbsp;=&nbsp;Directory.EnumerateFileSystemEntries&nbsp;path &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;branches&nbsp;=&nbsp;Seq.map&nbsp;readTree&nbsp;dirsAndFiles&nbsp;|&gt;&nbsp;Seq.toList &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(path,&nbsp;branches)</pre> </p> <p> This recursive function starts by checking whether the <code>path</code> is a file that exists. If it does, the path is a file, so it creates a new <code>Leaf</code> with that path. </p> <p> If <code>path</code> isn't a file, it's a directory. In that case, use <code>Directory.EnumerateFileSystemEntries</code> to enumerate all the directories and files in that directory, and map all those directory entries recursively. That produces all the <code>branches</code> for the current node. Finally, return a new <code>Node</code> with the <code>path</code> and the <code>branches</code>. </p> <h3 id="7f5e06eb61024264ad214d41b63a8a74"> Loading metadata <a href="#7f5e06eb61024264ad214d41b63a8a74" title="permalink">#</a> </h3> <p> The <code>readTree</code> function only produces a tree with <code>string</code> leaves, while the program requires a tree with <code>PhotoFile</code> leaves. You'll need to read the <a href="https://en.wikipedia.org/wiki/Exif">Exif</a> metadata from each file and enrich the tree with the <em>date-taken</em> data. </p> <p> In this code base, I've written a little <code>Photo</code> module to extract the desired metadata from an image file. I'm not going to list all the code here; if you're interested, the code is <a href="https://github.com/ploeh/picture-archivist">available on GitHub</a>. The <code>Photo</code> module enables you to write an impure operation like this: </p> <p> <pre><span style="color:green;">//&nbsp;FileInfo&nbsp;-&gt;&nbsp;PhotoFile&nbsp;option</span> <span style="color:blue;">let</span>&nbsp;readPhoto&nbsp;file&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;Photo.extractDateTaken&nbsp;file &nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;Option.map&nbsp;(<span style="color:blue;">fun</span>&nbsp;dateTaken&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;{&nbsp;File&nbsp;=&nbsp;file;&nbsp;TakenOn&nbsp;=&nbsp;dateTaken&nbsp;})</pre> </p> <p> This operation can fail for various reasons: <ul> <li>The file may not exist.</li> <li>The file exists, but has no metadata.</li> <li>The file has metadata, but no <em>date-taken</em> metadata.</li> <li>The <em>date-taken</em> metadata string is malformed.</li> </ul> When you traverse a <code>Tree&lt;string,string&gt;</code> with <code>readPhoto</code>, you'll get a <code>Tree&lt;string,PhotoFile option&gt;</code>. That's when you'll need <code>Tree.choose</code>. You'll see this soon. </p> <h3 id="59159ef499884e10ae92e5ef6e666c36"> Writing a tree to disk <a href="#59159ef499884e10ae92e5ef6e666c36" title="permalink">#</a> </h3> <p> The above <code>calculateMoves</code> function creates a <code>Tree&lt;string,Move&gt;</code>. The final piece of impure code you'll need to write is an operation that traverses such a tree and executes each <code>Move</code>. </p> <p> <pre><span style="color:green;">//&nbsp;Tree&lt;&#39;a,Move&gt;&nbsp;-&gt;&nbsp;unit</span> <span style="color:blue;">let</span>&nbsp;writeTree&nbsp;t&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;copy&nbsp;m&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Directory.CreateDirectory&nbsp;m.Destination.DirectoryName&nbsp;|&gt;&nbsp;ignore &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m.Source.CopyTo&nbsp;m.Destination.FullName&nbsp;|&gt;&nbsp;ignore &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printfn&nbsp;<span style="color:#a31515;">&quot;Copied&nbsp;to&nbsp;%s&quot;</span>&nbsp;m.Destination.FullName &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;compareFiles&nbsp;m&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;sourceStream&nbsp;=&nbsp;File.ReadAllBytes&nbsp;m.Source.FullName &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;destinationStream&nbsp;=&nbsp;File.ReadAllBytes&nbsp;m.Destination.FullName &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sourceStream&nbsp;=&nbsp;destinationStream &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;move&nbsp;m&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;copy&nbsp;m &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;compareFiles&nbsp;m&nbsp;<span style="color:blue;">then</span>&nbsp;m.Source.Delete&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;Tree.iter&nbsp;move&nbsp;t</pre> </p> <p> The <code>writeTree</code> function traverses the input tree, and for each <code>Move</code>, it first copies the file, then it verifies that the copy was successful, and finally, if that's the case, it deletes the source file. </p> <h3 id="f30093164b184bbf877f307fa4cf4c63"> Composition <a href="#f30093164b184bbf877f307fa4cf4c63" title="permalink">#</a> </h3> <p> You can now compose an <em>impure-pure-impure sandwich</em> from all the Lego pieces: </p> <p> <pre><span style="color:green;">//&nbsp;string&nbsp;-&gt;&nbsp;string&nbsp;-&gt;&nbsp;unit</span> <span style="color:blue;">let</span>&nbsp;movePhotos&nbsp;source&nbsp;destination&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;sourceTree&nbsp;=&nbsp;readTree&nbsp;source&nbsp;|&gt;&nbsp;Tree.map&nbsp;FileInfo &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;photoTree&nbsp;=&nbsp;Tree.choose&nbsp;readPhoto&nbsp;sourceTree &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;destinationTree&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Option.map&nbsp;(Archive.moveTo&nbsp;destination&nbsp;&gt;&gt;&nbsp;Archive.calculateMoves)&nbsp;photoTree &nbsp;&nbsp;&nbsp;&nbsp;Option.iter&nbsp;writeTree&nbsp;destinationTree</pre> </p> <p> First, you load the <code>sourceTree</code> using the <code>readTree</code> operation. This returns a <code>Tree&lt;string,string&gt;</code>, so map the leaves to <code>FileInfo</code> objects. You then load the image metatadata by traversing <code>sourceTree</code> with <code>Tree.choose readPhoto</code>. Each call to <code>readPhoto</code> produces a <code>PhotoFile option</code>, so this is where you want to use <code>Tree.choose</code> to throw all the <code>None</code> values away. </p> <p> Those two lines of code is the initial impure step of the sandwich (yes: mixed metaphors, I know). </p> <p> The pure part of the sandwich is the composition of the pure functions <code>moveTo</code> and <code>calculateMoves</code>. Since <code>photoTree</code> is a <code>Tree&lt;string,PhotoFile&gt; option</code>, you'll need to perform that transformation inside of <code>Option.map</code>. The resulting <code>destinationTree</code> is a <code>Tree&lt;string,Move&gt; option</code>. </p> <p> The final, impure step of the sandwich, then, is to apply all the moves with <code>writeTree</code>. </p> <h3 id="ab0013f79c184586a10aa014db496bef"> Execution <a href="#ab0013f79c184586a10aa014db496bef" title="permalink">#</a> </h3> <p> The <code>movePhotos</code> operation takes <code>source</code> and <code>destination</code> arguments. You could hypothetically call it from a rich client or a background process, but here I'll just call if from a command-line program. The <code>main</code> operation will have to parse the input arguments and call <code>movePhotos</code>: </p> <p> <pre>[&lt;EntryPoint&gt;] <span style="color:blue;">let</span>&nbsp;main&nbsp;argv&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">match</span>&nbsp;argv&nbsp;<span style="color:blue;">with</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;[|source;&nbsp;destination|]&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;movePhotos&nbsp;source&nbsp;destination &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;_&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;printfn&nbsp;<span style="color:#a31515;">&quot;Please&nbsp;provide&nbsp;source&nbsp;and&nbsp;destination&nbsp;directories&nbsp;as&nbsp;arguments.&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;0&nbsp;<span style="color:green;">//&nbsp;return&nbsp;an&nbsp;integer&nbsp;exit&nbsp;code</span></pre> </p> <p> You could write more sophisticated parsing of the program arguments, but that's not the topic of this article, so I only wrote the bare minimum required to get the program working. </p> <p> You can now compile and run the program: </p> <p> <pre>$ ./ArchivePictures "C:\Users\mark\Desktop\Test" "C:\Users\mark\Desktop\Test-Out" Copied to C:\Users\mark\Desktop\Test-Out\2003-04\2003-04-29 15.11.50.jpg Copied to C:\Users\mark\Desktop\Test-Out\2011-07\2011-07-10 13.09.36.jpg Copied to C:\Users\mark\Desktop\Test-Out\2014-04\2014-04-18 14.05.02.jpg Copied to C:\Users\mark\Desktop\Test-Out\2014-04\2014-04-17 17.11.40.jpg Copied to C:\Users\mark\Desktop\Test-Out\2014-05\2014-05-23 16.07.20.jpg Copied to C:\Users\mark\Desktop\Test-Out\2014-06\2014-06-21 16.48.40.jpg Copied to C:\Users\mark\Desktop\Test-Out\2014-06\2014-06-30 15.44.52.jpg Copied to C:\Users\mark\Desktop\Test-Out\2016-05\2016-05-01 09.25.23.jpg Copied to C:\Users\mark\Desktop\Test-Out\2017-08\2017-08-22 19.53.28.jpg</pre> </p> <p> This does indeed produce the expected destination directory structure. </p> <p> <img src="/content/binary/picture-archivist-destination-directory.png" alt="Seven example directories with pictures."> </p> <p> It's always nice when something turns out to work in practice, as well as in theory. </p> <h3 id="3e4503b89d8f4b81b8b9cac9d1f39021"> Summary <a href="#3e4503b89d8f4b81b8b9cac9d1f39021" title="permalink">#</a> </h3> <p> <a href="/2018/11/19/functional-architecture-a-definition">Functional software architecture</a> involves separating pure from impure code so that no pure functions invoke impure operations. Often, you can achieve that with what I call the <em>impure-pure-impure sandwich</em> architecture. In this example, you saw how to model the file system as a tree. This enables you to separate the impure file interactions from the pure program logic. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/09/16/picture-archivist-in-f Picture archivist in Haskell https://blog.ploeh.dk/2019/09/09/picture-archivist-in-haskell/ Mon, 09 Sep 2019 08:19:00 UTC <div id="post"> <p> <em>A comprehensive code example showing how to implement a functional architecture in Haskell.</em> </p> <p> This article shows how to implement the <a href="/2019/08/26/functional-file-system">picture archivist architecture described in the previous article</a>. In short, the task is to move some image files to directories based on their date-taken metadata. The architectural idea is to load a directory structure from disk into an in-memory tree, manipulate that tree, and use the resulting tree to perform the desired actions: </p> <p> <img src="/content/binary/functional-file-system-interaction.png" alt="A functional program typically loads data, transforms it, and stores it again."> </p> <p> Much of the program will manipulate the tree data, which is immutable. </p> <h3 id="770cf37f0e3c457782ea20b53257f2d1"> Tree <a href="#770cf37f0e3c457782ea20b53257f2d1" title="permalink">#</a> </h3> <p> You can start by defining a <a href="https://en.wikipedia.org/wiki/Rose_tree">rose tree</a>: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;Tree&nbsp;a&nbsp;b&nbsp;=&nbsp;Node&nbsp;a&nbsp;[Tree&nbsp;a&nbsp;b]&nbsp;|&nbsp;Leaf&nbsp;b&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> If you wanted to, you could put all the <code>Tree</code> code in a reusable library, because none of it is coupled to a particular application, such as <a href="https://amzn.to/2V06Kji">moving pictures</a>. You could also write a comprehensive test suite for the following functions, but in this article, I'll skip that. </p> <p> Notice that this sort of tree explicitly distinguishes between internal and leaf nodes. This is necessary because you'll need to keep track of the directory names (the internal nodes), while at the same time you'll want to enrich the leaves with additional data - data that you can't meaningfully add to the internal nodes. You'll see this later in the article. </p> <p> The <a href="/2019/08/05/rose-tree-catamorphism">rose tree catamorphism</a> is this <code>foldTree</code> function: </p> <p> <pre><span style="color:#2b91af;">foldTree</span>&nbsp;::&nbsp;(a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;[c]&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(b&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Tree</span>&nbsp;a&nbsp;b&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c foldTree&nbsp;&nbsp;_&nbsp;fl&nbsp;(Leaf&nbsp;x)&nbsp;=&nbsp;fl&nbsp;x foldTree&nbsp;fn&nbsp;fl&nbsp;(Node&nbsp;x&nbsp;xs)&nbsp;=&nbsp;fn&nbsp;x&nbsp;$&nbsp;foldTree&nbsp;fn&nbsp;fl&nbsp;&lt;$&gt;&nbsp;xs</pre> </p> <p> Sometimes I name the catamorphism <code>cata</code>, sometimes something like <code>tree</code>, but using a library like <code>Data.Tree</code> as another source of inspiration, in this article I chose to name it <code>foldTree</code>. </p> <p> In this article, tree functionality is (with one exception) directly or transitively implemented with <code>foldTree</code>. </p> <h3 id="f5541d8a36b04cf9a455824c5f3a21c7"> Filtering trees <a href="#f5541d8a36b04cf9a455824c5f3a21c7" title="permalink">#</a> </h3> <p> It'll be useful to be able to filter the contents of a tree. For example, the picture archivist program will only move image files with valid metadata. This means that it'll need to filter out all files that aren't image files, as well as image files without valid metadata. </p> <p> It turns out that it'll be useful to supply a function that throws away <code>Nothing</code> values from a tree of <code>Maybe</code> leaves. This is similar to the <code>catMaybes</code> function from <code>Data.Maybe</code>, so I call it <code>catMaybeTree</code>: </p> <p> <pre><span style="color:#2b91af;">catMaybeTree</span>&nbsp;::&nbsp;<span style="color:blue;">Tree</span>&nbsp;a&nbsp;(<span style="color:#2b91af;">Maybe</span>&nbsp;b)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&nbsp;(<span style="color:blue;">Tree</span>&nbsp;a&nbsp;b) catMaybeTree&nbsp;=&nbsp;foldTree&nbsp;(\x&nbsp;-&gt;&nbsp;Just&nbsp;.&nbsp;Node&nbsp;x&nbsp;.&nbsp;catMaybes)&nbsp;(<span style="color:blue;">fmap</span>&nbsp;Leaf)</pre> </p> <p> You may find the type of the function surprising. Why does it return a <code>Maybe Tree</code>, instead of simply a <code>Tree</code>? And if you accept the type as given, isn't this simply the <code>sequence</code> function? </p> <p> While <code>catMaybes</code> simply returns a list, it can do this because lists can be empty. This <code>Tree</code> type, on the other hand, can't be empty. If the purpose of <code>catMaybeTree</code> is to throw away all <code>Nothing</code> values, then how do you return a tree from <code>Leaf Nothing</code>? </p> <p> You can't return a <code>Leaf</code> because you have no value to put in the leaf. Similarly, you can't return a <code>Node</code> because, again, you have no value to put in the node. </p> <p> In order to handle this edge case, then, you'll have to return <code>Nothing</code>: </p> <p> <pre>Prelude Tree&gt; catMaybeTree $ Leaf Nothing Nothing</pre> </p> <p> Isn't this the same as <code>sequence</code>, then? It's not, because <code>sequence</code> short-circuits all data, as this list example shows: </p> <p> <pre>Prelude&gt; sequence [Just 42, Nothing, Just 2112] Nothing</pre> </p> <p> Contrast this with the behaviour of <code>catMaybes</code>: </p> <p> <pre>Prelude Data.Maybe&gt; catMaybes [Just 42, Nothing, Just 2112] [42,2112]</pre> </p> <p> You've yet to see the <code>Traversable</code> instance for <code>Tree</code>, but it behaves in the same way: </p> <p> <pre>Prelude Tree&gt; sequence $ Node "Foo" [Leaf (Just 42), Leaf Nothing, Leaf (Just 2112)] Nothing</pre> </p> <p> The <code>catMaybeTree</code> function, on the other hand, returns a filtered tree: </p> <p> <pre>Prelude Tree&gt; catMaybeTree $ Node "Foo" [Leaf (Just 42), Leaf Nothing, Leaf (Just 2112)] Just (Node "Foo" [Leaf 42,Leaf 2112])</pre> </p> <p> While the resulting tree is wrapped in a <code>Just</code> case, the leaves contain unwrapped values. </p> <h3 id="5f0287c6d6fe42f3ad73a8e31ba9b3c4"> Instances <a href="#5f0287c6d6fe42f3ad73a8e31ba9b3c4" title="permalink">#</a> </h3> <p> The <a href="/2019/08/05/rose-tree-catamorphism">article about the rose tree catamorphism</a> already covered how to add instances of <code>Bifunctor</code>, <code>Bifoldable</code>, and <code>Bitraversable</code>, so I'll give this only cursory treatment. Refer to that article for a more detailed treatment. The code that accompanies that article also has <a href="http://hackage.haskell.org/package/QuickCheck">QuickCheck</a> properties that verify the various laws associated with those instances. Here, I'll just list the instances without further comment: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Bifunctor</span>&nbsp;<span style="color:blue;">Tree</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;bimap&nbsp;f&nbsp;s&nbsp;=&nbsp;foldTree&nbsp;(Node&nbsp;.&nbsp;f)&nbsp;(Leaf&nbsp;.&nbsp;s) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Bifoldable</span>&nbsp;<span style="color:blue;">Tree</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;bifoldMap&nbsp;f&nbsp;=&nbsp;foldTree&nbsp;(\x&nbsp;xs&nbsp;-&gt;&nbsp;f&nbsp;x&nbsp;&lt;&gt;&nbsp;mconcat&nbsp;xs) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Bitraversable</span>&nbsp;<span style="color:blue;">Tree</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;bitraverse&nbsp;f&nbsp;s&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;foldTree&nbsp;(\x&nbsp;xs&nbsp;-&gt;&nbsp;Node&nbsp;&lt;$&gt;&nbsp;f&nbsp;x&nbsp;&lt;*&gt;&nbsp;sequenceA&nbsp;xs)&nbsp;(<span style="color:blue;">fmap</span>&nbsp;Leaf&nbsp;.&nbsp;s) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;(<span style="color:blue;">Tree</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;=&nbsp;second <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Foldable</span>&nbsp;(<span style="color:blue;">Tree</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;foldMap&nbsp;=&nbsp;bifoldMap&nbsp;mempty <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Traversable</span>&nbsp;(<span style="color:blue;">Tree</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;sequenceA&nbsp;=&nbsp;bisequenceA&nbsp;.&nbsp;first&nbsp;pure</pre> </p> <p> The picture archivist program isn't going to explicitly need all of these, but transitively, it will. </p> <h3 id="d1bbd6ef895f45619822126f44bf6bfb"> Moving pictures <a href="#d1bbd6ef895f45619822126f44bf6bfb" title="permalink">#</a> </h3> <p> So far, all the code shown here could be in a general-purpose reusable library, since it contains no functionality specifically related to image files. The rest of the code in this article, however, will be specific to the program. I'll put the domain model code in another module and import some functionality: </p> <p> <pre><span style="color:blue;">module</span>&nbsp;Archive&nbsp;<span style="color:blue;">where</span> <span style="color:blue;">import</span>&nbsp;Data.Time <span style="color:blue;">import</span>&nbsp;Text.Printf <span style="color:blue;">import</span>&nbsp;System.FilePath <span style="color:blue;">import</span>&nbsp;<span style="color:blue;">qualified</span>&nbsp;Data.Map.Strict&nbsp;<span style="color:blue;">as</span>&nbsp;Map <span style="color:blue;">import</span>&nbsp;Tree</pre> </p> <p> Notice that <code>Tree</code> is one of the imported modules. </p> <p> Later, we'll look at how to load a tree from the file system, but for now, we'll just pretend that we have such a tree. </p> <p> The major logic of the program is to create a destination tree based on a source tree. The leaves of the tree will have to carry some extra information apart from a file path, so you can introduce a specific type to capture that information: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;PhotoFile&nbsp;= &nbsp;&nbsp;PhotoFile&nbsp;{&nbsp;photoFileName&nbsp;::&nbsp;FilePath,&nbsp;takenOn&nbsp;::&nbsp;LocalTime&nbsp;} &nbsp;&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> A <code>PhotoFile</code> not only contains the file path for an image file, but also the date the photo was taken. This date can be extracted from the file's metadata, but that's an impure operation, so we'll delegate that work to the start of the program. We'll return to that later. </p> <p> Given a source tree of <code>PhotoFile</code> leaves, though, the program must produce a destination tree of files: </p> <p> <pre><span style="color:#2b91af;">moveTo</span>&nbsp;::&nbsp;(<span style="color:blue;">Foldable</span>&nbsp;t,&nbsp;<span style="color:blue;">Ord</span>&nbsp;a,&nbsp;<span style="color:blue;">PrintfType</span>&nbsp;a)&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;t&nbsp;<span style="color:blue;">PhotoFile</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Tree</span>&nbsp;a&nbsp;<span style="color:#2b91af;">FilePath</span> moveTo&nbsp;destination&nbsp;= &nbsp;&nbsp;Node&nbsp;destination&nbsp;.&nbsp;Map.foldrWithKey&nbsp;addDir&nbsp;<span style="color:blue;">[]</span>&nbsp;.&nbsp;<span style="color:blue;">foldr</span>&nbsp;groupByDir&nbsp;Map.empty &nbsp;&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;&nbsp;&nbsp;dirNameOf&nbsp;(LocalTime&nbsp;d&nbsp;_)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;(y,&nbsp;m,&nbsp;_)&nbsp;=&nbsp;toGregorian&nbsp;d&nbsp;<span style="color:blue;">in</span>&nbsp;printf&nbsp;<span style="color:#a31515;">&quot;%d-%02d&quot;</span>&nbsp;y&nbsp;m &nbsp;&nbsp;&nbsp;&nbsp;groupByDir&nbsp;(PhotoFile&nbsp;fileName&nbsp;t)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Map.insertWith&nbsp;<span style="color:#2b91af;">(++)</span>&nbsp;(dirNameOf&nbsp;t)&nbsp;[fileName] &nbsp;&nbsp;&nbsp;&nbsp;addDir&nbsp;name&nbsp;files&nbsp;dirs&nbsp;=&nbsp;Node&nbsp;name&nbsp;(Leaf&nbsp;&lt;$&gt;&nbsp;files)&nbsp;:&nbsp;dirs</pre> </p> <p> This <code>moveTo</code> function looks, perhaps, overwhelming, but it's composed of only three steps: <ol> <li>Create a map of destination folders (<code>foldr groupByDir Map.empty</code>).</li> <li>Create a list of branches from the map (<code>Map.foldrWithKey addDir []</code>).</li> <li>Create a tree from the list (<code>Node destination</code>).</li> </ol> Recall that when Haskell functions are composed with the <code>.</code> operator, you'll have to read the composition from right to left. </p> <p> Notice that this function works with any <code>Foldable</code> data container, so it'd work with lists and other data structures besides trees. </p> <p> The <code>moveTo</code> function starts by folding the input data into a map. The map is keyed by the directory name, which is formatted by the <code>dirNameOf</code> function. This function takes a <code>LocalTime</code> as input and formats it to a <code>YYYY-MM</code> format. For example, December 20, 2018 becomes <code>"2018-12"</code>. </p> <p> The entire mapping step groups the <code>PhotoFile</code> values into a map of the type <code>Map a [FilePath]</code>. All the image files taken in April 2014 are added to the list with the <code>"2014-04"</code> key, all the image files taken in July 2011 are added to the list with the <code>"2011-07"</code> key, and so on. </p> <p> In the next step, the <code>moveTo</code> function converts the map to a list of trees. This will be the branches (or sub-directories) of the <code>destination</code> directory. Because of the desired structure of the destination tree, this is a list of shallow branches. Each node contains only leaves. </p> <p> <img src="/content/binary/shallow-photo-destination-directories.png" alt="Shallow photo destination directories."> </p> <p> The only remaining step is to add that list of branches to a <code>destination</code> node. </p> <p> Since this is a <a href="https://en.wikipedia.org/wiki/Pure_function">pure function</a>, it's <a href="/2015/05/07/functional-design-is-intrinsically-testable">easy to unit test</a>. Just create some input values and call the function: </p> <p> <pre><span style="color:#a31515;">&quot;Move&nbsp;to&nbsp;destination&quot;</span>&nbsp;~:&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;(source,&nbsp;destination,&nbsp;expected)&nbsp;&lt;- &nbsp;&nbsp;&nbsp;&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;$&nbsp;lt&nbsp;2018&nbsp;11&nbsp;9&nbsp;11&nbsp;47&nbsp;17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;<span style="color:#a31515;">&quot;D&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>&nbsp;[Node&nbsp;<span style="color:#a31515;">&quot;2018-11&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>]]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;S&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>&nbsp;$&nbsp;lt&nbsp;1972&nbsp;6&nbsp;6&nbsp;16&nbsp;15&nbsp;00] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;<span style="color:#a31515;">&quot;D&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>&nbsp;[Node&nbsp;<span style="color:#a31515;">&quot;1972-06&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>]]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;S&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;L&quot;</span>&nbsp;$&nbsp;lt&nbsp;2002&nbsp;10&nbsp;12&nbsp;17&nbsp;16&nbsp;15, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;J&quot;</span>&nbsp;$&nbsp;lt&nbsp;2007&nbsp;4&nbsp;21&nbsp;17&nbsp;18&nbsp;19] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;<span style="color:#a31515;">&quot;D&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>&nbsp;[Node&nbsp;<span style="color:#a31515;">&quot;2002-10&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;L&quot;</span>],&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2007-04&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;J&quot;</span>]]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;1&nbsp;12&nbsp;17&nbsp;16&nbsp;15, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;3&nbsp;12&nbsp;17&nbsp;16&nbsp;15, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;1&nbsp;21&nbsp;17&nbsp;18&nbsp;19] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;<span style="color:#a31515;">&quot;2&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2010-01&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>], &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2010-03&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>]]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;foo&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;bar&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;1&nbsp;12&nbsp;17&nbsp;16&nbsp;15, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;3&nbsp;12&nbsp;17&nbsp;16&nbsp;15, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;1&nbsp;21&nbsp;17&nbsp;18&nbsp;19], &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;baz&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;d&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;3&nbsp;1&nbsp;2&nbsp;3&nbsp;4, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;e&quot;</span>&nbsp;$&nbsp;lt&nbsp;2011&nbsp;3&nbsp;4&nbsp;3&nbsp;2&nbsp;1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;]] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;<span style="color:#a31515;">&quot;qux&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;qux&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2010-01&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>], &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2010-03&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>,&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;d&quot;</span>], &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2011-03&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;e&quot;</span>]]) &nbsp;&nbsp;&nbsp;&nbsp;] &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;moveTo&nbsp;destination&nbsp;source &nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;expected&nbsp;~=?&nbsp;actual</pre> </p> <p> This is an <a href="/2018/05/07/inlined-hunit-test-lists">inlined</a> <a href="/2018/04/30/parametrised-unit-tests-in-haskell">parametrised HUnit test</a>. While it looks like a big unit test, it still follows my <a href="/2013/06/24/a-heuristic-for-formatting-code-according-to-the-aaa-pattern">test formatting heuristic</a>. There's only three expressions, but the <em>arrange</em> expression is big because it creates a list of test cases. </p> <p> Each test case is a triple of a <code>source</code> tree, a <code>destination</code> directory name, and an <code>expected</code> result. In order to make the test data code more compact, it utilises this test-specific helper function: </p> <p> <pre>lt&nbsp;y&nbsp;mth&nbsp;d&nbsp;h&nbsp;m&nbsp;s&nbsp;=&nbsp;LocalTime&nbsp;(fromGregorian&nbsp;y&nbsp;mth&nbsp;d)&nbsp;(TimeOfDay&nbsp;h&nbsp;m&nbsp;s)</pre> </p> <p> For each test case, the test calls the <code>moveTo</code> function with the <code>destination</code> directory name and the <code>source</code> tree. It then asserts that the <code>expected</code> value is equal to the <code>actual</code> value. </p> <h3 id="bcf9e8fd9d1b42bbb47b811be75385d0"> Calculating moves <a href="#bcf9e8fd9d1b42bbb47b811be75385d0" title="permalink">#</a> </h3> <p> One pure step remains. The result of calling the <code>moveTo</code> function is a tree with the desired structure. In order to actually move the files, though, for each file you'll need to keep track of both the source path and the destination path. To make that explicit, you can define a type for that purpose: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;Move&nbsp;= &nbsp;&nbsp;Move&nbsp;{&nbsp;sourcePath&nbsp;::&nbsp;FilePath,&nbsp;destinationPath&nbsp;::&nbsp;FilePath&nbsp;} &nbsp;&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> A <code>Move</code> is simply a data structure. Contrast this with typical object-oriented design, where it would be a (possibly polymorphic) method on an object. In functional programming, you'll regularly model <em>intent</em> with a data structure. As long as intents remain data, you can easily manipulate them, and once you're done with that, you can run an interpreter over your data structure to perform the work you want accomplished. </p> <p> The unit test cases for the <code>moveTo</code> function suggest that file names are local file names like <code>"L"</code>, <code>"J"</code>, <code>"a"</code>, and so on. That was only to make the tests as compact as possible, since the function actually doesn't manipulate the specific <code>FilePath</code> values. </p> <p> In reality, the file names will most likely be longer, and they could also contain the full path, instead of the local path: <code>"C:\foo\bar\a.jpg"</code>. </p> <p> If you call <code>moveTo</code> with a tree where each leaf has a fully qualified path, the output tree will have the desired structure of the destination tree, but the leaves will still contain the full path to each source file. That means that you can calculate a <code>Move</code> for each file: </p> <p> <pre><span style="color:#2b91af;">calculateMoves</span>&nbsp;::&nbsp;<span style="color:blue;">Tree</span>&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Tree</span>&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:blue;">Move</span> calculateMoves&nbsp;=&nbsp;imp&nbsp;<span style="color:#a31515;">&quot;&quot;</span> &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;imp&nbsp;path&nbsp;&nbsp;&nbsp;&nbsp;(Leaf&nbsp;x)&nbsp;=&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;x&nbsp;$&nbsp;replaceDirectory&nbsp;x&nbsp;path &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;imp&nbsp;path&nbsp;(Node&nbsp;x&nbsp;xs)&nbsp;=&nbsp;Node&nbsp;(path&nbsp;&lt;/&gt;&nbsp;x)&nbsp;$&nbsp;imp&nbsp;(path&nbsp;&lt;/&gt;&nbsp;x)&nbsp;&lt;$&gt;&nbsp;xs</pre> </p> <p> This function takes as input a <code>Tree FilePath FilePath</code>, which is compatible with the output of <code>moveTo</code>. It returns a <code>Tree FilePath Move</code>, i.e. a tree where the leaves are <code>Move</code> values. </p> <p> To be fair, returning a tree is overkill. A <code>[Move]</code> (list of moves) would have been just as useful, but in this article, I'm trying to describe how to write code with a <a href="/2018/11/19/functional-architecture-a-definition">functional architecture</a>. In the overview article, I explained how you can model a file system using a rose tree, and in order to emphasise that point, I'll stick with that model a little while longer. </p> <p> Earlier, I wrote that you can implement desired <code>Tree</code> functionality with the <code>foldTree</code> function, but that was a simplification. If you can implement the functionality of <code>calculateMoves</code> with <code>foldTree</code>, I don't know how. You can, however, implement it using explicit pattern matching and simple recursion. </p> <p> The <code>imp</code> function builds up a file path (using the <code>&lt;/&gt;</code> path combinator) as it recursively negotiates the tree. All <code>Leaf</code> nodes are converted to a <code>Move</code> value using the leaf node's current <code>FilePath</code> value as the <code>sourcePath</code>, and the <code>path</code> to figure out the desired <code>destinationPath</code>. </p> <p> This code is still easy to unit test: </p> <p> <pre><span style="color:#a31515;">&quot;Calculate&nbsp;moves&quot;</span>&nbsp;~:&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;(tree,&nbsp;expected)&nbsp;&lt;- &nbsp;&nbsp;&nbsp;&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Leaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Node&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>],&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;[Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Node&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>],&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Node&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;[Node&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>],&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;3&quot;</span>]], &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>)&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>], &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>)&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;3&quot;</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;3&quot;</span>]]) &nbsp;&nbsp;&nbsp;&nbsp;] &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;calculateMoves&nbsp;tree &nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;expected&nbsp;~=?&nbsp;actual</pre> </p> <p> The test cases in this parametrised test are tuples of an input <code>tree</code> and the <code>expected</code> tree. For each test case, the test calls the <code>calculateMoves</code> function with <code>tree</code> and asserts that the <code>actual</code> tree is equal to the <code>expected</code> tree. </p> <p> That's all the pure code you need in order to implement the desired functionality. Now you only need to write some code that loads a tree from disk, and imprints a destination tree to disk, as well as the code that composes it all. </p> <h3 id="062fff475b2b47e188dbd2bc930aa882"> Loading a tree from disk <a href="#062fff475b2b47e188dbd2bc930aa882" title="permalink">#</a> </h3> <p> The remaining code in this article is impure. You could put it in dedicated modules, but for this program, you're only going to need three functions and a bit of composition code, so you could also just put it all in the <code>Main</code> module. That's what I did. </p> <p> To load a tree from disk, you'll need a root directory, under which you load the entire tree. Given a directory path, you read a tree using a recursive function like this: </p> <p> <pre><span style="color:#2b91af;">readTree</span>&nbsp;::&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;(<span style="color:blue;">Tree</span>&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:#2b91af;">FilePath</span>) readTree&nbsp;path&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;isFile&nbsp;&lt;-&nbsp;doesFileExist&nbsp;path &nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;isFile &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">then</span>&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;Leaf&nbsp;path &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span>&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dirsAndfiles&nbsp;&lt;-&nbsp;listDirectory&nbsp;path &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;paths&nbsp;=&nbsp;<span style="color:blue;">fmap</span>&nbsp;(path&nbsp;&lt;/&gt;)&nbsp;dirsAndfiles &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;branches&nbsp;&lt;-&nbsp;traverse&nbsp;readTree&nbsp;paths &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;Node&nbsp;path&nbsp;branches</pre> </p> <p> This recursive function starts by checking whether the <code>path</code> is a file or a directory. If it's a file, it creates a new <code>Leaf</code> with that <code>FilePath</code>. </p> <p> If <code>path</code> isn't a file, it's a directory. In that case, use <code>listDirectory</code> to enumerate all the directories and files in that directory. These are only local names, so prefix them with <code>path</code> to create full paths, then <code>traverse</code> all those directory entries recursively. That produces all the <code>branches</code> for the current node. Finally, return a new <code>Node</code> with the <code>path</code> and the <code>branches</code>. </p> <h3 id="5ba31d6e6e7f4eee942e39349a45e1ed"> Loading metadata <a href="#5ba31d6e6e7f4eee942e39349a45e1ed" title="permalink">#</a> </h3> <p> The <code>readTree</code> function only produces a tree with <code>FilePath</code> leaves, while the program requires a tree with <code>PhotoFile</code> leaves. You'll need to read the <a href="https://en.wikipedia.org/wiki/Exif">Exif</a> metadata from each file and enrich the tree with the <em>date-taken</em> data. </p> <p> In this code base, I've used the <a href="http://hackage.haskell.org/package/hsexif">hsexif</a> library for this. That enables you to write an impure operation like this: </p> <p> <pre><span style="color:#2b91af;">readPhoto</span>&nbsp;::&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;(<span style="color:#2b91af;">Maybe</span>&nbsp;<span style="color:blue;">PhotoFile</span>) readPhoto&nbsp;path&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;exifData&nbsp;&lt;-&nbsp;parseFileExif&nbsp;path &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;dateTaken&nbsp;=&nbsp;either&nbsp;(<span style="color:blue;">const</span>&nbsp;Nothing)&nbsp;Just&nbsp;exifData&nbsp;&gt;&gt;=&nbsp;getDateTimeOriginal &nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;PhotoFile&nbsp;path&nbsp;&lt;$&gt;&nbsp;dateTaken</pre> </p> <p> This operation can fail for various reasons: <ul> <li>The file may not exist.</li> <li>The file exists, but has no metadata.</li> <li>The file has metadata, but no <em>date-taken</em> metadata.</li> <li>The <em>date-taken</em> metadata string is malformed.</li> </ul> The program is just going to skip all files from which it can't extract <em>date-taken</em> metadata, so <code>readPhoto</code> converts the <code>Either</code> value returned by <code>parseFileExif</code> to <code>Maybe</code> and binds the result with <code>getDateTimeOriginal</code>. </p> <p> When you <code>traverse</code> a <code>Tree FilePath FilePath</code> with <code>readPhoto</code>, you'll get a <code>Tree FilePath (Maybe PhotoFile)</code>. That's when you'll need <code>catMaybeTree</code>. You'll see this soon. </p> <h3 id="8b8d1709f9ed4fe2bc78e4ea9b2a2508"> Writing a tree to disk <a href="#8b8d1709f9ed4fe2bc78e4ea9b2a2508" title="permalink">#</a> </h3> <p> The above <code>calculateMoves</code> function creates a <code>Tree FilePath Move</code>. The final piece of impure code you'll need to write is an operation that traverses such a tree and executes each <code>Move</code>. </p> <p> <pre><span style="color:#2b91af;">applyMoves</span>&nbsp;::&nbsp;<span style="color:blue;">Foldable</span>&nbsp;t&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;t&nbsp;<span style="color:blue;">Move</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;() applyMoves&nbsp;=&nbsp;traverse_&nbsp;move &nbsp;&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;&nbsp;&nbsp;move&nbsp;m&nbsp;=&nbsp;copy&nbsp;m&nbsp;&gt;&gt;&nbsp;compareFiles&nbsp;m&nbsp;&gt;&gt;=&nbsp;deleteSource &nbsp;&nbsp;&nbsp;&nbsp;copy&nbsp;(Move&nbsp;s&nbsp;d)&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;createDirectoryIfMissing&nbsp;True&nbsp;$&nbsp;takeDirectory&nbsp;d &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;copyFileWithMetadata&nbsp;s&nbsp;d &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">putStrLn</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;Copied&nbsp;to&nbsp;&quot;</span>&nbsp;++&nbsp;<span style="color:blue;">show</span>&nbsp;d &nbsp;&nbsp;&nbsp;&nbsp;compareFiles&nbsp;m@(Move&nbsp;s&nbsp;d)&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sourceBytes&nbsp;&lt;-&nbsp;B.<span style="color:blue;">readFile</span>&nbsp;s &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;destinationBytes&nbsp;&lt;-&nbsp;B.<span style="color:blue;">readFile</span>&nbsp;d &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;<span style="color:blue;">if</span>&nbsp;sourceBytes&nbsp;==&nbsp;destinationBytes&nbsp;<span style="color:blue;">then</span>&nbsp;Just&nbsp;m&nbsp;<span style="color:blue;">else</span>&nbsp;Nothing &nbsp;&nbsp;&nbsp;&nbsp;deleteSource&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Nothing&nbsp;=&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">()</span> &nbsp;&nbsp;&nbsp;&nbsp;deleteSource&nbsp;(Just&nbsp;(Move&nbsp;s&nbsp;_))&nbsp;=&nbsp;removeFile&nbsp;s</pre> </p> <p> As I wrote above, a tree of <code>Move</code> values is, to be honest, overkill. Any <code>Foldable</code> container will do, as the <code>applyMoves</code> operation demonstrates. It traverses the data structure, and for each <code>Move</code>, it first copies the file, then it verifies that the copy was successful, and finally, if that's the case, it deletes the source file. </p> <p> All of the operations invoked by these three steps are defined in various libraries part of the base GHC installation. You're welcome to peruse <a href="https://github.com/ploeh/picture-archivist">the source code repository</a> if you're interested in the details. </p> <h3 id="d336cf55dc9746c08cbed32041803173"> Composition <a href="#d336cf55dc9746c08cbed32041803173" title="permalink">#</a> </h3> <p> You can now compose an <em>impure-pure-impure sandwich</em> from all the Lego pieces: </p> <p> <pre><span style="color:#2b91af;">movePhotos</span>&nbsp;::&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;() movePhotos&nbsp;source&nbsp;destination&nbsp;=&nbsp;<span style="color:blue;">fmap</span>&nbsp;fold&nbsp;$&nbsp;runMaybeT&nbsp;$&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;sourceTree&nbsp;&lt;-&nbsp;lift&nbsp;$&nbsp;readTree&nbsp;source &nbsp;&nbsp;photoTree&nbsp;&lt;-&nbsp;MaybeT&nbsp;$&nbsp;catMaybeTree&nbsp;&lt;$&gt;&nbsp;traverse&nbsp;readPhoto&nbsp;sourceTree &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;destinationTree&nbsp;=&nbsp;calculateMoves&nbsp;$&nbsp;moveTo&nbsp;destination&nbsp;photoTree &nbsp;&nbsp;lift&nbsp;$&nbsp;applyMoves&nbsp;destinationTree</pre> </p> <p> First, you load the <code>sourceTree</code> using the <code>readTree</code> operation. This is a <code>Tree FilePath FilePath</code> value, because the code is written in <code>do</code> notation, and the context is <code>MaybeT IO ()</code>. You then load the image metatadata by traversing <code>sourceTree</code> with <code>readPhoto</code>. This produces a <code>Tree FilePath (Maybe PhotoFile)</code> that you then filter with <code>catMaybeTree</code>. Again, because of <code>do</code> notation and monad transformer shenanigans, <code>photoTree</code> is a <code>Tree FilePath PhotoFile</code> value. </p> <p> Those two lines of code is the initial impure step of the sandwich (yes: mixed metaphors, I know). </p> <p> The pure part of the sandwich is the composition of the pure functions <code>moveTo</code> and <code>calculateMoves</code>. The result is a <code>Tree FilePath Move</code> value. </p> <p> The final, impure step of the sandwich, then, is to <code>applyMoves</code>. </p> <h3 id="8b44f4d2cd2241e18bff6d40c1ad9ee9"> Execution <a href="#8b44f4d2cd2241e18bff6d40c1ad9ee9" title="permalink">#</a> </h3> <p> The <code>movePhotos</code> operation takes <code>source</code> and <code>destination</code> arguments. You could hypothetically call it from a rich client or a background process, but here I'll just call if from a command-line program. The <code>main</code> operation will have to parse the input arguments and call <code>movePhotos</code>: </p> <p> <pre><span style="color:#2b91af;">main</span>&nbsp;::&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;() main&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;args&nbsp;&lt;-&nbsp;getArgs &nbsp;&nbsp;<span style="color:blue;">case</span>&nbsp;args&nbsp;<span style="color:blue;">of</span> &nbsp;&nbsp;&nbsp;&nbsp;[source,&nbsp;destination]&nbsp;-&gt;&nbsp;movePhotos&nbsp;source&nbsp;destination &nbsp;&nbsp;&nbsp;&nbsp;_&nbsp;-&gt;&nbsp;<span style="color:blue;">putStrLn</span>&nbsp;<span style="color:#a31515;">&quot;Please&nbsp;provide&nbsp;source&nbsp;and&nbsp;destination&nbsp;directories&nbsp;as&nbsp;arguments.&quot;</span></pre> </p> <p> You could write more sophisticated parsing of the program arguments, but that's not the topic of this article, so I only wrote the bare minimum required to get the program working. </p> <p> You can now compile and run the program: </p> <p> <pre>$ ./archpics "C:\Users\mark\Desktop\Test" "C:\Users\mark\Desktop\Test-Out" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2003-04\\2003-04-29 15.11.50.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2011-07\\2011-07-10 13.09.36.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2014-04\\2014-04-17 17.11.40.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2014-04\\2014-04-18 14.05.02.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2014-05\\2014-05-23 16.07.20.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2014-06\\2014-06-30 15.44.52.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2014-06\\2014-06-21 16.48.40.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2016-05\\2016-05-01 09.25.23.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2017-08\\2017-08-22 19.53.28.jpg"</pre> </p> <p> This does indeed produce the expected destination directory structure. </p> <p> <img src="/content/binary/picture-archivist-destination-directory.png" alt="Seven example directories with pictures."> </p> <p> It's always nice when something turns out to work in practice, as well as in theory. </p> <h3 id="c50c7ac1276146d79715a5e7ddadfe6d"> Summary <a href="#c50c7ac1276146d79715a5e7ddadfe6d" title="permalink">#</a> </h3> <p> Functional software architecture involves separating pure from impure code so that no pure functions invoke impure operations. Often, you can achieve that with what I call the <em>impure-pure-impure sandwich</em> architecture. In this example, you saw how to model the file system as a tree. This enables you to separate the impure file interactions from the pure program logic. </p> <p> The Haskell type system enforces the <em>functional interaction law</em>, which implies that the architecture is, indeed, properly functional. Other languages, like <a href="https://fsharp.org">F#</a>, don't enforce the law via the compiler, but that doesn't prevent you doing functional programming. Now that we've verified that the architecture is, indeed, functional, we can port it to F#. </p> <p> <strong>Next:</strong> <a href="/2019/09/16/picture-archivist-in-f">Picture archivist in F#</a>. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="f237d98d453a4bcb9a3d58a05bf21d34"> <div class="comment-author"><a href="https://majiehong.com">Jiehong</a></div> <div class="comment-content"> <p> This seems a fair architecture. </p> <p> However, at first glance it does not seem very memory efficient, because everything might be loaded in RAM, and that poses a strict limit. </p> <p> But then, I remember that Haskell does lazy evaluation, so is it the case here? Are path and the tree lazily loaded and processed? </p> <p> In "traditional" architectures, IO would be scattered inside the program, and as each file might be read one at a time, and handled. This sandwich of purity with impure buns forces not to do that. </p> </div> <div class="comment-date">2019-09-09 11:47 UTC</div> </div> <div class="comment" id="ca660cdc1f094bfb8cc9896bb1084460"> <div class="comment-author"><a href="/">Mark Seemann</a></div> <div class="comment-content"> <p> Jiehong, thank you for writing. It's true that Haskell is lazily evaluated, but some strictness rules apply to <code>IO</code>, so it's not so simple. </p> <p> Just running a quick experiment with the code base shown here, when I try to move thousands of files, the program sits and thinks for quite some time before it starts to output progress. This indicates to me that it does, indeed, load at least the <em>structure</em> of the tree into memory before it starts moving the files. Once it does that, though, it looks like it runs at constant memory. </p> <p> There's an interplay of laziness and <code>IO</code> in Haskell that I still don't sufficiently master. When I publish the port to F#, however, it should be clear that you could replace all the nodes of the tree with explicitly lazy values. I'd be surprised if something like that isn't possible in Haskell as well, but here I'll solicit help from readers more well-versed in these matters than I am. </p> </div> <div class="comment-date">2019-09-09 19:16 UTC</div> </div> <div class="comment" id="dd26f6d047b5492b8a012b30d96ad18b"> <div class="comment-author">André Cardoso</div> <div class="comment-content"> <p> I really like your posts and I'm really liking this series. But I struggle with Haskell syntax, specially the difference between the operators $, &lt;$&gt;, &lt;&gt;, &lt;*&gt;. Is there a cheat sheet explaining these operators? </p> </div> <div class="comment-date">2019-09-12 13:51 UTC</div> </div> <div class="comment" id="2e71f695ed9f4cfa8467df818f072da8"> <div class="comment-author"><a href="/">Mark Seemann</a></div> <div class="comment-content"> <p> André, thank you for writing. I've written about why <a href="/2018/07/02/terse-operators-make-business-code-more-readable">I think that terse operators make the code overall more readable</a>, but that's obviously not an explanation of any of those operators. </p> <p> I'm not aware of any cheat sheets for Haskell, although a Google search seems to indicate that many exist. I'm not sure that a cheat sheet will help much if one doesn't know Haskell, and if one does know Haskell, one is likely to also know those operators. </p> <p> <a href="https://hackage.haskell.org/package/base/docs/Prelude.html#v:-36-">$</a> is a sort of delimiter that often saves you from having to nest other function calls in brackets. </p> <p> <a href="https://hackage.haskell.org/package/base/docs/Prelude.html#v:-60--36--62-">&lt;$&gt;</a> is just an infix alias for <code>fmap</code>. In C#, that <a href="/2018/03/22/functors">corresponds to the <code>Select</code> method</a>. </p> <p> <code>&lt;&gt;</code> is a generalised associative binary operation as defined by <a href="http://hackage.haskell.org/package/base/docs/Data-Semigroup.html">Data.Semigroup</a> or <a href="http://hackage.haskell.org/package/base/docs/Data-Monoid.html">Data.Monoid</a>. You can <a href="/2017/10/05/monoids-semigroups-and-friends">read more about monoids and semigroups here on the blog</a>. </p> <p> <a href="http://hackage.haskell.org/package/base/docs/Control-Applicative.html">&lt;*&gt;</a> is part of the <code>Applicative</code> type class. It's hard to translate to other languages, but <a href="/2018/10/01/applicative-functors">when I make the attempt</a>, I usually call it <code>Apply</code>. </p> </div> <div class="comment-date">2019-09-12 15:45 UTC</div> </div> </div> <hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/09/09/picture-archivist-in-haskell