ploeh blog http://blog.ploeh.dk danish software design en-us Mark Seemann Mon, 21 Jan 2019 13:08:27 UTC Mon, 21 Jan 2019 13:08:27 UTC Some thoughts on anti-patterns http://blog.ploeh.dk/2019/01/21/some-thoughts-on-anti-patterns/ Mon, 21 Jan 2019 07:30:00 UTC <div id="post"> <p> <em>What's an anti-pattern? Are there rules to identify them, or is it just name-calling? Before I use the term, I try to apply some rules of thumb.</em> </p> <p> It takes time to write a book. Months, even years. It took me two years to write the first edition of <a href="http://amzn.to/12p90MG">Dependency Injection in .NET</a>. The <a href="https://amzn.to/2TE8tJx">second edition of Dependency Injection in .NET</a> is also the result of much work; not so much by me, but by my co-author <a href="http://www.cuttingedge.it/blogs/steven">Steven van Deursen</a>. </p> <p> When you write a book single-handedly, you can be as opinionated as you'd like. When you have a co-author, regardless of how much you think alike, there's bound to be some disagreements. Steven and I agreed about most of the changes we'd like to make to the second edition, but each of us had to yield or compromise a few times. </p> <p> An interesting experience has been that on more than one occasion where I've reluctantly had to yield to Steven, over the time, I've come to appreciate his position. Two minds think better than one. </p> <h3 id="6497bdfd47db433c92a6ec4fabfd4e92"> Ambient Context <a href="#6497bdfd47db433c92a6ec4fabfd4e92" title="permalink">#</a> </h3> <p> One of the changes that Steven wanted to make was that he wanted to change the status of the <em>Ambient Context</em> pattern to an anti-pattern. While I never use that pattern myself, I included it in the first edition in the spirit of the original <a href="http://amzn.to/XBYukB">Design Patterns</a> book. The <em>Gang of Four</em> made it clear that the patterns they'd described weren't invented, but rather discovered: <blockquote> <p> "We have included only designs that have been applied more than once in different systems." </p> <footer><cite>Gamma et al, <em>Design Patterns</em>, 1994, p. 2</cite></footer> </blockquote> The spirit, as I understand it, is to identify solutions that already exist, and catalogue them. When I wrote the first edition of my book, I tried to do that as well. </p> <p> I'd noticed what I eventually named the <em>Ambient Context</em> pattern several places in the .NET Base Class Library. Some of those APIs are still around today. <a href="https://docs.microsoft.com/dotnet/api/system.threading.thread.currentprincipal">Thread.CurrentPrincipal</a>, <a href="https://docs.microsoft.com/dotnet/api/system.globalization.cultureinfo.currentculture">CultureInfo.CurrentCulture</a>, <a href="https://en.wikipedia.org/wiki/Thread-local_storage">thread-local storage</a>, <a href="https://docs.microsoft.com/dotnet/api/system.web.httpcontext.current">HttpContext.Current</a>, and so on. </p> <p> None of these really have anything to do with Dependency Injection (DI), but people sometimes attempt to use them to solve problems similar to the problems that DI addresses. For that reason, and because the pattern was so prevalent, I included it in the book - as a pattern, not an anti-pattern. </p> <p> Steven wanted to make it an anti-pattern, and I conceded. I wasn't sure I was ready to explicitly call it out as an anti-pattern, but I agreed to the change. I'm becoming increasingly happy that Steven talked me into it. </p> <h3 id="08fbf0fd59154a57bbba936128f6c60e"> Pareto efficiency <a href="#08fbf0fd59154a57bbba936128f6c60e" title="permalink">#</a> </h3> <p> I've heard said of me that I'm one of those people who call everything I don't like an anti-pattern. I don't think that's true. </p> <p> I think people's perception of me is skewed because even today, the most visited page (my greatest hit, if you will) is an article called <a href="http://blog.ploeh.dk/2010/02/03/ServiceLocatorisanAnti-Pattern">Service Locator is an Anti-Pattern</a>. (It concerns me a bit that an article from 2010 seems to be my crowning achievement. I hope I haven't peaked yet, but the numbers tell a different tale.) </p> <p> While I've used the term <em>anti-pattern</em> in other connections, I prefer to be conservative with my use of the word. I tend to use it only when I feel confident that something is, indeed, an anti-pattern. </p> <p> What's an anti-pattern? <a href="https://amzn.to/2VHDX3m">AntiPatterns</a> defines it like this: <blockquote> <p> "An AntiPattern is a literary form that describes a commonly occurring solution to a problem that generates decidedly negative consequences." </p> <footer><cite>Brown et al, <em>AntiPatterns</em>, 1998, p. 7</cite></footer> </blockquote> As definitions go, it's quite amphibolous. Is it the problem that generates negative consequences? Hardly. In the context, it's clear that it's the solution that causes problems. In any case, just because it's in a book doesn't necessarily make it right, but I find it a good start. </p> <p> I think that the phrase <em>decidedly negative consequences</em> is key. Most solutions come with <em>some</em> disadvantages, but in order for a 'solution' to be an anti-pattern, the disadvantages must clearly outweigh any advantages produced. </p> <p> I usually look at it another way. If I can solve the problem in a different way that generates at least as many advantages, but fewer disadvantages, then the first 'solution' might be an anti-pattern. This way of viewing the problem may stem from my background in economics. In that perspective, an anti-pattern simply isn't <a href="https://en.wikipedia.org/wiki/Pareto_efficiency">Pareto optimal</a>. </p> <h3 id="eb04af30ae5b40529fda1588525aee6d"> Falsifiability <a href="#eb04af30ae5b40529fda1588525aee6d" title="permalink">#</a> </h3> <p> Another rule of thumb I employ to determine whether a solution could be an anti-pattern is <a href="https://en.wikipedia.org/wiki/Karl_Popper">Popper</a>'s concept of <a href="https://en.wikipedia.org/wiki/Falsifiability">falsifiability</a>. As a continuation of the Pareto efficiency perspective, an anti-pattern is a 'solution' that you can improve without any (significant) trade-offs. </p> <p> That turns claims about anti-patterns into falsifiable statements, which I consider is the most intellectually honest way to go about claiming that things are bad. </p> <p> Take, for example, the claim that <em>Service Locator is an anti-pattern</em>. In light of Pareto efficiency, that's a falsifiable claim. All you have to do to prove me wrong is to present a situation where Service Locator solves a problem, and I can't come up with a better solution. </p> <p> I made the claim about Service Locator in 2010, and so far, no one has been able to present such a situation, even though several have tried. I'm fairly confident making that claim. </p> <p> This way of looking at the term anti-pattern, however, makes me wary of declaiming solutions anti-patterns just because I don't like them. Could there be a counter-argument, some niche scenario, where the pattern actually couldn't be improved without trade-offs? </p> <p> I didn't take it lightly when Steven suggested making Ambient Context an anti-pattern. </p> <h3 id="e027fe12038c4160a3be19bce065cd74"> Preliminary status <a href="#e027fe12038c4160a3be19bce065cd74" title="permalink">#</a> </h3> <p> I've had some time to think about Ambient Context since I had the (civil) discussion with Steven. The more I think about it, the more I think that he's right; that Ambient Context really <em>is</em> an anti-pattern. </p> <p> I never use that pattern myself, so it's clear to me that for all the situations that I typically encounter, there's always better solutions, with no significant trade-offs. </p> <p> The question is: could there be some niche scenario that I'm not aware of, where Ambient Context is a bona fide good solution? </p> <p> The more I think about this, the more I'm beginning to believe that there isn't. It remains to be seen, though. It remains to be falsified. </p> <h3 id="ed7478fa76324922a5543964e9c8c48e"> Summary <a href="#ed7478fa76324922a5543964e9c8c48e" title="permalink">#</a> </h3> <p> I'm so happy that Steven van Deursen agreed to co-author the second edition of <em>Dependency Injection in .NET</em> with me. The few areas where we've disagreed, I've ultimately come around to agree with him. He's truly taken a good book and made it better. </p> <p> One of the changes is that Ambient Context is now classified as an anti-pattern. Originally, I wasn't sure that this was the correct thing to do, but I've since changed my mind. I do think that Ambient Context belongs in the anti-patterns chapter. </p> <p> I could be wrong, though. I was before. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="4493b077ecd84d6d8217d4944e11471a"> <div class="comment-author"><a href="https://rebus.fm">Mogens Heller Grabe</a></div> <div class="comment-content"> <p> Thanks for great input for discussion :P </p> <p> Like with all other patterns and anti-patterns, I think there's a time and a place. </p> <p> Simply looking at it in a one-dimensional manner, i.e. asking "does there exist a solution to this problem with the same advantages but less downsides?" must be qualified with "IN THIS TIME AND PLACE", in my opinion. </p> <p> This way, the patterns/anti-patterns distinction does not make that much sense in a global perspective, because all patterns can be an anti-patterns in some situations, and vice versa. </p> <p> For example, I like what <em>Ambient Context</em> does in <a href="https://github.com/rebus-org/Rebus">Rebus</a>: It provides a mechanism that enables user code to transparently enlist its bus operations in a unit of work, without requiring user code to pass that unit of work to each operation. </p> <p> This is very handy, e.g. in OWIN-based applications, where the unit of work can be managed by an OWIN middleware that uses a <a href="https://github.com/rebus-org/Rebus/wiki/Transactions#i-am-not-in-a-transaction---i-want-to-either-publish-a-message-or-send-several-messages"><code>RebusTransactionScope</code></a>, this way enlisting all send/publish operations on the bus in that unit of work. </p> <p> Had it not been possible to automatically pick up an ongoing ambient Rebus transaction context, one would probably need to pollute the interfaces of one's application with an <code>ITransactionContext</code> argument, thus not handling the cross-cutting concern of managing the unit of work in a cross-cutting manner. </p> </div> <div class="comment-date">2019-01-21 12:37 UTC</div> </div> </div> <hr> This blog is totally free, but if you like it, please consider <a href="http://blog.ploeh.dk/support">supporting it</a>. Mark Seemann http://blog.ploeh.dk/2019/01/21/some-thoughts-on-anti-patterns An Either functor http://blog.ploeh.dk/2019/01/14/an-either-functor/ Mon, 14 Jan 2019 07:27:00 UTC <div id="post"> <p> <em>Either forms a normal functor. A placeholder 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>. As another article explains, <a href="http://blog.ploeh.dk/2019/01/07/either-bifunctor">Either is a bifunctor</a>. This makes it trivially a functor. As such, this article is mostly a place-holder to fit the spot in the <em>functor table of contents</em>, thereby indicating that Either is a functor. </p> <p> Since Either is a bifunctor, it's actually not one, but two, functors. Many languages, C# included, are best equipped to deal with unambiguous functors. This is also true in <a href="https://haskell.org">Haskell</a>, where <code>Either l r</code> is only a <code>Functor</code> over the right side. Likewise, in C#, you can make <code>IEither&lt;L, R&gt;</code> a functor by implementing <code>Select</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">R1</span>&gt;&nbsp;Select&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">R</span>,&nbsp;<span style="color:#2b91af;">R1</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">R</span>&gt;&nbsp;source, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">R</span>,&nbsp;<span style="color:#2b91af;">R1</span>&gt;&nbsp;selector) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;source.SelectRight(selector); }</pre> </p> <p> This method simply delegates all implementation to the <code>SelectRight</code> method; it's just <code>SelectRight</code> by another name. It obeys the functor laws, since these are just specializations of the bifunctor laws, and we know that Either is a proper bifunctor. </p> <p> It would have been technically possible to instead implement a <code>Select</code> method by calling <code>SelectLeft</code>, but it seems generally more useful to enable syntactic sugar for mapping over 'happy path' scenarios. This enables you to write projections over operations that can fail. </p> <p> Here's some <em>C# Interactive</em> examples that use the <code>FindWinner</code> helper method from <a href="http://blog.ploeh.dk/2018/06/11/church-encoded-either">the Church-encoded Either article</a>. Imagine that you're collecting votes; you're trying to pick the highest-voted integer, but in reality, you're only interested in seeing if the number is positive or not. Since <code>FindWinner</code> returns <code>IEither&lt;VoteError, T&gt;</code>, and this type is a functor, you can project the right result, while any left result short-circuits the query. First, here's a successful query: </p> <p> <pre>&gt; <span style="color:blue;">from</span>&nbsp;i&nbsp;<span style="color:blue;">in</span>&nbsp;FindWinner(1,&nbsp;2,&nbsp;-3,&nbsp;-1,&nbsp;2,&nbsp;-1,&nbsp;-1)&nbsp;<span style="color:blue;">select</span>&nbsp;i&nbsp;&gt;&nbsp;0 Right&lt;VoteError, bool&gt;(false)</pre> </p> <p> This query succeeds, resulting in a <code>Right</code> object. The contained value is <code>false</code> because the winner of the vote is <code>-1</code>, which isn't a positive number. </p> <p> On the other hand, the following query fails because of a tie. </p> <p> <pre>&gt; <span style="color:blue;">from</span>&nbsp;i&nbsp;<span style="color:blue;">in</span>&nbsp;FindWinner(1,&nbsp;2,&nbsp;-3,&nbsp;-1,&nbsp;2,&nbsp;-1)&nbsp;<span style="color:blue;">select</span>&nbsp;i&nbsp;&gt;&nbsp;0 Left&lt;VoteError, bool&gt;(Tie)</pre> </p> <p> Because the result is tied on <code>-1</code>, the return value is a <code>Left</code> object containing the <code>VoteError</code> value <code>Tie</code>. </p> <p> Another source of error is an empty input collection: </p> <p> <pre>&gt; <span style="color:blue;">from</span>&nbsp;i&nbsp;<span style="color:blue;">in</span>&nbsp;FindWinner&lt;<span style="color:blue;">int</span>&gt;()&nbsp;<span style="color:blue;">select</span>&nbsp;i&nbsp;&gt;&nbsp;0 Left&lt;VoteError, bool&gt;(Empty)</pre> </p> <p> This time, the <code>Left</code> object contains the <code>Empty</code> error value, since no winner can be found from an empty collection. </p> <p> While the <code>Select</code> method doesn't implement any behaviour that <code>SelectRight</code> doesn't already afford, it enables you to use C# query syntax, as demonstrated by the above examples. </p> <p> <strong>Next:</strong> <a href="http://blog.ploeh.dk/2018/08/06/a-tree-functor">A Tree functor</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="http://blog.ploeh.dk/support">supporting it</a>. Mark Seemann http://blog.ploeh.dk/2019/01/14/an-either-functor Either bifunctor http://blog.ploeh.dk/2019/01/07/either-bifunctor/ Mon, 07 Jan 2019 09:13:00 UTC <div id="post"> <p> <em>Either forms a bifunctor. An article for object-oriented programmers.</em> </p> <p> This article is an instalment in <a href="http://blog.ploeh.dk/2018/12/24/bifunctors">an article series about bifunctors</a>. As the overview article explains, essentially there's two practically useful bifunctors: pairs and <a href="http://blog.ploeh.dk/2018/06/11/church-encoded-either">Either</a>. In <a href="http://blog.ploeh.dk/2018/12/31/tuple-bifunctor">the previous article</a>, you saw how a pair (a two-tuple) forms a bifunctor. In this article, you'll see how Either also forms a bifunctor. </p> <h3 id="b30721a6a66a427eb1a7159d66290337"> Mapping both dimensions <a href="#b30721a6a66a427eb1a7159d66290337" title="permalink">#</a> </h3> <p> In the previous article, you saw how, if you have maps over both dimensions, you can trivially implement <code>SelectBoth</code> (what <a href="https://www.haskell.org">Haskell</a> calls <code>bimap</code>): </p> <p> <pre><span style="color:blue;">return</span>&nbsp;source.SelectFirst(selector1).SelectSecond(selector2);</pre> </p> <p> The relationship can, however, go both ways. If you implement <code>SelectBoth</code>, you can derive <code>SelectFirst</code> and <code>SelectSecond</code> from it. In this article, you'll see how to do that for Either. </p> <p> Given the <a href="http://blog.ploeh.dk/2018/06/11/church-encoded-either">Church-encoded Either</a>, the implementation of <code>SelectBoth</code> can be achieved in a single expression: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">L1</span>,&nbsp;<span style="color:#2b91af;">R1</span>&gt;&nbsp;SelectBoth&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">L1</span>,&nbsp;<span style="color:#2b91af;">R</span>,&nbsp;<span style="color:#2b91af;">R1</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">R</span>&gt;&nbsp;source, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;&nbsp;selectLeft, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">R</span>,&nbsp;<span style="color:#2b91af;">R1</span>&gt;&nbsp;selectRight) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;source.Match&lt;<span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">L1</span>,&nbsp;<span style="color:#2b91af;">R1</span>&gt;&gt;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;onLeft:&nbsp;&nbsp;l&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;&nbsp;<span style="color:#2b91af;">Left</span>&lt;<span style="color:#2b91af;">L1</span>,&nbsp;<span style="color:#2b91af;">R1</span>&gt;(&nbsp;selectLeft(l)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;onRight:&nbsp;r&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Right</span>&lt;<span style="color:#2b91af;">L1</span>,&nbsp;<span style="color:#2b91af;">R1</span>&gt;(selectRight(r))); }</pre> </p> <p> Given that the input <code>source</code> is an <code>IEither&lt;L, R&gt;</code> object, there's isn't much you can do. That interface only defines a single member, <code>Match</code>, so that's the only method you can call. When you do that, you have to supply the two arguments <code>onLeft</code> and <code>onRight</code>. </p> <p> The <code>Match</code> method is defined like this: </p> <p> <pre><span style="color:#2b91af;">T</span>&nbsp;Match&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;&nbsp;onLeft,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">R</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;&nbsp;onRight)</pre> </p> <p> Given the desired return type of <code>SelectBoth</code>, you know that <code>T</code> should be <code>IEither&lt;L1, R1&gt;</code>. This means, then, that for <code>onLeft</code>, you must supply a function of the type <code>Func&lt;L, IEither&lt;L1, R1&gt;&gt;</code>. Since a functor is a structure-preserving map, you should translate a <em>left</em> case to a <em>left</em> case, and a <em>right</em> case to a <em>right</em> case. This implies that the concrete return type that matches <code>IEither&lt;L1, R1&gt;</code> for the <code>onLeft</code> argument is <code>Left&lt;L1, R1&gt;</code>. </p> <p> When you write the function with the type <code>Func&lt;L, IEither&lt;L1, R1&gt;&gt;</code> as a lambda expression, the input argument <code>l</code> has the type <code>L</code>. In order to create a <code>new Left&lt;L1, R1&gt;</code>, however, you need an <code>L1</code> object. How do you produce an <code>L1</code> object from an <code>L</code> object? You call <code>selectLeft</code> with <code>l</code>, because <code>selectLeft</code> is a function of the type <code>Func&lt;L, L1&gt;</code>. </p> <p> You can apply the same line of reasoning to the <code>onRight</code> argument. Write a lambda expression that takes an <code>R</code> object <code>r</code> as input, call <code>selectRight</code> to turn that into an <code>R1</code> object, and return it wrapped in a <code>new Right&lt;L1, R1&gt;</code> object. </p> <p> This works as expected: </p> <p> <pre>&gt; <span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Left</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(<span style="color:#a31515;">&quot;foo&quot;</span>).SelectBoth(<span style="color:blue;">string</span>.IsNullOrWhiteSpace,&nbsp;i&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(i)) Left&lt;bool, DateTime&gt;(false) &gt; <span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Right</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(1337).SelectBoth(<span style="color:blue;">string</span>.IsNullOrWhiteSpace,&nbsp;i&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(i)) Right&lt;bool, DateTime&gt;([01.01.0001 00:00:00])</pre> </p> <p> Notice that both of the above statements evaluated in <em>C# Interactive</em> use the same projections as input to <code>SelectBoth</code>. Clearly, though, because the inputs are first a <code>Left</code> value, and secondly a <code>Right</code> value, the outputs differ. </p> <h3 id="10a641d7ad0b44158f74665fd87feb5e"> Mapping the left side <a href="#10a641d7ad0b44158f74665fd87feb5e" title="permalink">#</a> </h3> <p> When you have <code>SelectBoth</code>, you can trivially implement the translations for each dimension in isolation. In the previous article, I called these methods <code>SelectFirst</code> and <code>SelectSecond</code>. In this article, I've chosen to instead name them <code>SelectLeft</code> and <code>SelectRight</code>, but they still corresponds to Haskell's <code>first</code> and <code>second</code> <code>Bifunctor</code> functions. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">L1</span>,&nbsp;<span style="color:#2b91af;">R</span>&gt;&nbsp;SelectLeft&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">L1</span>,&nbsp;<span style="color:#2b91af;">R</span>&gt;(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">R</span>&gt;&nbsp;source,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;&nbsp;selector) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;source.SelectBoth(selector,&nbsp;r&nbsp;=&gt;&nbsp;r); }</pre> </p> <p> The method body is literally a one-liner. Just call <code>SelectBoth</code> with <code>selector</code> as the projection for the left side, and the identity function as the projection for the right side. This ensures that if the actual value is a <code>Right&lt;L, R&gt;</code> object, nothing's going to happen. Only if the input is a <code>Left&lt;L, R&gt;</code> object will the projection run: </p> <p> <pre>&gt; <span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Left</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(<span style="color:#a31515;">&quot;&quot;</span>).SelectLeft(<span style="color:blue;">string</span>.IsNullOrWhiteSpace) Left&lt;bool, int&gt;(true) &gt; <span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Left</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(<span style="color:#a31515;">&quot;bar&quot;</span>).SelectLeft(<span style="color:blue;">string</span>.IsNullOrWhiteSpace) Left&lt;bool, int&gt;(false) &gt; <span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Right</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(42).SelectLeft(<span style="color:blue;">string</span>.IsNullOrWhiteSpace) Right&lt;bool, int&gt;(42)</pre> </p> <p> In the above <em>C# Interactive</em> session, you can see how projecting three different objects using <code>string.IsNullOrWhiteSpace</code> works. When the <code>Left</code> object indeed does contain an empty string, the result is a <code>Left</code> value containing <code>true</code>. When the object contains <code>"bar"</code>, however, it contains <code>false</code>. Furthermore, when the object is a <code>Right</code> value, the mapping has no effect. </p> <h3 id="b9027a241d6444d5b869a8a1b92659c5"> Mapping the right side <a href="#b9027a241d6444d5b869a8a1b92659c5" title="permalink">#</a> </h3> <p> Similar to <code>SelectLeft</code>, you can also trivially implement <code>SelectRight</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">R1</span>&gt;&nbsp;SelectRight&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">R</span>,&nbsp;<span style="color:#2b91af;">R1</span>&gt;(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">R</span>&gt;&nbsp;source,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">R</span>,&nbsp;<span style="color:#2b91af;">R1</span>&gt;&nbsp;selector) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;source.SelectBoth(l&nbsp;=&gt;&nbsp;l,&nbsp;selector); }</pre> </p> <p> This is another one-liner calling <code>SelectBoth</code>, with the difference that the identity function <code>l =&gt; l</code> is passed as the first argument, instead of as the last. This ensures that only <code>Right</code> values are mapped: </p> <p> <pre>&gt; <span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Left</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(<span style="color:#a31515;">&quot;baz&quot;</span>).SelectRight(i&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(i)) Left&lt;string, DateTime&gt;("baz") &gt; <span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Right</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(1_234_567_890).SelectRight(i&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(i)) Right&lt;string, DateTime&gt;([01.01.0001 00:02:03])</pre> </p> <p> In the above examples, <code>Right</code> integers are projected into <code>DateTime</code> values, whereas <code>Left</code> strings stay strings. </p> <h3 id="a80a8d7ebbce46b4914749f46cd99e89"> Identity laws <a href="#a80a8d7ebbce46b4914749f46cd99e89" title="permalink">#</a> </h3> <p> Either obeys all the bifunctor laws. While it's formal work to prove that this is the case, you can get an intuition for it via examples. Often, I use a property-based testing library like <a href="https://fscheck.github.io/FsCheck">FsCheck</a> or <a href="https://github.com/hedgehogqa/fsharp-hedgehog">Hedgehog</a> to demonstrate (not prove) that laws hold, but in this article, I'll keep it simple and only cover each law with a parametrised test. </p> <p> <pre><span style="color:blue;">private</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">T</span>&nbsp;Id&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:#2b91af;">T</span>&nbsp;x)&nbsp;=&gt;&nbsp;x; <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:blue;">object</span>[]&gt;&nbsp;BifunctorLawsData { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">get</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">yield</span>&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;&nbsp;<span style="color:#2b91af;">Left</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(<span style="color:#a31515;">&quot;foo&quot;</span>)&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">yield</span>&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;&nbsp;<span style="color:#2b91af;">Left</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(<span style="color:#a31515;">&quot;bar&quot;</span>)&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">yield</span>&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;&nbsp;<span style="color:#2b91af;">Left</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(<span style="color:#a31515;">&quot;baz&quot;</span>)&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">yield</span>&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Right</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(&nbsp;&nbsp;&nbsp;42)&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">yield</span>&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Right</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(&nbsp;1337)&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">yield</span>&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Right</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(&nbsp;&nbsp;&nbsp;&nbsp;0)&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;} } [<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SelectLeftObeysFirstFunctorLaw(<span style="color:#2b91af;">IEither</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;e) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(e,&nbsp;e.SelectLeft(Id)); }</pre> </p> <p> This test uses <a href="https://xunit.github.io">xUnit.net</a>'s <code>[Theory]</code> feature to supply a small set of example input values. The input values are defined by the <code>BifunctorLawsData</code> property, since I'll reuse the same values for all the bifunctor law demonstration tests. </p> <p> The tests also use the identity function implemented as a <code>private</code> function called <code>Id</code>, since C# doesn't come equipped with such a function in the Base Class Library. </p> <p> For all the <code>IEither&lt;string, int&gt;</code> objects <code>e</code>, the test simply verifies that the original Either <code>e</code> is equal to the Either projected over the first axis with the <code>Id</code> function. </p> <p> Likewise, the first functor law applies when translating over the second dimension: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SelectRightObeysFirstFunctorLaw(<span style="color:#2b91af;">IEither</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;e) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(e,&nbsp;e.SelectRight(Id)); }</pre> </p> <p> This is the same test as the previous test, with the only exception that it calls <code>SelectRight</code> instead of <code>SelectLeft</code>. </p> <p> Both <code>SelectLeft</code> and <code>SelectRight</code> are implemented by <code>SelectBoth</code>, so the real test is whether this method obeys the identity law: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SelectBothObeysIdentityLaw(<span style="color:#2b91af;">IEither</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;e) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(e,&nbsp;e.SelectBoth(Id,&nbsp;Id)); }</pre> </p> <p> Projecting over both dimensions with the identity function does, indeed, return an object equal to the input object. </p> <h3 id="5ee147f408d64bc78171ade1f968b9aa"> Consistency law <a href="#5ee147f408d64bc78171ade1f968b9aa" title="permalink">#</a> </h3> <p> In general, it shouldn't matter whether you map with <code>SelectBoth</code> or a combination of <code>SelectLeft</code> and <code>SelectRight</code>: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;ConsistencyLawHolds(<span style="color:#2b91af;">IEither</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;e) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">bool</span>&nbsp;f(<span style="color:blue;">string</span>&nbsp;s)&nbsp;=&gt;&nbsp;<span style="color:blue;">string</span>.IsNullOrWhiteSpace(s); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">DateTime</span>&nbsp;g(<span style="color:blue;">int</span>&nbsp;i)&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(i); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(e.SelectBoth(f,&nbsp;g),&nbsp;e.SelectRight(g).SelectLeft(f)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e.SelectLeft(f).SelectRight(g), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e.SelectRight(g).SelectLeft(f)); }</pre> </p> <p> This example creates two local functions <code>f</code> and <code>g</code>. The first function, <code>f</code>, just delegates to <code>string.IsNullOrWhiteSpace</code>, although I want to stress that this is just an example. The law should hold for any two (<a href="https://en.wikipedia.org/wiki/Pure_function">pure</a>) functions. The second function, <code>g</code>, creates a new <code>DateTime</code> object from an integer, using one of the <code>DateTime</code> constructor overloads. </p> <p> The test then verifies that you get the same result from calling <code>SelectBoth</code> as when you call <code>SelectLeft</code> followed by <code>SelectRight</code>, or the other way around. </p> <h3 id="509bf515dac14e0e95346ee604ba26af"> Composition laws <a href="#509bf515dac14e0e95346ee604ba26af" title="permalink">#</a> </h3> <p> The composition laws insist that you can compose functions, or translations, and that again, the choice to do one or the other doesn't matter. Along each of the axes, it's just the second functor law applied. This parametrised test demonstrates that the law holds for <code>SelectLeft</code>: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SecondFunctorLawHoldsForSelectLeft(<span style="color:#2b91af;">IEither</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;e) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">bool</span>&nbsp;f(<span style="color:blue;">int</span>&nbsp;x)&nbsp;=&gt;&nbsp;x&nbsp;%&nbsp;2&nbsp;==&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;g(<span style="color:blue;">string</span>&nbsp;s)&nbsp;=&gt;&nbsp;s.Length; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(e.SelectLeft(x&nbsp;=&gt;&nbsp;f(g(x))),&nbsp;e.SelectLeft(g).SelectLeft(f)); }</pre> </p> <p> Here, <code>f</code> is the <em>even</em> function, whereas <code>g</code> is a local function that returns the length of a string. The second functor law states that mapping <code>f(g(x))</code> in a single step is equivalent to first mapping over <code>g</code> and then map the result of that using <code>f</code>. </p> <p> The same law applies if you fix the first dimension and translate over the second: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SecondFunctorLawHoldsForSelectRight(<span style="color:#2b91af;">IEither</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;e) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">char</span>&nbsp;f(<span style="color:blue;">bool</span>&nbsp;b)&nbsp;=&gt;&nbsp;b&nbsp;?&nbsp;<span style="color:#a31515;">&#39;T&#39;</span>&nbsp;:&nbsp;<span style="color:#a31515;">&#39;F&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">bool</span>&nbsp;g(<span style="color:blue;">int</span>&nbsp;i)&nbsp;=&gt;&nbsp;i&nbsp;%&nbsp;2&nbsp;==&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(e.SelectRight(x&nbsp;=&gt;&nbsp;f(g(x))),&nbsp;e.SelectRight(g).SelectRight(f)); }</pre> </p> <p> Here, <code>f</code> is a local function that returns <code>'T'</code> for <code>true</code> and <code>'F'</code> for <code>false</code>, and <code>g</code> is a local function that, as you've seen before, determines whether a number is even. Again, the test demonstrates that the output is the same whether you map over an intermediary step, or whether you map using only a single step. </p> <p> This generalises to the composition law for <code>SelectBoth</code>: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SelectBothCompositionLawHolds(<span style="color:#2b91af;">IEither</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;e) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">bool</span>&nbsp;f(<span style="color:blue;">int</span>&nbsp;x)&nbsp;=&gt;&nbsp;x&nbsp;%&nbsp;2&nbsp;==&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;g(<span style="color:blue;">string</span>&nbsp;s)&nbsp;=&gt;&nbsp;s.Length; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">char</span>&nbsp;h(<span style="color:blue;">bool</span>&nbsp;b)&nbsp;=&gt;&nbsp;b&nbsp;?&nbsp;<span style="color:#a31515;">&#39;T&#39;</span>&nbsp;:&nbsp;<span style="color:#a31515;">&#39;F&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">bool</span>&nbsp;i(<span style="color:blue;">int</span>&nbsp;x)&nbsp;=&gt;&nbsp;x&nbsp;%&nbsp;2&nbsp;==&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e.SelectBoth(x&nbsp;=&gt;&nbsp;f(g(x)),&nbsp;y&nbsp;=&gt;&nbsp;h(i(y))), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e.SelectBoth(g,&nbsp;i).SelectBoth(f,&nbsp;h)); }</pre> </p> <p> Again, whether you translate in one or two steps shouldn't affect the outcome. </p> <p> As all of these tests demonstrate, the bifunctor laws hold for Either. The tests only showcase six examples for either a string or an integer, but I hope it gives you an intuition how any Either object is a bifunctor. After all, the <code>SelectLeft</code>, <code>SelectRight</code>, and <code>SelectBoth</code> methods are all generic, and they behave the same for all generic type arguments. </p> <h3 id="7b8babee4af64eeaa93fe4562ed721bd"> Summary <a href="#7b8babee4af64eeaa93fe4562ed721bd" title="permalink">#</a> </h3> <p> Either objects are bifunctors. You can translate the first and second dimension of an Either object independently of each other, and the bifunctor laws hold for any pure translation, no matter how you compose the projections. </p> <p> As always, there can be performance differences between the various compositions, but the outputs will be the same regardless of composition. </p> <p> A functor, and by extension, a bifunctor, is a structure-preserving map. This means that any projection preserves the structure of the underlying container. For Either objects, it means that <em>left</em> objects remain <em>left</em> objects, and <em>right</em> objects remain <em>right</em> objects, even if the contained values change. Either is characterised by containing exactly one value, but it can be either a <em>left</em> value or a <em>right</em> value. No matter how you translate it, it still contains only a single value - <em>left</em> or <em>right</em>. </p> <p> The other common bifunctor, <em>pair</em>, is complementary. Not only does it also have two dimensions, but a pair always contains both values at once. </p> <p> <strong>Next:</strong> <a href="http://blog.ploeh.dk/2018/01/08/software-design-isomorphisms">Software design isomorphisms</a> </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="http://blog.ploeh.dk/support">supporting it</a>. Mark Seemann http://blog.ploeh.dk/2019/01/07/either-bifunctor Tuple bifunctor http://blog.ploeh.dk/2018/12/31/tuple-bifunctor/ Mon, 31 Dec 2018 12:13:00 UTC <div id="post"> <p> <em>A Pair (a two-tuple) forms a bifunctor. An article for object-oriented programmers.</em> </p> <p> This article is an instalment in <a href="http://blog.ploeh.dk/2018/12/24/bifunctors">an article series about bifunctors</a>. In the previous overview, you learned about the general concept of a bifunctor. In practice, there's two useful bifunctor instances: pairs (two-tuples) and <a href="http://blog.ploeh.dk/2018/06/11/church-encoded-either">Either</a>. In this article, you'll see how a pair is a bifunctor, and in the next article, you'll see how Either fits the same abstraction. </p> <h3 id="d918d0271c33406ba3047ef162212100"> Tuple as a functor <a href="#d918d0271c33406ba3047ef162212100" title="permalink">#</a> </h3> <p> You can treat a normal pair (two-tuple) as a <a href="http://blog.ploeh.dk/2018/03/22/functors">functor</a> by mapping one of the elements, while keeping the other generic type fixed. In <a href="https://www.haskell.org">Haskell</a>, when you have types with multiple type arguments, you often 'fix' the types from the left, leaving the right-most type free to vary. Doing this for a pair, which in C# has the type <code>Tuple&lt;T, U&gt;</code>, this means that tuples are functors if we keep <code>T</code> fixed and enable translation of the second element from <code>U1</code> to <code>U2</code>. </p> <p> This is easy to implement with a standard <code>Select</code> extension method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Tuple</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">U2</span>&gt;&nbsp;Select&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">U1</span>,&nbsp;<span style="color:#2b91af;">U2</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Tuple</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">U1</span>&gt;&nbsp;source, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">U1</span>,&nbsp;<span style="color:#2b91af;">U2</span>&gt;&nbsp;selector) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:#2b91af;">Tuple</span>.Create(source.Item1,&nbsp;selector(source.Item2)); }</pre> </p> <p> You simply return a new tuple by carrying <code>source.Item1</code> over without modification, while on the other hand calling <code>selector</code> with <code>source.Item2</code>. Here's a simple example, which also highlights that C# understands functors: </p> <p> <pre><span style="color:blue;">var</span>&nbsp;t&nbsp;=&nbsp;<span style="color:#2b91af;">Tuple</span>.Create(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;42); <span style="color:blue;">var</span>&nbsp;actual&nbsp;=&nbsp;<span style="color:blue;">from</span>&nbsp;i&nbsp;<span style="color:blue;">in</span>&nbsp;t &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">select</span>&nbsp;i&nbsp;%&nbsp;2&nbsp;==&nbsp;0;</pre> </p> <p> Here, <code>actual</code> is a <code>Tuple&lt;string, bool&gt;</code> with the values <code>"foo"</code> and <code>true</code>. Inside the query expression, <code>i</code> is an <code>int</code>, and the <code>select</code> expression returns a <code>bool</code> value indicating whether the number is even or odd. Notice that the <code>string</code> in the first element disappears inside the query expression. It's still there, but the code inside the query expression can't see <code>"foo"</code>. </p> <h3 id="589f054d8dab47a4bb308951ee76f96b"> Mapping the first element <a href="#589f054d8dab47a4bb308951ee76f96b" title="permalink">#</a> </h3> <p> There's no technical reason why the mapping has to be over the second element; it's just how Haskell does it by convention. There are other, more philosophical reasons for that convention, but in the end, they boil down to the ultimately arbitrary cultural choice of reading from left to right (in Western scripts). </p> <p> You can translate the first element of a tuple as easily: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Tuple</span>&lt;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">U</span>&gt;&nbsp;SelectFirst&lt;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">U</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Tuple</span>&lt;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">U</span>&gt;&nbsp;source, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">T2</span>&gt;&nbsp;selector) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:#2b91af;">Tuple</span>.Create(selector(source.Item1),&nbsp;source.Item2); }</pre> </p> <p> While, technically, you <em>can</em> call this method <code>Select</code>, this can confuse the C# compiler's overload resolution system - at least if you have a tuple of two identical types (e.g. <code>Tuple&lt;int, int&gt;</code> or <code>Tuple&lt;string, string&gt;</code>). In order to avoid that sort of confusion, I decided to give the method another name, and in keeping with how C# LINQ methods tend to get names, I thought <code>SelectFirst</code> sounded reasonable. </p> <p> In Haskell, this function is called <code>first</code>, and is part of the <code>Bifunctor</code> type class: </p> <p> <pre>Prelude Data.Bifunctor&gt; first (even . length) ("foo", 42) (False,42)</pre> </p> <p> In C#, you can perform the same translation using the above <code>SelectFirst</code> extension method: </p> <p> <pre><span style="color:blue;">var</span>&nbsp;t&nbsp;=&nbsp;<span style="color:#2b91af;">Tuple</span>.Create(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;42); <span style="color:blue;">var</span>&nbsp;actual&nbsp;=&nbsp;t.SelectFirst(s&nbsp;=&gt;&nbsp;s.Length&nbsp;%&nbsp;2&nbsp;==&nbsp;0);</pre> </p> <p> This also returns a <code>Tuple&lt;bool, int&gt;</code> containing the values <code>false</code> and <code>42</code>. Notice that in this case, the first element <code>"foo"</code> is translated into <code>false</code> (because its length is odd), while the second element <code>42</code> carries over unchanged. </p> <h3 id="7da2d817bebb40cbb2221212158324f8"> Mapping the second element <a href="#7da2d817bebb40cbb2221212158324f8" title="permalink">#</a> </h3> <p> You've already seen how the above <code>Select</code> method maps over the second element of a pair. This means that you can already map over both dimensions of the bifunctor, but perhaps, for consistency's sake, you'd also like to add an explicit <code>SelectSecond</code> method. This is now trivial to implement, since it can delegate its work to <code>Select</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Tuple</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">U2</span>&gt;&nbsp;SelectSecond&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">U1</span>,&nbsp;<span style="color:#2b91af;">U2</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Tuple</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">U1</span>&gt;&nbsp;source, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">U1</span>,&nbsp;<span style="color:#2b91af;">U2</span>&gt;&nbsp;selector) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;source.Select(selector); }</pre> </p> <p> There's no separate implementation; the only thing this method does is to delegate work to the <code>Select</code> method. It's literally the <code>Select</code> method, just with another name. </p> <p> Clearly, you could also have done it the other way around: implement <code>SelectSecond</code> and then call it from <code>Select</code>. </p> <p> The <code>SelectSecond</code> method works as you'd expect: </p> <p> <pre><span style="color:blue;">var</span>&nbsp;t&nbsp;=&nbsp;<span style="color:#2b91af;">Tuple</span>.Create(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;1337); <span style="color:blue;">var</span>&nbsp;actual&nbsp;=&nbsp;t.SelectSecond(i&nbsp;=&gt;&nbsp;i&nbsp;%&nbsp;2&nbsp;==&nbsp;0);</pre> </p> <p> Again, <code>actual</code> is a tuple containing the values <code>"foo"</code> and <code>false</code>, because <code>1337</code> isn't even. </p> <p> This fits with the Haskell implementation, where <code>SelectSecond</code> is called <code>second</code>: </p> <p> <pre>Prelude Data.Bifunctor&gt; second even ("foo", 1337) ("foo",False)</pre> </p> <p> The result is still a pair where the first element is <code>"foo"</code> and the second element <code>False</code>, exactly like in the C# example. </p> <h3 id="17ce6b48946b4877924ddc5e3f841283"> Mapping both elements <a href="#17ce6b48946b4877924ddc5e3f841283" title="permalink">#</a> </h3> <p> With <code>SelectFirst</code> and <code>SelectSecond</code>, you can trivially implement <code>SelectBoth</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Tuple</span>&lt;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">U2</span>&gt;&nbsp;SelectBoth&lt;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">U1</span>,&nbsp;<span style="color:#2b91af;">U2</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Tuple</span>&lt;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">U1</span>&gt;&nbsp;source, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">T2</span>&gt;&nbsp;selector1, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">U1</span>,&nbsp;<span style="color:#2b91af;">U2</span>&gt;&nbsp;selector2) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;source.SelectFirst(selector1).SelectSecond(selector2); }</pre> </p> <p> This method takes two translations, <code>selector1</code> and <code>selector2</code>, and first uses <code>SelectFirst</code> to project along the first axis, and then <code>SelectSecond</code> to map the second dimension. </p> <p> This implementation creates an intermediary pair that callers never see, so this could theoretically be inefficient. In this article, however, I want to show you that it's possible to implement <code>SelectBoth</code> based on <code>SelectFirst</code> and <code>SelectSecond</code>. In the next article, you'll see how to do it the other way around. </p> <p> Using <code>SelectBoth</code> is easy: </p> <p> <pre><span style="color:blue;">var</span>&nbsp;t&nbsp;=&nbsp;<span style="color:#2b91af;">Tuple</span>.Create(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;42); <span style="color:blue;">var</span>&nbsp;actual&nbsp;=&nbsp;t.SelectBoth(s&nbsp;=&gt;&nbsp;s.First(),&nbsp;i&nbsp;=&gt;&nbsp;i&nbsp;%&nbsp;2&nbsp;==&nbsp;0);</pre> </p> <p> This translation returns a pair where the first element is <code>'f'</code> and the second element is <code>true</code>. This is because the first lambda expression <code>s =&gt; s.First()</code> returns the first element of the input string <code>"foo"</code>, whereas the second lambda expression <code>i =&gt; i % 2 == 0</code> determines that <code>42</code> is even. </p> <p> In Haskell, <code>SelectBoth</code> is called <code>bimap</code>: </p> <p> <pre>Prelude Data.Bifunctor&gt; bimap head even ("foo", 42) ('f',True)</pre> </p> <p> The return value is consistent with the C# example, since the input is also equivalent. </p> <h3 id="93cde34382844098885a14a06aa03948"> Identity laws <a href="#93cde34382844098885a14a06aa03948" title="permalink">#</a> </h3> <p> Pairs obey all the bifunctor laws. While it's formal work to prove that this is the case, you can get an intuition for it via examples. Often, I use a property-based testing library like <a href="https://fscheck.github.io/FsCheck">FsCheck</a> or <a href="https://github.com/hedgehogqa/fsharp-hedgehog">Hedgehog</a> to demonstrate (not prove) that laws hold, but in this article, I'll keep it simple and only cover each law with a parametrised test. </p> <p> <pre><span style="color:blue;">private</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">T</span>&nbsp;Id&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:#2b91af;">T</span>&nbsp;x)&nbsp;=&gt;&nbsp;x; [<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;42)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;bar&quot;</span>,&nbsp;1337)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foobar&quot;</span>,&nbsp;0)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;ploeh&quot;</span>,&nbsp;7)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;fnaah&quot;</span>,&nbsp;-6)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SelectFirstObeysFirstFunctorLaw(<span style="color:blue;">string</span>&nbsp;first,&nbsp;<span style="color:blue;">int</span>&nbsp;second) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;t&nbsp;=&nbsp;<span style="color:#2b91af;">Tuple</span>.Create(first,&nbsp;second); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(t,&nbsp;t.SelectFirst(Id)); }</pre> </p> <p> This test uses <a href="https://xunit.github.io">xUnit.net</a>'s <code>[Theory]</code> feature to supply a small set of example input values. It defines the identity function as a <code>private</code> function called <code>Id</code>, since C# doesn't come equipped with such a function in the Base Class Library. </p> <p> The test simply creates a tuple with the input values and verifies that the original tuple <code>t</code> is equal to the tuple projected over the first axis with the <code>Id</code> function. </p> <p> Likewise, the first functor law applies when translating over the second dimension: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;42)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;bar&quot;</span>,&nbsp;1337)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foobar&quot;</span>,&nbsp;0)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;ploeh&quot;</span>,&nbsp;7)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;fnaah&quot;</span>,&nbsp;-6)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SelectSecondObeysFirstFunctorLaw(<span style="color:blue;">string</span>&nbsp;first,&nbsp;<span style="color:blue;">int</span>&nbsp;second) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;t&nbsp;=&nbsp;<span style="color:#2b91af;">Tuple</span>.Create(first,&nbsp;second); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(t,&nbsp;t.SelectSecond(Id)); }</pre> </p> <p> This is the same test as the previous test, with the only exception that it calls <code>SelectSecond</code> instead of <code>SelectFirst</code>. </p> <p> Since <code>SelectBoth</code> in this example is implemented by composing <code>SelectFirst</code> and <code>SelectSecond</code>, you should expect it to obey the general identity law for bifunctors. It does, but it's always nice to see it with your own eyes: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;42)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;bar&quot;</span>,&nbsp;1337)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foobar&quot;</span>,&nbsp;0)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;ploeh&quot;</span>,&nbsp;7)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;fnaah&quot;</span>,&nbsp;-6)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SelectBothObeysIdentityLaw(<span style="color:blue;">string</span>&nbsp;first,&nbsp;<span style="color:blue;">int</span>&nbsp;second) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;t&nbsp;=&nbsp;<span style="color:#2b91af;">Tuple</span>.Create(first,&nbsp;second); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(t,&nbsp;t.SelectBoth(Id,&nbsp;Id)); }</pre> </p> <p> Here you can see that projecting over both dimensions with the identity function returns the original tuple. </p> <h3 id="6bd839540b9646db9acfe25b0227b241"> Consistency law <a href="#6bd839540b9646db9acfe25b0227b241" title="permalink">#</a> </h3> <p> In general, it shouldn't matter whether you map with <code>SelectBoth</code> or a combination of <code>SelectFirst</code> and <code>SelectSecond</code>: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;42)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;bar&quot;</span>,&nbsp;1337)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foobar&quot;</span>,&nbsp;0)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;ploeh&quot;</span>,&nbsp;7)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;ConsistencyLawHolds(<span style="color:blue;">string</span>&nbsp;first,&nbsp;<span style="color:blue;">int</span>&nbsp;second) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">bool</span>&gt;&nbsp;f&nbsp;=&nbsp;<span style="color:blue;">string</span>.IsNullOrWhiteSpace; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:#2b91af;">DateTime</span>&gt;&nbsp;g&nbsp;=&nbsp;i&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(i); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;t&nbsp;=&nbsp;<span style="color:#2b91af;">Tuple</span>.Create(first,&nbsp;second); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectBoth(f,&nbsp;g),&nbsp;t.SelectSecond(g).SelectFirst(f)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectFirst(f).SelectSecond(g), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectSecond(g).SelectFirst(f)); }</pre> </p> <p> This example creates two functions <code>f</code> and <code>g</code>. The first function, <code>f</code>, is just an alias for <code>string.IsNullOrWhiteSpace</code>, although I want to stress that it's just an example. The law should hold for any two (<a href="https://en.wikipedia.org/wiki/Pure_function">pure</a>) functions. The second function, <code>g</code>, creates a new <code>DateTime</code> object from an integer, using one of the <code>DateTime</code> constructor overloads. </p> <p> The test then verifies that you get the same result from calling <code>SelectBoth</code> as when you call <code>SelectFirst</code> followed by <code>SelectSecond</code>, or the other way around. </p> <h3 id="866a68ce5f3e4513882409498e743bb3"> Composition laws <a href="#866a68ce5f3e4513882409498e743bb3" title="permalink">#</a> </h3> <p> The composition laws insist that you can compose functions, or translations, and that again, the choice to do one or the other doesn't matter. Along each of the axes, it's just the second functor law applied. You've already seen that <code>SelectSecond</code> is nothing but an alias for <code>Select</code>, so surely, the second functor law must hold for <code>SelectSecond</code> as well. This parametrised test demonstrates that it does: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;42)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;bar&quot;</span>,&nbsp;1337)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foobar&quot;</span>,&nbsp;0)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;ploeh&quot;</span>,&nbsp;7)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;fnaah&quot;</span>,&nbsp;-6)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SecondFunctorLawHoldsForSelectSecond(<span style="color:blue;">string</span>&nbsp;first,&nbsp;<span style="color:blue;">int</span>&nbsp;second) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">bool</span>,&nbsp;<span style="color:blue;">char</span>&gt;&nbsp;f&nbsp;=&nbsp;b&nbsp;=&gt;&nbsp;b&nbsp;?&nbsp;<span style="color:#a31515;">&#39;T&#39;</span>&nbsp;:&nbsp;<span style="color:#a31515;">&#39;F&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">bool</span>&gt;&nbsp;g&nbsp;=&nbsp;i&nbsp;=&gt;&nbsp;i&nbsp;%&nbsp;2&nbsp;==&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;t&nbsp;=&nbsp;<span style="color:#2b91af;">Tuple</span>.Create(first,&nbsp;second); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectSecond(x&nbsp;=&gt;&nbsp;f(g(x))), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectSecond(g).SelectSecond(f)); }</pre> </p> <p> Here, <code>f</code> is a function that returns <code>'T'</code> for <code>true</code> and <code>'F'</code> for <code>false</code>, and <code>g</code> is a function that, as you've seen before, determines whether a number is even. The second functor law states that mapping <code>f(g(x))</code> in a single step is equivalent to first mapping over <code>g</code> and then map the result of that using <code>f</code>. </p> <p> The same law applies if you fix the second dimension and translate over the first: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;42)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;bar&quot;</span>,&nbsp;1337)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foobar&quot;</span>,&nbsp;0)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;ploeh&quot;</span>,&nbsp;7)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;fnaah&quot;</span>,&nbsp;-6)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SecondFunctorLawHoldsForSelectFirst(<span style="color:blue;">string</span>&nbsp;first,&nbsp;<span style="color:blue;">int</span>&nbsp;second) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">bool</span>&gt;&nbsp;f&nbsp;=&nbsp;x&nbsp;=&gt;&nbsp;x&nbsp;%&nbsp;2&nbsp;==&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;g&nbsp;=&nbsp;s&nbsp;=&gt;&nbsp;s.Length; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;t&nbsp;=&nbsp;<span style="color:#2b91af;">Tuple</span>.Create(first,&nbsp;second); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectFirst(x&nbsp;=&gt;&nbsp;f(g(x))), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectFirst(g).SelectFirst(f)); }</pre> </p> <p> Here, <code>f</code> is the <em>even</em> function, whereas <code>g</code> is a function that returns the length of a string. Again, the test demonstrates that the output is the same whether you map over an intermediary step, or whether you map using only a single step. </p> <p> This generalises to the composition law for <code>SelectBoth</code>: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;42)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;bar&quot;</span>,&nbsp;1337)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;foobar&quot;</span>,&nbsp;0)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;ploeh&quot;</span>,&nbsp;7)] [<span style="color:#2b91af;">InlineData</span>(<span style="color:#a31515;">&quot;fnaah&quot;</span>,&nbsp;-6)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SelectBothCompositionLawHolds(<span style="color:blue;">string</span>&nbsp;first,&nbsp;<span style="color:blue;">int</span>&nbsp;second) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">bool</span>&gt;&nbsp;f&nbsp;=&nbsp;x&nbsp;=&gt;&nbsp;x&nbsp;%&nbsp;2&nbsp;==&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;g&nbsp;=&nbsp;s&nbsp;=&gt;&nbsp;s.Length; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">bool</span>,&nbsp;<span style="color:blue;">char</span>&gt;&nbsp;h&nbsp;=&nbsp;b&nbsp;=&gt;&nbsp;b&nbsp;?&nbsp;<span style="color:#a31515;">&#39;T&#39;</span>&nbsp;:&nbsp;<span style="color:#a31515;">&#39;F&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">bool</span>&gt;&nbsp;i&nbsp;=&nbsp;x&nbsp;=&gt;&nbsp;x&nbsp;%&nbsp;2&nbsp;==&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;t&nbsp;=&nbsp;<span style="color:#2b91af;">Tuple</span>.Create(first,&nbsp;second); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectBoth(x&nbsp;=&gt;&nbsp;f(g(x)),&nbsp;y&nbsp;=&gt;&nbsp;h(i(y))), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectBoth(g,&nbsp;i).SelectBoth(f,&nbsp;h)); }</pre> </p> <p> Again, whether you translate in one or two steps shouldn't affect the outcome. </p> <p> As all of these tests demonstrate, the bifunctor laws hold for pairs. The tests only showcase 4-5 examples for a pair of string and integer, but I hope it gives you an intuition how any pair is a bifunctor. After all, the <code>SelectFirst</code>, <code>SelectSecond</code>, and <code>SelectBoth</code> methods are all generic, and they behave the same for all generic type arguments. </p> <h3 id="dfd4aa6edc66462c9d02d46ce44b1bda"> Summary <a href="#dfd4aa6edc66462c9d02d46ce44b1bda" title="permalink">#</a> </h3> <p> Pairs (two-tuples) are bifunctors. You can translate the first and second element of a pair independently of each other, and the bifunctor laws hold for any pure translation, no matter how you compose the projections. </p> <p> As always, there can be performance differences between the various compositions, but the outputs will be the same regardless of composition. </p> <p> A functor, and by extension, a bifunctor, is a structure-preserving map. This means that any projection preserves the structure of the underlying container. In practice that means that for pairs, no matter how you translate a pair, it remains a pair. A pair is characterised by containing two values at once, and no matter how you translate it, it'll still contain two values. </p> <p> The other common bifunctor, Either, is complementary. While it has two dimensions, it only contains one value, which is of either the one type or the other. It's still a bifunctor, though, because mappings preserve the structure of Either, too. </p> <p> <strong>Next:</strong> <a href="http://blog.ploeh.dk/2019/01/07/either-bifunctor">Either bifunctor</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="http://blog.ploeh.dk/support">supporting it</a>. Mark Seemann http://blog.ploeh.dk/2018/12/31/tuple-bifunctor Bifunctors http://blog.ploeh.dk/2018/12/24/bifunctors/ Mon, 24 Dec 2018 14:40:00 UTC <div id="post"> <p> <em>Bifunctors are like functors, only they vary in two dimensions instead of one. An article for object-oriented programmers.</em> </p> <p> This article is a continuation of <a href="http://blog.ploeh.dk/2018/03/22/functors">the article series about functors</a> and about <a href="http://blog.ploeh.dk/2018/10/01/applicative-functors">applicative functors</a>. In this article, you'll learn about a generalisation called a <em>bifunctor</em>. The prefix <em>bi</em> typically indicates that there's <em>two</em> of something, and that's also the case here. </p> <p> As you've already seen in the functor articles, a functor is a mappable <a href="https://bartoszmilewski.com/2014/01/14/functors-are-containers">container</a> of generic values, like <code>Foo&lt;T&gt;</code>, where the type of the contained value(s) can be any generic type <code>T</code>. A bifunctor is just a container with two independent generic types, like <code>Bar&lt;T, U&gt;</code>. If you can map each of the types independently of the other, you may have a bifunctor. </p> <p> The two most common bifunctors are tuples and Either. </p> <h3 id="c8062c28a0ed471a8995bee180d14aa6"> Maps <a href="#c8062c28a0ed471a8995bee180d14aa6" title="permalink">#</a> </h3> <p> A normal functor is based on a structure-preserving map of the contents within a container. You can, for example, translate an <code>IEnumerable&lt;int&gt;</code> to an <code>IEnumerable&lt;string&gt;</code>, or a <code>Maybe&lt;DateTime&gt;</code> to a <code>Maybe&lt;bool&gt;</code>. The axis of variability is the generic type argument <code>T</code>. You can translate <code>T1</code> to <code>T2</code> inside a container, but the type of the container remains the same: you can translate <code>Tree&lt;T1&gt;</code> to <code>Tree&lt;T2&gt;</code>, but it remains a <code>Tree&lt;&gt;</code>. </p> <p> <img src="/content/binary/monofunctors.png" alt="Three translations: IEnumerable, Maybe, and Tree."> </p> <p> A bifunctor involves a pair of maps, one for each generic type. You can map a <code>Bar&lt;string, int&gt;</code> to a <code>Bar&lt;bool, int&gt;</code>, or to a <code>Bar&lt;string, DateTime&gt;</code>, or even to a <code>Bar&lt;bool, DateTime&gt;</code>. Notice that the last example, mapping from <code>Bar&lt;string, int&gt;</code> to <code>Bar&lt;bool, DateTime&gt;</code> could be viewed as translating both axes simultaneously. </p> <p> <img src="/content/binary/bifunctor.png" alt="Bifunctor diagram."> </p> <p> In <a href="https://www.haskell.org">Haskell</a>, the two maps are called <code>first</code> and <code>second</code>, while the 'simultaneous' map is called <code>bimap</code>. </p> <p> The <code>first</code> translation translates the first, or left-most, value in the container. You can use it to map <code>Bar&lt;string, int&gt;</code> to a <code>Bar&lt;bool, int&gt;</code>. In C#, we could decide to call the method <code>SelectFirst</code>, or <code>SelectLeft</code>, in order to align with the C# naming convention of calling the functor morphism <code>Select</code>. </p> <p> Likewise, the <code>second</code> map translates the second, or right-most, value in the container. This is where you map <code>Bar&lt;string, int&gt;</code> to <code>Bar&lt;string, DateTime&gt;</code>. In C#, we could call the method <code>SelectSecond</code>, or <code>SelectRight</code>. </p> <p> The <code>bimap</code> function maps both values in the container in one go. This corresponds to a translation from <code>Bar&lt;string, int&gt;</code> to <code>Bar&lt;bool, DateTime&gt;</code>. In C#, we could call the method <code>SelectBoth</code>. There's no established naming conventions for bifunctors in C# that I know of, so these names are just some that I made up. </p> <p> You'll see examples of how to implement and use such functions in the next articles: <ul> <li><a href="http://blog.ploeh.dk/2018/12/31/tuple-bifunctor">Tuple bifunctor</a></li> <li><a href="http://blog.ploeh.dk/2019/01/07/either-bifunctor">Either bifunctor</a></li> </ul> Other bifunctors exist, but those two are the most common. </p> <h3 id="838097e59afd4555b989594b62082f39"> Identity laws <a href="#838097e59afd4555b989594b62082f39" title="permalink">#</a> </h3> <p> As is the case with functors, laws govern bifunctors. Some of the functor laws carry over, but are simply repeated over both axes, while other laws are generalisations of the functor laws. For example, the first functor law states that if you translate a container with the identity function, the result is the original input. This generalises to bifunctors as well: </p> <p> <pre>bimap id id ≡ id</pre> </p> <p> This just states that if you translate both axes using the <a href="http://blog.ploeh.dk/2017/11/13/endomorphism-monoid">endomorphic</a> Identity, it's equivalent to applying the Identity. </p> <p> <img src="/content/binary/bimap-id-id-bifunctor-law.png" alt="The bifunctor law for applying id to both axes simultaneously."> </p> <p> Using C# syntax, you could express the law like this: </p> <p> <pre>bf.SelectBoth(id,&nbsp;id)&nbsp;==&nbsp;bf;</pre> </p> <p> Here, <code>bf</code> is some bifunctor, and <code>id</code> is the identity function. The point is that if you translate over both axes, but actually don't perform a real translation, nothing happens. </p> <p> Likewise, if you consider a bifunctor a functor over two dimensions, the first functor law should hold for both: </p> <p> <pre>first id ≡ id second id ≡ id</pre> </p> <p> Both of those equalities only restate the first functor law for each dimension. If you map an axis with the identity function, nothing happens: </p> <p> <img src="/content/binary/first-id-second-id-bifunctor-laws.png" alt="The first functor law applied to both dimensions of a bifunctor."> </p> <p> In C#, you can express both laws like this: </p> <p> <pre>bf.SelectFirst(id)&nbsp;==&nbsp;bf; bf.SelectSecond(id)&nbsp;==&nbsp;bf;</pre> </p> <p> When calling <code>SelectFirst</code>, you translate only the first axis while you keep the second axis constant. When calling <code>SelectSecond</code> it's the other way around: you translate only the second axis while keeping the first axis constant. In both cases, though, if you use the identity function for the translation, you effectively keep the mapped dimension constant as well. Therefore, one would expect the result to be the same as the input. </p> <h3 id="57cfa8fd78084e8ca19d073d856a8c8a"> Consistency law <a href="#57cfa8fd78084e8ca19d073d856a8c8a" title="permalink">#</a> </h3> <p> As you'll see in the articles on tuple and Either bifunctors, you can derive <code>bimap</code> or <code>SelectBoth</code> from <code>first</code>/<code>SelectFirst</code> and <code>second</code>/<code>SelectSecond</code>, or the other way around. If, however, you decide to implement all three functions, they must act in a consistent manner. The name <em>Consistency law</em>, however, is entirely my own invention. If it has a more well-known name, I'm not aware of it. </p> <p> In pseudo-Haskell syntax, you can express the law like this: </p> <p> <pre>bimap f g ≡ first f . second g</pre> </p> <p> This states that mapping (using the functions <code>f</code> and <code>g</code>) simultaneously should produce the same result as mapping using an intermediary step: </p> <p> <img src="/content/binary/bifunctor-consistency-law.png" alt="The bifunctor Consistency law."> </p> <p> In C#, you could express it like this: </p> <p> <pre>bf.SelectBoth(f,&nbsp;g)&nbsp;==&nbsp;bf.SelectSecond(g).SelectFirst(f);</pre> </p> <p> You can project the input bifunctor <code>bf</code> using both <code>f</code> and <code>g</code> in a single step, or you can first translate the second dimension with <code>g</code> and then subsequently map that intermediary result along the first axis with <code>f</code>. </p> <p> The above diagram ought to commute: </p> <p> <img src="/content/binary/bifunctor-consistency-commutativity-law.png" alt="The bifunctor Consistency law."> </p> <p> It shouldn't matter whether the intermediary step is applying <code>f</code> along the first axis or <code>g</code> along the second axis. In C#, we can write it like this: </p> <p> <pre>bf.SelectFirst(f).SelectSecond(g)&nbsp;==&nbsp;bf.SelectSecond(g).SelectFirst(f);</pre> </p> <p> On the left-hand side, you first translate the bifunctor <code>bf</code> along the first axis, using <code>f</code>, and then translate that intermediary result along the second axis, using <code>g</code>. On the right-hand side, you first project <code>bf</code> along the second axis, using <code>g</code>, and then map that intermediary result over the first dimension, using <code>f</code>. </p> <p> Regardless of order of translation, the result should be the same. </p> <h3 id="a1d12a9d1afe428684b3d693a39cb5d1"> Composition laws <a href="#a1d12a9d1afe428684b3d693a39cb5d1" title="permalink">#</a> </h3> <p> Similar to how the first functor law generalises to bifunctors, the second functor law generalises as well. For (mono)functors, the second functor law states that if you have two functions over the same dimension, it shouldn't matter whether you perform a projection in one, composed step, or in two steps with an intermediary result. </p> <p> For bifunctors, you can generalise that law and state that you can project over both dimensions in one or two steps: </p> <p> <pre>bimap (f . g) (h . i) ≡ bimap f h . bimap g i</pre> </p> <p> If you have two functions, <code>f</code> and <code>g</code>, that compose, and two other functions, <code>h</code> and <code>i</code>, that also compose, you can translate in either one or two steps; the result should be the same. </p> <p> <img src="/content/binary/bimap-composition-law.png" alt="The bifunctor composition law."> </p> <p> In C#, you can express the law like this: </p> <p> <pre>bf.SelectBoth(x&nbsp;=&gt;&nbsp;f(g(x)),&nbsp;y&nbsp;=&gt;&nbsp;h(i(y)))&nbsp;==&nbsp;bf.SelectBoth(g,&nbsp;i).SelectBoth(f,&nbsp;h);</pre> </p> <p> On the left-hand side, the first dimension is translated in one step. For each <code>x</code> contained in <code>bf</code>, the translation first invokes <code>g(x)</code>, and then immediately calls <code>f</code> with the output of <code>g(x)</code>. The second dimension also gets translated in one step. For each <code>y</code> contained in <code>bf</code>, the translation first invokes <code>i(y)</code>, and then immediately calls <code>h</code> with the output of <code>i(y)</code>. </p> <p> On the right-hand side, you first translate <code>bf</code> along both axes using <code>g</code> and <code>i</code>. This produces an intermediary result that you can use as input for a second translation with <code>f</code> and <code>h</code>. </p> <p> The translation on the left-hand side should produce the same output as the right-hand side. </p> <p> Finally, if you keep one of the dimensions fixed, you essentially have a normal functor, and the second functor law should still hold. For example, if you hold the second dimension fixed, translating over the first dimension is equivalent to a normal functor projection, so the second functor law should hold: </p> <p> <pre>first (f . g) ≡ first f . first g</pre> </p> <p> If you replace <code>first</code> with <code>fmap</code>, you have the second functor law. </p> <p> <img src="/content/binary/second-functor-law-over-first-bifunctor-dimension.png" alt="The second functor law applied to the first dimension of a bifunctor."> </p> <p> In C#, you can write it like this: </p> <p> <pre>bf.SelectFirst(x&nbsp;=&gt;&nbsp;f(g(x)))&nbsp;==&nbsp;bf.SelectFirst(g).SelectFirst(f);</pre> </p> <p> Likewise, you can keep the first dimension constant and apply the second functor law to projections along the second axis: </p> <p> <pre>second (f . g) ≡ second f . second g</pre> </p> <p> Again, if you replace <code>second</code> with <code>fmap</code>, you have the second functor law. </p> <p> <img src="/content/binary/second-functor-law-over-second-bifunctor-dimension.png" alt="The second functor law applied to the second dimension of a bifunctor."> </p> <p> In C#, you express it like this: </p> <p> <pre>bf.SelectSecond(x&nbsp;=&gt;&nbsp;f(g(x)))&nbsp;==&nbsp;bf.SelectSecond(g).SelectSecond(f);</pre> </p> <p> The last two of these composition laws are specialisations of the general composition law, but where you fix either one or the other dimension. </p> <h3 id="41120f4d6ead482f9254a62853d9e1c4"> Summary <a href="#41120f4d6ead482f9254a62853d9e1c4" title="permalink">#</a> </h3> <p> A bifunctor is a container that can be translated over two dimensions, instead of a (mono)functor, which is a container that can be translated over a single dimension. In reality, there isn't a multitude of different bifunctors. While others exist, tuples and Either are the two most common bifunctors. They share an abstraction, but are still fundamentally different. A tuple always contains values of both dimensions at the same time, whereas Either only contains one of the values. </p> <p> Do trifunctors, quadfunctors, and so on, exist? Nothing prevents that, but they aren't particularly useful; in practice, you never run into them. </p> <p> <strong>Next:</strong> <a href="http://blog.ploeh.dk/2018/12/31/tuple-bifunctor">Tuple bifunctor</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="http://blog.ploeh.dk/support">supporting it</a>. Mark Seemann http://blog.ploeh.dk/2018/12/24/bifunctors The Lazy applicative functor http://blog.ploeh.dk/2018/12/17/the-lazy-applicative-functor/ Mon, 17 Dec 2018 07:52:00 UTC <div id="post"> <p> <em>Lazy computations form an applicative functor.</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>. A previous article has described how <a href="http://blog.ploeh.dk/2018/09/10/the-lazy-functor">lazy computations form a functor</a>. In this article, you'll see that lazy computations also form an applicative functor. </p> <h3 id="c04ca371d39847cc86a90240a7f53745"> Apply <a href="#c04ca371d39847cc86a90240a7f53745" title="permalink">#</a> </h3> <p> As you have <a href="http://blog.ploeh.dk/2018/10/15/an-applicative-password-list">previously seen</a>, C# isn't the best fit for the concept of applicative functors. Nevertheless, you can write an <code>Apply</code> extension method following the applicative 'code template': </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;Apply&lt;<span style="color:#2b91af;">TResult</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Lazy</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;">Lazy</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;source) { &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.Value(source.Value)); }</pre> </p> <p> The <code>Apply</code> method takes both a lazy <code>selector</code> and a lazy value called <code>source</code>. It applies the function to the value and returns the result, still as a lazy value. If you have a lazy function <code>f</code> and a lazy value <code>x</code>, you can use the method like this: </p> <p> <pre><span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&gt;&nbsp;f&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <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;f.Apply(x);</pre> </p> <p> The utility of <code>Apply</code>, however, mostly tends to emerge when you need to chain multiple <a href="https://bartoszmilewski.com/2014/01/14/functors-are-containers">containers</a> together; in this case, multiple lazy values. You can do that by adding as many overloads to <code>Apply</code> as you need: </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;">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;">Lazy</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;">Lazy</span>&lt;<span style="color:#2b91af;">T1</span>&gt;&nbsp;source) { &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;">Func</span>&lt;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;(()&nbsp;=&gt;&nbsp;y&nbsp;=&gt;&nbsp;selector.Value(source.Value,&nbsp;y)); }</pre> </p> <p> This overload partially applies the input function. When <code>selector</code> is a function that takes two arguments, you can apply a single of those two arguments, and the result is a new function that closes over the value, but still waits for its second input argument. You can use it like this: </p> <p> <pre><span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">char</span>,&nbsp;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&gt;&nbsp;f&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:#2b91af;">Lazy</span>&lt;<span style="color:blue;">char</span>&gt;&nbsp;c&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:#2b91af;">Lazy</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;i&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:#2b91af;">Lazy</span>&lt;<span style="color:blue;">string</span>&gt;&nbsp;s&nbsp;=&nbsp;f.Apply(c).Apply(i);</pre> </p> <p> Notice that you can chain the various overloads of <code>Apply</code>. In the above example, you have a lazy function that takes a <code>char</code> and an <code>int</code> as input, and returns a <code>string</code>. It could, for instance, be a function that invokes <a href="https://docs.microsoft.com/en-us/dotnet/api/system.string.-ctor?view=netframework-4.7.2#System_String__ctor_System_Char_System_Int32_">the equivalent <code>string</code> constructor overload</a>. </p> <p> Calling <code>f.Apply(c)</code> uses the overload that takes a <code>Lazy&lt;Func&lt;T1, T2, TResult&gt;&gt;</code> as input. The return value is a <code>Lazy&lt;Func&lt;int, string&gt;&gt;</code>, which the first <code>Apply</code> then picks up, to return a <code>Lazy&lt;string&gt;</code>. </p> <p> Usually, you may have one, two, or several lazy values, whereas your function itself isn't contained in a <code>Lazy</code> container. While you can use a helper method such as <code>Lazy.FromValue</code> to 'elevate' a 'normal' function to a lazy function value, it's often more convenient if you have another <code>Apply</code> overload 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;">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;">Func</span>&lt;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;selector, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">T1</span>&gt;&nbsp;source) { &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;">Func</span>&lt;<span style="color:#2b91af;">T2</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&gt;(()&nbsp;=&gt;&nbsp;y&nbsp;=&gt;&nbsp;selector(source.Value,&nbsp;y)); }</pre> </p> <p> The only difference to the equivalent overload is that in this overload, <code>selector</code> isn't a <code>Lazy</code> value, while <code>source</code> still is. This simplifies usage: </p> <p> <pre><span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">char</span>,&nbsp;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;f&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:#2b91af;">Lazy</span>&lt;<span style="color:blue;">char</span>&gt;&nbsp;c&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:#2b91af;">Lazy</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;i&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:#2b91af;">Lazy</span>&lt;<span style="color:blue;">string</span>&gt;&nbsp;s&nbsp;=&nbsp;f.Apply(c).Apply(i);</pre> </p> <p> Notice that in this variation of the example, <code>f</code> is no longer a <code>Lazy&lt;Func&lt;...&gt;&gt;</code>, but just a normal <code>Func</code>. </p> <h3 id="966d763816c84c839b7704cdebfd7bac"> F# <a href="#966d763816c84c839b7704cdebfd7bac" title="permalink">#</a> </h3> <p> <a href="https://fsharp.org">F#</a>'s type inference is more powerful than C#'s, so you don't have to resort to various overloads to make things work. You could, for example, create a minimal <code>Lazy</code> module: </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 &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Lazy&lt;(&#39;a&nbsp;-&gt;&nbsp;&#39;b)&gt;&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;apply&nbsp;(x&nbsp;:&nbsp;Lazy&lt;_&gt;)&nbsp;(f&nbsp;:&nbsp;Lazy&lt;_&gt;)&nbsp;=&nbsp;<span style="color:blue;">lazy</span>&nbsp;f.Value&nbsp;x.Value</pre> </p> <p> In this code listing, I've repeated the <code>map</code> function shown in a <a href="http://blog.ploeh.dk/2018/09/10/the-lazy-functor">previous article</a>. It's not required for the implementation of <code>apply</code>, but you'll see it in use shortly, so I thought it was convenient to include it in the listing. </p> <p> If you belong to the camp of F# programmers who think that F# should emulate <a href="https://www.haskell.org">Haskell</a>, you can also introduce an operator: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;(&lt;*&gt;)&nbsp;f&nbsp;x&nbsp;=&nbsp;Lazy.apply&nbsp;x&nbsp;f</pre> </p> <p> Notice that this <code>&lt;*&gt;</code> operator simply flips the arguments of <code>Lazy.apply</code>. If you introduce such an operator, be aware that the admonition from <a href="http://blog.ploeh.dk/2018/10/01/applicative-functors">the overview article</a> still applies. In Haskell, the <code>&lt;*&gt;</code> operator applies to any <code>Applicative</code>, which makes it truly general. In F#, once you define an operator like this, it applies specifically to a particular container type, which, in this case, is <code>Lazy&lt;'a&gt;</code>. </p> <p> You can replicate the first of the above C# examples like this: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;f&nbsp;:&nbsp;Lazy&lt;int&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;string&gt;&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:blue;">let</span>&nbsp;x&nbsp;:&nbsp;Lazy&lt;int&gt;&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:blue;">let</span>&nbsp;y&nbsp;:&nbsp;Lazy&lt;string&gt;&nbsp;=&nbsp;Lazy.apply&nbsp;x&nbsp;f</pre> </p> <p> Alternatively, if you want to use the <code>&lt;*&gt;</code> operator, you can compute <code>y</code> like this: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;y&nbsp;:&nbsp;Lazy&lt;string&gt;&nbsp;=&nbsp;f&nbsp;&lt;*&gt;&nbsp;x</pre> </p> <p> Chaining multiple lazy computations together also works: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;f&nbsp;:&nbsp;Lazy&lt;char&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;int&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;string&gt;&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:blue;">let</span>&nbsp;c&nbsp;:&nbsp;Lazy&lt;char&gt;&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:blue;">let</span>&nbsp;i&nbsp;:&nbsp;Lazy&lt;int&gt;&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:blue;">let</span>&nbsp;s&nbsp;=&nbsp;Lazy.apply&nbsp;c&nbsp;f&nbsp;|&gt;&nbsp;Lazy.apply&nbsp;i</pre> </p> <p> Again, you can compute <code>s</code> with the operator, if that's more to your liking: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;s&nbsp;:&nbsp;Lazy&lt;string&gt;&nbsp;=&nbsp;f&nbsp;&lt;*&gt;&nbsp;c&nbsp;&lt;*&gt;&nbsp;i</pre> </p> <p> Finally, if your function isn't contained in a <code>Lazy</code> value, you can start out with <code>Lazy.map</code>: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;f&nbsp;:&nbsp;char&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;int&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;string&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:blue;">let</span>&nbsp;c&nbsp;:&nbsp;Lazy&lt;char&gt;&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:blue;">let</span>&nbsp;i&nbsp;:&nbsp;Lazy&lt;int&gt;&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:blue;">let</span>&nbsp;s&nbsp;:&nbsp;Lazy&lt;string&gt;&nbsp;=&nbsp;Lazy.map&nbsp;f&nbsp;c&nbsp;|&gt;&nbsp;Lazy.apply&nbsp;i</pre> </p> <p> This works without requiring additional overloads. Since F# natively supports partial function application, the first step in the pipeline, <code>Lazy.map f c</code> has the type <code>Lazy&lt;int -&gt; string&gt;</code> because <code>f</code> is a function of the type <code>char -&gt; int -&gt; string</code>, but in the first step, <code>Lazy.map f c</code> only supplies <code>c</code>, which contains a <code>char</code> value. </p> <p> Once more, if you prefer the infix operator, you can also compute <code>s</code> as: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;s&nbsp;:&nbsp;Lazy&lt;string&gt;&nbsp;=&nbsp;<span style="color:blue;">lazy</span>&nbsp;f&nbsp;&lt;*&gt;&nbsp;c&nbsp;&lt;*&gt;&nbsp;i</pre> </p> <p> While I find <a href="http://blog.ploeh.dk/2018/07/02/terse-operators-make-business-code-more-readable">operator-based syntax attractive in Haskell code</a>, I'm more hesitant about such syntax in F#. </p> <h3 id="63a6579eeb644627b02efc3f9aabd202"> Haskell <a href="#63a6579eeb644627b02efc3f9aabd202" title="permalink">#</a> </h3> <p> As outlined in the <a href="http://blog.ploeh.dk/2018/09/10/the-lazy-functor">previous article</a>, Haskell is already lazily evaluated, so it makes little sense to introduce an explicit <code>Lazy</code> data container. While Haskell's built-in <code>Identity</code> isn't quite equivalent to .NET's <code>Lazy&lt;T&gt;</code> object, some similarities remain; most notably, the <a href="http://blog.ploeh.dk/2018/09/03/the-identity-functor">Identity functor</a> is also applicative: </p> <p> <pre>Prelude Data.Functor.Identity&gt; :t f f :: a -&gt; Int -&gt; [a] Prelude Data.Functor.Identity&gt; :t c c :: Identity Char Prelude Data.Functor.Identity&gt; :t i i :: Num a =&gt; Identity a Prelude Data.Functor.Identity&gt; :t f &lt;$&gt; c &lt;*&gt; i f &lt;$&gt; c &lt;*&gt; i :: Identity String</pre> </p> <p> This little GHCi session simply illustrates that if you have a 'normal' function <code>f</code> and two <code>Identity</code> values <code>c</code> and <code>i</code>, you can compose them using the infix <em>map</em> operator <code>&lt;$&gt;</code>, followed by the infix <em>apply</em> operator <code>&lt;*&gt;</code>. This is equivalent to the F# expression <code>Lazy.map f c |&gt; Lazy.apply i</code>. </p> <p> Still, this makes little sense, since all Haskell expressions are already lazily evaluated. </p> <h3 id="d3ddcafbb8e14bfea2c18828cf44f244"> Summary <a href="#d3ddcafbb8e14bfea2c18828cf44f244" title="permalink">#</a> </h3> <p> The Lazy functor is also an <em>applicative functor</em>. This can be used to combine multiple lazily computed values into a single lazily computed value. </p> <p> <strong>Next:</strong> <a href="http://blog.ploeh.dk/2018/12/24/bifunctors">Bifunctors</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="http://blog.ploeh.dk/support">supporting it</a>. Mark Seemann http://blog.ploeh.dk/2018/12/17/the-lazy-applicative-functor Danish CPR numbers in F# http://blog.ploeh.dk/2018/12/10/danish-cpr-numbers-in-f/ Mon, 10 Dec 2018 08:14:00 UTC <div id="post"> <p> <em>An example of domain-modelling in F#, including a fine example of using the option type as an applicative functor.</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>, although the applicative functor example doesn't appear until towards the end. This article also serves the purpose of showing an example of <a href="http://amzn.to/WBCwx7">Domain-Driven Design</a> in F#. </p> <h3 id="163a2e2ecb144172a974d1eb23ff6703"> Danish personal identification numbers <a href="#163a2e2ecb144172a974d1eb23ff6703" title="permalink">#</a> </h3> <p> As outlined in the <a href="http://blog.ploeh.dk/2018/11/26/the-test-data-generator-applicative-functor">previous article</a>, in Denmark, everyone has a <a href="https://en.wikipedia.org/wiki/Personal_identification_number_(Denmark)">personal identification number</a>, in Danish called <em>CPR-nummer</em> (<em>CPR number</em>). </p> <p> CPR numbers have a simple format: <code>DDMMYY-SSSS</code>, where the first six digits indicate a person's birth date, and the last four digits are a sequence number. Some information, however, is also embedded in the sequence number. An example could be <code>010203-1234</code>, which indicates a woman born February 1, 1903. </p> <p> One way to model this in <a href="https://fsharp.org">F#</a> is with a single-case discriminated union: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;<span style="color:teal;">CprNumber</span>&nbsp;=&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:navy;">CprNumber</span>&nbsp;<span style="color:blue;">of</span>&nbsp;(<span style="color:teal;">int</span>&nbsp;*&nbsp;<span style="color:teal;">int</span>&nbsp;*&nbsp;<span style="color:teal;">int</span>&nbsp;*&nbsp;<span style="color:teal;">int</span>)&nbsp;<span style="color:blue;">with</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">override</span>&nbsp;x.<span style="color:navy;">ToString</span>&nbsp;()&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;(<span style="color:navy;">CprNumber</span>&nbsp;(day,&nbsp;month,&nbsp;year,&nbsp;sequenceNumber))&nbsp;=&nbsp;x &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:navy;">sprintf</span>&nbsp;<span style="color:#a31515;">&quot;</span><span style="color:teal;">%02d%02d%02d</span><span style="color:#a31515;">-</span><span style="color:teal;">%04d</span><span style="color:#a31515;">&quot;</span>&nbsp;day&nbsp;month&nbsp;year&nbsp;sequenceNumber</pre> </p> <p> This is a common idiom in F#. In object-oriented design with e.g. C# or Java, you'd typically create a class and put guard clauses in its constructor. This would prevent a user from initialising an object with invalid data (such as <code>401500-1234</code>). While you <em>can</em> create classes in F# as well, a single-case union with a private case constructor can achieve the same degree of encapsulation. </p> <p> In this case, I decided to use a quadruple (4-tuple) as the internal representation, but this isn't visible to users. This gives me the option to refactor the internal representation, if I need to, without breaking existing clients. </p> <h3 id="83eaa41329eb4d8b894e0640f600f110"> Creating CPR number values <a href="#83eaa41329eb4d8b894e0640f600f110" title="permalink">#</a> </h3> <p> Since the <code>CprNumber</code> case constructor is private, you can't just create new values like this: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;<span style="color:#9b9b9b;">cpr</span>&nbsp;=&nbsp;CprNumber&nbsp;(1,&nbsp;1,&nbsp;1,&nbsp;1118) </pre> </p> <p> If you're outside the <code>Cpr</code> module that defines the type, this <strong>doesn't compile</strong>. This is by design, but obviously you need a way to create values. For convenience, input values for day, month, and so on, are represented as <code>int</code>s, which can be zero, negative, or way too large for CPR numbers. There's no way to statically guarantee that you can create a value, so you'll have to settle for a <code>tryCreate</code> function; i.e. a function that returns <code>Some CprNumber</code> if the input is valid, or <code>None</code> if it isn't. In <a href="https://www.haskell.org">Haskell</a>, this pattern is called a <em>smart constructor</em>. </p> <p> There's a couple of rules to check. All integer values must fall in certain ranges. Days must be between 1 and 31, months must be between 1 and 12, and so on. One way to enable succinct checks like that is with an <a href="https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/active-patterns">active pattern</a>: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;<span style="color:blue;">private</span>&nbsp;(|<span style="color:navy;">Between</span>|_|)&nbsp;min&nbsp;max&nbsp;candidate&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;min&nbsp;&lt;=&nbsp;candidate&nbsp;&amp;&amp;&nbsp;candidate&nbsp;&lt;=&nbsp;max &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">then</span>&nbsp;<span style="color:navy;">Some</span>&nbsp;candidate &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span>&nbsp;<span style="color:navy;">None</span></pre> </p> <p> Straightforward: return <code>Some candidate</code> if <code>candidate</code> is between <code>min</code> and <code>max</code>; otherwise, <code>None</code>. This enables you to pattern-match input integer values to particular ranges. </p> <p> Perhaps you've already noticed that years are represented with only two digits. CPR is an old system (from 1968), and back then, bits were expensive. No reason to waste bits on recording the millennium or century in which people were born. It turns out, after all, that there's a way to at least partially figure out the century in which people were born. The first digit of the sequence number contains that information: </p> <p> <pre><span style="color:green;">//&nbsp;int&nbsp;-&gt;&nbsp;int&nbsp;-&gt;&nbsp;int</span> <span style="color:blue;">let</span>&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:navy;">calculateFourDigitYear</span>&nbsp;year&nbsp;sequenceNumber&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;centuryDigit&nbsp;=&nbsp;sequenceNumber&nbsp;/&nbsp;1000&nbsp;<span style="color:green;">//&nbsp;Integer&nbsp;division</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Table&nbsp;from&nbsp;https://da.wikipedia.org/wiki/CPR-nummer</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">match</span>&nbsp;centuryDigit,&nbsp;year&nbsp;<span style="color:blue;">with</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:navy;">Between</span>&nbsp;0&nbsp;3&nbsp;_,&nbsp;_&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;1900 &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;<span style="color:navy;">Between</span>&nbsp;0&nbsp;36&nbsp;_&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;2000 &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;&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;1900 &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:navy;">Between</span>&nbsp;5&nbsp;8&nbsp;_,&nbsp;<span style="color:navy;">Between</span>&nbsp;0&nbsp;57&nbsp;_&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;2000 &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:navy;">Between</span>&nbsp;5&nbsp;8&nbsp;_,&nbsp;_&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;1800 &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;_&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;<span style="color:navy;">Between</span>&nbsp;0&nbsp;36&nbsp;_&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;2000 &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;_&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&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;1900 &nbsp;&nbsp;&nbsp;&nbsp;+&nbsp;year</pre> </p> <p> As the code comment informs the reader, there's a table that defines the century, based on the two-digit year and the first digit of the sequence number. Note that birth dates in the nineteenth century are possible. No Danes born before 1900 are alive any longer, but at the time the CPR system was introduced, one person in the system was born in 1863! </p> <p> The <code>calculateFourDigitYear</code> function starts by pulling the first digit out of the sequence number. This is a four-digit number, so dividing by 1,000 produces the digit. I left a comment about integer division, because I often miss that detail when I read code. </p> <p> The big pattern-match expression uses the <code>Between</code> active pattern, but it ignores the return value from the pattern. This explains the wild cards (<code>_</code>), I hope. </p> <p> Although a pattern-match expression is often formatted over several lines of code, it's a single expression that produces a single value. Often, you see code where a <code>let</code>-binding binds a named value to a pattern-match expression. Another occasional idiom is to pipe a pattern-match expression to a function. In the <code>calculateFourDigitYear</code> function I use a language construct I've never seen anywhere else: the eight-lines pattern-match expression returns an <code>int</code>, which I simply add to <code>year</code> using the <code>+</code> operator. </p> <p> Both <code>calculateFourDigitYear</code> and the <code>Between</code> active pattern are private functions. They're only there as support functions for the public API. You can now implement a <code>tryCreate</code> function: </p> <p> <pre><span style="color:green;">//&nbsp;int&nbsp;-&gt;&nbsp;int&nbsp;-&gt;&nbsp;int&nbsp;-&gt;&nbsp;int&nbsp;-&gt;&nbsp;CprNumber&nbsp;option</span> <span style="color:blue;">let</span>&nbsp;<span style="color:navy;">tryCreate</span>&nbsp;day&nbsp;month&nbsp;year&nbsp;sequenceNumber&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">match</span>&nbsp;month,&nbsp;year,&nbsp;sequenceNumber&nbsp;<span style="color:blue;">with</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:navy;">Between</span>&nbsp;1&nbsp;12&nbsp;m,&nbsp;<span style="color:navy;">Between</span>&nbsp;0&nbsp;99&nbsp;y,&nbsp;<span style="color:navy;">Between</span>&nbsp;0&nbsp;9999&nbsp;s&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;fourDigitYear&nbsp;=&nbsp;<span style="color:navy;">calculateFourDigitYear</span>&nbsp;y&nbsp;s &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;1&nbsp;&lt;=&nbsp;day&nbsp;&amp;&amp;&nbsp;day&nbsp;&lt;=&nbsp;<span style="color:teal;">DateTime</span>.<span style="color:navy;">DaysInMonth</span>&nbsp;(fourDigitYear,&nbsp;m) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">then</span>&nbsp;<span style="color:navy;">Some</span>&nbsp;(<span style="color:navy;">CprNumber</span>&nbsp;(day,&nbsp;m,&nbsp;y,&nbsp;s)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span>&nbsp;<span style="color:navy;">None</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;_&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:navy;">None</span></pre> </p> <p> The <code>tryCreate</code> function begins by pattern-matching a triple (3-tuple) using the <code>Between</code> active pattern. The <code>month</code> must always be between <code>1</code> and <code>12</code> (both included), the <code>year</code> must be between <code>0</code> and <code>99</code>, and the <code>sequenceNumber</code> must always be between <code>0</code> and <code>9999</code> (in fact, I'm not completely sure if <code>0000</code> is valid). </p> <p> Finding the appropriate range for the <code>day</code> is more intricate. Is <code>31</code> always valid? Clearly not, because there's no November 31, for example. Is <code>30</code> always valid? No, because there's never a February 30. Is <code>29</code> valid? This depends on whether or not the year is a leap year. </p> <p> This reveals why you need <code>calculateFourDigitYear</code>. While you can use <code>DateTime.DaysInMonth</code> to figure out how many days a given month has, you need the year. Specifically, February 19<strong>00</strong> had 28 days, while February 20<strong>00</strong> had 29. </p> <p> Ergo, if <code>day</code>, <code>month</code>, <code>year</code>, and <code>sequenceNumber</code> all fall within their appropriate ranges, <code>tryCreate</code> returns a <code>Some CprNumber</code> value; otherwise, it returns <code>None</code>. </p> <p> Notice how this is different from an object-oriented constructor with guard clauses. If you try to create an object with invalid input, it'll throw an exception. If you try to create a <code>CprNumber</code> value, you'll receive a <code>CprNumber option</code>, and you, as the client developer, <em>must</em> handle both the <code>Some</code> and the <code>None</code> case. The compiler will enforce this. </p> <p> <pre>&gt; let gjern = Cpr.tryCreate 11 11 11 1118;; val gjern : Cpr.CprNumber option = Some 111111-1118 &gt; gjern |&gt; Option.map Cpr.born;; val it : DateTime option = Some 11.11.1911 00:00:00</pre> </p> <p> As most F# developers know, F# gives you enough syntactic sugar to make this a joy rather than a chore... and the warm and fuzzy feeling of safety is priceless. </p> <h3 id="78793bd7fceb4dc99bab81ccb7abb305"> CPR data <a href="#78793bd7fceb4dc99bab81ccb7abb305" title="permalink">#</a> </h3> <p> The above FSI session uses <code>Cpr.born</code>, which you haven't seen yet. With the tools available so far, it's trivial to implement; all the work is already done: </p> <p> <pre><span style="color:green;">//&nbsp;CprNumber&nbsp;-&gt;&nbsp;DateTime</span> <span style="color:blue;">let</span>&nbsp;<span style="color:navy;">born</span>&nbsp;(<span style="color:navy;">CprNumber</span>&nbsp;(day,&nbsp;month,&nbsp;year,&nbsp;sequenceNumber))&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:teal;">DateTime</span>&nbsp;(<span style="color:navy;">calculateFourDigitYear</span>&nbsp;year&nbsp;sequenceNumber,&nbsp;month,&nbsp;day)</pre> </p> <p> While the <code>CprNumber</code> case constructor is <code>private</code>, it's still available from inside of the module. The <code>born</code> function pattern-matches <code>day</code>, <code>month</code>, <code>year</code>, and <code>sequenceNumber</code> out of its input argument, and trivially delegates the hard work to <code>calculateFourDigitYear</code>. </p> <p> Another piece of data you can deduce from a CPR number is the gender of the person: </p> <p> <pre><span style="color:green;">//&nbsp;CprNumber&nbsp;-&gt;&nbsp;bool</span> <span style="color:blue;">let</span>&nbsp;<span style="color:navy;">isFemale</span>&nbsp;(<span style="color:navy;">CprNumber</span>&nbsp;(_,&nbsp;_,&nbsp;_,&nbsp;sequenceNumber))&nbsp;=&nbsp;sequenceNumber&nbsp;%&nbsp;2&nbsp;&nbsp;=&nbsp;0 <span style="color:blue;">let</span>&nbsp;<span style="color:navy;">isMale</span>&nbsp;&nbsp;&nbsp;(<span style="color:navy;">CprNumber</span>&nbsp;(_,&nbsp;_,&nbsp;_,&nbsp;sequenceNumber))&nbsp;=&nbsp;sequenceNumber&nbsp;%&nbsp;2&nbsp;&lt;&gt;&nbsp;0</pre> </p> <p> The rule is that if the sequence number is even, then the person is female; otherwise, the person is male (and if you change sex, you get a new CPR number). </p> <p> <pre>&gt; gjern |&gt; Option.map Cpr.isFemale;; val it : bool option = Some true</pre> </p> <p> Since <code>1118</code> is even, this is a woman. </p> <h3 id="235df75fd03a41e49b5a1fc3767e6ce8"> Parsing CPR strings <a href="#235df75fd03a41e49b5a1fc3767e6ce8" title="permalink">#</a> </h3> <p> CPR numbers are often passed around as text, so you'll need to be able to parse a <code>string</code> representation. As described in the <a href="http://blog.ploeh.dk/2018/11/26/the-test-data-generator-applicative-functor">previous article</a>, you should follow <a href="https://en.wikipedia.org/wiki/Robustness_principle">Postel's law</a>. Input could include extra white space, and the middle dash could be missing. </p> <p> The .NET Base Class Library contains enough utility methods working on <code>string</code> values that this isn't going to be particularly difficult. It can, however, be awkward to interoperate with object-oriented APIs, so you'll often benefit from adding a few utility functions that give you curried functions instead of objects with methods. Here's one that adapts <code>Int32.TryParse</code>: </p> <p> <pre><span style="color:blue;">module</span>&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:teal;">Int</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;string&nbsp;-&gt;&nbsp;int&nbsp;option</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:navy;">tryParse</span>&nbsp;candidate&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">match</span>&nbsp;candidate&nbsp;|&gt;&nbsp;<span style="color:teal;">Int32</span>.<span style="color:navy;">TryParse</span>&nbsp;<span style="color:blue;">with</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:blue;">true</span>,&nbsp;i&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:navy;">Some</span>&nbsp;i &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> Nothing much goes on here. While F# has pleasant syntax for handling <code>out</code> parameters, it can be inconvenient to have to pattern-match every time you'd like to try to parse an integer. </p> <p> Here's another helper function: </p> <p> <pre><span style="color:blue;">module</span>&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:teal;">String</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;int&nbsp;-&gt;&nbsp;int&nbsp;-&gt;&nbsp;string&nbsp;-&gt;&nbsp;string&nbsp;option</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:navy;">trySubstring</span>&nbsp;startIndex&nbsp;length&nbsp;(s&nbsp;:&nbsp;<span style="color:teal;">string</span>)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;s.Length&nbsp;&lt;&nbsp;startIndex&nbsp;+&nbsp;length &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">then</span>&nbsp;<span style="color:navy;">None</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span>&nbsp;<span style="color:navy;">Some</span>&nbsp;(s.<span style="color:navy;">Substring</span>&nbsp;(startIndex,&nbsp;length))</pre> </p> <p> This one comes with two benefits: The first benefit is that it's curried, which enables partial application and piping. You'll see an example of this further down. The second benefit is that it handles at least one error condition in a type-safe manner. When trying to extract a sub-string from a string, the <code>Substring</code> <em>method</em> can throw an exception if the index or length arguments are out of range. This function checks whether it can extract the requested sub-string, and returns <code>None</code> if it can't. </p> <p> I wouldn't be surprised if there are edge cases (for example involving negative integers) that <code>trySubstring</code> doesn't handle gracefully, but as you may have noticed, this is a function in a <code>private</code> module. I only need it to handle a particular use case, and it does that. </p> <p> You can now add the <code>tryParse</code> function: </p> <p> <pre><span style="color:green;">//&nbsp;string&nbsp;-&gt;&nbsp;CprNumber&nbsp;option</span> <span style="color:blue;">let</span>&nbsp;<span style="color:navy;">tryParse</span>&nbsp;(candidate&nbsp;:&nbsp;<span style="color:teal;">string</span>&nbsp;)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;(&lt;*&gt;)&nbsp;fo&nbsp;xo&nbsp;=&nbsp;fo&nbsp;|&gt;&nbsp;<span style="color:teal;">Option</span>.<span style="color:navy;">bind</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="color:navy;">f</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;xo&nbsp;|&gt;&nbsp;<span style="color:teal;">Option</span>.<span style="color:navy;">map</span>&nbsp;<span style="color:navy;">f</span>) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;canonicalized&nbsp;=&nbsp;candidate.<span style="color:navy;">Trim</span>().<span style="color:navy;">Replace</span>(<span style="color:#a31515;">&quot;-&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;&quot;</span>) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;dayCandidate&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;canonicalized&nbsp;|&gt;&nbsp;<span style="color:teal;">String</span>.<span style="color:navy;">trySubstring</span>&nbsp;0&nbsp;2 &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;monthCandidate&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;canonicalized&nbsp;|&gt;&nbsp;<span style="color:teal;">String</span>.<span style="color:navy;">trySubstring</span>&nbsp;2&nbsp;2 &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;yearCandidate&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=&nbsp;canonicalized&nbsp;|&gt;&nbsp;<span style="color:teal;">String</span>.<span style="color:navy;">trySubstring</span>&nbsp;4&nbsp;2 &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;sequenceNumberCandidate&nbsp;=&nbsp;canonicalized&nbsp;|&gt;&nbsp;<span style="color:teal;">String</span>.<span style="color:navy;">trySubstring</span>&nbsp;6&nbsp;4 &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:navy;">Some</span>&nbsp;<span style="color:navy;">tryCreate</span> &nbsp;&nbsp;&nbsp;&nbsp;&lt;*&gt;&nbsp;<span style="color:teal;">Option</span>.<span style="color:navy;">bind</span>&nbsp;<span style="color:teal;">Int</span>.<span style="color:navy;">tryParse</span>&nbsp;dayCandidate &nbsp;&nbsp;&nbsp;&nbsp;&lt;*&gt;&nbsp;<span style="color:teal;">Option</span>.<span style="color:navy;">bind</span>&nbsp;<span style="color:teal;">Int</span>.<span style="color:navy;">tryParse</span>&nbsp;monthCandidate &nbsp;&nbsp;&nbsp;&nbsp;&lt;*&gt;&nbsp;<span style="color:teal;">Option</span>.<span style="color:navy;">bind</span>&nbsp;<span style="color:teal;">Int</span>.<span style="color:navy;">tryParse</span>&nbsp;yearCandidate &nbsp;&nbsp;&nbsp;&nbsp;&lt;*&gt;&nbsp;<span style="color:teal;">Option</span>.<span style="color:navy;">bind</span>&nbsp;<span style="color:teal;">Int</span>.<span style="color:navy;">tryParse</span>&nbsp;sequenceNumberCandidate &nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;&nbsp;<span style="color:teal;">Option</span>.<span style="color:navy;">bind</span>&nbsp;<span style="color:navy;">id</span></pre> </p> <p> The function starts by defining a private <code>&lt;*&gt;</code> operator. Readers of the <a href="http://blog.ploeh.dk/2018/10/01/applicative-functors">applicative functor article series</a> will recognise this as the 'apply' operator. The reason I added it as a private operator is that I don't need it anywhere else in the code base, and in F#, I'm always worried that if I add <code>&lt;*&gt;</code> at a more visible level, it could collide with other definitions of <code>&lt;*&gt;</code> - for example <a href="http://blog.ploeh.dk/2018/10/08/full-deck">one for lists</a>. This one particularly makes <code>option</code> an applicative functor. </p> <p> The first step in parsing <code>candidate</code> is to remove surrounding white space and the interior dash. </p> <p> The next step is to use <code>String.trySubstring</code> to pull out candidates for <em>day</em>, <em>month</em>, and so on. Each of these four are <code>string option</code> values. </p> <p> All four of these must be <code>Some</code> values before we can even start to attempt to turn them into a <code>CprNumber</code> value. If only a single value is <code>None</code>, <code>tryParse</code> should return <code>None</code> as well. </p> <p> You may want to re-read the <a href="http://blog.ploeh.dk/2018/10/15/an-applicative-password-list">article on the List applicative functor</a> for a detailed explanation of how the <code>&lt;*&gt;</code> operator works. In <code>tryParse</code>, you have four <code>option</code> values, so you apply them all using four <code>&lt;*&gt;</code> operators. Since four values are being applied, you'll need a function that takes four curried input arguments of the appropriate types. In this case, all four are <code>int option</code> values, so for the first expression in the <code>&lt;*&gt;</code> chain, you'll need an option of a function that takes four <code>int</code> arguments. </p> <p> Lo and behold! <code>tryCreate</code> takes four <code>int</code> arguments, so the only action you need to take is to make it an <code>option</code> by putting it in a <code>Some</code> case. </p> <p> The only remaining hurdle is that <code>tryCreate</code> returns <code>CprNumber option</code>, and since you're already 'in' the <code>option</code> applicative functor, you now have a <code>CprNumber option option</code>. Fortunately, <code>bind id</code> is always the 'flattening' combo, so that's easily dealt with. </p> <p> <pre>&gt; let andreas = Cpr.tryParse " 0109636221";; val andreas : Cpr.CprNumber option = Some 010963-6221</pre> </p> <p> Since you now have both a way to parse a string, and turn a <code>CprNumber</code> into a string, you can write the usual round-trip property: </p> <p> <pre>[&lt;<span style="color:teal;">Fact</span>&gt;] <span style="color:blue;">let</span>&nbsp;<span style="color:navy;">``CprNumber&nbsp;correctly&nbsp;round-trips``</span>&nbsp;()&nbsp;=&nbsp;<span style="color:teal;">Property</span>.<span style="color:navy;">check</span>&nbsp;&lt;|&nbsp;<span style="color:blue;">property</span>&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;expected&nbsp;=&nbsp;<span style="color:teal;">Gen</span>.cprNumber &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;&nbsp;actual&nbsp;&nbsp;&nbsp;=&nbsp;expected&nbsp;|&gt;&nbsp;<span style="color:navy;">string</span>&nbsp;|&gt;&nbsp;<span style="color:teal;">Cpr</span>.<span style="color:navy;">tryParse</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:navy;">Some</span>&nbsp;expected&nbsp;=!&nbsp;actual&nbsp;}</pre> </p> <p> This test uses <a href="https://github.com/hedgehogqa/fsharp-hedgehog">Hedgehog</a>, <a href="https://github.com/SwensenSoftware/unquote">Unquote</a>, and <a href="https://xunit.github.io">xUnit.net</a>. The previous article demonstrates a way to test that <code>Cpr.tryParse</code> can handle mangled input. </p> <h3 id="503bb1791d344b1f917734cffe2320f6"> Summary <a href="#503bb1791d344b1f917734cffe2320f6" title="permalink">#</a> </h3> <p> This article mostly exhibited various F# design techniques you can use to achieve an even better degree of encapsulation than you can easily get with object-oriented languages. Towards the end, you saw how using <code>option</code> as an applicative functor enables you to compose more complex optional values from smaller values. If just a single value is <code>None</code>, the entire expression becomes <code>None</code>, but if all values are <code>Some</code> values, the computation succeeds. </p> <p> This article is an entry in the <a href="https://sergeytihon.com/2018/10/22/f-advent-calendar-in-english-2018">F# Advent Calendar in English 2018</a>. </p> <p> <strong>Next: </strong> <a href="http://blog.ploeh.dk/2018/12/17/the-lazy-applicative-functor">The Lazy applicative functor</a>. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="559c8543d61042a0bdcbe938ac97de12"> <div class="comment-author"><a href="https://activesolution.se">Viktor Andersson</a></div> <div class="comment-content"> <p> Great post, a very good read! Interestingly enough we recently made an F# implementation for the swedish personal identification number. In fact <a href="https://github.com/ActiveLogin/ActiveLogin.Identity">v1.0.0</a> will be published any day now. Interesting to see how the problem with four-digit years are handled differently in Denmark and Sweden. </p> <p> I really like the Between Active pattern of your solution, we did not really take as a generic approach, instead we modeled with types for Year, Month, Day, etc. But I find your solution to be very concise and clear. Also we worked with the Result type instead of Option to be able to provide the client with helpful error messages. For our Object Oriented friends we are also exposing a C#-friendly facade which adds a bit of boiler plate code. </p> </div> <div class="comment-date">2018-12-18 06:26 UTC</div> </div> <div class="comment" id="26683afcb79c444f9887f112323b935a"> <div class="comment-author"><a href="http://blog.ploeh.dk">Mark Seemann</a></div> <div class="comment-content"> <p> Viktor, thank you for your kind words. The <code>Result</code> (or <a href="http://blog.ploeh.dk/2018/06/11/church-encoded-either">Either</a>) type does, indeed, provide more information when things go wrong. This can be useful when client code needs to handle different error cases in different ways. Sometimes, it may also be useful, as you write, when you want to provide more <a href="http://blog.ploeh.dk/2014/12/23/exception-messages-are-for-programmers">helpful error messages</a>. </p> <p> Particularly when it comes to parsing or input validation, <a href="http://blog.ploeh.dk/2018/11/05/applicative-validation">Either can be useful</a>. </p> <p> The main reason I chose to model with <code>option</code> in this article was that I wanted to demonstrate how to use the <a href="http://blog.ploeh.dk/2018/10/01/applicative-functors">applicative</a> nature of <code>option</code>, but I suppose I could have equally done so with <code>Result</code>. </p> </div> <div class="comment-date">2018-12-18 9:09 UTC</div> </div> </div> <hr> This blog is totally free, but if you like it, please consider <a href="http://blog.ploeh.dk/support">supporting it</a>. Mark Seemann http://blog.ploeh.dk/2018/12/10/danish-cpr-numbers-in-f Set is not a functor http://blog.ploeh.dk/2018/12/03/set-is-not-a-functor/ Mon, 03 Dec 2018 07:58:00 UTC <div id="post"> <p> <em>Sets aren't functors. An example 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 way functors are frequently presented to programmes is as a generic <a href="https://bartoszmilewski.com/2014/01/14/functors-are-containers">container</a> (<code>Foo&lt;T&gt;</code>) equipped with a translation method, normally called <em>map</em>, but in C# <a href="http://blog.ploeh.dk/2015/08/03/idiomatic-or-idiosyncratic">idiomatically</a> called <code>Select</code>. </p> <p> It'd be tempting to believe that any generic type with a <code>Select</code> method is a functor, but it takes more than that. The <code>Select</code> method must also obey the <a href="http://blog.ploeh.dk/2018/03/22/functors">functor laws</a>. This article shows an example of a translation that violates the second functor law. </p> <h3 id="5a13402d14f54ce689a7ae4e62f54233"> Mapping sets <a href="#5a13402d14f54ce689a7ae4e62f54233" title="permalink">#</a> </h3> <p> The .NET Base Class Library comes with a class called <a href="https://docs.microsoft.com/en-gb/dotnet/api/system.collections.generic.hashset-1">HashSet&lt;T&gt;</a>. This generic class implements <code>IEnumerable&lt;T&gt;</code>, so, via extension methods, it has a <code>Select</code> method. </p> <p> Unfortunately, that <code>Select</code> method isn't a structure-preserving translation of sets. The problem is that it treats sets as enumerable sequences, which implies an order to elements that isn't part of a set's structure. </p> <p> In order to understand what the problem is, consider this <a href="https://xunit.github.io">xUnit.net</a> test: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SetAsEnumerableSelectLeadsToWrongConclusions() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;set1&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HashSet</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;{&nbsp;1,&nbsp;2,&nbsp;3&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;set2&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HashSet</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;{&nbsp;3,&nbsp;2,&nbsp;1&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.True(set1.SetEquals(set2)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;id&nbsp;=&nbsp;x&nbsp;=&gt;&nbsp;x; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;seq1&nbsp;=&nbsp;set1.AsEnumerable().Select(id); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;seq2&nbsp;=&nbsp;set2.AsEnumerable().Select(id); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.False(seq1.SequenceEqual(seq2)); }</pre> </p> <p> This test creates two sets, and by using a <a href="http://xunitpatterns.com/Guard%20Assertion.html">Guard Assertion</a> demonstrates that they're equal to each other. It then proceeds to <code>Select</code> over both sets, using the identity function <code>id</code>. The return values aren't <code>HashSet&lt;T&gt;</code> objects, but rather <code>IEnumerable&lt;T&gt;</code> sequences. Due to an implementation detail in <code>HashSet&lt;T&gt;</code>, these two sequences are different, because they were populated in reverse order of each other. </p> <p> The problem is that the <code>Select</code> extension method has the signature <code>IEnumerable&lt;TResult&gt; Select&lt;T, TResult&gt;(IEnumerable&lt;T&gt;, Func&lt;T, TResult&gt;)</code>. It doesn't operate on <code>HashSet&lt;T&gt;</code>, but instead treats it as an ordered sequence of elements. A set isn't intrinsically ordered, so that's not the translation you need. </p> <p> To be clear, <code>IEnumerable&lt;T&gt;</code> <em>is</em> a functor (as long as the sequence is <a href="https://en.wikipedia.org/wiki/Referential_transparency">referentially transparent</a>). It's just not the functor you're looking for. What you need is a method with the signature <code>HashSet&lt;TResult&gt; Select&lt;T, TResult&gt;(HashSet&lt;T&gt;, Func&lt;T, TResult&gt;)</code>. Fortunately, such a method is trivial to implement: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">HashSet</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;">HashSet</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;">HashSet</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;(source.AsEnumerable().Select(selector)); }</pre> </p> <p> This extension method offers a proper <code>Select</code> method that translates one <code>HashSet&lt;T&gt;</code> into another. It does so by enumerating the elements of the set, then using the <code>Select</code> method for <code>IEnumerable&lt;T&gt;</code>, and finally wrapping the resulting sequence in a new <code>HashSet&lt;TResult&gt;</code> object. </p> <p> This is a better candidate for a translation of sets. Is it a functor, then? </p> <h3 id="44c78cf51897490a8d844a89eaa8ef73"> Second functor law <a href="#44c78cf51897490a8d844a89eaa8ef73" title="permalink">#</a> </h3> <p> Even though <code>HashSet&lt;T&gt;</code> and the new <code>Select</code> method have the correct types, it's still only a functor if it obeys the functor laws. It's easy, however, to come up with a counter-example that demonstrates that <code>Select</code> violates the second functor law. </p> <p> Consider a pair of conversion methods between <code>string</code> and <code>DateTimeOffset</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">DateTimeOffset</span>&nbsp;ParseDateTime(<span style="color:blue;">string</span>&nbsp;s) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">DateTimeOffset</span>&nbsp;dt; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(<span style="color:#2b91af;">DateTimeOffset</span>.TryParse(s,&nbsp;<span style="color:blue;">out</span>&nbsp;dt)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;dt; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:#2b91af;">DateTimeOffset</span>.MinValue; } <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">string</span>&nbsp;FormatDateTime(<span style="color:#2b91af;">DateTimeOffset</span>&nbsp;dt) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;dt.ToString(<span style="color:#a31515;">&quot;yyyy&#39;-&#39;MM&#39;-&#39;dd&#39;T&#39;HH&#39;:&#39;mm&#39;:&#39;sszzz&quot;</span>); }</pre> </p> <p> The first method, <code>ParseDateTime</code>, converts a <code>string</code> into a <code>DateTimeOffset</code> value. It tries to parse the input, and returns the corresponding <code>DateTimeOffset</code> value if this is possible; for all other input values, it simply returns <code>DateTimeOffset.MinValue</code>. You may dislike how the method deals with input values it can't parse, but that's not important. In order to prove that sets aren't functors, I just need <em>one</em> counter-example, and the one I'll pick will not involve unparseable strings. </p> <p> The <code>FormatDateTime</code> method converts any <code>DateTimeOffset</code> value to an <a href="https://en.wikipedia.org/wiki/ISO_8601">ISO 8601 string</a>. </p> <p> The <code>DateTimeOffset</code> type is the interesting piece of the puzzle. In case you're not intimately familiar with it, a <code>DateTimeOffset</code> value contains a date, a time, and a time-zone offset. You can, for example create one like this: </p> <p> <pre>&gt; <span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTimeOffset</span>(2018,&nbsp;4,&nbsp;17,&nbsp;15,&nbsp;9,&nbsp;55,&nbsp;<span style="color:#2b91af;">TimeSpan</span>.FromHours(2)) [17.04.2018 15:09:55 +02:00]</pre> </p> <p> This represents April 17, 2018, at 15:09:55 at UTC+2. You can convert that value to UTC: </p> <p> <pre>&gt; <span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTimeOffset</span>(2018,&nbsp;4,&nbsp;17,&nbsp;15,&nbsp;9,&nbsp;55,&nbsp;<span style="color:#2b91af;">TimeSpan</span>.FromHours(2)).ToUniversalTime() [17.04.2018 13:09:55 +00:00]</pre> </p> <p> This value clearly contains different constituent elements, but it does represent the same instant in time. This is how <code>DateTimeOffset</code> implements <code>Equals</code>. These two object are considered equal, as the following test will demonstrate. </p> <p> In a sense, you could argue that there's some sense in implementing equality for <code>DateTimeOffset</code> in that way, but this unusual behaviour provides just the counter-example that demonstrates that sets aren't functors: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SetViolatesSecondFunctorLaw() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;x&nbsp;=&nbsp;<span style="color:#a31515;">&quot;2018-04-17T13:05:28+02:00&quot;</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;y&nbsp;=&nbsp;<span style="color:#a31515;">&quot;2018-04-17T11:05:28+00:00&quot;</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(ParseDateTime(x),&nbsp;ParseDateTime(y)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;set&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HashSet</span>&lt;<span style="color:blue;">string</span>&gt;&nbsp;{&nbsp;x,&nbsp;y&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;l&nbsp;=&nbsp;set.Select(ParseDateTime).Select(FormatDateTime); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;r&nbsp;=&nbsp;set.Select(s&nbsp;=&gt;&nbsp;FormatDateTime(ParseDateTime(s))); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.False(l.SetEquals(r)); }</pre> </p> <p> This passing test provides the required counter-example. It first creates two ISO 8601 representations of the same instant. As the Guard Assertion demonstrates, the corresponding <code>DateTimeOffset</code> values are considered equal. </p> <p> In <a href="http://blog.ploeh.dk/2013/06/24/a-heuristic-for-formatting-code-according-to-the-aaa-pattern">the <em>act</em> phase</a>, the test creates a <code>set</code> of these two strings. It then performs two round-trips over <code>DateTimeOffset</code> and back to <code>string</code>. The second functor law states that it shouldn't matter whether you do it in one or two steps, but it does. <code>Assert.False</code> passes because <code>l</code> is <em>not</em> equal to <code>r</code>. Q.E.D. </p> <h3 id="f392310c11984d08a31bf6456849dd01"> An illustration <a href="#f392310c11984d08a31bf6456849dd01" title="permalink">#</a> </h3> <p> The problem is that sets only contain one element of each value, and due to the way that <code>DateTimeOffset</code> interprets equality, two values that both represent the same instant are collapsed into a single element when taking an intermediary step. You can illustrate it like this: </p> <p> <img src="/content/binary/set-violating-second-functor-law.png" alt="Diagram illustrating the above counter-example."> </p> <p> In this illustration, I've hidden the date behind an ellipsis in order to improve clarity. The date segments are irrelevant in this example, since they're all identical. </p> <p> You start with a set of two <code>string</code> values. These are obviously different, so the set contains two elements. When you map the set using the <code>ParseDateTime</code> function, you get two <code>DateTimeOffset</code> values that .NET considers equal. For that reason, <code>HashSet&lt;DateTimeOffset&gt;</code> considers the second value redundant, and ignores it. Therefore, the intermediary set contains only a single element. When you map that set with <code>FormatDateTime</code>, there's only a single element to translate, so the final set contains only a single <code>string</code> value. </p> <p> On the other hand, when you map the input set without an intermediary set, each <code>string</code> value is first converted into a <code>DateTimeOffset</code> value, and then immediately thereafter converted back to a <code>string</code> value. Since the two resulting strings are different, the resulting set contains two values. </p> <p> Which of these paths is correct, then? Both of them. That's the problem. When considering the semantics of sets, both translations produce correct results. Since the results diverge, however, the translation isn't a functor. </p> <h3 id="ee52a36b611b40c5a7d015bea3cbf1dc"> Summary <a href="#ee52a36b611b40c5a7d015bea3cbf1dc" title="permalink">#</a> </h3> <p> A functor must not only preserve the structure of the data container, but also of functions. The functor laws express that a translation of functions preserves the structure of how the functions compose, in addition to preserving the structure of the containers. Mapping a set doesn't preserve those structures, and that's the reason that sets aren't functors. </p> <h3 id="649aceb6a241450abc861ec63f34ff0a"> P.S. <a href="#649aceb6a241450abc861ec63f34ff0a" title="permalink">#</a> </h3> <p> <strong>2019-01-09.</strong> There's been some controversy around this post, and more than one person has pointed out to me that the underlying reason that the functor laws are violated in the above example is because <code>DateTimeOffset</code> behaves oddly. Specifically, its <code>Equals</code> implementation breaks the <em>substitution property</em> of equality. See e.g. <a href="https://giacomociti.github.io">Giacomo Citi</a>'s <a href="https://giacomociti.github.io/2019/01/02/Abstract-types-are-more-equal.html">response</a> for details. </p> <p> The term <em>functor</em> originates from <a href="https://en.wikipedia.org/wiki/Category_theory">category theory</a>, and I don't claim to be an expert on that topic. It's unclear to me if the underlying concept of <em>equality</em> is explicitly defined in category theory, but it wouldn't surprise me if it is. If that definition involves the substitution property, then the counter-example presented here says nothing about Set as a functor, but rather that <code>DateTimeOffset</code> has unlawful equality behaviour. </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 consider <a href="http://blog.ploeh.dk/support">supporting it</a>. Mark Seemann http://blog.ploeh.dk/2018/12/03/set-is-not-a-functor The Test Data Generator applicative functor http://blog.ploeh.dk/2018/11/26/the-test-data-generator-applicative-functor/ Mon, 26 Nov 2018 07:24:00 UTC <div id="post"> <p> <em>Test Data Generator modelled as an applicative functor, with examples in C# and 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>. It shows yet another example of an applicative functor. I tend to think of applicative functors as an abstraction of 'combinations' of values and functions, but this is most evident for lists and other collections. Even so, I think that the intuition also holds for <a href="http://blog.ploeh.dk/2018/10/29/the-maybe-applicative-functor">Maybe as an applicative functor</a> as well as <a href="http://blog.ploeh.dk/2018/11/05/applicative-validation">validation as an applicative functor</a>. This is also the case for the <a href="http://blog.ploeh.dk/2017/09/18/the-test-data-generator-functor">Test Data Generator functor</a>. </p> <h3 id="bc5212f7353f44f793ed20399d359bfe"> Applicative generator in C# <a href="#bc5212f7353f44f793ed20399d359bfe" title="permalink">#</a> </h3> <p> In a <a href="http://blog.ploeh.dk/2017/09/18/the-test-data-generator-functor">previous article</a>, you saw how to implement a Test Data Generator as a functor in C#. The core class is this <code>Generator&lt;T&gt;</code> class: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">Generator</span>&lt;<span style="color:#2b91af;">T</span>&gt; { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">Random</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;&nbsp;generate; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;Generator(<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">Random</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;&nbsp;generate) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(generate&nbsp;==&nbsp;<span style="color:blue;">null</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">throw</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ArgumentNullException</span>(<span style="color:blue;">nameof</span>(generate)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.generate&nbsp;=&nbsp;generate; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Generator</span>&lt;<span style="color:#2b91af;">T1</span>&gt;&nbsp;Select&lt;<span style="color:#2b91af;">T1</span>&gt;(<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">T1</span>&gt;&nbsp;f) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(f&nbsp;==&nbsp;<span style="color:blue;">null</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">throw</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ArgumentNullException</span>(<span style="color:blue;">nameof</span>(f)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">Random</span>,&nbsp;<span style="color:#2b91af;">T1</span>&gt;&nbsp;newGenerator&nbsp;=&nbsp;r&nbsp;=&gt;&nbsp;f(<span style="color:blue;">this</span>.generate(r)); &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;">Generator</span>&lt;<span style="color:#2b91af;">T1</span>&gt;(newGenerator); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">T</span>&nbsp;Generate(<span style="color:#2b91af;">Random</span>&nbsp;random) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(random&nbsp;==&nbsp;<span style="color:blue;">null</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">throw</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ArgumentNullException</span>(<span style="color:blue;">nameof</span>(random)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">this</span>.generate(random); &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> This is merely repetition from the earlier article. </p> <p> <code>Generator&lt;T&gt;</code> is already a functor, but you can make it an <em>applicative</em> functor by adding an extension method like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Generator</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;">Generator</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;">Generator</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;generator) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(selectors&nbsp;==&nbsp;<span style="color:blue;">null</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">throw</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ArgumentNullException</span>(<span style="color:blue;">nameof</span>(selectors)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(generator&nbsp;==&nbsp;<span style="color:blue;">null</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">throw</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ArgumentNullException</span>(<span style="color:blue;">nameof</span>(generator)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">Random</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;newGenerator&nbsp;=&nbsp;r&nbsp;=&gt; &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;f&nbsp;=&nbsp;selectors.Generate(r); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;x&nbsp;=&nbsp;generator.Generate(r); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;f(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;">Generator</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;(newGenerator); }</pre> </p> <p> The <code>Apply</code> function combines a generator of functions with a generator of values. Given these two generators, it defines a closure over both, and packages that function in a new generator object. </p> <h3 id="58282543d8c4409cb596547e131bf249"> CPR example <a href="#58282543d8c4409cb596547e131bf249" title="permalink">#</a> </h3> <p> When is it interesting to combine a randomly selected function with a randomly generated value? Here's an example. </p> <p> In Denmark, everyone has a <a href="https://en.wikipedia.org/wiki/Personal_identification_number_(Denmark)">personal identification number</a>, in Danish called <em>CPR-nummer</em> (<em>CPR number</em>). It's somewhat comparable to the <a href="https://en.wikipedia.org/wiki/Social_Security_number">U.S. Social Security number</a>, but surely more Orwellian. </p> <p> CPR numbers have a simple format: <code>DDMMYY-SSSS</code>, where the first six digits indicate a person's birth date, and the last four digits are a sequence number. An example could be <code>010203-1234</code>, which indicates a woman born February 1, 1903. Assume that you're writing a system that has to accept CPR numbers as input. You've represented CPR number as a class called <code>CprNumber</code>, and you've already written a parser, but now it turns out that sometimes users enter slightly malformed data. </p> <p> Sometimes users copy and paste CPR numbers from other sources, and occasionally, they inadvertently include a leading or trailing space. Other users forget the dash between the birth date and the sequence number. In other words, sometimes you receive input like <code>"050301-4231 "</code> or <code>"1211993321"</code>. </p> <p> Using your fancy Test Data Generator, you'd like to write a test that verifies that your parser follows <a href="https://en.wikipedia.org/wiki/Robustness_principle">Postel's law</a>: <em>Be conservative in what you send, be liberal in what you accept</em>. </p> <p> Assume that you already have a generator that can produce valid <code>CprNumber</code> objects. One test strategy, then, could be to generate a valid <code>CprNumber</code> object, convert it to a string, slightly taint or mangle that string, and then attempt to parse the tainted string. </p> <p> There's more than one way to taint a valid CPR number string. You could, for example, define three functions like these: </p> <p> <pre><span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;addLeadingSpace&nbsp;=&nbsp;s&nbsp;=&gt;&nbsp;<span style="color:#a31515;">&quot;&nbsp;&quot;</span>&nbsp;+&nbsp;s; <span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;addTrailingSpace&nbsp;=&nbsp;s&nbsp;=&gt;&nbsp;s&nbsp;+&nbsp;<span style="color:#a31515;">&quot;&nbsp;&quot;</span>; <span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;removeDash&nbsp;=&nbsp;s&nbsp;=&gt;&nbsp;s.Replace(<span style="color:#a31515;">&quot;-&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;&quot;</span>);</pre> </p> <p> The first function adds a leading space to a string, the second adds a trailing space, and the third removes all dashes it finds. Can you make a generator out of those functions? </p> <p> Yes, you can, with this common general-purpose method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Generator</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;Elements&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:blue;">params</span>&nbsp;<span style="color:#2b91af;">T</span>[]&nbsp;alternatives) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(alternatives&nbsp;==&nbsp;<span style="color:blue;">null</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">throw</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ArgumentNullException</span>(<span style="color:blue;">nameof</span>(alternatives)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Generator</span>&lt;<span style="color:#2b91af;">T</span>&gt;(r&nbsp;=&gt; &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;index&nbsp;=&nbsp;r.Next(alternatives.Length); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;alternatives[index]; &nbsp;&nbsp;&nbsp;&nbsp;}); }</pre> </p> <p> This generator randomly selects a value from an array of values, with equal probability. It's a common method, because you'll find equivalent functions in <a href="https://en.wikipedia.org/wiki/QuickCheck">QuickCheck</a>, <a href="https://fscheck.github.io/FsCheck">FsCheck</a>, and <a href="https://github.com/hedgehogqa/fsharp-hedgehog">Hedgehog</a> (where it's called <code>item</code>). </p> <p> You can write the entire test like this: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;ParseCorrectlyHandlesTaintedInput() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;addLeadingSpace&nbsp;=&nbsp;s&nbsp;=&gt;&nbsp;<span style="color:#a31515;">&quot;&nbsp;&quot;</span>&nbsp;+&nbsp;s; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;addTrailingSpace&nbsp;=&nbsp;s&nbsp;=&gt;&nbsp;s&nbsp;+&nbsp;<span style="color:#a31515;">&quot;&nbsp;&quot;</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;removeDash&nbsp;=&nbsp;s&nbsp;=&gt;&nbsp;s.Replace(<span style="color:#a31515;">&quot;-&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;&quot;</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Generator</span>&lt;<span style="color:#2b91af;">Func</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;&gt;&nbsp;tainters&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Gen</span>.Elements( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;addLeadingSpace, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;addTrailingSpace, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;removeDash, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s&nbsp;=&gt;&nbsp;addLeadingSpace(removeDash(s)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s&nbsp;=&gt;&nbsp;addTrailingSpace(addLeadingSpace(s))); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;g&nbsp;=&nbsp;tainters.Apply(<span style="color:#2b91af;">Gen</span>.CprNumber.Select(n&nbsp;=&gt;&nbsp;n.ToString())); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;rnd&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Random</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;candidate&nbsp;=&nbsp;g.Generate(rnd); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">CprNumber</span>&nbsp;dummy; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;actual&nbsp;=&nbsp;<span style="color:#2b91af;">CprNumber</span>.TryParse(candidate,&nbsp;<span style="color:blue;">out</span>&nbsp;dummy); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.True(actual); }</pre> </p> <p> You first define the three 'tainting' functions, and then create the <code>tainters</code> generator. Notice that this generator not only contains the three functions, but also combinations of these functions. I didn't include all possible combinations of functions, but in <a href="http://blog.ploeh.dk/2018/10/22/applicative-combinations-of-functions">an earlier article</a>, you saw how to do just that. </p> <p> <code>Gen.CprNumber</code> is a <code>Generator&lt;CprNumber&gt;</code>, while you actually need a <code>Generator&lt;string&gt;</code>. Since <code>Generator&lt;T&gt;</code> is a functor, you can easily map <code>Gen.CprNumber</code> with its <code>Select</code> method. </p> <p> You now have a <code>Generator&lt;Func&lt;string, string&gt;&gt;</code> (<code>tainters</code>) and a <code>Generator&lt;string&gt;</code>, so you can combine them using <code>Apply</code>. The result <code>g</code> is another <code>Generator&lt;string&gt;</code> that generates 'tainted', but still valid, CPR string representations. </p> <p> In order to keep the example as simple as possible, the <em>Arrange</em> and <em>Assert</em> phases of the test only checks if <code>CprNumber.TryParse</code> returns <code>true</code>. A better test would also verify that the resulting <code>CprNumber</code> value was correct, but in order to do that, you need to keep the originally generated <code>CprNumber</code> object around so that you can compare this expected value to the actual value. This is possible, but complicates the code, so I left it out of the example. </p> <h3 id="f3d0db787eaf4a018a593daaa78f9e17"> F# Hedgehog <a href="#f3d0db787eaf4a018a593daaa78f9e17" title="permalink">#</a> </h3> <p> You can translate the above unit test to F#, using <a href="https://github.com/hedgehogqa/fsharp-hedgehog">Hedgehog</a> as a property-based testing library. Another option would be <a href="https://fscheck.github.io/FsCheck">FsCheck</a>. Without further ado, I present to you the test: </p> <p> <pre>[&lt;<span style="color:teal;">Fact</span>&gt;] <span style="color:blue;">let</span>&nbsp;<span style="color:navy;">``Correctly&nbsp;parses&nbsp;tainted&nbsp;text``</span>&nbsp;()&nbsp;=&nbsp;<span style="color:teal;">Property</span>.<span style="color:navy;">check</span>&nbsp;&lt;|&nbsp;<span style="color:blue;">property</span>&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:navy;">removeDash</span>&nbsp;(s&nbsp;:&nbsp;<span style="color:teal;">string</span>)&nbsp;=&nbsp;s.<span style="color:navy;">Replace</span>&nbsp;(<span style="color:#a31515;">&quot;-&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;&quot;</span>) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;candidate&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:teal;">Gen</span>.<span style="color:navy;">item</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:navy;">sprintf</span>&nbsp;<span style="color:#a31515;">&quot;&nbsp;</span><span style="color:teal;">%s</span><span style="color:#a31515;">&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:navy;">sprintf</span>&nbsp;<span style="color:#a31515;">&quot;</span><span style="color:teal;">%s</span><span style="color:#a31515;">&nbsp;&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:navy;">removeDash</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:navy;">removeDash</span>&nbsp;&gt;&gt;&nbsp;<span style="color:navy;">sprintf</span>&nbsp;<span style="color:#a31515;">&quot;&nbsp;</span><span style="color:teal;">%s</span><span style="color:#a31515;">&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:navy;">sprintf</span>&nbsp;<span style="color:#a31515;">&quot;&nbsp;</span><span style="color:teal;">%s</span><span style="color:#a31515;">&nbsp;&quot;</span>] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;*&gt;&nbsp;<span style="color:teal;">Gen</span>.<span style="color:navy;">map</span>&nbsp;<span style="color:navy;">string</span>&nbsp;<span style="color:teal;">Gen</span>.cprNumber &nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;<span style="color:teal;">Cpr</span>.<span style="color:navy;">tryParse</span>&nbsp;candidate &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:navy;">test</span>&nbsp;<span style="background:yellow;">&lt;@&nbsp;</span><span style="background:yellow;">actual</span><span style="background:yellow;">&nbsp;</span><span style="background:yellow;">|&gt;</span><span style="background:yellow;">&nbsp;</span><span style="color:teal;background:yellow;">Option</span><span style="background:yellow;">.</span><span style="color:navy;background:yellow;">isSome</span><span style="background:yellow;">&nbsp;@&gt;</span>&nbsp;}</pre> </p> <p> As I already mentioned in passing, Hedgehog's equivalent to the above <code>Elements</code> method is called <code>Gen.item</code>. Here, you see the same five functions as above passed in a list. Thanks to partial application and type inference, an expression like <code>sprintf " %s"</code> is already a function of the type <code>string -&gt; string</code>, as is <code>removeDash</code>. For the last of the five functions, I found it easier to write (and read) <code>sprintf " %s "</code> instead of <code>sprintf " %s" &gt;&gt; sprintf "%s "</code>. </p> <p> Equivalent to the C# example, <code>Gen.cprNumber</code> is a <code>Gen&lt;CprNumber&gt;</code>, so mapping it with the built-in <code>string</code> function translates it to a <code>Gen&lt;string&gt;</code>. </p> <p> Hedgehog already includes an <code>&lt;*&gt;</code> operator; <code>Gen</code> is an applicative functor. </p> <h3 id="f7c420f0d4e641a384749187d7bbf217"> Summary <a href="#f7c420f0d4e641a384749187d7bbf217" title="permalink">#</a> </h3> <p> Applicative functors are fairly common. I find it intuitive to think of them as an abstraction of how to make combinations of things. Modelling a Test Data Generator as an applicative functor enables you to create random combinations of functions and values. </p> <p> While working on the Hedgehog example, I discovered another great use of <code>option</code> as an applicative functor. You can see this in the next article. </p> <p> <strong>Next: </strong> <a href="http://blog.ploeh.dk/2018/12/10/danish-cpr-numbers-in-f">Danish CPR numbers in F#</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="http://blog.ploeh.dk/support">supporting it</a>. Mark Seemann http://blog.ploeh.dk/2018/11/26/the-test-data-generator-applicative-functor Functional architecture: a definition http://blog.ploeh.dk/2018/11/19/functional-architecture-a-definition/ Mon, 19 Nov 2018 09:44:00 UTC <div id="post"> <p> <em>How do you know whether your software architecture follows good functional programming practices? Here's a way to tell.</em> </p> <p> Over the years, I've written articles on functional architecture, including <a href="http://blog.ploeh.dk/2016/03/18/functional-architecture-is-ports-and-adapters">Functional architecture is Ports and Adapters</a>, given <a href="https://vimeo.com/180287057">conference talks</a>, and even produced <a href="http://blog.ploeh.dk/functional-architecture-with-fsharp">a Pluralsight course</a> on the topic. How should we define <em>functional architecture</em>, though? </p> <p> People sometimes ask me about their <a href="https://fsharp.org">F#</a> code: <em>How do I know that my F# code is functional?</em> </p> <p> Please permit me a little detour before I answer that question. </p> <h3 id="f752f048f6ef445d8625f1710317620b"> What's the definition of object-oriented design? <a href="#f752f048f6ef445d8625f1710317620b" title="permalink">#</a> </h3> <p> Object-oriented design (OOD) has been around for decades; at least since the nineteen-sixties. Sometimes people get into discussions about whether or not a particular design is good object-oriented design. I know, since I've found myself in such discussions more than once. </p> <p> These discussions usually die out without resolution, because it seems that no-one can provide a sufficiently rigorous definition of OOD that enables people to determine an outcome. One thing's certain, though, so I'd like to posit this corollary to <a href="https://en.wikipedia.org/wiki/Godwin%27s_law">Godwin's law</a>: <blockquote> As a discussion about OOD grows longer, the probability of a comparison involving Alan Kay approaches 1. </blockquote> Not that I, in any way, wish to suggest any logical relationship between <a href="https://en.wikipedia.org/wiki/Alan_Kay">Alan Kay</a> and Hitler, but in a discussion about OOD, sooner or later someone states: <blockquote> "That's not what Alan Kay had in mind!" </blockquote> That may be true, even. </p> <p> My problem with that assertion is that I've never been able to figure out exactly what Alan Kay had in mind. It's something that involves message-passing and <a href="https://en.wikipedia.org/wiki/Smalltalk">Smalltalk</a>, and conceivably, the best modern example of this style of programming might be <a href="https://www.erlang.org">Erlang</a> (often, ironically, touted as a functional programming language). </p> <p> This doesn't seem to be a good basis for determining whether or not something is object-oriented. </p> <p> In any case, despite what Alan Kay had in mind, that wasn't the object-oriented programming we got. While <a href="https://en.wikipedia.org/wiki/Eiffel_(programming_language)">Eiffel</a> is in many ways a strange programming language, the philosophy of OOD presented in <a href="http://amzn.to/1claOin">Object-Oriented Software Construction</a> feels, to me, like something from which <a href="https://www.java.com">Java</a> could develop. </p> <p> I'm not aware of the detailed history of Java, but the spirit of the language seems more compatible with Bertrand Meyer's vision than with Alan Kay's. </p> <p> Subsequently, C# would hardly look the way it does had it not been for Java. </p> <p> The OOD we got wasn't the OOD originally envisioned. To make matters worse, the OOD we did get seems to be driven by unclear principles. Yes, there's the idea about encapsulation, but while Meyer had some very specific ideas about design-by-contract, that was the distinguishing trait of his vision that <em>didn't</em> make the transition to Java or C#. </p> <p> It's not clear what OOD is, but I think we can do better when it comes to functional programming (FP). </p> <h3 id="305ccccf2de84354bdb68b5b80d34fc9"> Referential transparency <a href="#305ccccf2de84354bdb68b5b80d34fc9" title="permalink">#</a> </h3> <p> It's possible to pinpoint what FP is to a degree not possible with OOD. Some people may be uncomfortable with the following definition; I don't claim that this is a generally accepted definition. It does have, however, the advantage that it's precise and supports <a href="https://en.wikipedia.org/wiki/Falsifiability">falsification</a>. </p> <p> The foundation of FP is <a href="https://en.wikipedia.org/wiki/Referential_transparency">referential transparency</a>. It's the idea that, for an expression, the left- and right-hand sides of the equal sign are truly equal: </p> <p> <pre>two = 1 + 1</pre> </p> <p> In <a href="https://www.haskell.org">Haskell</a>, this is enforced by the compiler. The <code>=</code> operator truly implies equality. To be clear, this isn't the case in C#: </p> <p> <pre><span style="color:blue;">var</span>&nbsp;two&nbsp;=&nbsp;1&nbsp;+&nbsp;1;</pre> </p> <p> In C#, Java, and other imperative languages, the <code>=</code> implies <em>assignment</em>, not equality. Here, <code>two</code> can change, despite the absurdity of the claim. </p> <p> When code is referentially transparent, then you can substitute the expression on the right-hand side with the symbol on the left-hand side. This seems obvious when we consider addition of two numbers, but becomes less clear when we consider function invocation: </p> <p> <pre>i = findBestNumber [42, 1337, 2112, 90125]</pre> </p> <p> In Haskell, functions are referentially transparent. You don't know exactly what <code>findBestNumber</code> does, but you do know that you can substitute <code>i</code> with <code>findBestNumber [42, 1337, 2112, 90125]</code>, or vice versa. </p> <p> In order for a function to be referentially transparent (also known as a <a href="https://en.wikipedia.org/wiki/Pure_function">pure function</a>), it must have two properties: <ul> <li>It must always return the same output for the same input. We call this quality <em>determinism</em>.</li> <li>It must have no side effects.</li> </ul> As far as I can tell, all else in FP follows from this definition. For example, values must be immutable, because if they aren't, you could mutate them, and that would count as a side effect. </p> <p> The reason I prefer this definition is that it supports falsification. You can assert that a function or value is pure; all it takes is a single counter-example to prove that it's not. A counter-example can be either an input value that doesn't always produce the same return value, or a function call that produces a side effect. </p> <p> I'm not aware of any other definition that offers similar decision power. </p> <h3 id="43505c00cc25416db2b47a89912fd731"> IO <a href="#43505c00cc25416db2b47a89912fd731" title="permalink">#</a> </h3> <p> All software produces side effects: Changing a pixel on a monitor is a side effect. Writing a byte to disk is a side effect. Transmitting a bit over a network is a side effect. It seems that it'd be impossible to interact with pure functions, and indeed, it is, without some sort of affordance for impurity. </p> <p> Haskell resolves this problem with the <code>IO</code> monad, but the purpose of this article isn't to serve as an introduction to Haskell, monads, or <code>IO</code>. The point is only that in FP, you need some sort of 'wormhole' that will enable you to interact with the real world. There's no way around that, but logically, the rules still apply. Pure functions must stay deterministic and free of side effects. </p> <p> It follows that you have two groups of operations: impure activities and pure functions. </p> <p> <img src="/content/binary/impure-actions-pure-functions-no-arrows.png" alt="Two sets: the set of impure activities and the set of pure functions."> </p> <p> While there are rules for pure functions, those rules still allow for interaction. One pure function can call another pure function. Such an interaction doesn't change the properties of any of those functions. Both caller and callee remain side-effect-free and deterministic. </p> <p> <img src="/content/binary/impure-actions-pure-functions-pure-arrows.png" alt="Set of impure activities and set of pure functions. The pure functions now have arrows between them."> </p> <p> The impure activities can also interact. No rules apply to them: </p> <p> <img src="/content/binary/impure-actions-pure-functions-impure-and-pure-arrows.png" alt="Sets of impure activities and pure functions. Both sets now have internal arrows."> </p> <p> Finally, since no rules apply to impure activities, they can invoke pure functions: </p> <p> <img src="/content/binary/impure-actions-pure-functions-all-valid-arrows.png" alt="Sets of impure activities and pure functions, now also with arrows going from impure to pure."> </p> <p> Impure activities are unbound by rules, so they can do anything they need to do, including painting pixels, writing to files, or calling pure functions. A pure function is deterministic and has no side effects. Those properties don't change just because the result is subsequently displayed on a screen. </p> <p> The fourth combination of arrows is, however, illegal. <blockquote> A pure function can't invoke an impure activity. </blockquote> If it did, it would either transitively produce a side effect or non-deterministic behaviour. </p> <p> This is the rule of functional architecture. You can also explain it with a table: <table> <col> <col> <colgroup span="2"></colgroup> <thead> <tr> <td colspan="2" rowspan="2"></td> <th colspan="2" scope="colgroup">Callee</th> </tr> <tr> <th scope="col">Impure</th> <th scope="col">Pure</th> </tr> </thead> <tbody> <tr> <th rowspan="2" scope="rowgroup">Caller</th> <th scope="row">Impure</th> <td><span style="color:green">Valid</span></td> <td><span style="color:green">Valid</span></td> </tr> <tr> <th scope="row">Pure</th> <td><span style="color:red">Invalid</span></td> <td><span style="color:green">Valid</span></td> </tr> </tbody> </table> Let's call the above rule the <em>functional interaction law</em>: a pure function can't invoke an impure activity. A functional architecture, then, is a code base that obeys that law, and has a significant portion of pure code. </p> <p> Clearly, you can trivially obey the functional interaction law by writing exclusively impure code. In a sense, this is what you do by default in imperative programming languages. If you're familiar with Haskell, imagine writing an entire program in <code>IO</code>. That would be possible, but pointless. </p> <p> Thus, we need to add the qualifier that a significant part of the code base should consist of pure code. How much? The more, the better. Subjectively, I'd say significantly more than half the code base should be pure. I'm concerned, though, that stating a hard limit is as useful here <a href="http://blog.ploeh.dk/2015/11/16/code-coverage-is-a-useless-target-measure">as it is for code coverage</a>. </p> <h3 id="1009a90ea922424285e5f9a4bb30524e"> Tooling <a href="#1009a90ea922424285e5f9a4bb30524e" title="permalink">#</a> </h3> <p> How do you verify that you obey the functional interaction law? Unfortunately, in most languages the answer is that this requires painstaking analysis. This can be surprisingly tricky to get right. Consider this realistic F# example: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;createEmailNotification&nbsp;templates&nbsp;msg&nbsp;(user&nbsp;:&nbsp;UserEmailData)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;{&nbsp;SubjectLine&nbsp;=&nbsp;subjectTemplate;&nbsp;Content&nbsp;=&nbsp;contentTemplate&nbsp;}&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;templates &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;Map.tryFind&nbsp;user.Localization &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;Option.defaultValue&nbsp;(Map.find&nbsp;Localizations.english&nbsp;templates) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;r&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Templating.append &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Templating.replacementOfEnvelope&nbsp;msg) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Templating.replacementOfFlatRecord&nbsp;user) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;subject&nbsp;=&nbsp;Templating.run&nbsp;subjectTemplate&nbsp;r &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;content&nbsp;=&nbsp;Templating.run&nbsp;contentTemplate&nbsp;r &nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;RecipientUserId&nbsp;=&nbsp;user.UserId &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;EmailAddress&nbsp;=&nbsp;user.EmailAddress &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NotificationSubjectLine&nbsp;=&nbsp;subject &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NotificationText&nbsp;=&nbsp;content &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CreatedDate&nbsp;=&nbsp;DateTime.UtcNow &nbsp;&nbsp;&nbsp;&nbsp;}</pre> </p> <p> Is this a pure function? </p> <p> You may protest that this isn't a fair question, because you don't know what, say, <code>Templating.replacementOfFlatRecord</code> does, but that turns out to be irrelevant. The presence of <code>DateTime.UtcNow</code> makes the entire function impure, because getting the current date and time is non-deterministic. This trait is transitive, which means that any code that calls <code>createEmailNotification</code> is also going to be impure. </p> <p> That means that the purity of an expression like the following easily becomes obscure. </p> <p> <pre><span style="color:blue;">let</span>&nbsp;emailMessages&nbsp;=&nbsp;specificUsers&nbsp;|&gt;&nbsp;Seq.map&nbsp;(createEmailNotification&nbsp;templates&nbsp;msg)</pre> </p> <p> Is this a pure expression? In this case, we've just established that <code>createEmailNotification</code> is impure, so that wasn't hard to answer. The problem, however, is that the burden is on you, the code reader, to remember which functions are pure, and which ones aren't. In a large code base, this soon becomes a formidable endeavour. </p> <p> It'd be nice if there was a tool that could automatically check the functional interaction law. </p> <p> This is where many people in the functional programming community become uncomfortable about this definition of functional architecture. The only tools that I'm aware of that enforce the functional interaction law are a few programming languages, most notably Haskell (others exist, too). </p> <p> Haskell enforces the functional interaction law via its <code>IO</code> type. You can't use an <code>IO</code> value from within a pure function (a function that doesn't return <code>IO</code>). If you try, your code doesn't compile. </p> <p> I've personally used Haskell repeatedly to understand the limits of functional architecture, for example to establish that <a href="http://blog.ploeh.dk/2017/01/30/partial-application-is-dependency-injection">Dependency Injection isn't functional</a> because it makes everything impure. </p> <p> The overall lack of tooling, however, may make people uncomfortable, because it means that most so-called functional languages (e.g. F#, Erlang, <a href="https://elixir-lang.org/">Elixir</a>, and <a href="https://clojure.org">Clojure</a>) offer no support for validating or enforcing functional architecture. </p> <p> My own experience with writing entire applications in F# is that I frequently, inadvertently violate the functional interaction law somewhere deep in the bowels of my code. </p> <h3 id="8e33b2ffd51f46f18e38c5add37f1728"> Conclusion <a href="#8e33b2ffd51f46f18e38c5add37f1728" title="permalink">#</a> </h3> <p> What's functional architecture? I propose that it's code that obeys the functional architecture law, and that is made up of a significant portion of pure functions. </p> <p> This is a narrow definition. It excludes a lot of code bases that could easily be considered 'functional enough'. By the definition, I don't intend to denigrate fine programming languages like F#, Clojure, Erlang, etcetera. I personally find it a joy to write in F#, which is my default language choice for .NET programming. </p> <p> My motivation for offering this definition, albeit restrictive, is to avoid the OOD situation where it seems entirely subjective whether or not something is object-oriented. With the functional interaction law, we may conclude that most (non-Haskell) programs are probably not 'really' functional, but at least we establish an falsifiable ideal to strive for. </p> <p> This would enable us to look at, say, an F# code base and start discussing <em>how close to the ideal is it?</em> </p> <p> Ultimately, functional architecture isn't a goal in itself. It's a means to achieve an objective, such as a sustainable code base. I find that FP helps me keep a code base sustainable, but often, 'functional enough' is sufficient to accomplish that. </p> </div> <div id="comments"> <hr /> <h2 id="comments-header">Comments</h2> <div class="comment" id="ccf908a42b644b8b9bb2bf6bcbc25052"> <div class="comment-author"> <a href="https://github.com/MaxKot">Max Kiselev</a> </div> <div class="comment-content"> <p> Good idea of basing the definition on falsifiability! </p> <p> The createEmailNotification example makes me wonder though. If it is not a functional design, then what design it actually is? I mean it has to be some design and it does not looks like object-oriented or procedural one. </p> </div> <div class="comment-date">2018-11-20 21:36 UTC</div> </div> <div class="comment" id="6a4ca5d3da3e4a63a413982f589c384c"> <div class="comment-author"><a href="http://blog.ploeh.dk">Mark Seemann</a></div> <div class="comment-content"> <p> Max, thank you for writing. I'm not sure whether the assertion that it <em>has</em> to be some design or other is axiomatically obvious, but I suppose that we humans have an innate need to categorise things. </p> <p> Don Syme calls F# a <em>functional-first</em> language, and that epithet could easily apply to that style of programming as well. Other options could be <em>near-functional</em>, or perhaps, if we're in a slightly more academic mood, <em>quasi-functional</em>. </p> <p> In daily use, we'd probably still call code like that <em>functional</em>, and I don't think it'll cause much confusion. </p> <p> If I remember the history of programming correctly, the first attempts at functional programming didn't focus on referential transparency, but simply on the concept of functions as first-class language features, including lambda expressions and higher-order functions. The little I know of <a href="https://en.wikipedia.org/wiki/Lisp_(programming_language)">Lisp</a> corroborates that view on the history of functional programming. </p> <p> Only later (I think) did languages appear that make compile-time distinction between pure and impure code. </p> <p> My purpose with this article wasn't to exclude a large number of languages or code bases from being functional, but just to offer a falsifiable test that we can use for evaluation purposes, if we're ever in doubt. This is something that I feel is sorely missing from the object-oriented debate, and while I can't think of a way to remedy the OOD situation, I hope that the present definition of functional architecture presents firmer ground upon which to have a debate. </p> </div> <div class="comment-date">2018-11-21 6:42 UTC</div> </div> <div class="comment" id="902887b4a1954daf8be09e35ce685fbb"> <div class="comment-author"><a href="https://github.com/wachulski">Marcin Wachulski</a></div> <div class="comment-content"> <p> Thank you for your definition that forms good grounds for reasoning about functional property of code. I remember some people say that even C# is functional as it allows for <em>delegates</em>. Several thoughts: </p> <p> 1. Remember <a href="https://docs.microsoft.com/en-us/dotnet/api/system.diagnostics.contracts.pureattribute?view=netcore-2.1">[Pure]</a> attribute and CodeContracts? It aided the purpose of defensive programming to hold pre/postconditions and invariants. I have this impression that both functional purity and defensive programming help us find ad-hoc quasi-mathematical proofs of code correctness after we load a codebase to our heads. It's way easier then to presume how it works and make changes. Of course it's not mathematical in the strict sense, but still - we tend to trust the code more (e.g. threading). I'm pretty sure unit tests belong to this family too. </p> <p> 2. Isn't the purity concept anywhere close to gateways (code that crosses the boundaries of program determinism control zone, e.g. IO, time, volatile memory)? It's especially evident while refactoring legacy code to make it unit testable. We often extract out infrastructure dependent parts (impure activities, e.g. DateTime.Now) for the other be deterministic (pure) and hence - testable. </p> <p> 3. Can the whole program/system be as pure as this: <pre>INPUT -> PURE_CODE -> OUTPUT</pre> I'm afraid not as it'd mean the pure code needed to know all the required input data upfront. That's impossible most of times. So, when it comes to measures, I'd argue that the number of pure code lines is enough to tell how pure the codebase is. I'd accompany this with e.g. percentile distribution of pure chunk length (functions/blocks of contingent im/purity etc.). E.g. I'd personally favour 1) over 2) in the following: <pre> 1. INPUT -> 3 x LONG_PURE_CHUNK + 2 x LONG_IMPURE_CHUNK -> OUTPUT 2. INPUT -> 10 x SHORT_PURE_CHUNK + 7 x SHORT_IMPURE_CHUNK -> OUTPUT </pre> </p> <p> 4. I'd love to see such tools too :) I believe the purity concept does not pertain only to FP nor OO and is related to the early foundational days of computer programming with mathematical proofs they had. </p> </div> <div class="comment-date">2018-11-23 10:51 UTC</div> </div> <div class="comment" id="82b14ead068b42698186710ba7bcf145"> <div class="comment-author"><a href="http://blog.ploeh.dk">Mark Seemann</a></div> <div class="comment-content"> <p> Marcin, thank you for writing. To be clear, you can perform side effects or non-deterministic behaviour in C# delegates, so delegates aren't guaranteed to be referentially transparent. In fact, <a href="http://blog.ploeh.dk/2018/01/22/function-isomorphisms">delegates, and particularly closures, are isomorphic to objects</a>. In C#, <a href="http://blog.ploeh.dk/2014/03/10/solid-the-next-step-is-functional">they even compile to classes</a>. </p> <p> I'm aware that some people think that they're doing functional programming when they use lambda expressions in C#, but I disagree. </p> <p> I'll see if I can address your other comments below. </p> <h3 id="c085eef3102d437ba9c6cbe3363b8976"> Re: 1. <a href="#c085eef3102d437ba9c6cbe3363b8976" title="permalink">#</a> </h3> <p> Some functions are certainly ad-hoc, while <a href="http://blog.ploeh.dk/2017/10/04/from-design-patterns-to-category-theory">others are grounded in mathematics</a>. I agree that pure functions 'fit better in your brain', mostly because it's clear that the only stimuli that can affect the outcome of the function is the input. Granted, if we imagine a concrete, ad-hoc function that takes 23 function arguments, we might still consider it bad code. Small functions, though, tend to be easy to reason about. </p> <p> I've previously written about the <a href="http://blog.ploeh.dk/2016/02/10/types-properties-software">relationship between types and tests</a>, and I believe that there's some sort of linearity in that relationship. The better the type system, the fewer tests you need. The weaker the type system, the more tests you need. It's no wonder that the unit testing culture related to languages like Ruby seems stronger than in the Haskell community. </p> <h3 id="405184fce774458ba8d3484c2580f322"> Re: 2. <a href="#405184fce774458ba8d3484c2580f322" title="permalink">#</a> </h3> <p> In my experience, most people make legacy code more testable by introducing some variation of Dependency Injection. This may enable you to control some otherwise non-deterministic behaviour from tests, but <a href="http://blog.ploeh.dk/2017/01/27/from-dependency-injection-to-dependency-rejection">it doesn't make the design more functional</a>. Those types of dependencies (e.g. on <code>DateTime.Now</code>) are inherently impure, and therefore they make everything that invokes them impure as well. The above <em>functional interaction law</em> excludes such a design from being considered functional. </p> <p> <a href="http://blog.ploeh.dk/2015/05/07/functional-design-is-intrinsically-testable">Functional code, on the other hand, is intrinsically testable</a>. Watch out for a future series of articles that show how to move an object-oriented architecture towards something both more functional, more sustainable, and more testable. </p> <h3 id="5201a19bec7b413ebb6e7ca3e2dfbc81"> Re: 3. <a href="#5201a19bec7b413ebb6e7ca3e2dfbc81" title="permalink">#</a> </h3> <p> A command-line utility <em>could</em> be as pure as you suggest, but most other programs will need to at least <ol> <li>load some more data from impure sources, such as files, databases, or the current time,</li> <li>run some pure functions,</li> <li>output the results to some impure destinations, such as files, databases, UI, email, and so on.</li> </ol> I call this type of architecture a <a href="http://blog.ploeh.dk/2017/02/02/dependency-rejection">pure-impure-pure sandwich</a>, and you can <a href="http://blog.ploeh.dk/2017/07/10/pure-interactions">often, but not always, structure your application code in that way</a>. </p> <h3 id="e8befe231edf474899477eb39074d8d0"> Re: 4. <a href="#e8befe231edf474899477eb39074d8d0" title="permalink">#</a> </h3> <p> I'm not sure I understand what you mean by that comment, but the mathematical proofs about computability pre-date computer programming. Gödel's work on recursive functions is from 1933, Church's work on lambda calculus is from 1936, and Turing's paper <em>On Computable Numbers, with an Application to the Entscheidungsproblem</em> is from later in 1936. Turing and Church later showed that <a href="https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis">all three definitions of computability are equivalent</a>. </p> <p> I don't know much about Gödel's work, but lambda calculus is defined entirely on the foundation of <em>functions</em>, while the Turing machines described in Turing's paper have nothing to do with functions in the mathematical sense. </p> <p> Mathematical functions are, however, referentially transparent. They're also <em>total</em>, meaning that they always return a result for any input in the function's domain. Due to the halting problem, a Turing-complete language can't guarantee that all functions are total. </p> </div> <div class="comment-date">2018-11-24 9:04 UTC</div> </div> </div> <hr> This blog is totally free, but if you like it, please consider <a href="http://blog.ploeh.dk/support">supporting it</a>. Mark Seemann http://blog.ploeh.dk/2018/11/19/functional-architecture-a-definition