ploeh blog http://blog.ploeh.dk danish software design en-us Mark Seemann Sat, 17 Nov 2018 10:30:16 UTC Sat, 17 Nov 2018 10:30:16 UTC What to test and not to test http://blog.ploeh.dk/2018/11/12/what-to-test-and-not-to-test/ Mon, 12 Nov 2018 07:45:00 UTC <div id="post"> <p> <em>Should you unit test everything? Hardly surprising, the answer is that It Depends™. This article outlines some of the circumstances you might consider.</em> </p> <p> Some years ago, I, somewhat to my own surprise, found myself on the wrong side of a controversy about whether one should <a href="http://blog.ploeh.dk/2013/03/08/test-trivial-code">test trivial code</a>. The context was a discussion about Test-Driven Development (TDD), and for reasons that I still stand behind today, I argued that you should test all code, including trivial code, such as property getters. </p> <p> Most of the 'TDD community' reacted quite negatively to that article, some in not-so-nice ways. Some people reacted, I believe, based on their dislike of the conclusion, without responding to my arguments. Others, however, gave reasoned rebuttals. When people like <a href="https://lostechies.com/derickbailey/2013/03/11/on-testing-trivia-code/">Derick Bailey</a> and <a href="https://rendlelabs.com/blog/dont-unit-test-trivial-code">Mark Rendle disagree with me</a>, in a reasoned matter, even, I consider that a good reason to revisit my thinking. </p> <p> Could I have been wrong? That certainly wouldn't be the first time, but even re-reading the article today, I find my logic sound. Yet, I've substantially nuanced my position since then. </p> <p> It took me some time to understand how I could disagree so radically with people I respect. It didn't take me five years, though, but while I've been at peace with the apparent conflict for years, I've never written a coherent description of my current understanding of this problem space. This article is my attempt to remedy that omission. </p> <h3 id="eb43b60a35394df6b812514ac794cefe"> Context matters <a href="#eb43b60a35394df6b812514ac794cefe" title="permalink">#</a> </h3> <p> Whenever you consult an expert about how to address a problem, you'll invariably get the answer that <em>it depends</em>. I'd suggest that if you don't get that answer, the person is probably not an expert, after all. A useful expert will also be able to tell you on <em>what</em> 'it' depends. </p> <p> In an abstract sense, what 'it' depends on is <em>the context</em>. </p> <p> I wrote my original piece from a particular context. Part of that context is explicitly present in the article, but another part is entirely implicit. People read the article from within their own contexts, which in many cases turned out to be incongruent with mine. No wonder people disagreed. </p> <h3 id="9181a2688ce042d882cfe73a3bfed57e"> Watching the wildlife <a href="#9181a2688ce042d882cfe73a3bfed57e" title="permalink">#</a> </h3> <p> My context at that time was that I had some success with <a href="https://github.com/AutoFixture/AutoFixture">AutoFixture</a>, an open source library, which is what I consider <a href="http://blog.ploeh.dk/2012/12/18/RangersandZookeepers">wildlife</a> software. Once you've released a version of the software, you have no control of where it's installed, or how it's used. </p> <p> This means that backwards compatibility becomes important. If I broke something, I would inconvenience the users of my software. Making sure that compatibility didn't break became one of my highest priorities. I used unit tests for regression tests, and I did, indeed, test the entire public API of AutoFixture, to make sure that no breaking changes were introduced. </p> <p> That was my implicit context. Read in that light, my dogmatic insistence on testing everything hopefully makes a little more sense. </p> <p> Does that mean that my conclusion transfers to other circumstances? No, of course it doesn't. If you're developing and maintaining <a href="http://blog.ploeh.dk/2012/12/18/RangersandZookeepers">zoo software</a>, breaking changes are of less concern. From that perspective, my article could easily look like the creation of an unhinged mind. </p> <h3 id="a15643275c1a4d7ab484cacafa53b7da"> The purpose of tests <a href="#a15643275c1a4d7ab484cacafa53b7da" title="permalink">#</a> </h3> <p> In order to figure out what to test, and what not to test, you should ask yourself the question: <em>what's the purpose of testing?</em> </p> <p> At first glance, that may seem like an inane question, but there's actually more than one purpose of a unit test. When doing TDD, the purpose of a test is to provide feedback about the API you're developing. <a href="http://blog.ploeh.dk/2011/11/10/TDDimprovesreusability">A unit test is the first client of the production API</a>. If a test is difficult to write, the production API is difficult to use. More on TDD later, though. </p> <p> You may say that another purpose of automated tests is that they prevent errors. That's not the case, though. Automated tests prevent <em>regressions</em>. </p> <p> If you wrote the correct test, your test suite may also help to prevent errors, but a unit test is only as good as the programmer who wrote it. You could have made a mistake when you wrote the test. Or perhaps you misunderstood the specification of what you were trying to implement. <a href="http://blog.ploeh.dk/2013/04/02/why-trust-tests">Why do you even trust tests?</a> </p> <h3 id="d5b17ea45ed741899002d50fbb3e98c9"> The cost of regressions <a href="#d5b17ea45ed741899002d50fbb3e98c9" title="permalink">#</a> </h3> <p> Why do you want to prevent regressions? Because they're costly? </p> <p> Based on the little risk management I know about, you operate with two dimensions of risk: the impact of an event, should it occur, and the probability that the event occurs. </p> <p> Should we all be worried that an asteroid will hit the Earth and wipe out most life? The impact of such an event is truly catastrophic, yet the probability is diminishingly small, so the <em>risk</em> is insignificant. The risk of going for a drive in a car is much higher. </p> <p> How do you reduce risk? You either decrease the probability that the adverse event will happen, or you reduce the impact of it, should it happen. </p> <p> <a href="http://www.higherorderlogic.com/">Steve Freeman</a> once wrote a nice article about the distinction between fail-safe software, and software that could safely fail. Unfortunately, that article seems to have disappeared from the internet. The point, however, was that with unit tests, we attempt to make our software fail-safe. The unit tests act as a gate that prevents bad versions of the software from being released. That's not a bad strategy for managing risk, but only half of the strategies available. </p> <p> For example, <a href="http://amzn.to/1axt5YA">Continuous Delivery</a> describes how you can use <a href="https://martinfowler.com/bliki/CanaryRelease.html">Canary Releases</a> and automated rollbacks to reduce the impact of errors. That's what Steve Freeman called <em>safe fail</em>. </p> <p> I apologise for this detour around risk management, but I think that it's important that you make an explicit decision about automated testing. You can use unit tests to prevent regressions. What's the impact of an error in production, though? </p> <p> This depends on the type of software you're developing. When considering alternatives, I often envision the various options as inhabiting a continuum: </p> <p> <img src="/content/binary/test-coverage-continuum.png" alt="Test coverage continuum; no coverage to the left, maximum coverage to the right."> </p> <p> For some types of software, an error 'in production' could be fatal. This would be the case for guidance software for <a href="https://en.wikipedia.org/wiki/Voyager_1">Voyager 1</a>, <a href="https://en.wikipedia.org/wiki/Voyager_2">2</a>, other guidance software, software for medical devices, and so on. If you deploy a defect to Voyager 2, you've probably lost the craft for ever. </p> <p> (I'd be surprised if the Voyager guidance software is actually covered by unit tests, but I'd expect that other quality assurance checks are in place. For comparison, the space shuttle software development process has been appraised at CMMI level 5.) </p> <p> On the other side of the continuum, as a software developer, you probably write small ad-hoc development tools for your own use. For example, a few years ago I did a lot of <a href="https://en.wikipedia.org/wiki/Representational_state_transfer">REST</a> API development, and many of the APIs I worked with required <a href="https://en.wikipedia.org/wiki/OAuth">OAuth</a> authentication. I wrote a little command-line program that I could use to log on to an internal system and exchange that to a token. I don't think that I wrote any tests for that program. If there were problems with it, I'd just open the source code and fix the problem. Errors were cheap in that situation. </p> <p> Most software probably falls somewhere in the middle of those extremes. The cost of errors in wildlife software is probably higher than it is for zoo software, but most software can get by with less coverage than <em>everything</em>. </p> <h3 id="7db262526ca2459b813c0fda4f1e6999"> Cyclomatic complexity <a href="#7db262526ca2459b813c0fda4f1e6999" title="permalink">#</a> </h3> <p> How do you know that your software works? You test it. If you want to automate your testing efforts, you write unit tests... but a unit test suite is software. How do you know that your tests work? Is it going to be <a href="https://en.wikipedia.org/wiki/Turtles_all_the_way_down">turtles all the way down</a>? </p> <p> I think that we can <a href="http://blog.ploeh.dk/2013/04/02/why-trust-tests">trust tests for other reasons</a>, but one of them is that each test case exercises a deterministic path through a unit that supports many paths of execution. </p> <p> <img src="/content/binary/one-test-path-through-complex-unit.png" alt="Diagram that shows a unit test exercising one path through a unit."> </p> <p> In other words, each unit test is an example of a singular execution path. Tests, then, should have a <a href="http://en.wikipedia.org/wiki/Cyclomatic_complexity">cyclomatic complexity</a> of 1. In other words, you write (test) code with a cyclomatic complexity of 1 in order to test code with a higher cyclomatic complexity. </p> <p> Should you test code that has a cyclomatic complexity of 1? </p> <p> What would be the point of that? Why would you write a unit test with a cyclomatic complexity of 1 to test a piece of code with a cyclomatic complexity of 1? Wouldn't you just be adding more code? </p> <p> From the perspective of <em>trusting</em> the code, there's no reason to trust such a test more than the code that it exercises. In that light, I think it makes sense to <em>not</em> write that test. </p> <p> To be clear, there could be other reasons to test code with a cyclomatic complexity of 1. One reason, that I pointed out in my original article, is that you don't know if the simple piece of code will <em>stay</em> simple. Another reason is to prevent regressions. A common metaphor for unit testing is <a href="http://en.wikipedia.org/wiki/Double-entry_bookkeeping_system">double-entry bookkeeping</a>. If you write the unit test in a different way than the implementation, the two views on that behaviour may keep each other in check. You could do that with triangulation using <a href="http://xunitpatterns.com/Parameterized%20Test.html">parametrised tests</a>, or perhaps with property-based testing. </p> <p> I tend to use a heuristic where the farther to the left I am on the above continuum, the more I'm inclined to skip testing of simple functionality. Code with a cyclomatic complexity of 1 falls into that bucket. </p> <h3 id="5899a274dd0f4697b86772d3d0a5d6ce"> TDD <a href="#5899a274dd0f4697b86772d3d0a5d6ce" title="permalink">#</a> </h3> <p> Let's return our attention to TDD. The previous paragraphs have mostly discussed automated tests as a way to prevent regressions. TDD gives us an entirely different motivation for writing tests: the tests provide feedback on the design of our production code. </p> <p> Viewed like this, the tests themselves are only artefacts of the TDD process. It's usually a good idea to keep them around after the standard red-green-refactor cycle, because they serve double-duty as regression tests. </p> <p> Should you test-drive everything? If you're inexperienced with TDD, you get the best exercise by test-driving as much as possible. This still doesn't have to mean that you must write a an explicit test case for each class member. That's what both Mark Rendle and Derick Bailey pointed out. It's often enough if the tests somehow exercise those members. </p> <p> Revisiting my old article, my mistake was that I conflated TDD with regression testing. My motivation for writing an explicit test case for each member, no matter how trivial, was to preserve backwards compatibility. It really had nothing to do with TDD. </p> <h3 id="f0834719ee414d7e81a32c7cb32e8256"> When in doubt <a href="#f0834719ee414d7e81a32c7cb32e8256" title="permalink">#</a> </h3> <p> Despite all other rules of thumb I've so far listed, I'll suggest a few exceptions. </p> <p> Even if a piece of code theoretically has a cyclomatic complexity of 1, if you're in doubt of how it works, then write a test. </p> <p> If you have a defect in production, then reproduce that defect with one or more tests, even if the code in question is 'trivial'. Obviously, it wasn't trivial after all, if it caused a bug in production. </p> <h3 id="51cfec77312e45f7a2dd60b55096ba17"> Pragmatism <a href="#51cfec77312e45f7a2dd60b55096ba17" title="permalink">#</a> </h3> <p> When you're leaning something new, you're typically struggling with even the most basic concepts. That's just how learning works. In that phase of learning, it often pays to follow explicit rules. A way to think about this is the <a href="http://en.wikipedia.org/wiki/Dreyfus_model_of_skill_acquisition">Dreyfus model of skill acquisition</a>. Once you gain some experience, you can start deviating from the rules. We could call this <em>pragmatism</em>. </p> <p> I often discuss TDD with people who plead for pragmatism. Those people have typically practised TDD for years, if not decades. So have I, and, believe it or not, I'm often quite pragmatic when I practice TDD 'for real'. This is, however, a prerogative of experience. <blockquote> You can only be pragmatic if you know how to be dogmatic. </blockquote> I use the concept of <em>dogmatism</em> as an antonym to <em>pragmatism</em>. I view pragmatism in programming as the choice of practical solutions over theoretical principles. It's a <em>choice</em>, which means that you must be aware of alternatives. </p> <p> If you don't know the (principled) alternative, there's no choice. </p> <p> When you're learning something new, you're still not aware of how to do things according to principle. That's natural. I find myself in that situation all the time. If you keep at it, though, eventually you'll have gained enough experience that you can make actual choices. </p> <p> This applies to TDD as well. When you're still learning TDD, stick to the principles, particularly when it's inconvenient. Once you've done TDD for a few years, you've earned the right to be pragmatic. </p> <h3 id="11ce36adfdeb4b8e8c6b640e28691aa0"> Conclusion <a href="#11ce36adfdeb4b8e8c6b640e28691aa0" title="permalink">#</a> </h3> <p> Which parts of your code base should you (unit) test? It Depends™. </p> <p> It depends on why you are unit testing, and on the cost of defects in production, and probably many other things I didn't think of. </p> <p> What's the purpose of tests? Are you using TDD to get feedback on your API design ideas? Or is the main purpose of tests to prevent regressions? Your answers to such questions should guide your decisions on how much to test. </p> <p> Recently, I've mostly been writing about topics related to computer science, such as the <a href="http://blog.ploeh.dk/2017/10/04/from-design-patterns-to-category-theory">relationships between various branches of mathematics to computation</a>. In such realms, laws apply, and answers tend to be either right or wrong. A piece like this article is different. </p> <p> This is fundamentally a deeply subjective essay. It's based on my experience with writing automated tests in various circumstances since 2003. I've tried to be as explicit about my context as possible, but I've most likely failed to identify one or more implicit assumptions or biases. I do, therefore, encourage comments. </p> <p> I wrote this commentary because people keep asking me about how much to test, and when. I suppose it's because they wish to learn from me, and I'm happy to share what I know, to the best of my ability. I have much to learn myself, though, so read this only as the partial, flawed, personal answer that it is. </p> </div> <hr> This blog is totally free, but if you like it, please <a href="https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=NZEPYW8KVZ8WL">buy me a cup of coffee</a>. Mark Seemann http://blog.ploeh.dk/2018/11/12/what-to-test-and-not-to-test Applicative validation http://blog.ploeh.dk/2018/11/05/applicative-validation/ Mon, 05 Nov 2018 07:05:00 UTC <div id="post"> <p> <em>Validate input in applicative style for superior readability and composability.</em> </p> <p> This article is an instalment in <a href="http://blog.ploeh.dk/2018/10/01/applicative-functors">an article series about applicative functors</a>. It demonstrates how applicative style can be used to compose small validation functions to a larger validation function in such a way that no validation messages are lost, and the composition remains readable. </p> <p> All example code in this article is given in <a href="https://www.haskell.org">Haskell</a>. No <a href="https://fsharp.org">F#</a> translation is offered, because <a href="http://fsharpforfunandprofit.com">Scott Wlaschin</a> has an <a href="https://fsharpforfunandprofit.com/posts/elevated-world-3/#validation">equivalent example covering input validation in F#</a>. </p> <h3 id="789d9704d9a2434f8631d718e8be3f17"> JSON validation <a href="#789d9704d9a2434f8631d718e8be3f17" title="permalink">#</a> </h3> <p> In my <a href="http://blog.ploeh.dk/functional-architecture-with-fsharp">Pluralsight course about a functional architecture in F#</a>, you can see an example of an on-line restaurant reservation system. I often return to that example scenario, so for regular readers of this blog, it should be known territory. For newcomers, imagine that you've been asked to develop an HTTP-based API that accepts JSON documents containing restaurant reservations. Such a JSON document could look like this: </p> <p> <pre>{ &nbsp;&nbsp;<span style="color:#2e75b6;">&quot;date&quot;</span>:&nbsp;<span style="color:#a31515;">&quot;2017-06-27&nbsp;18:30:00+02:00&quot;</span>, &nbsp;&nbsp;<span style="color:#2e75b6;">&quot;name&quot;</span>:&nbsp;<span style="color:#a31515;">&quot;Mark&nbsp;Seemann&quot;</span>, &nbsp;&nbsp;<span style="color:#2e75b6;">&quot;email&quot;</span>:&nbsp;<span style="color:#a31515;">&quot;mark@example.com&quot;</span>, &nbsp;&nbsp;<span style="color:#2e75b6;">&quot;quantity&quot;</span>:&nbsp;4 }</pre> </p> <p> It contains the date and time of the (requested) reservation, the email address and name of the person making the reservation, as well as the number of people who will be dining. Particularly, notice that the date and time is represented as a string value (specifically, in <a href="https://en.wikipedia.org/wiki/ISO_8601">ISO 8601</a> format), since JSON has no built-in date and time data type. </p> <p> In Haskell, you can represent such a JSON document using a type like this: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;<span style="color:#dd0000;">ReservationJson</span>&nbsp;<span style="color:#666666;">=</span>&nbsp;<span style="color:#dd0000;">ReservationJson</span>&nbsp;{ &nbsp;&nbsp;<span style="color:#600277;">jsonDate</span>&nbsp;::&nbsp;String, &nbsp;&nbsp;<span style="color:#600277;">jsonQuantity</span>&nbsp;::&nbsp;Double, &nbsp;&nbsp;<span style="color:#600277;">jsonName</span>&nbsp;::&nbsp;String, &nbsp;&nbsp;<span style="color:#600277;">jsonEmail</span>&nbsp;::&nbsp;String&nbsp;} &nbsp;&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#a31515;">Eq</span>,&nbsp;<span style="color:#a31515;">Show</span>,&nbsp;<span style="color:#a31515;">Read</span>,&nbsp;<span style="color:#a31515;">Generic</span>)</pre> </p> <p> Haskell's strength is in its type system, so you should prefer to model a reservation using a strong type: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;<span style="color:#dd0000;">Reservation</span>&nbsp;<span style="color:#666666;">=</span>&nbsp;<span style="color:#dd0000;">Reservation</span>&nbsp;{ &nbsp;&nbsp;<span style="color:#600277;">reservationDate</span>&nbsp;::&nbsp;<span style="color:blue;">ZonedTime</span>, &nbsp;&nbsp;<span style="color:#600277;">reservationQuantity</span>&nbsp;::&nbsp;Int, &nbsp;&nbsp;<span style="color:#600277;">reservationName</span>&nbsp;::&nbsp;String, &nbsp;&nbsp;<span style="color:#600277;">reservationEmail</span>&nbsp;::&nbsp;String&nbsp;} &nbsp;&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#a31515;">Show</span>,&nbsp;<span style="color:#a31515;">Read</span>)</pre> </p> <p> Instead of modelling the date and time as a string, you model it as a <code>ZonedTime</code> value. Additionally, you should model quantity as an integer, since a floating point value doesn't make much sense. </p> <p> While you can always translate a <code>Reservation</code> value to a <code>ReservationJson</code> value, the converse doesn't hold. There are <code>ReservationJson</code> values that you can't translate to <code>Reservation</code>. Such <code>ReservationJson</code> values are invalid. </p> <p> You should write code to validate and translate <code>ReservationJson</code> values to <code>Reservation</code> values, if possible. </p> <h3 id="e71bff7b635a449eb05a503c75c4f887"> Specialised validations <a href="#e71bff7b635a449eb05a503c75c4f887" title="permalink">#</a> </h3> <p> The <code>ReservationJson</code> type is a complex type, because it's composed of multiple (four) elements of different types. You can easily define at least three validation rules that ought to hold: <ol> <li>You should be able to convert the <code>jsonDate</code> value to a <code>ZonedTime</code> value.</li> <li><code>jsonQuantity</code> must be a positive integer.</li> <li><code>jsonEmail</code> should look believably like an email address.</li> </ol> When you have a complex type where more than one validation rule applies, your code will be most readable and maintainable if you can write each rule as an independent function. </p> <p> In Haskell, people often use <code>Either</code> for validation, but instead of using <code>Either</code> directly, I'll introduce a specialised <code>Validation</code> type: </p> <p> <pre><span style="color:blue;">newtype</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;e&nbsp;r&nbsp;<span style="color:#666666;">=</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;(<span style="color:#dd0000;">Either</span>&nbsp;e&nbsp;r)&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#a31515;">Eq</span>,&nbsp;<span style="color:#a31515;">Show</span>,&nbsp;<span style="color:#a31515;">Functor</span>) </pre> </p> <p> You'll notice that this is simply a redefinition of <code>Either</code>. Haskell can automatically derive its <code>Functor</code> instance with the <code>DeriveFunctor</code> language extension. </p> <p> My motivation for introducing a new type is that the way that <code>Either</code> is <code>Applicative</code> is not quite how I'd like it to be. Introducing a <code>newtype</code> enables you to change how a type behaves. More on that later. First, you can implement the three individual validation functions. </p> <h3 id="89e88d794a0449189eff92795a2bca04"> Date validation <a href="#89e88d794a0449189eff92795a2bca04" title="permalink">#</a> </h3> <p> If the JSON date value is an ISO 8601-formatted string, then you can parse it as a <code>ZonedTime</code>. In that case, you should return the <code>Right</code> case of <code>Validation</code>. If you can't parse the string into a <code>ZonedTime</code> value, you should return a <code>Left</code> value containing a helpful error message. </p> <p> <pre><span style="color:#600277;">validateDate</span>&nbsp;::&nbsp;String&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Validation</span>&nbsp;[String]&nbsp;<span style="color:blue;">ZonedTime</span> validateDate&nbsp;candidate&nbsp;<span style="color:#666666;">=</span> &nbsp;&nbsp;<span style="color:blue;">case</span>&nbsp;readMaybe&nbsp;candidate&nbsp;<span style="color:blue;">of</span> &nbsp;&nbsp;&nbsp;&nbsp;Just&nbsp;d&nbsp;&nbsp;<span style="color:#666666;">-&gt;</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;<span style="color:#666666;">$</span>&nbsp;Right&nbsp;d &nbsp;&nbsp;&nbsp;&nbsp;Nothing&nbsp;<span style="color:#666666;">-&gt;</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;<span style="color:#666666;">$</span>&nbsp;Left&nbsp;[<span style="color:#a31515;">&quot;Not&nbsp;a&nbsp;date.&quot;</span>]</pre> </p> <p> This function uses <code>readMaybe</code> from <code>Text.Read</code> to attempt to parse the <code>candidate</code> <code>String</code>. When <code>readMaybe</code> can read the <code>String</code> value, it returns a <code>Just</code> value with the parsed value inside; otherwise, it returns <code>Nothing</code>. The function pattern-matches on those two cases and returns the appropriate value in each case. </p> <p> Notice that errors are represented as a list of <code>String</code> values, although this particular function only returns a single message in its list of error messages. The reason for that is that you should be able to collect multiple validation issues for a complex value such as <code>ReservationJson</code>, and keeping track of errors in a list makes that possible. </p> <p> Haskell <a href="https://en.wikipedia.org/wiki/Code_golf">golfers</a> may argue that this implementation is overly verbose, and it could, for instance, instead be written as: </p> <p> <pre>validateDate&nbsp;<span style="color:#666666;">=</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;<span style="color:#666666;">.</span>&nbsp;maybe&nbsp;(Left&nbsp;[<span style="color:#a31515;">&quot;Not&nbsp;a&nbsp;date.&quot;</span>])&nbsp;Right&nbsp;<span style="color:#666666;">.</span>&nbsp;readMaybe </pre> </p> <p> which is true, but not as readable. Both versions get the job done, though, as these GCHi-based ad-hoc tests demonstrate: </p> <p> <pre>λ&gt; validateDate "2017/27/06 18:30:00 UTC+2" Validation (Left ["Not a date."]) λ&gt; validateDate "2017-06-27 18:30:00+02:00" Validation (Right 2017-06-27 18:30:00 +0200)</pre> </p> <p> That takes care of parsing dates. On to the next validation function. </p> <h3 id="df33c4c13805494b844793bac0577e5b"> Quantity validation <a href="#df33c4c13805494b844793bac0577e5b" title="permalink">#</a> </h3> <p> JSON numbers aren't guaranteed to be integers, so it's possible that even a well-formed Reservation JSON document could contain a <code>quantity</code> property of <code>9.7</code>, <code>-11.9463</code>, or similar. When handling restaurant reservations, however, it only makes sense to handle positive integers. Even <code>0</code> is useless in this context. Thus, validation must check for two conditions, so in principle, you could write two separate functions for that. In order to keep the example simple, though, I've included both tests in the same function: </p> <p> <pre><span style="color:#600277;">validateQuantity</span>&nbsp;::&nbsp;Double&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Validation</span>&nbsp;[String]&nbsp;Int validateQuantity&nbsp;candidate&nbsp;<span style="color:#666666;">=</span> &nbsp;&nbsp;<span style="color:#af00db;">if</span>&nbsp;isInt&nbsp;candidate&nbsp;<span style="color:#666666;">&amp;&amp;</span>&nbsp;candidate&nbsp;<span style="color:#666666;">&gt;</span>&nbsp;<span style="color:#09885a;">0</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#af00db;">then</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;<span style="color:#666666;">$</span>&nbsp;Right&nbsp;<span style="color:#666666;">$</span>&nbsp;round&nbsp;candidate &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#af00db;">else</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;<span style="color:#666666;">$</span>&nbsp;Left&nbsp;[<span style="color:#a31515;">&quot;Not&nbsp;a&nbsp;positive&nbsp;integer.&quot;</span>] &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;isInt&nbsp;x&nbsp;<span style="color:#666666;">=</span>&nbsp;x&nbsp;<span style="color:#666666;">==</span>&nbsp;fromInteger&nbsp;(round&nbsp;x)</pre> </p> <p> If <code>candidate</code> is both an integer, and greater than zero, then <code>validateQuantity</code> returns <code>Right</code>; otherwise, it returns a <code>Left</code> value containing an error message. Like <code>validateDate</code>, you can easily test <code>validateQuantity</code> in GHCi: </p> <p> <pre>λ&gt; validateQuantity 4 Validation (Right 4) λ&gt; validateQuantity (-1) Validation (Left ["Not a positive integer."]) λ&gt; validateQuantity 2.32 Validation (Left ["Not a positive integer."])</pre> </p> <p> Perhaps you can think of rules for names, but I can't, so we'll leave the name be and move on to validating email addresses. </p> <h3 id="7eb2c9f79bfa4f7fa866094d094c5e2c"> Email validation <a href="#7eb2c9f79bfa4f7fa866094d094c5e2c" title="permalink">#</a> </h3> <p> It's <a href="http://haacked.com/archive/2007/08/21/i-knew-how-to-validate-an-email-address-until-i.aspx">notoriously difficult to validate SMTP addresses</a>, so you shouldn't even try. It seems fairly safe to assume, however, that an email address must contain at least one <code>@</code> character, so that's going to be all the validation you have to implement: </p> <p> <pre><span style="color:#600277;">validateEmail</span>&nbsp;::&nbsp;String&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Validation</span>&nbsp;[String]&nbsp;String validateEmail&nbsp;candidate&nbsp;<span style="color:#666666;">=</span> &nbsp;&nbsp;<span style="color:#af00db;">if</span>&nbsp;<span style="color:#a31515;">&#39;@&#39;</span>&nbsp;<span style="color:#666666;">`elem`</span>&nbsp;candidate &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#af00db;">then</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;<span style="color:#666666;">$</span>&nbsp;Right&nbsp;candidate &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#af00db;">else</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;<span style="color:#666666;">$</span>&nbsp;Left&nbsp;[<span style="color:#a31515;">&quot;Not&nbsp;an&nbsp;email&nbsp;address.&quot;</span>]</pre> </p> <p> Straightforward. Try it out in GHCI: </p> <p> <pre>λ&gt; validateEmail "foo" Validation (Left ["Not an email address."]) λ&gt; validateEmail "foo@example.org" Validation (Right "foo@example.org")</pre> </p> <p> Indeed, that works. </p> <h3 id="bcfce51ff4e94f79a6648a7e373ebc82"> Applicative composition <a href="#bcfce51ff4e94f79a6648a7e373ebc82" title="permalink">#</a> </h3> <p> What you really should be doing is to validate a <code>ReservationJson</code> value. You have the three validation rules implemented, so now you have to compose them. There is, however, a catch: you must evaluate all rules, and return a list of <em>all</em> the errors you encountered. That's probably going to be a better user experience for a user. </p> <p> That's the reason you can't use <code>Either</code>. While it's <code>Applicative</code>, it doesn't behave like you'd like it to behave in this scenario. Particularly, the problem is that it throws away all but the first <code>Left</code> value it finds: </p> <p> <pre>λ&gt; Right (,,) &lt;*&gt; Right 42 &lt;*&gt; Left "foo" &lt;*&gt; Left "bar" Left "foo"</pre> </p> <p> Notice how <code>Left "bar"</code> is ignored. </p> <p> With the new type <code>Validation</code> based on <code>Either</code>, you can now define how it behaves as an applicative functor: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Monoid</span>&nbsp;m&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;<span style="color:blue;">Applicative</span>&nbsp;(<span style="color:blue;">Validation</span>&nbsp;m)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;pure&nbsp;<span style="color:#666666;">=</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;<span style="color:#666666;">.</span>&nbsp;pure &nbsp;&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;(Left&nbsp;x)&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;(Left&nbsp;y)&nbsp;<span style="color:#666666;">=</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;(Left&nbsp;(mappend&nbsp;x&nbsp;y)) &nbsp;&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;f&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;r&nbsp;<span style="color:#666666;">=</span>&nbsp;<span style="color:#dd0000;">Validation</span>&nbsp;(f&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;r)</pre> </p> <p> This instance is restricted to <code>Monoid</code> <code>Left</code> types. It has special behaviour for the case where both expressions passed to <code>&lt;*&gt;</code> are <code>Left</code> values. In that case, it uses <code>mappend</code> (from <code>Monoid</code>) to 'add' the two <code>Left</code> values together in a new <code>Left</code> value. </p> <p> For all other cases, this instance of <code>Applicative</code> delegates to the behaviour defined for <code>Either</code>. It also uses <code>pure</code> from <code>Either</code> to implement its own <code>pure</code> function. </p> <p> Lists (<code>[]</code>) <a href="http://blog.ploeh.dk/2017/10/10/strings-lists-and-sequences-as-a-monoid">form a monoid</a>, and since all the above validation functions return lists of errors, it means that you can compose them using this definition of <code>Applicative</code>: </p> <p> <pre><span style="color:#600277;">validateReservation</span>&nbsp;::&nbsp;<span style="color:blue;">ReservationJson</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Validation</span>&nbsp;[String]&nbsp;<span style="color:blue;">Reservation</span> validateReservation&nbsp;candidate&nbsp;<span style="color:#666666;">=</span> &nbsp;&nbsp;pure&nbsp;<span style="color:#dd0000;">Reservation</span>&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;vDate&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;vQuantity&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;vName&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;vEmail &nbsp;&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;&nbsp;&nbsp;vDate&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#666666;">=</span>&nbsp;validateDate&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#666666;">$</span>&nbsp;jsonDate&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;candidate &nbsp;&nbsp;&nbsp;&nbsp;vQuantity&nbsp;<span style="color:#666666;">=</span>&nbsp;validateQuantity&nbsp;<span style="color:#666666;">$</span>&nbsp;jsonQuantity&nbsp;candidate &nbsp;&nbsp;&nbsp;&nbsp;vName&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#666666;">=</span>&nbsp;pure&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#666666;">$</span>&nbsp;jsonName&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;candidate &nbsp;&nbsp;&nbsp;&nbsp;vEmail&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#666666;">=</span>&nbsp;validateEmail&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#666666;">$</span>&nbsp;jsonEmail&nbsp;&nbsp;&nbsp;&nbsp;candidate</pre> </p> <p> The <code>candidate</code> is a <code>ReservationJson</code> value, but each of the validation functions work on either <code>String</code> or <code>Double</code>, so you'll have to use the <code>ReservationJson</code> type's access functions (<code>jsonDate</code>, <code>jsonQuantity</code>, and so on) to pull the relevant values out of it. Once you have those, you can pass them as arguments to the appropriate validation function. </p> <p> Since there's no rule for <code>jsonName</code>, you can use <code>pure</code> to create a <code>Validation</code> value. All four resulting values (<code>vDate</code>, <code>vQuantity</code>, <code>vName</code>, and <code>vEmail</code>) are <code>Validation [String]</code> values; only their <code>Right</code> types differ. </p> <p> The <code>Reservation</code> record constructor is a function of the type <code>ZonedTime -&gt; Int -&gt; String -&gt; String -&gt; Reservation</code>, so when you arrange the four <code>v*</code> values correctly between the <code>&lt;*&gt;</code> operator, you have the desired composition. </p> <p> Try it in GHCi: </p> <p> <pre>λ&gt; validateReservation $ ReservationJson "2017-06-30 19:00:00+02:00" 4 "Jane Doe" "j@example.com" Validation (Right (Reservation { &nbsp;&nbsp;&nbsp;&nbsp;reservationDate = 2017-06-30 19:00:00 +0200, &nbsp;&nbsp;&nbsp;&nbsp;reservationQuantity = 4, &nbsp;&nbsp;&nbsp;&nbsp;reservationName = "Jane Doe", &nbsp;&nbsp;&nbsp;&nbsp;reservationEmail = "j@example.com"})) λ&gt; validateReservation $ ReservationJson "2017/14/12 6pm" 4.1 "Jane Doe" "jane.example.com" Validation (Left ["Not a date.","Not a positive integer.","Not an email address."]) λ&gt; validateReservation $ ReservationJson "2017-06-30 19:00:00+02:00" (-3) "Jane Doe" "j@example.com" Validation (Left ["Not a positive integer."])</pre> </p> <p> The first <code>ReservationJson</code> value passed to <code>validateReservation</code> is valid, so the return value is a <code>Right</code> value. </p> <p> The next <code>ReservationJson</code> value is about as wrong as it can be, so three different error messages are returned in a <code>Left</code> value. This demonstrates that <code>Validation</code> doesn't give up the first time it encounters a <code>Left</code> value, but rather collects them all. </p> <p> The third example demonstrates that even a single invalid value (in this case a negative quantity) is enough to make the entire input invalid, but as expected, there's only a single error message. </p> <h3 id="b9d3fd6c208647dc988ef0ffc64cf061"> Summary <a href="#b9d3fd6c208647dc988ef0ffc64cf061" title="permalink">#</a> </h3> <p> Validation may be the poster child of applicative functors, but it <em>is</em> a convenient way to solve the problem. In this article you saw how to validate a complex data type, collecting and reporting on all problems, if any. </p> <p> In order to collect all errors, instead of immediately short-circuiting on the first error, you have to deviate from the standard <code>Either</code> implementation of <code>&lt;*&gt;</code>. If you go back to read Scott Wlaschin's article, you should be aware that it specifically implements its applicative functor in that way, instead of the normal behaviour of <code>Either</code>. </p> <p> More applicative functors exist. This article series has, I think, room for more examples. </p> <p> <strong>Next:</strong> The Test Data Generator applicative functor. </p> </div><hr> This blog is totally free, but if you like it, please <a href="https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=NZEPYW8KVZ8WL">buy me a cup of coffee</a>. Mark Seemann http://blog.ploeh.dk/2018/11/05/applicative-validation The Maybe applicative functor http://blog.ploeh.dk/2018/10/29/the-maybe-applicative-functor/ Mon, 29 Oct 2018 06:17:00 UTC <div id="post"> <p> <em>An introduction to the Maybe applicative functor for object-oriented programmers.</em> </p> <p> This article is an instalment in <a href="http://blog.ploeh.dk/2018/10/01/applicative-functors">an article series about applicative functors</a>. Previously, in a related series, you got an introduction to <a href="http://blog.ploeh.dk/2018/03/26/the-maybe-functor">Maybe as a functor</a>. Not all functors are applicative, but some are, and Maybe is one of them (like list). </p> <p> In this article, you'll see how to make a C# Maybe class applicative. While I'm going to start with <a href="https://fsharp.org">F#</a> and <a href="https://www.haskell.org">Haskell</a>, you can skip to the C# section if you'd like. </p> <h3 id="f88a2d0afbe84b7695fe4247e3cfe941"> F# <a href="#f88a2d0afbe84b7695fe4247e3cfe941" title="permalink">#</a> </h3> <p> A few years ago, <a href="http://blog.ploeh.dk/2016/06/28/roman-numerals-via-property-based-tdd">I did the <em>Roman numerals</em> kata</a> in F#. This is an exercise where you have to convert between normal base 10 integers and <a href="https://en.wikipedia.org/wiki/Roman_numerals">Roman numerals</a>. Conversions can fail in both directions, because Roman numerals don't support negative numbers, zero, or numbers greater than 3,999, and Roman numerals represented as strings could be malformed. </p> <p> Some Roman numbers are written in a subtractive style, e.g. "IV" means <em>subtract 1 (I) from 5 (V)</em>. It's easy enough to subtract two numbers, but because parsing isn't guaranteed to succeed, I didn't have two numbers; I had two number <em>options</em> (recall that in F#, Maybe is called <code>option</code>). </p> <p> How do you subtract one <code>int option</code> from another <code>int option</code>? </p> <p> Both of these values could be <code>Some</code>, or they could be <code>None</code>. What should happen in each case? With Maybe, only four combinations are possible, so you can put them in a table: <table> <thead> <tr> <th></th> <th><code>Some x</code></th> <th><code>None</code></th> </tr> </thead> <tbody> <tr> <td><strong><code>Some y</code></strong></td> <td><code>Some (x - y)</code></td> <td><code>None</code></td> </tr> <tr> <td><strong><code>None</code></strong></td> <td><code>None</code></td> <td><code>None</code></td> </tr> </tbody> </table> Only if both values are <code>Some</code> cases should you return a <code>Some</code> case with the result of the subtraction; in all other cases, you should return <code>None</code>. </p> <p> You can do this with regular pattern matching, but it's hardly the most elegant solution: </p> <p> <pre><span style="color:green;">//&nbsp;int&nbsp;option</span> <span style="color:blue;">let</span>&nbsp;difference&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">match</span>&nbsp;minuend,&nbsp;subtrahend&nbsp;<span style="color:blue;">with</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:navy;">Some</span>&nbsp;m,&nbsp;<span style="color:navy;">Some</span>&nbsp;s&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:navy;">Some</span>&nbsp;(m&nbsp;-&nbsp;s) &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;_&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:navy;">None</span></pre> </p> <p> You <em>could</em> attempt to solve this with a specialised helper function like this: </p> <p> <pre><span style="color:blue;">module</span>&nbsp;<span style="color:teal;">Option</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;&#39;a&nbsp;option&nbsp;-&gt;&nbsp;&#39;b&nbsp;option&nbsp;-&gt;&nbsp;&#39;c&nbsp;option</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:navy;">map2</span>&nbsp;<span style="color:navy;">f</span>&nbsp;xo&nbsp;yo&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">match</span>&nbsp;xo,&nbsp;yo&nbsp;<span style="color:blue;">with</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:navy;">Some</span>&nbsp;x,&nbsp;<span style="color:navy;">Some</span>&nbsp;y&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:navy;">Some</span>&nbsp;(<span style="color:navy;">f</span>&nbsp;x&nbsp;y) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;_&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:navy;">None</span></pre> </p> <p> which you could use like this: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;difference&nbsp;=&nbsp;<span style="color:teal;">Option</span>.<span style="color:navy;">map2</span>&nbsp;(-)&nbsp;minuend&nbsp;subtrahend </pre> </p> <p> It doesn't, however, generalise well... What if you need to operate on three option values, instead of two? Or four? Should you add <code>map3</code> and <code>map4</code> functions as well? </p> <p> Making <code>option</code> an applicative functor addresses that problem. Here's one possible implementation of <code>&lt;*&gt;</code>: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b)&nbsp;option&nbsp;-&gt;&nbsp;&#39;a&nbsp;option&nbsp;-&gt;&nbsp;&#39;b&nbsp;option</span> <span style="color:blue;">let</span>&nbsp;(&lt;*&gt;)&nbsp;fo&nbsp;xo&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">match</span>&nbsp;fo,&nbsp;xo&nbsp;<span style="color:blue;">with</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:navy;">Some</span>&nbsp;<span style="color:navy;">f</span>,&nbsp;<span style="color:navy;">Some</span>&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:navy;">Some</span>&nbsp;(<span style="color:navy;">f</span>&nbsp;x) &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;_&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:navy;">None</span></pre> </p> <p> This enables you two write the subtraction like this: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;difference&nbsp;=&nbsp;<span style="color:navy;">Some</span>&nbsp;(-)&nbsp;&lt;*&gt;&nbsp;minuend&nbsp;&lt;*&gt;&nbsp;subtrahend </pre> </p> <p> For a detailed explanation on how that works, see the <a href="http://blog.ploeh.dk/2018/10/08/full-deck">previous explanation for lists</a>; it works the same way for Maybe as it does for List. </p> <p> In the end, however, I didn't think that this was the most readable code, so in the Roman numeral exercise, I chose to use a <a href="https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/computation-expressions">computation expression</a> instead. </p> <h3 id="264aaa993b7643b692716bed1b3e2b92"> Haskell <a href="#264aaa993b7643b692716bed1b3e2b92" title="permalink">#</a> </h3> <p> In Haskell, <code>Maybe</code> is already <code>Applicative</code> as part of the language. Without further ado, you can simply write: </p> <p> <pre>difference&nbsp;<span style="color:#666666;">=</span>&nbsp;pure&nbsp;<span style="color:#600277;">(-)</span>&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;minuend&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;subtrahend </pre> </p> <p> As is the case with the F# code, I don't consider this the most <em>readable</em> way to express the subtraction of two integers. In F#, I ultimately decided to use a computation expression. In Haskell, that's equivalent to using <code>do</code> notation: </p> <p> <pre><span style="color:#600277;">difference</span>&nbsp;::&nbsp;Maybe&nbsp;Integer difference&nbsp;<span style="color:#666666;">=</span>&nbsp;<span style="color:#af00db;">do</span> &nbsp;&nbsp;m&nbsp;<span style="color:#666666;">&lt;-</span>&nbsp;minuend &nbsp;&nbsp;s&nbsp;<span style="color:#666666;">&lt;-</span>&nbsp;subtrahend &nbsp;&nbsp;return&nbsp;<span style="color:#666666;">$</span>&nbsp;m&nbsp;<span style="color:#666666;">-</span>&nbsp;s</pre> </p> <p> While more verbose, I think it's clearer that one number is being subtracted from another number. </p> <p> This works for <code>Maybe</code> because not only is <code>Maybe</code> <code>Applicative</code>, it's also a <code>Monad</code>. It's its monadness that enables the <code>do</code> notation. Not all applicative functors are monads, but Maybe is. </p> <h3 id="67a752fec39f4944984f505c125632f1"> C# <a href="#67a752fec39f4944984f505c125632f1" title="permalink">#</a> </h3> <p> In a <a href="http://blog.ploeh.dk/2018/03/26/the-maybe-functor">previous article</a> you saw how to implement the Maybe functor in C#. You can extend it so that it also becomes an applicative functor: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;Apply&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;&nbsp;selector, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;source) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(selector.HasItem&nbsp;&amp;&amp;&nbsp;source.HasItem) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;(selector.Item(source.Item)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;(); } <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;&nbsp;Apply&lt;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;&nbsp;selector, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">T1</span>&gt;&nbsp;source) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(selector.HasItem&nbsp;&amp;&amp;&nbsp;source.HasItem) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;g&nbsp;=&nbsp;x&nbsp;=&gt;&nbsp;selector.Item(source.Item,&nbsp;x); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;(g); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;(); }</pre> </p> <p> As was the case for making sequences applicative in C#, you <a href="http://blog.ploeh.dk/2018/10/15/an-applicative-password-list">need overloads of the <code>Apply</code> method</a>, because C#'s type inference is inadequate for this task. </p> <p> If you have two <code>Maybe&lt;int&gt;</code> values, <code>minuend</code> and <code>subtrahend</code>, you can now perform the subtraction: </p> <p> <pre><span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;subtract&nbsp;=&nbsp;(x,&nbsp;y)&nbsp;=&gt;&nbsp;x&nbsp;-&nbsp;y; <span style="color:#2b91af;">Maybe</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;difference&nbsp;=&nbsp;subtract.ToMaybe().Apply(minuend).Apply(subtrahend);</pre> </p> <p> Like in F# and Haskell, applicative style is hardly the most readable way to express subtraction. It'd be nice if you could write it like Haskell's <code>do</code> notation. You can, but to do that, you must make Maybe a monad, and this isn't a monad tutorial. <a href="http://mikehadlow.com">Mike Hadlow</a> has a good <a href="http://mikehadlow.blogspot.dk/2011/01/monads-in-c1-introduction.html">monad tutorial for C# developers</a>, the gist of which is that you must implement <code>SelectMany</code> in order to turn your generic type into a monad. For now, I'll leave this as an exercise for you, but if you add an appropriate <code>SelectMany</code> method, you'd be able to write the subtraction like this: </p> <p> <pre><span style="color:#2b91af;">Maybe</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;difference&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">from</span>&nbsp;m&nbsp;<span style="color:blue;">in</span>&nbsp;minuend &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">from</span>&nbsp;s&nbsp;<span style="color:blue;">in</span>&nbsp;subtrahend &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">select</span>&nbsp;m&nbsp;-&nbsp;s;</pre> </p> <p> Again, I think this is more readable, but it does require that the type in question is a monad, and not all applicative functors are (but Maybe is). </p> <h3 id="b03175fcd3a74155a3ceac26fb02aed0"> Summary <a href="#b03175fcd3a74155a3ceac26fb02aed0" title="permalink">#</a> </h3> <p> This article demonstrates that lists or sequences aren't the only applicative functors. Maybe is also an applicative functor, but more exist. The next article will give you another example. </p> <p> <strong>Next:</strong> <a href="http://blog.ploeh.dk/2018/11/05/applicative-validation">Applicative validation</a>. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="d42afea512c243019f500a345638cecb"> <div class="comment-author">Tyson Williams</div> <div class="comment-content"> <blockquote> As was the case for making sequences applicative in C#, you <a href="http://blog.ploeh.dk/2018/10/15/an-applicative-password-list">need overloads of the <code>Apply</code> method</a>, because C#'s type inference is inadequate for this task. </blockquote> <p> I think <a href=http://blog.ploeh.dk/2018/10/15/an-applicative-password-list/#b4e76681ea894aa3be1e6b836343c148">we agreed</a> that the issue is not C#'s weak type inference but its lack of default function currying? My guess is that you wrote this quoted part of this article before my comment on your previous article. </p> </div> <div class="comment-date">2018-11-06 02:44 UTC</div> </div> <div class="comment" id="0bb16509bbea463bab48c9e97acea2c5"> <div class="comment-author"><a href="http://blog.ploeh.dk">Mark Seemann</a></div> <div class="comment-content"> <p> Tyson, thank you for writing. <blockquote> "My guess is that you wrote this quoted part of this article before my comment on your previous article." </blockquote> Yes, <a href="https://github.com/ploeh/ploeh.github.com/commit/078cb3e938bfb911363cc8ab1139dfc5ad435349">June 27, 2017, in fact</a>... </p> <p> You're correct that this particular issue is related to the uncurried nature of C# methods. </p> <p> I do, however, maintain that C#'s type inference capabilities are weaker than F#'s or Haskell's. To be clear, I view this as the result of priorities. I don't think that the people who designed and wrote the C# compiler are less skilled than the designers of F# or Haskell. The C# compiler has to solve many other problems, such as for example overload resolution, which is a language feature in direct opposition to currying. The C# compiler is excellent at overload resolution, a task with which the F# compiler sometimes struggle (and is not even a language feature in Haskell). </p> <p> Your comment is, however, a reminder that I should consider how I phrase such notions in the future. Thank you for pointing that out. As I'm publishing and get feedback, I constantly learn new things. I'm always grateful when someone like you take the time to educate me. </p> <p> I'll see if I can improve in the future. I do, however, still have a backlog of articles I wrote months, or even more than a year, ago, so it's possible that more errors escape my attention when I proof read them before publication. If that happens, I'll appreciate more corrections. </p> </div> <div class="comment-date">2018-11-06 7:30 UTC</div> </div> <div class="comment" id="01d5086d3f9a4d93ad4bea131521bafa"> <div class="comment-author">Tyson Williams</div> <div class="comment-content"> <p> Thank you very much for your kind reply. I agree with everything you said. </p> <p> I will expand my comment a bit to give a clearer picture of my understanding. </p> <p> First, very little is "needed"; most things are merely sufficient. In particular, we don't <i>need</i> to overload your <code>Apply</code> method to achieve your goal. As <a href="http://blog.ploeh.dk/2018/10/15/an-applicative-password-list/#0ded7ac93aad8ba7b1063dd49c2051f1">I mentioned before</a>, it sufficies to have a single <code>Apply</code> method and instead create overloads of a function called <code>curry</code> that explicitly curries a given function. Furthermore, I think there is a sense in which this latter approach to overcome the lack of default currying is somehow minimal or most abstract or most general. </p> <p> Second, compared to languages like F# or Haskell, type inference is definitely weaker in C#. This issue was also present (in a subtle way) in your previous article, but I decided to largely ignore it in order to keep my comment more focused. In your <a href="http://blog.ploeh.dk/2018/10/15/an-applicative-password-list/">previous article</a>, you expliciltly defined the local variable <code>concat</code> like this <blockquote> <pre><span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;concat&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;(x,&nbsp;y,&nbsp;z,&nbsp;æ,&nbsp;ø,&nbsp;å)&nbsp;=&gt;&nbsp;x&nbsp;+&nbsp;y&nbsp;+&nbsp;z&nbsp;+&nbsp;æ&nbsp;+&nbsp;ø&nbsp;+&nbsp;å;</pre> </blockquote> In particular, you explicitly told the C# compiler that the type of all of these six variable is <code><span style="color:blue;">string</span></code>. That part was necessary; the type inference in C# is not strong enough to innfer (possibily in some use of <code>concat</code>) that the types could be <code><span style="color:blue;">string</span></code>. </p> <p> Suppose instead of defining <code>concat</code> as a local variable (with <code><span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;</code> as its type) you had defined it as a member method on a class. Then its type in C# is some kind "method group". The method group of a method essentially corresponds to the set of methods containing itself and its overloads. Then in order to pass <code>concat</code> into <code>curry</code>, there needs to be a type conversion (or cast) from its method group to <code><span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;</code>. This is also something that the C# system cannot do, and so Language Ext has overloads of a <a href="https://github.com/louthy/language-ext/blob/master/LanguageExt.Core/Prelude/Prelude_Func.cs#L24">function called <code>fun</code></a> to do this explicitly. Using it on our hypothetical member function <code>concat</code> would look like <pre>fun&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;(concat)</pre> Again, I think there is a sense in which this explicit way to specify non-inferable types is somehow minimal or most abstract or most general. </p> <p> My impression is that there is some low hanging fruit here for strengthing the type inference of the C# compiler. If a method group correpsonds to a singleton set (and that method has no <code>ref</code> or <code>out</code> arguments), then I would think it would be straight forward to consider an implicit cast from the method group to the corresponding <code>Func</code> or <code>Action</code> delegate. </p> </div> <div class="comment-date">2018-11-06 15:31 UTC</div> </div> </div> <hr> This blog is totally free, but if you like it, please <a href="https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=NZEPYW8KVZ8WL">buy me a cup of coffee</a>. Mark Seemann http://blog.ploeh.dk/2018/10/29/the-maybe-applicative-functor Applicative combinations of functions http://blog.ploeh.dk/2018/10/22/applicative-combinations-of-functions/ Mon, 22 Oct 2018 10:21:00 UTC <div id="post"> <p> <em>Applicative lists and sequences enable you to create combinations of functions as well as values.</em> </p> <p> This article is an instalment in <a href="http://blog.ploeh.dk/2018/10/01/applicative-functors">an article series about applicative functors</a>. In the <a href="http://blog.ploeh.dk/2018/10/15/an-applicative-password-list">previous article</a>, you saw how you can use applicative lists and sequences to generate combinations of values; specifically, the example demonstrated how to generate various password character combinations. </p> <p> People often create passwords by using a common word as basis, and then turn characters into upper- or lower case. Someone feeling particularly tech-savvy may replace certain characters with digits, in an imitation of <a href="https://en.wikipedia.org/wiki/Leet">1337</a>. While this isn't secure, let's look at how to create various combinations of transformations using applicative lists and sequences. </p> <h3 id="302fedff3eed4c09b277bd4ee3523ff3"> List of functions <a href="#302fedff3eed4c09b277bd4ee3523ff3" title="permalink">#</a> </h3> <p> In the previous article, I mentioned that there was a feature of applicative lists that I had, so far, deliberately ignored. </p> <p> If you consider an example like this: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;passwordCombinations&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;[<span style="color:navy;">sprintf</span>&nbsp;<span style="color:#a31515;">&quot;</span><span style="color:teal;">%s%s%s%s%s%s</span><span style="color:#a31515;">&quot;</span>] &nbsp;&nbsp;&nbsp;&nbsp;&lt;*&gt;&nbsp;[<span style="color:#a31515;">&quot;P&quot;</span>;&nbsp;<span style="color:#a31515;">&quot;p&quot;</span>]&nbsp;&lt;*&gt;&nbsp;[<span style="color:#a31515;">&quot;a&quot;</span>;&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>]&nbsp;&lt;*&gt;&nbsp;[<span style="color:#a31515;">&quot;ssw&quot;</span>]&nbsp;&lt;*&gt;&nbsp;[<span style="color:#a31515;">&quot;o&quot;</span>;&nbsp;<span style="color:#a31515;">&quot;0&quot;</span>]&nbsp;&lt;*&gt;&nbsp;[<span style="color:#a31515;">&quot;rd&quot;</span>]&nbsp;&lt;*&gt;&nbsp;[<span style="color:#a31515;">&quot;&quot;</span>;&nbsp;<span style="color:#a31515;">&quot;!&quot;</span>]</pre> </p> <p> you may have already noticed that while the left side of the <code>&lt;*&gt;</code> operator is a list of functions, it contains only a single function. What happens if you supply more than a single function? </p> <p> You get a combination of each function and each list element. </p> <p> Assume that you have three functions to convert characters: </p> <p> <pre><span style="color:blue;">module</span>&nbsp;<span style="color:teal;">Char</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;char&nbsp;-&gt;&nbsp;char</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:navy;">toUpper</span>&nbsp;c&nbsp;=&nbsp;System.<span style="color:teal;">Char</span>.<span style="color:navy;">ToUpperInvariant</span>&nbsp;c &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;char&nbsp;-&gt;&nbsp;char</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:navy;">toLower</span>&nbsp;c&nbsp;=&nbsp;System.<span style="color:teal;">Char</span>.<span style="color:navy;">ToLowerInvariant</span>&nbsp;c &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Not&nbsp;even&nbsp;trying&nbsp;to&nbsp;be&nbsp;complete:</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;char&nbsp;-&gt;&nbsp;char</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:navy;">to1337</span>&nbsp;=&nbsp;<span style="color:blue;">function</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#a31515;">&#39;a&#39;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#a31515;">&#39;A&#39;</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#a31515;">&#39;4&#39;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#a31515;">&#39;b&#39;</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#a31515;">&#39;6&#39;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#a31515;">&#39;E&#39;</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#a31515;">&#39;3&#39;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#a31515;">&#39;H&#39;</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#a31515;">&#39;#&#39;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#a31515;">&#39;i&#39;</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#a31515;">&#39;!&#39;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#a31515;">&#39;l&#39;</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#a31515;">&#39;1&#39;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#a31515;">&#39;o&#39;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#a31515;">&#39;O&#39;</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#a31515;">&#39;0&#39;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#a31515;">&#39;t&#39;</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#a31515;">&#39;+&#39;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;c&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c</pre> </p> <p> All three are functions that convert one <code>char</code> value to another, although many values could pass through without being modified. Since they all have the same type, you can create a list of them: </p> <p> <pre>&gt; List.map String.map [Char.toUpper; Char.toLower; Char.to1337] &lt;*&gt; ["Hello"; "World"];; val it : string list = ["HELLO"; "WORLD"; "hello"; "world"; "#e110"; "W0r1d"]</pre> </p> <p> There's a bit to unpack there. Recall that all three functions in the <code>Char</code> module have the same type: <code>char -&gt; char</code>. Making a list of them gives you a <code>(char -&gt; char) list</code>, but you really need a <code>(string -&gt; string) list</code>. Fortunately, the built-in <code>String.map</code> function takes a <code>char -&gt; char</code> function and uses it to map each <code>char</code> values in a <code>string</code>. Thus, <code>List.map String.map [Char.toUpper; Char.toLower; Char.to1337]</code> gives you a <code>(string -&gt; string) list</code>. </p> <p> When you apply (<code>&lt;*&gt;</code>) that list of functions with a list of <code>string</code> values, you get all possible combinations of each function used with each string. Both <code>"Hello"</code> and <code>"World"</code> are converted to upper case, lower case, and 1337. </p> <h3 id="fde27240cfaf4479bc31ff50d3f619d0"> Combinations of functions <a href="#fde27240cfaf4479bc31ff50d3f619d0" title="permalink">#</a> </h3> <p> Perhaps you're happy with the above combinations, but can we do better? As an example, you'll notice that <code>to1337</code> only converts an upper-case <code>'E'</code> to <code>'3'</code>, but ignores a lower-case <code>'e'</code>. What if you also want the combination where <code>'e'</code> is first converted to upper case, and then to 1337? You'd like that, but you still want to retain the combinations where each of these transformations are applied without the other. </p> <p> Fear not; functions are values, so you can combine them as well! </p> <p> In the previous article, did you notice how you could model the presence or absence of a particular value? Specifically, the last character in the potential password could be <code>'!'</code>, but <code>'!'</code> could also be omitted. </p> <p> Consider, again, the expression for all password combinations: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;passwordCombinations&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;[<span style="color:navy;">sprintf</span>&nbsp;<span style="color:#a31515;">&quot;</span><span style="color:teal;">%s%s%s%s%s%s</span><span style="color:#a31515;">&quot;</span>] &nbsp;&nbsp;&nbsp;&nbsp;&lt;*&gt;&nbsp;[<span style="color:#a31515;">&quot;P&quot;</span>;&nbsp;<span style="color:#a31515;">&quot;p&quot;</span>]&nbsp;&lt;*&gt;&nbsp;[<span style="color:#a31515;">&quot;a&quot;</span>;&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>]&nbsp;&lt;*&gt;&nbsp;[<span style="color:#a31515;">&quot;ssw&quot;</span>]&nbsp;&lt;*&gt;&nbsp;[<span style="color:#a31515;">&quot;o&quot;</span>;&nbsp;<span style="color:#a31515;">&quot;0&quot;</span>]&nbsp;&lt;*&gt;&nbsp;[<span style="color:#a31515;">&quot;rd&quot;</span>]&nbsp;&lt;*&gt;&nbsp;[<span style="color:#a31515;">&quot;&quot;</span>;&nbsp;<span style="color:#a31515;">&quot;!&quot;</span>]</pre> </p> <p> Notice that the last list contains two options: <code>"!"</code> and the empty string (<code>""</code>). You can read about this in <a href="http://blog.ploeh.dk/2017/10/06/monoids">another article series</a>, but <a href="http://blog.ploeh.dk/2017/10/10/strings-lists-and-sequences-as-a-monoid">character strings are monoids</a>, and one of the characteristics of monoids is that they have an <em>identity</em> element - a 'neutral' element, if you will. For strings, it's <code>""</code>; you can append or prepend the empty string as much as you'd like, but it's not going to change the other string. </p> <p> If you have a set of <a href="http://blog.ploeh.dk/2017/11/13/endomorphism-monoid">functions of the type <code>'a -&gt; 'a</code>, then the built-in function <code>id</code> is the identity element</a>. You can compose any <code>'a -&gt; 'a</code> function with <code>id</code>, and it's not going to change the other function. </p> <p> Since functions are values, then, you can create <em>combinations of functions:</em> </p> <p> <pre><span style="color:green;">//&nbsp;(char&nbsp;-&gt;&nbsp;char)&nbsp;list</span> <span style="color:blue;">let</span>&nbsp;maps&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;[<span style="color:blue;">fun</span>&nbsp;<span style="color:navy;">f</span>&nbsp;<span style="color:navy;">g</span>&nbsp;<span style="color:navy;">h</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:navy;">f</span>&nbsp;&gt;&gt;&nbsp;<span style="color:navy;">g</span>&nbsp;&gt;&gt;&nbsp;<span style="color:navy;">h</span>] &nbsp;&nbsp;&nbsp;&nbsp;&lt;*&gt;&nbsp;[<span style="color:teal;">Char</span>.<span style="color:navy;">toUpper</span>;&nbsp;<span style="color:navy;">id</span>] &nbsp;&nbsp;&nbsp;&nbsp;&lt;*&gt;&nbsp;[<span style="color:teal;">Char</span>.<span style="color:navy;">toLower</span>;&nbsp;<span style="color:navy;">id</span>] &nbsp;&nbsp;&nbsp;&nbsp;&lt;*&gt;&nbsp;[<span style="color:teal;">Char</span>.<span style="color:navy;">to1337</span>;&nbsp;<span style="color:navy;">id</span>]</pre> </p> <p> Here, <code>maps</code> is a list of functions, but it's not only three functions as in the above example. It's <em>eight</em> functions: </p> <p> <pre>&gt; List.length maps;; val it : int = 8</pre> </p> <p> The above applicative composition of <code>maps</code> combines three lists of functions. Each list presents two alternatives: a function (e.g. <code>Char.toUpper</code>), and <code>id</code>. In other words, a choice between doing something, and doing nothing. The lambda expression <code>fun f g h -&gt; f &gt;&gt; g &gt;&gt; h</code> takes three (curried) arguments, and returns the composition of calling <code>f</code>, then passing the result of that to <code>g</code>, and again passing the result of that to <code>h</code>. <code>f</code> is either <code>Char.toUpper</code> or <code>id</code>, <code>g</code> is either <code>Char.toLower</code> or <code>id</code>, and <code>h</code> is either <code>Char.to1337</code> or <code>id</code>. That's eight possible combinations. </p> <p> Combine eight functions with two <code>string</code> values, and you get sixteen alternatives back: </p> <p> <pre>&gt; List.map String.map maps &lt;*&gt; ["Hello"; "World"];; val it : string list = ["he110"; "w0r1d"; "hello"; "world"; "#3LL0"; "W0RLD"; "HELLO"; "WORLD"; "he110"; "w0r1d"; "hello"; "world"; "#e110"; "W0r1d"; "Hello"; "World"]</pre> </p> <p> Notice, for example, how one of the suggested alternatives is <code>"#3LL0"</code>. Previously, there was no translation from <code>'e'</code> to <code>'3'</code>, but now there is, via <code>Char.toUpper &gt;&gt; id &gt;&gt; Char.to1337</code>. </p> <p> Some of the combinations are redundant. For example, <code>"hello"</code> is generated twice, by <code>Char.toUpper &gt;&gt; Char.toLower &gt;&gt; id</code> and <code>id &gt;&gt; Char.toLower &gt;&gt; id</code>, respectively. You can reduce the output with <code>List.distinct</code>: </p> <p> <pre>&gt; List.map String.map maps &lt;*&gt; ["Hello"; "World"] |&gt; List.distinct;; val it : string list = ["he110"; "w0r1d"; "hello"; "world"; "#3LL0"; "W0RLD"; "HELLO"; "WORLD"; "#e110"; "W0r1d"; "Hello"; "World"]</pre> </p> <p> You can write equivalent code in Haskell, but it's so similar to the F# code that there's no reason to show it. </p> <h3 id="2000ef3aa60148e597de68d16048745f"> Translation to C# <a href="#2000ef3aa60148e597de68d16048745f" title="permalink">#</a> </h3> <p> Using the <code>Apply</code> extension methods from the previous article, you can translate the above code to C#. </p> <p> While you can use the .NET Base Class Library's <code>Char.ToUpperInvariant</code> and <code>Char.ToLowerInvariant</code> methods as is, you'll need to supply a <code>to1337</code> function. You can write it as a named static method, but you can also write it as a delegate: </p> <p> <pre><span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">char</span>,&nbsp;<span style="color:blue;">char</span>&gt;&nbsp;to1337&nbsp;=&nbsp;c&nbsp;=&gt; { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">switch</span>&nbsp;(c) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">case</span>&nbsp;<span style="color:#a31515;">&#39;A&#39;</span>: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">case</span>&nbsp;<span style="color:#a31515;">&#39;a&#39;</span>: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:#a31515;">&#39;4&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">case</span>&nbsp;<span style="color:#a31515;">&#39;b&#39;</span>: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:#a31515;">&#39;6&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">case</span>&nbsp;<span style="color:#a31515;">&#39;E&#39;</span>: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:#a31515;">&#39;3&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">case</span>&nbsp;<span style="color:#a31515;">&#39;H&#39;</span>: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:#a31515;">&#39;#&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">case</span>&nbsp;<span style="color:#a31515;">&#39;i&#39;</span>: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:#a31515;">&#39;!&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">case</span>&nbsp;<span style="color:#a31515;">&#39;l&#39;</span>: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:#a31515;">&#39;1&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">case</span>&nbsp;<span style="color:#a31515;">&#39;o&#39;</span>: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">case</span>&nbsp;<span style="color:#a31515;">&#39;O&#39;</span>: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:#a31515;">&#39;0&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">case</span>&nbsp;<span style="color:#a31515;">&#39;t&#39;</span>: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:#a31515;">&#39;+&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">default</span>: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;c; &nbsp;&nbsp;&nbsp;&nbsp;} };</pre> </p> <p> You're also going to need an <code>id</code> function: </p> <p> <pre><span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">char</span>,&nbsp;<span style="color:blue;">char</span>&gt;&nbsp;id&nbsp;=&nbsp;c&nbsp;=&gt;&nbsp;c; </pre> </p> <p> In order to compose three functions to one, you can write something like this: </p> <p> <pre><span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">char</span>,&nbsp;<span style="color:blue;">char</span>&gt;,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">char</span>,&nbsp;<span style="color:blue;">char</span>&gt;,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">char</span>,&nbsp;<span style="color:blue;">char</span>&gt;,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">char</span>,&nbsp;<span style="color:blue;">char</span>&gt;&gt; &nbsp;&nbsp;&nbsp;&nbsp;compose3&nbsp;=&nbsp;(f,&nbsp;g,&nbsp;h)&nbsp;=&gt;&nbsp;x&nbsp;=&gt;&nbsp;h(g(f(x)));</pre> </p> <p> That's going to be a contender for some of the most obscure C# code I've written in a while. By the double use of <code>=&gt;</code>, you can tell that it's a delegate that returns a delegate. That's not even the worst part: check out the type of the thing! In reality, nothing happens here that doesn't also happen in the above F# code, but it's an example of the superiority of <a href="https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system">Hindley–Milner type inference</a>: in F#, you don't have to explicitly type out the type. </p> <p> With a function to compose three other functions, you can now apply the three alternative functions: </p> <p> <pre><span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">char</span>,&nbsp;<span style="color:blue;">char</span>&gt;&gt;&nbsp;maps&nbsp;=&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;compose3&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#2b91af;">Char</span>.ToUpperInvariant,&nbsp;id&nbsp;}) &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#2b91af;">Char</span>.ToLowerInvariant,&nbsp;id&nbsp;}) &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;to1337,&nbsp;id&nbsp;});</pre> </p> <p> Now you have a sequence of functions that translate <code>char</code> values to <code>char</code> values. What you really need, though, is a sequence of functions that translate <code>string</code> values to <code>string</code> values. </p> <p> The F# core library defines the built-in <code>String.map</code> function, but as far as I can tell, there's no equivalent method in the .NET Base Class Library. Therefore, you must implement it yourself: </p> <p> <pre><span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">char</span>,&nbsp;<span style="color:blue;">char</span>&gt;,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;&gt;&nbsp;stringMap&nbsp;=&nbsp;f&nbsp;=&gt; &nbsp;&nbsp;&nbsp;&nbsp;(<span style="color:blue;">string</span>&nbsp;s)&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">string</span>(s.Select(f).ToArray());</pre> </p> <p> This is a function that takes a <code>Func&lt;char, char&gt;</code> as input and returns a <code>Func&lt;string, string&gt;</code>. Again, the type declaration isn't the prettiest. </p> <p> You can now apply <code>maps</code> to some <code>string</code> values, using the <code>Apply</code> extension method: </p> <p> <pre><span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:blue;">string</span>&gt;&nbsp;hellos&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;maps.Select(stringMap).Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;Hello&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;World&quot;</span>&nbsp;});</pre> </p> <p> This produces exactly the same output as the above F# example, even in the same order. </p> <p> Applicative functors are elegant in F# and Haskell, but awkward in a language like C# - mostly because of its inferior type inference engine. </p> <h3 id="001d02c7aa40400391b899f723ef9baa"> Summary <a href="#001d02c7aa40400391b899f723ef9baa" title="permalink">#</a> </h3> <p> Previous articles demonstrated how applicative lists can be used to compose several lists into a list that contains all possible combinations. In this article you saw how this also extends to combinations of functions. </p> <p> The last three articles (including the present) focus on lists as applicative functors, but lists aren't the only type of applicative functor. In the next articles, you'll encounter some other applicative functors. </p> <p> <strong>Next:</strong> <a href="http://blog.ploeh.dk/2018/10/29/the-maybe-applicative-functor">The Maybe applicative functor</a>. </p> </div><hr> This blog is totally free, but if you like it, please <a href="https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=NZEPYW8KVZ8WL">buy me a cup of coffee</a>. Mark Seemann http://blog.ploeh.dk/2018/10/22/applicative-combinations-of-functions An applicative password list http://blog.ploeh.dk/2018/10/15/an-applicative-password-list/ Mon, 15 Oct 2018 05:54:00 UTC <div id="post"> <p> <em>How to use the applicative functor capabilities of lists to create a password list, with examples that object-oriented programmers can understand.</em> </p> <p> This article is an instalment in <a href="http://blog.ploeh.dk/2018/10/01/applicative-functors">an article series about applicative functors</a>. In the <a href="http://blog.ploeh.dk/2018/10/08/full-deck">previous article</a>, you saw how to use <a href="https://www.haskell.org">Haskell</a> and <a href="https://fsharp.org">F#</a> lists as applicative functors to generate combinations of values. In this article, you'll see a similar example, but this time, there will also be a C# example. </p> <h3 id="ab0acd0982a64569a68ba92b041739a9"> Guess the password variation <a href="#ab0acd0982a64569a68ba92b041739a9" title="permalink">#</a> </h3> <p> Years ago, I worked in an organisation that (among other things) produced much demo software. Often, the demo software would include a demonstration of the security features of a product, which meant that, as a user evaluating the software, you had to log in with a user name and password. In order to keep things simple, the password was usually <em>Passw0rd!</em>, or some variation thereof. </p> <p> (Keep in mind that this was demoware. Password strength wasn't a concern. We explicitly wanted the password to be easy to guess, so that users evaluating the software had a chance to test how log in worked. This was long before social login and the like.) </p> <p> We had more than one package of demoware, and over the years, variations of the standard password had snuck in. Sometimes it'd be all lower-case; sometimes it'd use <em>4</em> instead of <em>a</em>, and so on. As the years went on, the number of possible permutations grew. </p> <p> Recently, I had a similar problem, but for security reasons, I don't want to divulge what it was. Let's just pretend that I had to guess one of those old demo passwords. </p> <p> There weren't <em>that</em> many possible variations, but just enough that I couldn't keep them systematically in my head. <ul> <li>The first letter could be upper or lower case.</li> <li>The second letter could be <em>a</em> or <em>4</em>.</li> <li>The <em>o</em> could be replaced with a zero (<em>0</em>).</li> <li>The password could end with an exclamation mark (<em>!</em>), but it might also be omitted.</li> </ul> Having recently discovered the power of lists as applicative functors, I started F# Interactive (FSI), and wrote the following: </p> <p> <pre>&gt; let (&lt;*&gt;) fs l = fs |&gt; List.collect (fun f -&gt; l |&gt; List.map f);; val ( &lt;*&gt; ) : fs:('a -&gt; 'b) list -&gt; l:'a list -&gt; 'b list &gt; [sprintf "%s%s%s%s%s%s"] &lt;*&gt; ["P"; "p"] &lt;*&gt; ["a"; "4"] &lt;*&gt; ["ssw"] &lt;*&gt; ["o"; "0"] &lt;*&gt; ["rd"] &lt;*&gt; [""; "!"];; val it : string list = ["Password"; "Password!"; "Passw0rd"; "Passw0rd!"; "P4ssword"; "P4ssword!"; "P4ssw0rd"; "P4ssw0rd!"; "password"; "password!"; "passw0rd"; "passw0rd!"; "p4ssword"; "p4ssword!"; "p4ssw0rd"; "p4ssw0rd!"]</pre> </p> <p> This produces a list of all the possible password combinations according to the above rules. Since there weren't that many, I could start trying each from the start, until I found the correct variation. </p> <p> The first list contains a single function. Due to the way <code>sprintf</code> works, <code>sprintf "%s%s%s%s%s%s"</code> is a function that takes six (curried) <code>string</code> arguments, and returns a <code>string</code>. The number 6 is no coincidence, because you'll notice that the <code>&lt;*&gt;</code> operator is used six times. </p> <p> There's no reason to repeat the exegesis from the previous article, but briefly: <ol> <li><code>sprintf "%s%s%s%s%s%s"</code> has the type <code>string -&gt; string -&gt; string -&gt; string -&gt; string -&gt; string -&gt; string</code>.</li> <li><code>[sprintf "%s%s%s%s%s%s"]</code> has the type <code>(string -&gt; string -&gt; string -&gt; string -&gt; string -&gt; string -&gt; string) list</code>.</li> <li><code>[sprintf "%s%s%s%s%s%s"] &lt;*&gt; ["P"; "p"]</code> has the type <code>(string -&gt; string -&gt; string -&gt; string -&gt; string -&gt; string) list</code>.</li> <li><code>[sprintf "%s%s%s%s%s%s"] &lt;*&gt; ["P"; "p"] &lt;*&gt; ["a"; "4"]</code> has the type <code>(string -&gt; string -&gt; string -&gt; string -&gt; string) list</code>.</li> <li>...and so on.</li> </ol> Notice that every time you add another list with <code>&lt;*&gt;</code>, an argument is removed from the resulting function contained in the returned list. When you've applied six lists with the <code>&lt;*&gt;</code> operator, the return value is no longer a list of functions, but a list of values. </p> <p> Clearly, then, that's no coincidence. I deliberately shaped the initial function to take six arguments, so that it would match the six segments I wanted to model. </p> <p> Perhaps the most interesting quality of applicative functors is that you can compose an arbitrary number of objects, as long as you have a function to match the number of arguments. </p> <h3 id="25e1617d768a4705a9756f230ddd9b39"> Haskell <a href="#25e1617d768a4705a9756f230ddd9b39" title="permalink">#</a> </h3> <p> This time I started with F#, but in Haskell, <code>&lt;*&gt;</code> is a built-in operator, so obviously this also works there: </p> <p> <pre><span style="color:#600277;">passwordCombinations</span>&nbsp;::&nbsp;[String] passwordCombinations&nbsp;<span style="color:#666666;">=</span> &nbsp;&nbsp;[printf&nbsp;<span style="color:#a31515;">&quot;%s%s%s%s%s%s&quot;</span>] &nbsp;&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;[<span style="color:#a31515;">&quot;P&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;p&quot;</span>]&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;[<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>]&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;[<span style="color:#a31515;">&quot;ssw&quot;</span>]&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;[<span style="color:#a31515;">&quot;o&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;0&quot;</span>]&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;[<span style="color:#a31515;">&quot;rd&quot;</span>]&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;[<span style="color:#a31515;">&quot;&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;!&quot;</span>]</pre> </p> <p> The output is the same as the above F# code. </p> <h3 id="9c3412586a58460c8280212a13351331"> C# <a href="#9c3412586a58460c8280212a13351331" title="permalink">#</a> </h3> <p> While you can translate the concept of lists as an applicative functor to C#, this is where you start testing the limits of the language; or perhaps I've simply forgotten too much C# to do it full justice. </p> <p> Instead of making linked lists an applicative functor, let's consider a type closer to the spirit of the C# language: <code>IEnumerable&lt;T&gt;</code>. The following code attempts to turn <code>IEnumerable&lt;T&gt;</code> into an applicative functor. </p> <p> Consider the above F# implementation of <code>&lt;*&gt;</code> (explained in the previous article). It uses <code>List.collect</code> to flatten what would otherwise had been a list of lists. <code>List.collect</code> has the type <code>('a -&gt; 'b list) -&gt; 'a list -&gt; 'b list</code>. The corresponding method for <code>IEnumerable&lt;T&gt;</code> already exists in the .NET Base Class Library; it's called <a href="https://msdn.microsoft.com/en-us/library/bb534336">SelectMany</a>. (Incidentally, this is also the monadic <em>bind</em> function, but this is <em>still</em> not a monad tutorial.) </p> <p> For an applicative functor, we need a method that takes a sequence of functions, and a sequence of values, and produces a sequence of return values. You can translate the above F# function to this C# extension method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;Apply&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;&nbsp;selectors, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;source) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;selectors.SelectMany(source.Select); }</pre> </p> <p> That's a single line of code! That's not so bad. What's the problem? </p> <p> So far there's no problem. You can, for example, write code like this: </p> <p> <pre><span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;sl&nbsp;=&nbsp;s&nbsp;=&gt;&nbsp;s.Length; <span style="color:blue;">var</span>&nbsp;lengths&nbsp;=&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;sl&nbsp;}.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;bar&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;baz&quot;</span>&nbsp;});</pre> </p> <p> This will return a sequence of the numbers <code>3, 3, 3</code>. That seems, however, like quite a convoluted way of getting the lengths of some strings. A normal <code>Select</code> method would have sufficed. </p> <p> Is it possible to repeat the above password enumeration in C#? In order to do that, you need a function that takes six <code>string</code> arguments and returns a <code>string</code>: </p> <p> <pre><span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;concat&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;(x,&nbsp;y,&nbsp;z,&nbsp;æ,&nbsp;ø,&nbsp;å)&nbsp;=&gt;&nbsp;x&nbsp;+&nbsp;y&nbsp;+&nbsp;z&nbsp;+&nbsp;æ&nbsp;+&nbsp;ø&nbsp;+&nbsp;å;</pre> </p> <p> With programmers' penchant to start with the variable name <code>x</code>, and continue with <code>y</code> and <code>z</code>, most people will have a problem with six variables - but not us Danes! Fortunately, we've officially added three extra letters to our alphabet for this very purpose! So with that small problem out of the way, you can now attempt to reproduce the above F# code: </p> <p> <pre><span style="color:blue;">var</span>&nbsp;combinations&nbsp;=&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;concat&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;P&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;p&quot;</span>&nbsp;}) &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>&nbsp;}) &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;ssw&quot;</span>&nbsp;}) &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;o&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;0&quot;</span>&nbsp;}) &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;rd&quot;</span>&nbsp;}) &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;!&quot;</span>&nbsp;});</pre> </p> <p> That looks promising, but there's one problem: <em>it doesn't compile</em>. </p> <p> The problem is that <code>concat</code> is a function that takes six arguments, and the above <code>Apply</code> method expects <code>selectors</code> to be functions that take exactly one argument. </p> <p> Alas, while it's not pretty, you can attempt to address the problem with an overload: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">T3</span>,&nbsp;<span style="color:#2b91af;">T4</span>,&nbsp;<span style="color:#2b91af;">T5</span>,&nbsp;<span style="color:#2b91af;">T6</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;&nbsp;Apply&lt;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">T3</span>,&nbsp;<span style="color:#2b91af;">T4</span>,&nbsp;<span style="color:#2b91af;">T5</span>,&nbsp;<span style="color:#2b91af;">T6</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">T3</span>,&nbsp;<span style="color:#2b91af;">T4</span>,&nbsp;<span style="color:#2b91af;">T5</span>,&nbsp;<span style="color:#2b91af;">T6</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;&nbsp;selectors, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">T1</span>&gt;&nbsp;source) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;selectors.SelectMany(f&nbsp;=&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;source.Select(x&nbsp;=&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">T3</span>,&nbsp;<span style="color:#2b91af;">T4</span>,&nbsp;<span style="color:#2b91af;">T5</span>,&nbsp;<span style="color:#2b91af;">T6</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;g&nbsp;=&nbsp;(y,&nbsp;z,&nbsp;æ,&nbsp;ø,&nbsp;å)&nbsp;=&gt;&nbsp;f(x,&nbsp;y,&nbsp;z,&nbsp;æ,&nbsp;ø,&nbsp;å); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;g; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;})); }</pre> </p> <p> This overload of <code>Apply</code> takes <code>selectors</code> of arity six, and return a sequence of functions with arity five. </p> <p> Does it work now, then? </p> <p> Unfortunately, it still doesn't compile, because <code>new[] { concat }.Apply(new[] { "P", "p" })</code> has the type <code>IEnumerable&lt;Func&lt;string, string, string, string, string, string&gt;&gt;</code>, and no overload of <code>Apply</code> exists that supports <code>selectors</code> with arity five. </p> <p> You'll have to add such an overload as well: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">T3</span>,&nbsp;<span style="color:#2b91af;">T4</span>,&nbsp;<span style="color:#2b91af;">T5</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;&nbsp;Apply&lt;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">T3</span>,&nbsp;<span style="color:#2b91af;">T4</span>,&nbsp;<span style="color:#2b91af;">T5</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">T3</span>,&nbsp;<span style="color:#2b91af;">T4</span>,&nbsp;<span style="color:#2b91af;">T5</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;&nbsp;selectors, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">T1</span>&gt;&nbsp;source) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;selectors.SelectMany(f&nbsp;=&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;source.Select(x&nbsp;=&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">T3</span>,&nbsp;<span style="color:#2b91af;">T4</span>,&nbsp;<span style="color:#2b91af;">T5</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;g&nbsp;=&nbsp;(y,&nbsp;z,&nbsp;æ,&nbsp;ø)&nbsp;=&gt;&nbsp;f(x,&nbsp;y,&nbsp;z,&nbsp;æ,&nbsp;ø); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;g; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;})); }</pre> </p> <p> You can probably see where this is going. This overload returns a sequence of functions with arity four, so you'll have to add an <code>Apply</code> overload for such functions as well, plus for functions with arity three and two. Once you've done that, the above <a href="https://martinfowler.com/bliki/FluentInterface.html">fluent</a> chain of <code>Apply</code> method calls work, and you get a sequence containing all the password variations. </p> <p> <pre>&gt; <span style="color:blue;">new</span>[]&nbsp;{&nbsp;concat&nbsp;} . .Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;P&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;p&quot;</span>&nbsp;}) . .Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>&nbsp;}) . .Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;ssw&quot;</span>&nbsp;}) . .Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;o&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;0&quot;</span>&nbsp;}) . .Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;rd&quot;</span>&nbsp;}) . .Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;!&quot;</span>&nbsp;}) string[16] { "Password", "Password!", "Passw0rd", "Passw0rd!", "P4ssword", "P4ssword!", "P4ssw0rd", "P4ssw0rd!", "password", "password!", "passw0rd", "passw0rd!", "p4ssword", "p4ssword!", "p4ssw0rd", "p4ssw0rd!" }</pre> </p> <p> In F# and Haskell, the compiler automatically figures out the return type of each application, due to a combination of currying and <a href="https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system">Hindley–Milner type inference</a>. Perhaps I've allowed my C# skills to atrophy, but I don't think there's an easy resolution to this problem in C#. </p> <p> Obviously, you can always write a reusable library with <code>Apply</code> overloads that support up to some absurd arity. Once those methods are written, they're unlikely to change. Still, it seems to me that we're pushing the envelope. </p> <h3 id="5f60025e198f42ecbba731a0869217ed"> Summary <a href="#5f60025e198f42ecbba731a0869217ed" title="permalink">#</a> </h3> <p> In this article, you saw how to turn C# sequences into an applicative functor. While possible, there are some bumps in the road. </p> <p> There's still an aspect of using lists and sequences as applicative functors that I've been deliberately ignoring so far. The next article covers that. After that, we'll take a break from lists and look at some other applicative functors. </p> <p> <strong>Next:</strong> <a href="http://blog.ploeh.dk/2018/10/22/applicative-combinations-of-functions">Applicative combinations of functions</a>. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="0ded7ac93aad8ba7b1063dd49c2051f1"> <div class="comment-author">Tyson Williams</div> <div class="comment-content"> <blockquote> In F# and Haskell, the compiler automatically figures out the return type of each application, due to a combination of currying and Hindley–Milner type inference. Perhaps I've allowed my C# skills to atrophy, but I don't think there's an easy resolution to this problem in C#. </blockquote> <p> I think the difference is that all functions in F# and Haskell are automatically curried, but nothing is automatically curreid in C#. If you explicitly curry <code>concat</code>, then the code complies and works as expected. Here is one way to achieve that. </p> <p> <pre><span style="color:blue;">var</span>&nbsp;combinations&nbsp;=&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;LanguageExt.<span style="color:#2b91af;">Prelude</span>.curry(concat)&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;P&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;p&quot;</span>&nbsp;}) &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>&nbsp;}) &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;ssw&quot;</span>&nbsp;}) &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;o&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;0&quot;</span>&nbsp;}) &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;rd&quot;</span>&nbsp;}) &nbsp;&nbsp;&nbsp;&nbsp;.Apply(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;!&quot;</span>&nbsp;});</pre> </p> <p> In this example, I curried <code>concat</code> using <a href="https://github.com/louthy/language-ext/blob/master/LanguageExt.Core/Prelude/Prelude_Curry.cs#L65"><code>curry</code></a> from the NuGet package <a href="https://github.com/louthy/language-ext">LanguageExt</a>. It is a base class library for functional programming in C#. </p> <p> So you don't need many overloads of your <code>Apply</code> for varrying numbers of type parameters. You just need many overloads of <code>curry</code>. </p> </div> <div class="comment-date">2018-10-18 01:45 UTC</div> </div> <div class="comment" id="b4e76681ea894aa3be1e6b836343c148"> <div class="comment-author"><a href="http://blog.ploeh.dk">Mark Seemann</a></div> <div class="comment-content"> <p> Tyson, thank you for writing. Yes, you're right that it's the lack of default currying that makes this sort of style less than ideal in C#. This seems to be clearly demonstrated by your example. </p> </div> <div class="comment-date">2018-10-30 7:43 UTC</div> </div> </div><hr> This blog is totally free, but if you like it, please <a href="https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=NZEPYW8KVZ8WL">buy me a cup of coffee</a>. Mark Seemann http://blog.ploeh.dk/2018/10/15/an-applicative-password-list Full deck http://blog.ploeh.dk/2018/10/08/full-deck/ Mon, 08 Oct 2018 06:17:00 UTC <div id="post"> <p> <em>An introduction to applicative functors in Haskell, with a translation to F#.</em> </p> <p> This article is an instalment in <a href="http://blog.ploeh.dk/2018/10/01/applicative-functors">an article series about applicative functors</a>. While (non-applicative) <a href="http://blog.ploeh.dk/2018/03/22/functors">functors</a> can be translated to an object-oriented language like C# in a straightforward manner, applicative functors are more entrenched in functional languages like <a href="https://www.haskell.org">Haskell</a>. This article introduces the concept with a motivating example in Haskell, and also shows a translation to <a href="https://fsharp.org">F#</a>. In the next article, you'll also see how to implement an applicative functor in C#. </p> <h3 id="bdf22a40f9f04b6b9929f46dbafe7911"> Deck of cards in Haskell <a href="#bdf22a40f9f04b6b9929f46dbafe7911" title="permalink">#</a> </h3> <p> Imagine that you want to model a card game. In order to do so, you start by defining data types for suits, faces, and cards: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;<span style="color:#dd0000;">Suit</span>&nbsp;<span style="color:#666666;">=</span> &nbsp;&nbsp;<span style="color:#dd0000;">Diamonds</span>&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Hearts</span>&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Clubs</span>&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Spades</span>&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#a31515;">Show</span>,&nbsp;<span style="color:#a31515;">Eq</span>,&nbsp;<span style="color:#a31515;">Enum</span>,&nbsp;<span style="color:#a31515;">Bounded</span>) <span style="color:blue;">data</span>&nbsp;<span style="color:#dd0000;">Face</span>&nbsp;<span style="color:#666666;">=</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#dd0000;">Two</span>&nbsp;&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Three</span>&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Four</span>&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Five</span>&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Six</span>&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Seven</span>&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Eight</span>&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Nine</span>&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Ten</span> &nbsp;&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Jack</span>&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Queen</span>&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">King</span>&nbsp;<span style="color:#666666;">|</span>&nbsp;<span style="color:#dd0000;">Ace</span> &nbsp;&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#a31515;">Show</span>,&nbsp;<span style="color:#a31515;">Eq</span>,&nbsp;<span style="color:#a31515;">Enum</span>,&nbsp;<span style="color:#a31515;">Bounded</span>) <span style="color:blue;">data</span>&nbsp;<span style="color:#dd0000;">Card</span>&nbsp;<span style="color:#666666;">=</span>&nbsp;<span style="color:#dd0000;">Card</span>&nbsp;{&nbsp;face&nbsp;<span style="color:#666666;">::</span>&nbsp;<span style="color:#dd0000;">Face</span>,&nbsp;suit&nbsp;<span style="color:#666666;">::</span>&nbsp;<span style="color:#dd0000;">Suit</span>&nbsp;}&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#a31515;">Show</span>,&nbsp;<span style="color:#a31515;">Eq</span>)</pre> </p> <p> Since both <code>Suit</code> and <code>Face</code> are instances of the <code>Enum</code> and <code>Bounded</code> typeclasses, you can easily enumerate them: </p> <p> <pre><span style="color:#600277;">allFaces</span>&nbsp;::&nbsp;[<span style="color:blue;">Face</span>] allFaces&nbsp;<span style="color:#666666;">=</span>&nbsp;[minBound&nbsp;<span style="color:#666666;">..</span>&nbsp;maxBound] <span style="color:#600277;">allSuits</span>&nbsp;::&nbsp;[<span style="color:blue;">Suit</span>] allSuits&nbsp;<span style="color:#666666;">=</span>&nbsp;[minBound&nbsp;<span style="color:#666666;">..</span>&nbsp;maxBound]</pre> </p> <p> For example, <code>allSuits</code> enumerates all four <code>Suit</code> values: </p> <p> <pre>λ&gt; allSuits [Diamonds,Hearts,Clubs,Spades]</pre> </p> <p> Notice, by the way, how the code for <code>allFaces</code> and <code>allSuits</code> is identical. The behaviour, however, is different, because the types are different. </p> <p> While you can enumerate suits and faces, <em>how do you create a full deck of cards?</em> </p> <p> A full deck of cards should contain one card of every possible combination of suit and face. Here's one way to do it, taking advantage of lists being applicative functors: </p> <p> <pre><span style="color:#600277;">fullDeck</span>&nbsp;::&nbsp;[<span style="color:blue;">Card</span>] fullDeck&nbsp;<span style="color:#666666;">=</span>&nbsp;pure&nbsp;<span style="color:#dd0000;">Card</span>&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;allFaces&nbsp;<span style="color:#666666;">&lt;*&gt;</span>&nbsp;allSuits</pre> </p> <p> This will give you all the possible cards. Here are the first six: </p> <p> <pre>λ&gt; forM_ (take 6 fullDeck) print Card {face = Two, suit = Diamonds} Card {face = Two, suit = Hearts} Card {face = Two, suit = Clubs} Card {face = Two, suit = Spades} Card {face = Three, suit = Diamonds} Card {face = Three, suit = Hearts}</pre> </p> <p> How does it work? Let's break it down, starting from left: </p> <p> <pre>λ&gt; :type Card Card :: Face -&gt; Suit -&gt; Card λ&gt; :type pure Card pure Card :: Applicative f =&gt; f (Face -&gt; Suit -&gt; Card) λ&gt; :type pure Card &lt;*&gt; allFaces pure Card &lt;*&gt; allFaces :: [Suit -&gt; Card] λ&gt; :type pure Card &lt;*&gt; allFaces &lt;*&gt; allSuits pure Card &lt;*&gt; allFaces &lt;*&gt; allSuits :: [Card]</pre> </p> <p> From the top, <code>Card</code> is a function that takes a <code>Face</code> value and a <code>Suit</code> value and returns a <code>Card</code> value. Object-oriented programmers can think of it as a constructor. </p> <p> Next, <code>pure Card</code> is the <code>Card</code> function, elevated to an applicative functor. At this point, the compiler hasn't decided which particular applicative functor it is; it could be any applicative functor. Specifically, it turns out to be the list type (<code>[]</code>), which means that <code>pure Card</code> has the type <code>[Face -&gt; Suit -&gt; Card]</code>. That is: it's a list of functions, but a list of only a single function. At this point, however, this is still premature. The type doesn't materialise until we apply the second expression. </p> <p> The type of <code>allFaces</code> is clearly <code>[Face]</code>. Since the <code>&lt;*&gt;</code> operator has the type <code>Applicative f =&gt; f (a -&gt; b) -&gt; f a -&gt; f b</code>, the expression on the left must be the same functor as the expression on the right. The list type (<code>[]</code>) is an applicative functor, and because <code>allFaces</code> is a list, then <code>pure Card</code> must also be a list, in the expression <code>pure Card &lt;*&gt; allFaces</code>. In other words, in the definition of <code>&lt;*&gt;</code>, you can substitute <code>f</code> with <code>[]</code>, and <code>a</code> with <code>Face</code>. The interim result is <code>[Face -&gt; b] -&gt; [Face] -&gt; [b]</code>. What is <code>b</code>, then? </p> <p> You already know that <code>pure Card</code> has the type <code>[Face -&gt; Suit -&gt; Card]</code>, so <code>b</code> must be <code>Suit -&gt; Card</code>. That's the reason that <code>pure Card &lt;*&gt; allFaces</code> has the type <code>[Suit -&gt; Card]</code>. It's a list of functions. This means that you can use <code>&lt;*&gt;</code> a second time, this time with <code>allSuits</code>, which has the type <code>[Suit]</code>. </p> <p> Using the same line of reasoning as before, you can substitute <code>Suit</code> for <code>a</code> in the type of <code>&lt;*&gt;</code>, and you get <code>[Suit -&gt; b] -&gt; [Suit] -&gt; [b]</code>. What is <code>b</code> now? From the previous step, you know that the the expression on the left has the type <code>[Suit -&gt; Card]</code>, so <code>b</code> must be <code>Card</code>. That's why the entire expression has the type <code>[Card]</code>. </p> <h3 id="570f38cdb46b420e904fb656faa662ff"> Deck of cards in F# <a href="#570f38cdb46b420e904fb656faa662ff" title="permalink">#</a> </h3> <p> You can translate the above Haskell code to F#. The first step is to make F# lists applicative. F# also supports custom operators, so you can add a function called <code>&lt;*&gt;</code>: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b)&nbsp;list&nbsp;-&gt;&nbsp;&#39;a&nbsp;list&nbsp;-&gt;&nbsp;&#39;b&nbsp;list</span> <span style="color:blue;">let</span>&nbsp;(&lt;*&gt;)&nbsp;fs&nbsp;l&nbsp;=&nbsp;fs&nbsp;|&gt;&nbsp;<span style="color:teal;">List</span>.<span style="color:navy;">collect</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="color:navy;">f</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;l&nbsp;|&gt;&nbsp;<span style="color:teal;">List</span>.<span style="color:navy;">map</span>&nbsp;<span style="color:navy;">f</span>)</pre> </p> <p> This implementation iterates over all the functions in <code>fs</code>; for each function, it maps the list <code>l</code> with that function. Had you done that with a normal <code>List.map</code>, this would have returned a list of lists, but by using <code>List.collect</code>, you flatten the list. </p> <p> It's worth noting that this isn't the only way you could have implemented <code>&lt;*&gt;</code>, but this is the implementation that behaves like the Haskell function. An alternative implementation could have been this: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b)&nbsp;list&nbsp;-&gt;&nbsp;&#39;a&nbsp;list&nbsp;-&gt;&nbsp;&#39;b&nbsp;list</span> <span style="color:blue;">let</span>&nbsp;(&lt;*&gt;)&nbsp;fs&nbsp;=&nbsp;<span style="color:teal;">List</span>.<span style="color:navy;">collect</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;fs&nbsp;|&gt;&nbsp;<span style="color:teal;">List</span>.<span style="color:navy;">map</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="color:navy;">f</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:navy;">f</span>&nbsp;x))</pre> </p> <p> This variation has the same type as the first example, and still returns all combinations, but the order is different. In the following of this article, as well as in subsequent articles, I'll use the first version. </p> <p> Here's the playing cards example translated to F#: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;<span style="color:teal;">Suit</span>&nbsp;=&nbsp;<span style="color:navy;">Diamonds</span>&nbsp;|&nbsp;<span style="color:navy;">Hearts</span>&nbsp;|&nbsp;<span style="color:navy;">Clubs</span>&nbsp;|&nbsp;<span style="color:navy;">Spades</span> <span style="color:blue;">type</span>&nbsp;<span style="color:teal;">Face</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;<span style="color:navy;">Two</span>&nbsp;|&nbsp;<span style="color:navy;">Three</span>&nbsp;|&nbsp;<span style="color:navy;">Four</span>&nbsp;|&nbsp;<span style="color:navy;">Five</span>&nbsp;|&nbsp;<span style="color:navy;">Six</span>&nbsp;|&nbsp;<span style="color:navy;">Seven</span>&nbsp;|&nbsp;<span style="color:navy;">Eight</span>&nbsp;|&nbsp;<span style="color:navy;">Nine</span>&nbsp;|&nbsp;<span style="color:navy;">Ten</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:navy;">Jack</span>&nbsp;|&nbsp;<span style="color:navy;">Queen</span>&nbsp;|&nbsp;<span style="color:navy;">King</span>&nbsp;|&nbsp;<span style="color:navy;">Ace</span> <span style="color:blue;">type</span>&nbsp;<span style="color:teal;">Card</span>&nbsp;=&nbsp;{&nbsp;Face:&nbsp;<span style="color:teal;">Face</span>;&nbsp;Suit&nbsp;:&nbsp;<span style="color:teal;">Suit</span>&nbsp;} <span style="color:green;">//&nbsp;Face&nbsp;list</span> <span style="color:blue;">let</span>&nbsp;allFaces&nbsp;=&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:navy;">Two</span>;&nbsp;<span style="color:navy;">Three</span>;&nbsp;<span style="color:navy;">Four</span>;&nbsp;<span style="color:navy;">Five</span>;&nbsp;<span style="color:navy;">Six</span>;&nbsp;<span style="color:navy;">Seven</span>;&nbsp;<span style="color:navy;">Eight</span>;&nbsp;<span style="color:navy;">Nine</span>;&nbsp;<span style="color:navy;">Ten</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:navy;">Jack</span>;&nbsp;<span style="color:navy;">Queen</span>;&nbsp;<span style="color:navy;">King</span>;&nbsp;<span style="color:navy;">Ace</span>] <span style="color:green;">//&nbsp;Suit&nbsp;list</span> <span style="color:blue;">let</span>&nbsp;allSuits&nbsp;=&nbsp;[<span style="color:navy;">Diamonds</span>;&nbsp;<span style="color:navy;">Hearts</span>;&nbsp;<span style="color:navy;">Clubs</span>;&nbsp;<span style="color:navy;">Spades</span>] <span style="color:green;">//&nbsp;Card&nbsp;list</span> <span style="color:blue;">let</span>&nbsp;fullDeck&nbsp;=&nbsp;[<span style="color:blue;">fun</span>&nbsp;f&nbsp;s&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;{&nbsp;Face&nbsp;=&nbsp;f;&nbsp;Suit&nbsp;=&nbsp;s&nbsp;}]&nbsp;&lt;*&gt;&nbsp;allFaces&nbsp;&lt;*&gt;&nbsp;allSuits</pre> </p> <p> The F# code is slightly more verbose than the Haskell code, because you have to repeat all the cases for <code>Suit</code> and <code>Face</code>. You can't enumerate them automatically, like you can in Haskell. </p> <p> It didn't make much sense to me to attempt to define a <code>pure</code> function, so instead I simply inserted a single lambda expression in a list, using the normal square-bracket syntax. F# doesn't have constructors for record types, so you have to pass a lambda expression, whereas in Haskell, you could simply use the <code>Card</code> function. </p> <p> The result is the same, though: </p> <p> <pre>&gt; fullDeck |&gt; List.take 6 |&gt; List.iter (printfn "%A");; {Face = Two; Suit = Diamonds;} {Face = Two; Suit = Hearts;} {Face = Two; Suit = Clubs;} {Face = Two; Suit = Spades;} {Face = Three; Suit = Diamonds;} {Face = Three; Suit = Hearts;}</pre> </p> <p> While the mechanics of applicative functors translate well to F#, it leaves you with at least one problem. If you add the above operator <code>&lt;*&gt;</code>, you've now 'used up' that operator for lists. While you <em>can</em> define an operator of the same name for e.g. <code>option</code>, you'd have to put them in separate modules or namespaces in order to prevent them from colliding. This also means that you can't easily use them together. </p> <p> For that reason, I wouldn't consider this the most <a href="http://blog.ploeh.dk/2015/08/03/idiomatic-or-idiosyncratic">idiomatic</a> way to create a full deck of cards in F#. Normally, I'd do this instead: </p> <p> <pre><span style="color:green;">//&nbsp;Card&nbsp;list</span> <span style="color:blue;">let</span>&nbsp;fullDeck&nbsp;=&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">for</span>&nbsp;suit&nbsp;<span style="color:blue;">in</span>&nbsp;allSuits&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">for</span>&nbsp;face&nbsp;<span style="color:blue;">in</span>&nbsp;allFaces&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">yield</span>&nbsp;{&nbsp;Face&nbsp;=&nbsp;face;&nbsp;Suit&nbsp;=&nbsp;suit&nbsp;}&nbsp;]</pre> </p> <p> This alternative syntax takes advantage of F#'s 'extended list comprehension' syntax. FWIW, you could have done something similar in Haskell: </p> <p> <pre><span style="color:#600277;">fullDeck</span>&nbsp;::&nbsp;[<span style="color:blue;">Card</span>] fullDeck&nbsp;<span style="color:#666666;">=</span>&nbsp;[<span style="color:#dd0000;">Card</span>&nbsp;f&nbsp;s&nbsp;<span style="color:#666666;">|</span>&nbsp;f&nbsp;<span style="color:#666666;">&lt;-</span>&nbsp;allFaces,&nbsp;s&nbsp;<span style="color:#666666;">&lt;-</span>&nbsp;allSuits]</pre> </p> <p> List comprehension, however, is (as the name implies) specific to lists, whereas an <em>applicative functor</em> is a more general concept. </p> <h3 id="cef0030207354d1fbf0ab2c1a791eb84"> Summary <a href="#cef0030207354d1fbf0ab2c1a791eb84" title="permalink">#</a> </h3> <p> This article introduced you to lists as an applicative functor, using the motivating example of having to populate a full deck of cards with all possible combinations of suits and faces. </p> <p> The next article in the series shows another list example. The F# and Haskell code will be similar to the code in the present article, but the next article will also include a translation to C#. </p> <p> <strong>Next:</strong> <a href="http://blog.ploeh.dk/2018/10/15/an-applicative-password-list">An applicative password list</a>. </p> </div><hr> This blog is totally free, but if you like it, please <a href="https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=NZEPYW8KVZ8WL">buy me a cup of coffee</a>. Mark Seemann http://blog.ploeh.dk/2018/10/08/full-deck Applicative functors http://blog.ploeh.dk/2018/10/01/applicative-functors/ Mon, 01 Oct 2018 06:34:00 UTC <div id="post"> <p> <em>An applicative functor is a useful abstraction. While typically associated with functional programming, applicative functors can be conjured into existence in C# as well.</em> </p> <p> This article series is part of <a href="http://blog.ploeh.dk/2018/03/19/functors-applicatives-and-friends">a larger series of articles about functors, applicatives, and other mappable containers</a>. </p> <p> In a <a href="http://blog.ploeh.dk/2018/03/22/functors">former article series</a>, you learned about functors, and how they also exist in object-oriented design. Perhaps the utility of this still eludes you, although, if you've ever had experience with LINQ in C#, you should realise that the abstraction is invaluable. Functors are abundant; <em>applicative functors</em> not quite so much. On the other hand, applicative functors enable you to <em>do</em> more. </p> <p> I find it helpful to think of applicative functors as an abstraction that enable you to express <em>combinations</em> of things. </p> <p> In the functor article series, I mostly focused on the mechanics of implementation. In this article series, I think that you'll find it helpful to slightly change the perspective. In these articles, I'll show you various motivating examples of how applicative functors are useful. <ul> <li><a href="http://blog.ploeh.dk/2018/10/08/full-deck">Full deck</a></li> <li><a href="http://blog.ploeh.dk/2018/10/15/an-applicative-password-list">An applicative password list</a></li> <li><a href="http://blog.ploeh.dk/2018/10/22/applicative-combinations-of-functions">Applicative combinations of functions</a></li> <li><a href="http://blog.ploeh.dk/2018/10/29/the-maybe-applicative-functor">The Maybe applicative functor</a></li> <li><a href="http://blog.ploeh.dk/2018/11/05/applicative-validation">Applicative validation</a></li> <li>Test Data Generator</li> <li>Danish CPR numbers in F#</li> </ul> You should consider reading one or more of these articles before continuing the present article. </p> <h3 id="6173a96aedaa4e97ad868c159e6d06fa"> A Haskell perspective <a href="#6173a96aedaa4e97ad868c159e6d06fa" title="permalink">#</a> </h3> <p> A normal functor maps objects in an 'elevated world' (like C#'s <code>IEnumerable&lt;T&gt;</code> or <code>IObservable&lt;T&gt;</code>) using a function in the 'normal world'. As a variation, an applicative functor maps objects in an 'elevated world' using functions from the same 'elevated world'. </p> <p> In <a href="https://haskell.org">Haskell</a>, an applicative functor is defined <em>like</em> this: </p> <p> <pre><span style="color:blue;">class</span>&nbsp;Functor&nbsp;f&nbsp;=&gt;&nbsp;<span style="color:#a31515;">Applicative</span>&nbsp;f&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:#600277;">pure</span>&nbsp;&nbsp;::&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;f&nbsp;a &nbsp;&nbsp;(&lt;*<span style="color:blue;">&gt;</span>)&nbsp;::&nbsp;f&nbsp;(a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;b)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;f&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;f&nbsp;b </pre> </p> <p> This is a <strong>simplification</strong>; there's more to the <code>Applicative</code> typeclass than this, but this should highlight the essence. What it says is that an applicative functor must already be a <code>Functor</code>. It could be any sort of <code>Functor</code>, like <code>[]</code> (linked list), <code>Maybe</code>, <code>Either</code>, and so on. Since <code>Functor</code> is an abstraction, it's called <code>f</code>. </p> <p> The definition furthermore says that in order for a functor to be applicative, two functions must exist: <code>pure</code> and <code>&lt;*&gt;</code> (<em>'apply'</em>). </p> <p> <code>pure</code> is easy to understand. It simply 'elevates' a 'normal' value to a functor value. For example, you can elevate the number <code>42</code> to a list value by putting it in a list with a single element: <code>[42]</code>. Or you can elevate <code>"foo"</code> to <code>Maybe</code> by containing it in the <code>Just</code> case: <code>Just "foo"</code>. That is, literally, what <code>pure</code> does for <code>[]</code> (list) and <code>Maybe</code>. </p> <p> The <code>&lt;*&gt;</code> operator applies an 'elevated' function to an 'elevated' value. When <code>f</code> is <code>[]</code>, this literally means that you have a list of functions that you have to apply to a list of values. Perhaps you can already see what I meant by <em>combinations</em> of things. </p> <p> This sounds abstract, but follow the above list of links in order to see several examples. </p> <h3 id="6f9b2f13951e475d8c4fc9682ad96a94"> An F# perspective <a href="#6f9b2f13951e475d8c4fc9682ad96a94" title="permalink">#</a> </h3> <p> Applicative functors aren't explicitly modelled in <a href="https://fsharp.org">F#</a>, but they're easy enough to add if you need them. F# doesn't have typeclasses, so implementing applicative functors tend to be more on a case-by-case basis. </p> <p> If you need <code>list</code> to be applicative, <code>pure</code> should have the type <code>'a -&gt; 'a list</code>, and <code>&lt;*&gt;</code> should have the type <code>('a -&gt; 'b) list -&gt; 'a list -&gt; 'b list</code>. At this point, you already run into the problem that <code>pure</code> is a reserved keyword in F#, so you'll have to find another name, or simply ignore that function. </p> <p> If you need <code>option</code> to be applicative, <code>&lt;*&gt;</code> should have the type <code>('a -&gt; 'b) option -&gt; 'a option -&gt; 'b option</code>. Now you run into your second problem, because which function is <code>&lt;*&gt;</code>? The one for <code>list</code>, or the one for <code>option</code>? It can't be both, so you'll have to resort to all sorts of hygiene to prevent these two versions of the same operator from clashing. This somewhat limits its usefulness. </p> <p> Again, refer to the above list of linked articles for concrete examples. </p> <h3 id="cef395ee19644f30bfd1ad7a84b6f912"> A C# perspective <a href="#cef395ee19644f30bfd1ad7a84b6f912" title="permalink">#</a> </h3> <p> Applicative functors push the limits of what you can express in C#, but the equivalent to <code>&lt;*&gt;</code> would be a method with this signature: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Functor</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;Apply&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Functor</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;&nbsp;selector, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Functor</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;source)</pre> </p> <p> Here, the class <code>Functor&lt;T&gt;</code> is a place-holder for a proper functor class. A concrete example could be for <code>IEnumerable&lt;T&gt;</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;Apply&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;&nbsp;selectors, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;source)</pre> </p> <p> As you can see, here you somehow have to figure out how to combine a sequence of functions with a sequence of values. </p> <p> In some of the examples in the above list of linked articles, you'll see how this will stretch the capability of C#. </p> <h3 id="ffa16273a2a0428f90190f8d559cf0a6"> Summary <a href="#ffa16273a2a0428f90190f8d559cf0a6" title="permalink">#</a> </h3> <p> This article only attempts to provide an overview of applicative functors, while examples are given in linked articles. I find it helpful to think of applicative functors as an abstraction that enables you to model arbitrary <em>combinations</em> of objects. This is a core feature in Haskell, occasionally useful in F#, and somewhat alien to C#. </p> <p> <strong>Next:</strong> <a href="http://blog.ploeh.dk/2018/10/08/full-deck">Full deck</a>. </p> </div><hr> This blog is totally free, but if you like it, please <a href="https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=NZEPYW8KVZ8WL">buy me a cup of coffee</a>. Mark Seemann http://blog.ploeh.dk/2018/10/01/applicative-functors Asynchronous functors http://blog.ploeh.dk/2018/09/24/asynchronous-functors/ Mon, 24 Sep 2018 03:37:00 UTC <div id="post"> <p> <em>Asynchronous computations form functors. An article for object-oriented programmers.</em> </p> <p> This article is an instalment in <a href="http://blog.ploeh.dk/2018/03/22/functors">an article series about functors</a>. The previous article covered the <a href="http://blog.ploeh.dk/2018/09/10/the-lazy-functor">Lazy functor</a>. In this article, you'll learn about closely related functors: .NET Tasks and <a href="https://fsharp.org">F#</a> <a href="https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/asynchronous-workflows">asynchronous workflows</a>. </p> <p> A word of warning is in order. .NET Tasks aren't <a href="https://en.wikipedia.org/wiki/Referential_transparency">referentially transparent</a>, whereas F# asynchronous computations are. You could argue, then, that .NET Tasks aren't proper functors, but you mostly observe the difference when you perform impure operations. As a general observation, when impure operations are allowed, the conclusions of <a href="http://blog.ploeh.dk/2017/10/04/from-design-patterns-to-category-theory">this overall article series</a> are precarious. We can't radically change how the .NET languages work, so we'll have to soldier on, pretending that impure operations are delegated to other parts of our system. Under this undue assumption, we can pretend that <a href="https://docs.microsoft.com/en-us/dotnet/api/system.threading.tasks.task-1">Task&lt;T&gt;</a> forms a functor. </p> <h3 id="f82479d93d5d40ed83749a6d9fc309dc"> Task functor <a href="#f82479d93d5d40ed83749a6d9fc309dc" title="permalink">#</a> </h3> <p> You can write an idiomatic <code>Select</code> extension method for <code>Task&lt;T&gt;</code> like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">async</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Task</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;Select&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Task</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;source, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;selector) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;x&nbsp;=&nbsp;<span style="color:blue;">await</span>&nbsp;source; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;selector(x); }</pre> </p> <p> With this extension method in scope, you can compose asynchronous computations like this: </p> <p> <pre><span style="color:#2b91af;">Task</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;x&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:#2b91af;">Task</span>&lt;<span style="color:blue;">string</span>&gt;&nbsp;y&nbsp;=&nbsp;x.Select(i&nbsp;=&gt;&nbsp;i.ToString());</pre> </p> <p> Or, if you prefer <em>query syntax:</em> </p> <p> <pre><span style="color:#2b91af;">Task</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;x&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:#2b91af;">Task</span>&lt;<span style="color:blue;">string</span>&gt;&nbsp;y&nbsp;=&nbsp;<span style="color:blue;">from</span>&nbsp;i&nbsp;<span style="color:blue;">in</span>&nbsp;x&nbsp;<span style="color:blue;">select</span>&nbsp;i.ToString();</pre> </p> <p> In both cases, you start with a <code>Task&lt;int&gt;</code> which you map into a <code>Task&lt;string&gt;</code>. Perhaps you've noticed that these two examples closely resemble the equivalent <a href="http://blog.ploeh.dk/2018/09/10/the-lazy-functor">Lazy functor examples</a>. The resemblance isn't coincidental. The same <em>abstraction</em> is in use in both places. This is the <em>functor</em> abstraction. That's what this article series is all about, after all. </p> <p> The difference between the Task functor and the Lazy functor is that lazy computations don't run until forced. Tasks, on the other hand, typically start running in the background when created. Thus, when you finally <code>await</code> the value, you may actually not have to wait for it. This does, however, depend on how you created the initial task. </p> <h3 id="8d66efff8d5a4e73b3007878b3ec7227"> First functor law for Task <a href="#8d66efff8d5a4e73b3007878b3ec7227" title="permalink">#</a> </h3> <p> The <code>Select</code> method obeys the first functor law. As usual in this article series, actually proving that this is the case belongs to the realm of computer science. Instead of proving that the law holds, you can use property-based testing to demonstrate that it does. The following example shows a single property written with <a href="https://fscheck.github.io/FsCheck/">FsCheck</a> 2.11.0 and <a href="https://xunit.github.io/">xUnit.net</a> 2.4.0. </p> <p> <pre>[<span style="color:#2b91af;">Property</span>(QuietOnSuccess&nbsp;=&nbsp;<span style="color:blue;">true</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;TaskObeysFirstFunctorLaw(<span style="color:blue;">int</span>&nbsp;i) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;&nbsp;left&nbsp;=&nbsp;<span style="color:#2b91af;">Task</span>.FromResult(i); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;right&nbsp;=&nbsp;<span style="color:#2b91af;">Task</span>.FromResult(i).Select(x&nbsp;=&gt;&nbsp;x); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(left.Result,&nbsp;right.Result); }</pre> </p> <p> This property accesses the <a href="https://docs.microsoft.com/en-us/dotnet/api/system.threading.tasks.task-1.result">Result property</a> of the Tasks involved. This is typically not the preferred way to pull the value of Tasks, but I decided to do it like this since <a href="https://github.com/fscheck/FsCheck/issues/167">FsCheck 2.4.0 doesn't support asynchronous properties</a>. </p> <p> Even though you may feel that a property-based test gives you more confidence than a few hard-coded examples, such a test is nothing but a demonstration of the first functor law. It's no proof, and it only demonstrates that the law holds for <code>Task&lt;int&gt;</code>, not that it holds for <code>Task&lt;string&gt;</code>, <code>Task&lt;Product&gt;</code>, etcetera. </p> <h3 id="12b3ea8d8963414496a6c695f130a4b9"> Second functor law for Task <a href="#12b3ea8d8963414496a6c695f130a4b9" title="permalink">#</a> </h3> <p> As is the case with the first functor law, you can also use a property to demonstrate that the second functor law holds: </p> <p> <pre>[<span style="color:#2b91af;">Property</span>(QuietOnSuccess&nbsp;=&nbsp;<span style="color:blue;">true</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;TaskObeysSecondFunctorLaw( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">byte</span>&gt;&nbsp;f, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;g, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;i) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;&nbsp;left&nbsp;=&nbsp;<span style="color:#2b91af;">Task</span>.FromResult(i).Select(g).Select(f); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;right&nbsp;=&nbsp;<span style="color:#2b91af;">Task</span>.FromResult(i).Select(x&nbsp;=&gt;&nbsp;f(g(x))); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(left.Result,&nbsp;right.Result); }</pre> </p> <p> Again the same admonitions apply: that property is no proof. It does show, however, that given two functions, <code>f</code> and <code>g</code>, it doesn't matter if you map a Task in one or two steps. The output is the same in both cases. </p> <h3 id="d87480f7e0124db18b22aaacbff3672a"> Async functor <a href="#d87480f7e0124db18b22aaacbff3672a" title="permalink">#</a> </h3> <p> F# had asynchronous workflows long before C#, so it uses a slightly different model, supported by separate types. Instead of <code>Task&lt;T&gt;</code>, F# relies on a generic type called <a href="https://msdn.microsoft.com/en-us/visualfsharpdocs/conceptual/control.async%5b%27t%5d-type-%5bfsharp%5d">Async&lt;'T&gt;</a>. It's still a functor, since you can trivially implement a <code>map</code> function for it: </p> <p> <pre><span style="color:blue;">module</span>&nbsp;Async&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;&#39;a&nbsp;-&gt;&nbsp;Async&lt;&#39;a&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;fromValue&nbsp;x&nbsp;=&nbsp;async&nbsp;{&nbsp;<span style="color:blue;">return</span>&nbsp;x&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b)&nbsp;-&gt;&nbsp;Async&lt;&#39;a&gt;&nbsp;-&gt;&nbsp;Async&lt;&#39;b&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;map&nbsp;f&nbsp;x&nbsp;=&nbsp;async&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;x&#39;&nbsp;=&nbsp;x &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;f&nbsp;x&#39;&nbsp;}</pre> </p> <p> The <code>map</code> function uses the <code>async</code> <a href="https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/computation-expressions">computation expression</a> to access the value being computed asynchronously. You can use a <code>let!</code> binding to await the value computed in <code>x</code>, and then use the function <code>f</code> to translate that value. The <code>return</code> keyword turns the result into a new <code>Async</code> value. </p> <p> With the <code>map</code> function, you can write code like this: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;(x&nbsp;:&nbsp;Async&lt;int&gt;)&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:blue;">let</span>&nbsp;(y&nbsp;:&nbsp;Async&lt;string&gt;)&nbsp;=&nbsp;x&nbsp;|&gt;&nbsp;Async.map&nbsp;string</pre> </p> <p> Once you've composed an asynchronous workflow to your liking, you can run it to compute the value in which you're interested: </p> <p> <pre>&gt; Async.RunSynchronously y;; val it : string = "42"</pre> </p> <p> This is the main difference between F# asynchronous workflows and .NET Tasks. You have to explicitly run an asynchronous workflows, whereas Tasks are usually, implicitly, already running in the background. </p> <h3 id="f572e55512ab484584450dc0af7fe9b3"> First functor law for Async <a href="#f572e55512ab484584450dc0af7fe9b3" title="permalink">#</a> </h3> <p> The <code>Async.map</code> function obeys the first functor law. Like above, you can use FsCheck to demonstrate how that works: </p> <p> <pre>[&lt;Property(QuietOnSuccess&nbsp;=&nbsp;<span style="color:blue;">true</span>)&gt;] <span style="color:blue;">let</span>&nbsp;``Async&nbsp;obeys&nbsp;first&nbsp;functor&nbsp;law``&nbsp;(i&nbsp;:&nbsp;int)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;&nbsp;left&nbsp;=&nbsp;Async.fromValue&nbsp;i &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;right&nbsp;=&nbsp;Async.fromValue&nbsp;i&nbsp;|&gt;&nbsp;Async.map&nbsp;id &nbsp;&nbsp;&nbsp;&nbsp;Async.RunSynchronously&nbsp;left&nbsp;=!&nbsp;Async.RunSynchronously&nbsp;right</pre> </p> <p> In addition to FsCheck and xUnit.net, this property also uses <a href="https://github.com/SwensenSoftware/unquote">Unquote</a> 4.0.0 for the assertion. The <code>=!</code> operator is an assertion that the left-hand side <em>must equal</em> the right-hand side. If it doesn't, then the operator throws a descriptive exception. </p> <h3 id="6fd1ba5d9c0647c49ba06d7580b2c552"> Second functor law for Async <a href="#6fd1ba5d9c0647c49ba06d7580b2c552" title="permalink">#</a> </h3> <p> As is the case with the first functor law, you can also use a property to demonstrate that the second functor law holds: </p> <p> <pre>[&lt;Property(QuietOnSuccess&nbsp;=&nbsp;<span style="color:blue;">true</span>)&gt;] <span style="color:blue;">let</span>&nbsp;``Async&nbsp;obeys&nbsp;second&nbsp;functor&nbsp;law``&nbsp;(f&nbsp;:&nbsp;string&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;byte)&nbsp;g&nbsp;(i&nbsp;:&nbsp;int)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;&nbsp;left&nbsp;=&nbsp;Async.fromValue&nbsp;i&nbsp;|&gt;&nbsp;Async.map&nbsp;g&nbsp;|&gt;&nbsp;Async.map&nbsp;f &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;right&nbsp;=&nbsp;Async.fromValue&nbsp;i&nbsp;|&gt;&nbsp;Async.map&nbsp;(g&nbsp;&gt;&gt;&nbsp;f) &nbsp;&nbsp;&nbsp;&nbsp;Async.RunSynchronously&nbsp;left&nbsp;=!&nbsp;Async.RunSynchronously&nbsp;right</pre> </p> <p> As usual, the second functor law states that given two arbitrary (but <a href="https://en.wikipedia.org/wiki/Pure_function">pure</a>) functions <code>f</code> and <code>g</code>, it doesn't matter if you map an asynchronous workflow in one or two steps. There could be a difference in performance, but the functor laws don't concern themselves with the time dimension. </p> <p> Both of the above properties use the <code>Async.fromValue</code> helper function to create <code>Async</code> values. Perhaps you consider it cheating that it immediately produces a value, but you can add a delay if you want to pretend that actual asynchronous computation takes place. It'll make the tests run slower, but otherwise will not affect the outcome. </p> <h3 id="9ad596ae1e5f483cb6d02ad963a0a378"> Task and Async isomorphism <a href="#9ad596ae1e5f483cb6d02ad963a0a378" title="permalink">#</a> </h3> <p> The reason I've covered both <code>Task&lt;T&gt;</code> and <code>Async&lt;'a&gt;</code> in the same article is that they're equivalent. You can translate a Task to an asynchronous workflow, or the other way around. </p> <p> <img src="/content/binary/equivalence-of-task-and-async.png" alt="Equivalence of Task and Async."> </p> <p> There's performance implications of going back and forth between <code>Task&lt;T&gt;</code> and <code>Async&lt;'a&gt;</code>, but there's no loss of information. You can, therefore, consider these to representations of asynchronous computations <a href="http://blog.ploeh.dk/2018/01/08/software-design-isomorphisms">isomorphic</a>. </p> <h3 id="4bb86c51ae37462b94e278247d33f8f5"> Summary <a href="#4bb86c51ae37462b94e278247d33f8f5" title="permalink">#</a> </h3> <p> Whether you do asynchronous programming with <code>Task&lt;T&gt;</code> or <code>Async&lt;'a&gt;</code>, asynchronous computations form functors. This enables you to piecemeal compose asynchronous workflows. </p> <p> <strong>Next:</strong> <a href="http://blog.ploeh.dk/2018/10/01/applicative-functors">Applicative functors</a>. </p> </div><hr> This blog is totally free, but if you like it, please <a href="https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=NZEPYW8KVZ8WL">buy me a cup of coffee</a>. Mark Seemann http://blog.ploeh.dk/2018/09/24/asynchronous-functors Typing is not a programming bottleneck http://blog.ploeh.dk/2018/09/17/typing-is-not-a-programming-bottleneck/ Mon, 17 Sep 2018 08:16:00 UTC <div id="post"> <p> <em>Some developers seem to think that typing is a major bottleneck while programming. It's not.</em> </p> <p> I sometimes give programming advice to people. They approach me with a software design problem, and, to the best of my ability, I suggest a remedy. Despite my best intentions, my suggestions sometimes meet resistance. One common reaction is that <a href="http://blog.ploeh.dk/2015/08/03/idiomatic-or-idiosyncratic">my suggestion isn't idiomatic</a>, but recently, another type of criticism seems to be on the rise. </p> <p> The code that I suggest is too verbose. It involves too much typing. </p> <p> I'll use this article to reflect on that criticism. </p> <h3 id="d1f8398f96584ed09acce1b481b45cde"> The purpose of code <a href="#d1f8398f96584ed09acce1b481b45cde" title="permalink">#</a> </h3> <p> Before we get into the details of the issue, I'd like to start with the big picture. What's the purpose of code? </p> <p> I've discussed this extensively in my <a href="https://cleancoders.com">Clean Coders</a> video on <a href="https://cleancoders.com/episode/humane-code-real-episode-1/show">Humane Code</a>. In short, the purpose of source code is to <em>communicate</em> the workings of a piece of software to the next programmer who comes along. This could easily include your future self. </p> <p> Perhaps you disagree with that proposition. Perhaps you think that the purpose of source code is to produce working software. It's that, too, but that's not its only purpose. If that was the only purpose, you might as well write the software in machine code. </p> <p> Why do we have high-level programming languages like C#, Java, JavaScript, Ruby, Python, F#, Visual Basic, Haskell, heck - even C++? </p> <p> As far as I can tell, it's because programmers are all human, and humans have limited cognitive capacity. We can't keep track of hundreds, or thousands, of global variables, or the states of dozens of complex resources. We need tools that help us structure and understand complex systems so that they're broken down into (more) manageable chunks. High-level languages help us do that. </p> <p> The purpose of source code is to be understood. You read source code much more that you write. I'm not aware of any scientific studies, but I think most programmers will agree that over the lifetime of a code base, any line of code will be read orders of magnitude more often that it's edited. </p> <h3 id="b82afa298f114b8c89113ea5f40fc278"> Typing speed <a href="#b82afa298f114b8c89113ea5f40fc278" title="permalink">#</a> </h3> <p> How many lines of code do you produce during a productive working day? </p> <p> To be honest, I can't even answer that question myself. I've never measured it, since I consider it to be irrelevant. <a href="http://bit.ly/mythical-man-month">The Mythical Man-Month</a> gives the number as <em>10</em>, but let's be generous and pretend it's ten times that. This clearly depends on lots of factors, such as the language in which you're writing, the state of the code base, and so on. You'd tend to write more lines in a pristine greenfield code base, whereas you'll write fewer lines of code in a complicated legacy code base. </p> <p> How many characters is a line of code? Let's say it's 80 characters, because that's the maximum width code ought to have. I realise that many people write wider lines, but on the other hand, most developers (fortunately) use indentation, so as a counter-weight, code often has some blank space to the left as well. This is all back-of-the-envelope calculations anyway. </p> <p> When I worked in a Microsoft product group, we typically planned that a productive, 'full' day of coding was five hours. Even on productive days, the rest was used in meetings, administration, breaks, and so on. </p> <p> If you write code for five hours, and produce 100 lines of code, at 80 characters per line, that's 8,000 characters. Your IDE is likely to help you with statement completion and such, but for the sake of argument, let's pretend that you have to type it all in. </p> <p> 8,000 characters in five hours is 1,600 characters per hour, or 27 characters per minute. </p> <p> I'm not a particularly fast typist, but I can type ten times faster than that. </p> <p> Typing isn't a bottleneck. </p> <h3 id="cad0abab133848d98b4aada5e31d35d6"> Is more code worse? <a href="#cad0abab133848d98b4aada5e31d35d6" title="permalink">#</a> </h3> <p> I tend to <a href="http://blog.ploeh.dk/2013/02/04/BewareofProductivityTools">get drawn into these discussions from time to time</a>, but good programming has little to do with how fast you can produce lines of code. </p> <p> To be clear, I entirely accept that statement completion, refactoring support, and such are, in general, benign features. While I spend most of my programming time thinking and reading, I also tend to write code in bursts. The average count of lines per hour may not be great, but that's because averages smooth out the hills and the valleys of my activity. </p> <p> Still, increasingly frequent objection to some of my suggestions is that what I suggest implies 'too much' code. Recently, for example, I had to defend the merits of the <a href="https://martinfowler.com/bliki/FluentInterface.html">Fluent</a> Builder pattern that I suggest in my <a href="http://blog.ploeh.dk/2014/05/19/di-friendly-library">DI-Friendly Library</a> article. </p> <p> As another example, consider two alternatives for modelling a restaurant reservation. First, here's a terse option: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">Reservation</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">DateTimeOffset</span>&nbsp;Date&nbsp;{&nbsp;<span style="color:blue;">get</span>;&nbsp;<span style="color:blue;">set</span>;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">string</span>&nbsp;Email&nbsp;{&nbsp;<span style="color:blue;">get</span>;&nbsp;<span style="color:blue;">set</span>;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">string</span>&nbsp;Name&nbsp;{&nbsp;<span style="color:blue;">get</span>;&nbsp;<span style="color:blue;">set</span>;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">int</span>&nbsp;Quantity&nbsp;{&nbsp;<span style="color:blue;">get</span>;&nbsp;<span style="color:blue;">set</span>;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;IsAccepted&nbsp;{&nbsp;<span style="color:blue;">get</span>;&nbsp;<span style="color:blue;">set</span>;&nbsp;} }</pre> </p> <p> Here's a longer alternative: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">sealed</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">Reservation</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;Reservation( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">DateTimeOffset</span>&nbsp;date, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">string</span>&nbsp;name, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">string</span>&nbsp;email, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;quantity)&nbsp;: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>(date,&nbsp;name,&nbsp;email,&nbsp;quantity,&nbsp;<span style="color:blue;">false</span>) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;Reservation( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">DateTimeOffset</span>&nbsp;date, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">string</span>&nbsp;name, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">string</span>&nbsp;email, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;quantity, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">bool</span>&nbsp;isAccepted) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date&nbsp;=&nbsp;date; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Name&nbsp;=&nbsp;name; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Email&nbsp;=&nbsp;email; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity&nbsp;=&nbsp;quantity; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;IsAccepted&nbsp;=&nbsp;isAccepted; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">DateTimeOffset</span>&nbsp;Date&nbsp;{&nbsp;<span style="color:blue;">get</span>;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">string</span>&nbsp;Name&nbsp;{&nbsp;<span style="color:blue;">get</span>;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">string</span>&nbsp;Email&nbsp;{&nbsp;<span style="color:blue;">get</span>;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">int</span>&nbsp;Quantity&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;IsAccepted&nbsp;{&nbsp;<span style="color:blue;">get</span>;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;WithDate(<span style="color:#2b91af;">DateTimeOffset</span>&nbsp;newDate) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>(newDate,&nbsp;Name,&nbsp;Email,&nbsp;Quantity,&nbsp;IsAccepted); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;WithName(<span style="color:blue;">string</span>&nbsp;newName) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>(Date,&nbsp;newName,&nbsp;Email,&nbsp;Quantity,&nbsp;IsAccepted); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;WithEmail(<span style="color:blue;">string</span>&nbsp;newEmail) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>(Date,&nbsp;Name,&nbsp;newEmail,&nbsp;Quantity,&nbsp;IsAccepted); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;WithQuantity(<span style="color:blue;">int</span>&nbsp;newQuantity) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>(Date,&nbsp;Name,&nbsp;Email,&nbsp;newQuantity,&nbsp;IsAccepted); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;Accept() &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>(Date,&nbsp;Name,&nbsp;Email,&nbsp;Quantity,&nbsp;<span style="color:blue;">true</span>); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">override</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;Equals(<span style="color:blue;">object</span>&nbsp;obj) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(!(obj&nbsp;<span style="color:blue;">is</span>&nbsp;<span style="color:#2b91af;">Reservation</span>&nbsp;other)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">false</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;Equals(Date,&nbsp;other.Date) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&amp;&amp;&nbsp;Equals(Name,&nbsp;other.Name) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&amp;&amp;&nbsp;Equals(Email,&nbsp;other.Email) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&amp;&amp;&nbsp;Equals(Quantity,&nbsp;other.Quantity) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&amp;&amp;&nbsp;Equals(IsAccepted,&nbsp;other.IsAccepted); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">override</span>&nbsp;<span style="color:blue;">int</span>&nbsp;GetHashCode() &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Date.GetHashCode()&nbsp;^ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Name.GetHashCode()&nbsp;^ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Email.GetHashCode()&nbsp;^ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Quantity.GetHashCode()&nbsp;^ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;IsAccepted.GetHashCode(); &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> Which alternative is better? The short version is eight lines of code, including the curly brackets. The longer version is 78 lines of code. That's ten times as much. </p> <p> I prefer the longer version. While it takes longer to type, it comes with several benefits. The main benefit is that because it's immutable, it can have structural equality. This makes it trivial to compare objects, which, for example, is something you do all the time in unit test assertions. Another benefit is that such <a href="http://blog.ploeh.dk/2015/01/19/from-primitive-obsession-to-domain-modelling">Value Objects make better domain models</a>. The above <code>Reservation</code> <a href="https://martinfowler.com/bliki/ValueObject.html">Value Object</a> only shows the slightest sign of emerging domain logic in the <code>Accept</code> method, but once you start modelling like this, such objects seem to attract more domain behaviour. </p> <h3 id="78654bcab6ee4c57a24a5a41adf6c0fa"> Maintenance burden <a href="#78654bcab6ee4c57a24a5a41adf6c0fa" title="permalink">#</a> </h3> <p> Perhaps you're now convinced that typing speed may not be the bottleneck, but you still feel that you don't like the verbose <code>Reservation</code> alternative. More code could be an increased maintenance burden. </p> <p> Consider those <code>With[...]</code> methods, such as <code>WithName</code>, <code>WithQuantity</code>, and so on. Once you make objects immutable, such copy-and-update methods become indispensable. They enable you to change a single property of an object, while keeping all other values intact: </p> <p> <pre>&gt; <span style="color:blue;">var</span>&nbsp;r&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>(<span style="color:#2b91af;">DateTimeOffset</span>.Now,&nbsp;<span style="color:#a31515;">&quot;Foo&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;foo@example.com&quot;</span>,&nbsp;3); &gt; r.WithQuantity(4) Reservation { Date=[11.09.2018 19:19:29 +02:00], Email="foo@example.com", IsAccepted=false, Name="Foo", Quantity=4 }</pre> </p> <p> While convenient, such methods can increase the maintenance burden. If you realise that you need to change the name of one of the properties, you'll have to remember to also change the name of the copy-and-update method. For example, if you change <code>Quantity</code> to <code>NumberOfGuests</code>, you'll have to also remember to rename <code>WithQuantity</code> to <code>WithNumberOfGuests</code>. </p> <p> I'm not sure that I'm ready to concede that this is a prohibitive strain on the sustainability of a code base, but I do grant that it's a nuisance. This is one of the many reasons that I prefer to use programming languages better equipped for such domain modelling. In <a href="https://fsharp.org">F#</a>, for example, a record type similar to the above immutable <code>Reservation</code> class would be a one-liner: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;Reservation&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;Date&nbsp;:&nbsp;DateTimeOffset;&nbsp;Name&nbsp;:&nbsp;string;&nbsp;Email&nbsp;:&nbsp;string;&nbsp;Quantity&nbsp;:&nbsp;int;&nbsp;IsAccepted&nbsp;:&nbsp;bool&nbsp;}</pre> </p> <p> Such a declarative approach to types produces an immutable record with the same capabilities as the 78 lines of C# code. </p> <p> That's a different story, though. There's little correlation between the size of code, and how 'good' it is. Sometimes, less code is better; sometimes, more code is better. </p> <h3 id="ec55edfbe2a245b0b56188d4e8c6fbfb"> Summary <a href="#ec55edfbe2a245b0b56188d4e8c6fbfb" title="permalink">#</a> </h3> <p> I'll dispense with the usual Edsger Dijkstra and Bill Gates quotes on lines of code. The point that lines of code is a useless metric in software development has been made already. My point is a corollary. Apparently, it has to be explicitly stated: <em>Programmer productivity has nothing to do with typing speed.</em> </p> <p> Unless you're disabled in some way, you can type fast enough to be a productive programmer. Typing isn't a programming bottleneck. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="4bfb1d54e38449c7bc5d30e171d01179"> <div class="comment-author"><a href="http://honestillusion.com">James Curran</a></div> <div class="comment-content"> While I accept most of what you say, you are overlooking one key point: Better typists are better typists. Speed of typing (and volume of code produced) is the only statistic you look at. But what about <em>quality</em>? <br/> Watch a bad typist code. (It's easier with coding-heavy tutorial videos). It usually go as: type four or five characters, backspace, make a correction, type another six characters, backspace, make another fix, type a few more character, etc. <br/> They rarely get more than 10 keystrokes out before have to stop and go back. This reeks havoc with your cognitive flow, and makes it much harder to get into the "groove" of coding. Once you can type fluidly, you can concetrate on the code itself, rather than the mechanics of entering it. </div> <div class="comment-date">2018-09-19 02:02 UTC</div> </div> <div class="comment" id="3074a90b8bdb483dbc47d2364f056254"> <div class="comment-author"><a href="https://davideguida.com">Davide Guida</a></div> <div class="comment-content"> Lines of code has nothing to do with productivity. As professionals I think we all know this. <br /> Moreover, in many cases, too much verbosity might only lead to more defects (unless you're a strong advocate of TDD et similia)<br /> That said, one thing that I really liked about your article is the version of the Builder pattern you've implemented in the Reservation class. I love immutability in my classes and I often use the Builder pattern implemented as a inner class, just to be able to access the private cTor. <br/> One thing that I don't like with your approach is that in case you have a bit parameter list in your cTor (as you do in the example), the consumers are forced to create a "dummy" instance and then call the WithXXX() methods on it when possible. I guess it could be solved adding a static readonly Empty property on the Reservation class that can be used as a starting point. <br/> Anyways thank you for sharing this! </div> <div class="comment-date">2018-09-19 11:02 UTC</div> </div> <div class="comment" id="a4f8063cfaf84a10badd28981fac1ac5"> <div class="comment-author"><a href="http://blog.ploeh.dk">Mark Seemann</a></div> <div class="comment-content"> <p> James, thank you for writing. I agree that being able to type out your thoughts as fast as possible lowers the barrier between your brain and whatever medium you're working in. I had something similar in mind when I wrote <blockquote> "I also tend to write code in bursts. The average count of lines per hour may not be great, but that's because averages smooth out the hills and the valleys of my activity." </blockquote> I do, however, have mounting concerns about what you call the <em>groove</em> of coding. Flow state is generally characterised by a lack of reflection that I have often found to be counter-productive. These days, when programming, I deliberately use the Pomodoro technique - not to motivate me to code, but to force me to take breaks. Uncountable are the times I've had an important realisation about my work as soon as I'm away from the keyboard. These insights never seem to come to me when I'm in flow. </p> </div> <div class="comment-date">2018-09-21 4:53 UTC</div> </div> <div class="comment" id="8647083ea6c748b6bd2363790a9a69db"> <div class="comment-author">Radek Kapka</div> <div class="comment-content"> <blockquote> <p>Perhaps you&#39;re now convinced that typing speed may not be the bottleneck, but you still feel that you don&#39;t like the verbose <code>Reservation</code> alternative. More code could be an increased maintenance burden. Consider those <code>With[...]</code> methods, such as <code>WithName</code>, <code>WithQuantity</code>, and so on. Once you make objects immutable, such copy-and-update methods become indispensable.</p> </blockquote> <p>You could create a more generic <code>With</code> method that would enable modifying any property. Here is an alternative design of the <code>Reservation</code> class including such a method. It is untested, so it might not work properly in every case.</p> <pre><code>public sealed class Reservation { public Reservation( DateTimeOffset date, string name, string email, int quantity) : this(date, name, email, quantity, false) { } private Reservation( DateTimeOffset date, string name, string email, int quantity, bool isAccepted) { Date = date; Name = name; Email = email; Quantity = quantity; IsAccepted = isAccepted; } private Reservation() { } public DateTimeOffset Date { get; private set; } public string Name { get; private set; } public string Email { get; private set; } public int Quantity { get; private set; } public bool IsAccepted { get; private set; } public Reservation With(string propertyName, object value) { if (propertyName == null) { throw new ArgumentNullException(nameof(propertyName)); } var property = typeof(Reservation).GetProperty(propertyName); if (property == null) { throw new ArgumentException($"Property ${propertyName} does not exist."); } if (!IsAssignable(property, value)) { throw new ArgumentException($"Value ${value} is not assignable to property ${propertyName}"); } var result = new Reservation(); foreach (var prop in typeof(Reservation).GetProperties()) { prop.SetValue(result, prop.Name == propertyName ? value : prop.GetValue(this)); } return result; } public Reservation Accept() { return new Reservation(Date, Name, Email, Quantity, true); } public override bool Equals(object obj) { if (!(obj is Reservation other)) return false; return Equals(Date, other.Date) &amp;&amp; Equals(Name, other.Name) &amp;&amp; Equals(Email, other.Email) &amp;&amp; Equals(Quantity, other.Quantity) &amp;&amp; Equals(IsAccepted, other.IsAccepted); } public override int GetHashCode() { return Date.GetHashCode() ^ Name.GetHashCode() ^ Email.GetHashCode() ^ Quantity.GetHashCode() ^ IsAccepted.GetHashCode(); } private static bool IsAssignable(PropertyInfo property, object value) { if (value == null &amp;&amp; property.PropertyType.IsValueType &amp;&amp; Nullable.GetUnderlyingType(property.PropertyType) == null) { return false; } return value == null || property.PropertyType.IsAssignableFrom(value.GetType()); } } </code></pre><p>Of course this design is not type-safe and we are throwing exceptions whenever the types of property and value don&#39;t match. Property names can be passed using <code>nameof</code> which will provide compile-time feedback. I believe it would be possible to write a code analyzer that would help calling the <code>With</code> method by raising compilation errors whenever the types don&#39;t match. The <code>With</code> method could be even designed as an extension method on <code>object</code> and distributed in a Nuget package with the anayler alongside it.</p> </div> <div class="comment-date">2018-09-27 07:34 UTC</div> </div> </div> <hr> This blog is totally free, but if you like it, please <a href="https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=NZEPYW8KVZ8WL">buy me a cup of coffee</a>. Mark Seemann http://blog.ploeh.dk/2018/09/17/typing-is-not-a-programming-bottleneck The Lazy functor http://blog.ploeh.dk/2018/09/10/the-lazy-functor/ Mon, 10 Sep 2018 05:38:00 UTC <div id="post"> <p> <em>Lazy evaluation forms a functor. An article for object-oriented programmers.</em> </p> <p> This article is an instalment in <a href="http://blog.ploeh.dk/2018/03/22/functors">an article series about functors</a>. Previous articles have covered <a href="http://blog.ploeh.dk/2018/03/26/the-maybe-functor">Maybe</a>, <a href="http://blog.ploeh.dk/2018/08/06/a-tree-functor">rose trees</a>, and other functors. This article provides another example. </p> <p> Most programming languages are eagerly evaluated. Sometimes, however, you'd like to defer execution of an expensive operation. On .NET, you can use <a href="https://docs.microsoft.com/en-us/dotnet/api/system.lazy-1">Lazy&lt;T&gt;</a> to achieve that goal. This generic type, like so many others, forms a functor. </p> <h3 id="0bf1fee5cdf14792a9d235630dd6fc4c"> Functor <a href="#0bf1fee5cdf14792a9d235630dd6fc4c" title="permalink">#</a> </h3> <p> You can implement an idiomatic <code>Select</code> extension method for <code>Lazy&lt;T&gt;</code> like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;Select&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;source, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;selector) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;(()&nbsp;=&gt;&nbsp;selector(source.Value)); }</pre> </p> <p> This would, for example, enable you to write code like this: </p> <p> <pre><span style="color:#2b91af;">Lazy</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;x&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:#2b91af;">Lazy</span>&lt;<span style="color:blue;">string</span>&gt;&nbsp;y&nbsp;=&nbsp;x.Select(i&nbsp;=&gt;&nbsp;i.ToString());</pre> </p> <p> Or, using query syntax: </p> <p> <pre><span style="color:#2b91af;">Lazy</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;x&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:#2b91af;">Lazy</span>&lt;<span style="color:blue;">string</span>&gt;&nbsp;y&nbsp;=&nbsp;<span style="color:blue;">from</span>&nbsp;i&nbsp;<span style="color:blue;">in</span>&nbsp;x&nbsp;<span style="color:blue;">select</span>&nbsp;i.ToString();</pre> </p> <p> You can add more steps to such a pipeline of lazy computation until you finally decide to force evaluation with the <a href="https://docs.microsoft.com/en-us/dotnet/api/system.lazy-1.value">Value</a> property. </p> <p> Notice that while the <code>Select</code> method looks like it might force evaluation as well, by accessing the <code>Value</code> property, this happens inside a new lazily evaluated lambda expression. Thus, all steps in a <code>Lazy</code> pipeline are deferred until evaluation is forced. </p> <h3 id="35bdade6fc5d483da65d7d9623f23aa6"> First functor law <a href="#35bdade6fc5d483da65d7d9623f23aa6" title="permalink">#</a> </h3> <p> The <code>Select</code> method obeys the first functor law. As usual in this article series, actually proving that this is the case belongs in the realm of computer science. Instead of proving that the law holds, you can demonstrate that it does using property-based testing. The following example shows a single property written with <a href="https://fscheck.github.io/FsCheck/">FsCheck</a> 2.11.0 and <a href="https://xunit.github.io/">xUnit.net</a> 2.4.0. </p> <p> <pre>[<span style="color:#2b91af;">Property</span>(QuietOnSuccess&nbsp;=&nbsp;<span style="color:blue;">true</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;LazyObeysFirstFunctorLaw(<span style="color:blue;">int</span>&nbsp;i) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;left&nbsp;=&nbsp;<span style="color:#2b91af;">Lazy</span>.FromValue(i); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;right&nbsp;=&nbsp;<span style="color:#2b91af;">Lazy</span>.FromValue(i).Select(x&nbsp;=&gt;&nbsp;x); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(left.Value,&nbsp;right.Value); }</pre> </p> <p> Even though you may feel that a property-based test gives you more confidence than a few hard-coded examples, such a test is nothing but a demonstration of the first functor law. It's no proof, and it only demonstrates that the law holds for <code>Lazy&lt;int&gt;</code>, not that it holds for <code>Lazy&lt;string&gt;</code>, <code>Lazy&lt;Address&gt;</code>, etcetera. </p> <p> Both this property and the next uses this little static helper method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;FromValue&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:#2b91af;">T</span>&nbsp;value) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">T</span>&gt;(()&nbsp;=&gt;&nbsp;value); }</pre> </p> <p> This helper method is only a convenience. You can put in a delay if you want to pretend that actual lazy evaluation takes place. It'll make the tests run slower, but otherwise will not affect the outcome. </p> <h3 id="dcbd7ed68831441d85960a148336d82c"> Second functor law <a href="#dcbd7ed68831441d85960a148336d82c" title="permalink">#</a> </h3> <p> As is the case with the first functor law, you can also use a property to demonstrate that the second functor law holds: </p> <p> <pre>[<span style="color:#2b91af;">Property</span>(QuietOnSuccess&nbsp;=&nbsp;<span style="color:blue;">true</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;LazyObeysSecondFunctorLaw( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">byte</span>&gt;&nbsp;f, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;g, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;i) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;left&nbsp;=&nbsp;<span style="color:#2b91af;">Lazy</span>.FromValue(i).Select(g).Select(f); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;right&nbsp;=&nbsp;<span style="color:#2b91af;">Lazy</span>.FromValue(i).Select(x&nbsp;=&gt;&nbsp;f(g(x))); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(left.Value,&nbsp;right.Value); }</pre> </p> <p> Again the same admonitions apply: that property is no proof. It does show, however, that given two functions, <code>f</code> and <code>g</code>, it doesn't matter if you map a <code>Lazy</code> computation in one or two steps. The output is the same in both cases. </p> <h3 id="b7c5e06037a64c07822997dc1ede3921"> F# <a href="#b7c5e06037a64c07822997dc1ede3921" title="permalink">#</a> </h3> <p> <a href="https://fsharp.org">F#</a> has <a href="https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/lazy-computations">built-in language support for lazy evaluations</a>, but surprisingly doesn't supply a <code>map</code> function. You can, however, easily implement such a function yourself: </p> <p> <pre><span style="color:blue;">module</span>&nbsp;Lazy&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b)&nbsp;-&gt;&nbsp;Lazy&lt;&#39;a&gt;&nbsp;-&gt;&nbsp;Lazy&lt;&#39;b&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;map&nbsp;f&nbsp;(x&nbsp;:&nbsp;Lazy&lt;&#39;a&gt;)&nbsp;=&nbsp;<span style="color:blue;">lazy</span>&nbsp;f&nbsp;x.Value</pre> </p> <p> This enables you to write code like this: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;(x&nbsp;:&nbsp;Lazy&lt;int&gt;)&nbsp;=&nbsp;//&nbsp;...</span> <span style="color:blue;">let</span>&nbsp;(y&nbsp;:&nbsp;Lazy&lt;string&gt;)&nbsp;=&nbsp;x&nbsp;|&gt;&nbsp;Lazy.map&nbsp;string</pre> </p> <p> The F# language feature is based on the same <code>Lazy&lt;T&gt;</code> class that you can use from C# (and Visual Basic .NET), so the behaviour is the same as described above. The functor laws hold for the <code>Lazy.map</code> function just like it holds for the above <code>Select</code> method. </p> <h3 id="545d7a227c154f2d89dd3b0abbc0d49d"> Haskell <a href="#545d7a227c154f2d89dd3b0abbc0d49d" title="permalink">#</a> </h3> <p> Unlinke C#, F#, and most other programming languages, <a href="https://www.haskell.org">Haskell</a> is lazily evaluated. All values, whether scalar or complex, are lazy by default. For that reason, there's no explicit <em>Lazy</em> type in Haskell. </p> <p> Haskell values are, in themselves, not functors, but you can put any value into the <a href="http://blog.ploeh.dk/2018/09/03/the-identity-functor">Identity functor</a>. Since all values are already lazy, you could view <code>Identity</code> as Haskell's <em>Lazy</em> functor. </p> <p> The equivalence is only partial, however. .NET <code>Lazy</code> objects are small state machines. Before you've forced evaluation, they carry around the expression to be evaluated. Once you've evaluated the value once, <code>Lazy</code> objects effectively replace the lazy expression with its result. Thus, the next time you access the <code>Value</code> property, you immediately receive the result. </p> <p> Haskell's lazily evaluated values are different. Since they're immutable, they don't 'change state' like that. On the other hand, sometimes the Haskell compiler can identify optimisations that it can apply to make lazily evaluated values more efficient. In other cases, you may have to apply more explicit memoisation. </p> <h3 id="6adbe0c495f14e1eaac983c80df10ac4"> Summary <a href="#6adbe0c495f14e1eaac983c80df10ac4" title="permalink">#</a> </h3> <p> In languages with eager evaluation (which is most of them), you can model deferred executation as a functor. This enables you to compose lazily evaluated expressions piecemeal. </p> <p> <strong>Next:</strong> <a href="http://blog.ploeh.dk/2018/09/24/asynchronous-functors">Asynchronous functors</a>. </p> </div><hr> This blog is totally free, but if you like it, please <a href="https://www.paypal.com/cgi-bin/webscr?cmd=_s-xclick&hosted_button_id=NZEPYW8KVZ8WL">buy me a cup of coffee</a>. Mark Seemann http://blog.ploeh.dk/2018/09/10/the-lazy-functor