ploeh blog https://blog.ploeh.dk danish software design en-us Mark Seemann Mon, 15 Jul 2019 07:37:11 UTC Mon, 15 Jul 2019 07:37:11 UTC Tester-Doer isomorphisms https://blog.ploeh.dk/2019/07/15/tester-doer-isomorphisms/ Mon, 15 Jul 2019 07:35:00 UTC <div id="post"> <p> <em>The Tester-Doer pattern is equivalent to the Try-Parse idiom; both are equivalent to Maybe.</em> </p> <p> This article is part of <a href="/2018/01/08/software-design-isomorphisms">a series of articles about software design isomorphisms</a>. An isomorphism is when a bi-directional lossless translation exists between two representations. Such translations exist between the <em>Tester-Doer</em> pattern and the <em>Try-Parse</em> idiom. Both can also be translated into operations that return <a href="/2018/03/26/the-maybe-functor">Maybe</a>. </p> <p> <img src="/content/binary/tester-doer-try-parse-maybe-isomorphism.png" alt="Isomorphisms between Tester-Doer, Try-Parse, and Maybe."> </p> <p> Given an implementation that uses one of those three idioms or abstractions, you can translate your design into one of the other options. This doesn't imply that each is of equal value. When it comes to composability, Maybe is superior to the two other alternatives, and Tester-Doer isn't thread-safe. </p> <h3 id="e95c8f5d7a6445139b58445d30498493"> Tester-Doer <a href="#e95c8f5d7a6445139b58445d30498493" title="permalink">#</a> </h3> <p> The first time I explicitly encountered the Tester-Doer pattern was in the <a href="https://amzn.to/2zXCCfH">Framework Design Guidelines</a>, which is from where I've taken the name. The pattern is, however, older. The idea that you can query an object about whether a given operation would be possible, and then you only perform it if the answer is affirmative, is almost a leitmotif in <a href="http://amzn.to/1claOin">Object-Oriented Software Construction</a>. Bertrand Meyer often uses linked lists and stacks as examples, but I'll instead use the example that Krzysztof Cwalina and Brad Abrams use: </p> <p> <pre><span style="color:#2b91af;">ICollection</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;numbers&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:blue;">if</span>&nbsp;(!numbers.IsReadOnly) &nbsp;&nbsp;&nbsp;&nbsp;numbers.Add(1);</pre> </p> <p> The idea with the Tester-Doer pattern is that you test whether an intended operation is legal, and only perform it if the answer is affirmative. In the example, you only add to the <code>numbers</code> collection if <code>IsReadOnly</code> is <code>false</code>. Here, <code>IsReadOnly</code> is the <em>Tester</em>, and <code>Add</code> is the <em>Doer</em>. </p> <p> As Jeffrey Richter points out in the book, this is a dangerous pattern: <blockquote> "The potential problem occurs when you have multiple threads accessing the object at the same time. For example, one thread could execute the test method, which reports that all is OK, and before the doer method executes, another thread could change the object, causing the doer to fail." </blockquote> In other words, the pattern isn't thread-safe. While multi-threaded programming was always supported in .NET, this was less of a concern when the guidelines were first published (2006) than it is today. The guidelines were in internal use in Microsoft years before they were published, and there wasn't many multi-core processors in use back then. </p> <p> Another problem with the Tester-Doer pattern is with discoverability. If you're looking for a way to add an element to a collection, you'd usually consider your search over once you find the <code>Add</code> method. Even if you wonder <em>Is this operation safe? Can I always add an element to a collection?</em> you <em>might</em> consider looking for a <code>CanAdd</code> method, but not an <code>IsReadOnly</code> property. Most people don't even ask the question in the first place, though. </p> <h3 id="08bc9f42d8f048119f952aa9c2d94b34"> From Tester-Doer to Try-Parse <a href="#08bc9f42d8f048119f952aa9c2d94b34" title="permalink">#</a> </h3> <p> You could refactor such a Tester-Doer API to a single method, which is both thread-safe and discoverable. One option is a variation of the Try-Parse idiom (discussed in detail below). Using it could look like this: </p> <p> <pre><span style="color:#2b91af;">ICollection</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;numbers&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:blue;">bool</span>&nbsp;wasAdded&nbsp;=&nbsp;numbers.TryAdd(1);</pre> </p> <p> In this special case, you may not need the <code>wasAdded</code> variable, because the original <code>Add</code> operation never returned a value. If, on the other hand, you do care whether or not the element was added to the collection, you'd have to figure out what to do in the case where the return value is <code>true</code> and <code>false</code>, respectively. </p> <p> Compared to the more idiomatic example of the Try-Parse idiom below, you may have noticed that the <code>TryAdd</code> method shown here takes no <code>out</code> parameter. This is because the original <code>Add</code> method returns <code>void</code>; there's nothing to return. From <a href="/2018/01/15/unit-isomorphisms">unit isomorphisms</a>, however, we know that <em>unit</em> is isomorphic to <code>void</code>, so we could, more explicitly, have defined a <code>TryAdd</code> method with this signature: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;TryAdd(<span style="color:#2b91af;">T</span>&nbsp;item,&nbsp;<span style="color:blue;">out</span>&nbsp;<span style="color:#2b91af;">Unit</span>&nbsp;unit)</pre> </p> <p> There's no point in doing this, however, apart from demonstrating that the isomorphism holds. </p> <h3 id="e246bcfabcab42e8b76e2b3e314174c4"> From Tester-Doer to Maybe <a href="#e246bcfabcab42e8b76e2b3e314174c4" title="permalink">#</a> </h3> <p> You can also refactor the add-to-collection example to return a Maybe value, although in this degenerate case, it makes little sense. If you automate the refactoring process, you'd arrive at an API like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Unit</span>&gt;&nbsp;TryAdd(<span style="color:#2b91af;">T</span>&nbsp;item)</pre> </p> <p> Using it would look like this: </p> <p> <pre><span style="color:#2b91af;">ICollection</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;numbers&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Unit</span>&gt;&nbsp;m&nbsp;=&nbsp;numbers.TryAdd(1);</pre> </p> <p> The contract is consistent with what Maybe implies: You'd get an empty <code>Maybe&lt;Unit&gt;</code> object if the <em>add</em> operation 'failed', and a populated <code>Maybe&lt;Unit&gt;</code> object if the <em>add</em> operation succeeded. Even in the populated case, though, the value contained in the Maybe object would be <em>unit</em>, which carries no further information than its existence. </p> <p> To be clear, this isn't close to a proper functional design because all the interesting action happens as a side effect. Does the design have to be functional? No, it clearly isn't in this case, but Maybe is a concept that originated in functional programming, so you could be misled to believe that I'm trying to pass this particular design off as functional. It's not. </p> <p> A functional version of this API could look like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">ICollection</span>&lt;<span style="color:#2b91af;">T</span>&gt;&gt;&nbsp;TryAdd(<span style="color:#2b91af;">T</span>&nbsp;item)</pre> </p> <p> An implementation wouldn't mutate the object itself, but rather return a new collection with the added item, in case that was possible. This is, however, always possible, because you can always concatenate <code>item</code> to the front of the collection. In other words, this particular line of inquiry is increasingly veering into the territory of the absurd. This isn't, however, a counter-example of my proposition that the isomorphism exists; it's just a result of the initial example being degenerate. </p> <h3 id="9817f0d35d99428f93c38cab9fabc9ad"> Try-Parse <a href="#9817f0d35d99428f93c38cab9fabc9ad" title="permalink">#</a> </h3> <p> Another idiom described in the Framework Design Guidelines is the Try-Parse idiom. This seems to be a coding idiom more specific to the .NET framework, which is the reason I call it an <em>idiom</em> instead of a <em>pattern</em>. (Perhaps it is, after all, a pattern... I'm sure many of my readers are better informed about how problems like these are solved in other languages, and can enlighten me.) </p> <p> A better name might be <em>Try-Do</em>, since the idiom doesn't have to be constrained to parsing. The example that Cwalina and Abrams supply, however, relates to parsing a <code>string</code> into a <code>DateTime</code> value. Such an API is <a href="https://docs.microsoft.com/en-us/dotnet/api/system.datetime.tryparse">already available in the base class library</a>. Using it looks like this: </p> <p> <pre><span style="color:blue;">bool</span>&nbsp;couldParse&nbsp;=&nbsp;<span style="color:#2b91af;">DateTime</span>.TryParse(candidate,&nbsp;<span style="color:blue;">out</span>&nbsp;<span style="color:#2b91af;">DateTime</span>&nbsp;dateTime);</pre> </p> <p> Since <code>DateTime</code> is a <a href="https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/value-types">value type</a>, the <code>out</code> parameter will never be <code>null</code>, even if parsing fails. You can, however, examine the return value <code>couldParse</code> to determine whether the <code>candidate</code> could be parsed. </p> <p> In the running commentary in the book, Jeffrey Richter likes this much better: <blockquote> "I like this guideline a lot. It solves the race-condition problem and the performance problem." </blockquote> I agree that it's better than Tester-Doer, but that doesn't mean that you can't refactor such a design to that pattern. </p> <h3 id="166ef01b6b64481a85fe64a6e9e07dc6"> From Try-Parse to Tester-Doer <a href="#166ef01b6b64481a85fe64a6e9e07dc6" title="permalink">#</a> </h3> <p> While I see no compelling reason to design parsing attempts with the Tester-Doer pattern, it's possible. You could create an API that enables interaction like this: </p> <p> <pre><span style="color:#2b91af;">DateTime</span>&nbsp;dateTime&nbsp;=&nbsp;<span style="color:blue;">default</span>(<span style="color:#2b91af;">DateTime</span>); <span style="color:blue;">bool</span>&nbsp;canParse&nbsp;=&nbsp;<span style="color:#2b91af;">DateTimeEnvy</span>.CanParse(candidate); <span style="color:blue;">if</span>&nbsp;(canParse) &nbsp;&nbsp;&nbsp;&nbsp;dateTime&nbsp;=&nbsp;<span style="color:#2b91af;">DateTime</span>.Parse(candidate);</pre> </p> <p> You'd need to add a new <code>CanParse</code> method with this signature: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;CanParse(<span style="color:blue;">string</span>&nbsp;candidate)</pre> </p> <p> In this particular example, you don't have to add a <code>Parse</code> method, because it already exists in the base class library, but in other examples, you'd have to add such a method as well. </p> <p> This example doesn't suffer from issues with thread safety, since strings are immutable, but in general, that problem is always a concern with the Tester-Doer <a href="/2019/01/21/some-thoughts-on-anti-patterns">anti-pattern</a>. Discoverability still suffers in this example. </p> <h3 id="ffd6284cfc8f4f528d1a3b80849fbf8c"> From Try-Parse to Maybe <a href="#ffd6284cfc8f4f528d1a3b80849fbf8c" title="permalink">#</a> </h3> <p> While the Try-Parse idiom is thread-safe, it isn't composable. Every time you run into an API modelled over this template, you have to stop what you're doing and check the return value. Did the operation succeed? Was should the code do if it didn't? </p> <p> <em>Maybe</em>, on the other hand, is composable, so is a much better way to model problems such as parsing. Typically, methods or functions that return Maybe values are still prefixed with <em>Try</em>, but there's no longer any <code>out</code> parameter. A Maybe-based <code>TryParse</code> function could look like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">DateTime</span>&gt;&nbsp;TryParse(<span style="color:blue;">string</span>&nbsp;candidate)</pre> </p> <p> You could use it like this: </p> <p> <pre><span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">DateTime</span>&gt;&nbsp;m&nbsp;=&nbsp;<span style="color:#2b91af;">DateTimeEnvy</span>.TryParse(candidate);</pre> </p> <p> If the <code>candidate</code> was successfully parsed, you get a populated <code>Maybe&lt;DateTime&gt;</code>; if the string was invalid, you get an empty <code>Maybe&lt;DateTime&gt;</code>. </p> <p> A Maybe object composes much better with other computations. Contrary to the Try-Parse idiom, you don't have to stop and examine a Boolean return value. You don't even have to deal with empty cases at the point where you parse. Instead, you can defer the decision about what to do in case of failure until a later time, where it may be more obvious what to do in that case. </p> <h3 id="4f27ce3476114a5f9b0f80fd415e5370"> Maybe <a href="#4f27ce3476114a5f9b0f80fd415e5370" title="permalink">#</a> </h3> <p> In my <a href="https://blog.ploeh.dk/encapsulation-and-solid">Encapsulation and SOLID</a> Pluralsight course, you get a walk-through of all three options for dealing with an operation that could potentially fail. Like in this article, the course starts with Tester-Doer, progresses over Try-Parse, and arrives at a Maybe-based implementation. In that course, the example involves reading a (previously stored) message from a text file. The final API looks like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:blue;">string</span>&gt;&nbsp;Read(<span style="color:blue;">int</span>&nbsp;id)</pre> </p> <p> The protocol implied by such a signature is that you supply an ID, and if a message with that ID exists on disc, you receive a populated <code>Maybe&lt;string&gt;</code>; otherwise, an empty object. This is not only composable, but also thread-safe. For anyone who understands the <a href="/2017/10/04/from-design-patterns-to-category-theory">universal abstraction</a> of Maybe, it's clear that this is an operation that could fail. Ultimately, client code will have to deal with empty Maybe values, but this doesn't have to happen immediately. Such a decision can be deferred until a proper context exists for that purpose. </p> <h3 id="d35fbacb32bb4ef6afc843813ba901f1"> From Maybe to Tester-Doer <a href="#d35fbacb32bb4ef6afc843813ba901f1" title="permalink">#</a> </h3> <p> Since Tester-Doer is the least useful of the patterns discussed in this article, it makes little sense to refactor a Maybe-based API to a Tester-Doer implementation. Nonetheless, it's still possible. The API could look like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;Exists(<span style="color:blue;">int</span>&nbsp;id) <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">string</span>&nbsp;Read(<span style="color:blue;">int</span>&nbsp;id)</pre> </p> <p> Not only is this design not thread-safe, but it's another example of poor discoverability. While the doer is called <code>Read</code>, the tester isn't called <code>CanRead</code>, but rather <code>Exists</code>. If the class has other members, these could be listed interleaved between <code>Exists</code> and <code>Read</code>. It wouldn't be obvious that these two members were designed to be used together. </p> <p> Again, the intended usage is code like this: </p> <p> <pre><span style="color:blue;">string</span>&nbsp;message; <span style="color:blue;">if</span>&nbsp;(fileStore.Exists(49)) &nbsp;&nbsp;&nbsp;&nbsp;message&nbsp;=&nbsp;fileStore.Read(49);</pre> </p> <p> This is still problematic, because you need to decide what to do in the <code>else</code> case as well, although you don't see that case here. </p> <p> The point is, still, that you <em>can</em> translate from one representation to another without loss of information; not that you should. </p> <h3 id="3bbc92082af143d29681b2ce0bb11ccb"> From Maybe to Try-Parse <a href="#3bbc92082af143d29681b2ce0bb11ccb" title="permalink">#</a> </h3> <p> Of the three representations discussed in this article, I firmly believe that a Maybe-based API is superior. Unfortunately, the .NET base class library doesn't (yet) come with a built-in Maybe object, so if you're developing an API as part of a reusable library, you have two options: <ul> <li>Export the library's <code>Maybe&lt;T&gt;</code> type together with the methods that return it.</li> <li>Use Try-Parse for interoperability reasons.</li> </ul> This is the only reason I can think of to use the Try-Parse idiom. For the <code>FileStore</code> example from my Pluralsight course, this would imply not a <code>TryParse</code> method, but a <code>TryRead</code> method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;TryRead(<span style="color:blue;">int</span>&nbsp;id,&nbsp;<span style="color:blue;">out</span>&nbsp;<span style="color:blue;">string</span>&nbsp;message)</pre> </p> <p> This would enable you to expose the method in a reusable library. Client code could interact with it like this: </p> <p> <pre><span style="color:blue;">string</span>&nbsp;message; <span style="color:blue;">if</span>&nbsp;(!fileStore.TryRead(50,&nbsp;<span style="color:blue;">out</span>&nbsp;message)) &nbsp;&nbsp;&nbsp;&nbsp;message&nbsp;=&nbsp;<span style="color:#a31515;">&quot;&quot;</span>;</pre> </p> <p> This has all the problems associated with the Try-Parse idiom already discussed in this article, but it does, at least, have a basic use case. </p> <h3 id="c04073bcc534481eaaf1ba43dd2a22a4"> Isomorphism with Either <a href="#c04073bcc534481eaaf1ba43dd2a22a4" title="permalink">#</a> </h3> <p> At this point, I hope that you find it reasonable to believe that the three representations, Tester-Doer, Try-Parse, and Maybe, are isomorphic. You can translate between any of these representations to any other of these without loss of information. This also means that you can translate back again. </p> <p> While I've only argued with a series of examples, it's my experience that these three representations are truly isomorphic. You can always translate any of these representations into another. Mostly, though, I translate into Maybe. If you disagree with my proposition, all you have to do is to provide a counter-example. </p> <p> There's a fourth isomorphism that's already well-known, and that's between Maybe and <a href="/2018/06/11/church-encoded-either">Either</a>. Specifically, <code>Maybe&lt;T&gt;</code> is isomorphic to <code>Either&lt;Unit, T&gt;</code>. In <a href="https://www.haskell.org">Haskell</a>, this is easily demonstrated with this set of functions: </p> <p> <pre><span style="color:#2b91af;">toMaybe</span>&nbsp;::&nbsp;<span style="color:#2b91af;">Either</span>&nbsp;()&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&nbsp;a toMaybe&nbsp;(Left&nbsp;<span style="color:blue;">()</span>)&nbsp;=&nbsp;Nothing toMaybe&nbsp;(Right&nbsp;x)&nbsp;=&nbsp;Just&nbsp;x <span style="color:#2b91af;">fromMaybe</span>&nbsp;::&nbsp;<span style="color:#2b91af;">Maybe</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Either</span>&nbsp;()&nbsp;a fromMaybe&nbsp;Nothing&nbsp;=&nbsp;Left&nbsp;<span style="color:blue;">()</span> fromMaybe&nbsp;(Just&nbsp;x)&nbsp;=&nbsp;Right&nbsp;x</pre> </p> <p> Translated to C#, using the <a href="/2018/06/04/church-encoded-maybe">Church-encoded Maybe</a> together with the Church-encoded Either, these two functions could look like the following, starting with the conversion from Maybe to Either: </p> <p> <pre><span style="color:green;">//&nbsp;On&nbsp;Maybe:</span> <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;">Unit</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;&nbsp;ToEither&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IMaybe</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;source) { &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;">Unit</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;&gt;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nothing:&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Left</span>&lt;<span style="color:#2b91af;">Unit</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;(<span style="color:#2b91af;">Unit</span>.Value), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;just:&nbsp;x&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Right</span>&lt;<span style="color:#2b91af;">Unit</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;(x)); }</pre> </p> <p> Likewise, the conversion from Either to Maybe: </p> <p> <pre><span style="color:green;">//&nbsp;On&nbsp;Either:</span> <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IMaybe</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;ToMaybe&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">Unit</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;&nbsp;source) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;source.Match&lt;<span style="color:#2b91af;">IMaybe</span>&lt;<span style="color:#2b91af;">T</span>&gt;&gt;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;onLeft:&nbsp;_&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Nothing</span>&lt;<span style="color:#2b91af;">T</span>&gt;(), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;onRight:&nbsp;x&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Just</span>&lt;<span style="color:#2b91af;">T</span>&gt;(x)); }</pre> </p> <p> You can convert back and forth to your heart's content, as this parametrised <a href="https://xunit.github.io">xUnit.net</a> 2.3.1 test shows: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>] [<span style="color:#2b91af;">InlineData</span>(42)] [<span style="color:#2b91af;">InlineData</span>(1337)] [<span style="color:#2b91af;">InlineData</span>(2112)] [<span style="color:#2b91af;">InlineData</span>(90125)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;IsomorphicWithPopulatedMaybe(<span style="color:blue;">int</span>&nbsp;i) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;expected&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Right</span>&lt;<span style="color:#2b91af;">Unit</span>,&nbsp;<span style="color:blue;">int</span>&gt;(i); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;actual&nbsp;=&nbsp;expected.ToMaybe().ToEither(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(expected,&nbsp;actual); }</pre> </p> <p> I decided to exclude <code>IEither&lt;Unit, T&gt;</code> from the overall theme of this article in order to better contrast three alternatives that may not otherwise look equivalent. That <code>IEither&lt;Unit, T&gt;</code> is isomorphic to <code>IMaybe&lt;T&gt;</code> is a well-known result. Besides, I think that both of these two representations already inhabit the same conceptual space. Either and Maybe are both well-known in statically typed functional programming. </p> <h3 id="8e3e7b55ac1e49568712675713426e59"> Summary <a href="#8e3e7b55ac1e49568712675713426e59" title="permalink">#</a> </h3> <p> The Tester-Doer pattern is a decades-old design pattern that attempts to model how to perform operations that can potentially fail, without relying on exceptions for flow control. It predates mainstream multi-core processors by decades, which can explain why it even exists as a pattern in the first place. At the time people arrived at the pattern, thread-safety wasn't a big concern. </p> <p> The Try-Parse idiom is a thread-safe alternative to the Tester-Doer pattern. It combines the two <em>tester</em> and <em>doer</em> methods into a single method with an <code>out</code> parameter. While thread-safe, it's not composable. </p> <p> <em>Maybe</em> offers the best of both worlds. It's both thread-safe and composable. It's also as discoverable as any Try-Parse method. </p> <p> These three alternatives are all, however, isomorphic. This means that you can refactor any of the three designs into one of the other designs, without loss of information. It also means that you can implement <a href="https://en.wikipedia.org/wiki/Adapter_pattern">Adapters</a> between particular implementations, should you so desire. You see this frequently in <a href="https://fsharp.org">F#</a> code, where functions that return <code>'a option</code> adapt Try-Parse methods from the .NET base class library. </p> <p> While all three designs are equivalent in the sense that you can translate one into another, it doesn't imply that they're equally useful. <em>Maybe</em> is the superior design, and Tester-Doer clearly inferior. </p> <p> <strong>Next:</strong> <a href="/2018/05/22/church-encoding">Church encoding</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/07/15/tester-doer-isomorphisms Payment types catamorphism https://blog.ploeh.dk/2019/07/08/payment-types-catamorphism/ Mon, 08 Jul 2019 06:08:00 UTC <div id="post"> <p> <em>You can find the catamorphism for a custom sum type. Here's an example.</em> </p> <p> This article is part of an <a href="/2019/04/29/catamorphisms">article series about catamorphisms</a>. A catamorphism is a <a href="/2017/10/04/from-design-patterns-to-category-theory">universal abstraction</a> that describes how to digest a data structure into a potentially more compact value. </p> <p> This article presents the catamorphism for a domain-specific <a href="https://en.wikipedia.org/wiki/Tagged_union">sum type</a>, as well as how to identify it. The beginning of this article presents the catamorphism in C#, with a few examples. The rest of the article describes how to deduce the catamorphism. This part of the article presents my work in <a href="https://www.haskell.org">Haskell</a>. Readers not comfortable with Haskell can just read the first part, and consider the rest of the article as an optional appendix. </p> <p> In all previous articles in the series, you've seen catamorphisms for well-known data structures: <a href="/2019/05/06/boolean-catamorphism">Boolean values</a>, <a href="/2019/05/13/peano-catamorphism">Peano numbers</a>, <a href="/2019/05/20/maybe-catamorphism">Maybe</a>, <a href="/2019/06/10/tree-catamorphism">trees</a>, and so on. These are all general-purpose data structures, so you might be left with the impression that catamorphisms are only related to such general types. That's not the case. The point of this article is to demonstrate that you can find the catamorphism for your own custom, domain-specific sum type as well. </p> <h3 id="2b6f7df594c0474589ae9805f1e1a1d0"> C# catamorphism <a href="#2b6f7df594c0474589ae9805f1e1a1d0" title="permalink">#</a> </h3> <p> The custom type we'll examine in this article is the <a href="/2018/06/18/church-encoded-payment-types">Church-encoded payment types</a> I've previously written about. It's just an example of a custom data type, but it serves the purpose of illustration because I've already shown it as a Church encoding in C#, <a href="/2018/06/25/visitor-as-a-sum-type">as a Visitor in C#</a>, and <a href="/2016/11/28/easy-domain-modelling-with-types">as a discriminated union in F#</a>. </p> <p> The catamorphism for the <code>IPaymentType</code> interface is the <code>Match</code> method: </p> <p> <pre><span style="color:#2b91af;">T</span>&nbsp;Match&lt;<span style="color:#2b91af;">T</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">PaymentService</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;&nbsp;individual, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">PaymentService</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;&nbsp;parent, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">ChildPaymentService</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;&nbsp;child);</pre> </p> <p> As has turned out to be a common trait, the catamorphism is identical to the Church encoding. </p> <p> I'm not going to show more than a few examples of using the <code>Match</code> method, because you can find other examples in the previous articles, </p> <p> <pre>&gt; <span style="color:#2b91af;">IPaymentType</span>&nbsp;p&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Individual</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">PaymentService</span>(<span style="color:#a31515;">&quot;Visa&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;Pay&quot;</span>)); &gt; p.Match(ps&nbsp;=&gt;&nbsp;ps.Name,&nbsp;ps&nbsp;=&gt;&nbsp;ps.Name,&nbsp;cps&nbsp;=&gt;&nbsp;cps.PaymentService.Name) "Visa" &gt; <span style="color:#2b91af;">IPaymentType</span>&nbsp;p&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Parent</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">PaymentService</span>(<span style="color:#a31515;">&quot;Visa&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;Pay&quot;</span>)); &gt; p.Match(ps&nbsp;=&gt;&nbsp;ps.Name,&nbsp;ps&nbsp;=&gt;&nbsp;ps.Name,&nbsp;cps&nbsp;=&gt;&nbsp;cps.PaymentService.Name) "Visa" &gt; <span style="color:#2b91af;">IPaymentType</span>&nbsp;p&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Child</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ChildPaymentService</span>(<span style="color:#a31515;">&quot;1234&quot;</span>,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">PaymentService</span>(<span style="color:#a31515;">&quot;Visa&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;Pay&quot;</span>))); &gt; p.Match(ps&nbsp;=&gt;&nbsp;ps.Name,&nbsp;ps&nbsp;=&gt;&nbsp;ps.Name,&nbsp;cps&nbsp;=&gt;&nbsp;cps.PaymentService.Name) "Visa"</pre> </p> <p> These three examples from a <em>C# Interactive</em> session demonstrate that no matter which payment method you use, you can use the same <code>Match</code> method call to extract the payment name from the <code>p</code> object. </p> <h3 id="f2334a900eef421cb24c6e48a96e411b"> Payment types F-Algebra <a href="#f2334a900eef421cb24c6e48a96e411b" title="permalink">#</a> </h3> <p> As in the <a href="/2019/06/24/full-binary-tree-catamorphism">previous article</a>, I'll use <code>Fix</code> and <code>cata</code> as explained in <a href="https://bartoszmilewski.com">Bartosz Milewski</a>'s excellent <a href="https://bartoszmilewski.com/2017/02/28/f-algebras/">article on F-Algebras</a>. </p> <p> First, you'll have to define the auxiliary types involved in this API: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;PaymentService&nbsp;=&nbsp;PaymentService&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;paymentServiceName&nbsp;::&nbsp;String &nbsp;&nbsp;,&nbsp;paymentServiceAction&nbsp;::&nbsp;String &nbsp;&nbsp;}&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>) <span style="color:blue;">data</span>&nbsp;ChildPaymentService&nbsp;=&nbsp;ChildPaymentService&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;originalTransactionKey&nbsp;::&nbsp;String &nbsp;&nbsp;,&nbsp;parentPaymentService&nbsp;::&nbsp;PaymentService &nbsp;&nbsp;}&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> While F-Algebras and fixed points are mostly used for recursive data structures, you can also define an F-Algebra for a non-recursive data structure. You already saw examples of that in the articles about <a href="/2019/05/06/boolean-catamorphism">Boolean catamorphism</a>, <a href="/2019/05/20/maybe-catamorphism">Maybe catamorphism</a>, and <a href="/2019/06/03/either-catamorphism">Either catamorphism</a>. While each of the three payment types have associated data, none of it is parametrically polymorphic, so a single type argument for the carrier type suffices: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;PaymentTypeF&nbsp;c&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;IndividualF&nbsp;PaymentService &nbsp;&nbsp;|&nbsp;ParentF&nbsp;PaymentService &nbsp;&nbsp;|&nbsp;ChildF&nbsp;ChildPaymentService &nbsp;&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;<span style="color:blue;">PaymentTypeF</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;_&nbsp;(IndividualF&nbsp;ps)&nbsp;=&nbsp;IndividualF&nbsp;ps &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;_&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(ParentF&nbsp;ps)&nbsp;=&nbsp;ParentF&nbsp;ps &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;_&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(ChildF&nbsp;cps)&nbsp;=&nbsp;ChildF&nbsp;cps</pre> </p> <p> I chose to call the carrier type <code>c</code> (for <em>carrier</em>). As was also the case with <code>BoolF</code>, <code>MaybeF</code>, and <code>EitherF</code>, the <code>Functor</code> instance ignores the map function because the carrier type is missing from all three cases. Like the <code>Functor</code> instances for <code>BoolF</code>, <code>MaybeF</code>, and <code>EitherF</code>, it'd seem that nothing happens, but at the type level, this is still a translation from <code>PaymentTypeF c</code> to <code>PaymentTypeF c1</code>. Not much of a function, perhaps, but definitely an <em>endofunctor</em>. </p> <p> Some helper functions make it a little easier to create <code>Fix PaymentTypeF</code> values, but there's really not much to them: </p> <p> <pre><span style="color:#2b91af;">individualF</span>&nbsp;::&nbsp;<span style="color:blue;">PaymentService</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">PaymentTypeF</span> individualF&nbsp;=&nbsp;Fix&nbsp;.&nbsp;IndividualF <span style="color:#2b91af;">parentF</span>&nbsp;::&nbsp;<span style="color:blue;">PaymentService</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">PaymentTypeF</span> parentF&nbsp;=&nbsp;Fix&nbsp;.&nbsp;ParentF <span style="color:#2b91af;">childF</span>&nbsp;::&nbsp;<span style="color:blue;">ChildPaymentService</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">PaymentTypeF</span> childF&nbsp;=&nbsp;Fix&nbsp;.&nbsp;ChildF</pre> </p> <p> That's all you need to identify the catamorphism. </p> <h3 id="da3c2c0fee2747bebb1db38c15110bcb"> Haskell catamorphism <a href="#da3c2c0fee2747bebb1db38c15110bcb" title="permalink">#</a> </h3> <p> At this point, you have two out of three elements of an F-Algebra. You have an endofunctor (<code>PaymentTypeF</code>), and an object <code>c</code>, but you still need to find a morphism <code>PaymentTypeF c -&gt; c</code>. </p> <p> As in the previous articles, start by writing a function that will become the catamorphism, based on <code>cata</code>: </p> <p> <pre>paymentF&nbsp;=&nbsp;cata&nbsp;alg &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;(IndividualF&nbsp;ps)&nbsp;=&nbsp;<span style="color:blue;">undefined</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(ParentF&nbsp;ps)&nbsp;=&nbsp;<span style="color:blue;">undefined</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(ChildF&nbsp;cps)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> While this compiles, with its <code>undefined</code> implementations, it obviously doesn't do anything useful. I find, however, that it helps me think. How can you return a value of the type <code>c</code> from the <code>IndividualF</code> case? You could pass an argument to the <code>paymentF</code> function, but you shouldn't ignore the data <code>ps</code> contained in the case, so it has to be a function: </p> <p> <pre>paymentF&nbsp;fi&nbsp;=&nbsp;cata&nbsp;alg &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;(IndividualF&nbsp;ps)&nbsp;=&nbsp;fi&nbsp;ps &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(ParentF&nbsp;ps)&nbsp;=&nbsp;<span style="color:blue;">undefined</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(ChildF&nbsp;cps)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> I chose to call the argument <code>fi</code>, for <em>function, individual</em>. You can pass a similar argument to deal with the <code>ParentF</code> case: </p> <p> <pre>paymentF&nbsp;fi&nbsp;fp&nbsp;=&nbsp;cata&nbsp;alg &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;(IndividualF&nbsp;ps)&nbsp;=&nbsp;fi&nbsp;ps &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(ParentF&nbsp;ps)&nbsp;=&nbsp;fp&nbsp;ps &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(ChildF&nbsp;cps)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> And of course with the remaining <code>ChildF</code> case as well: </p> <p> <pre><span style="color:#2b91af;">paymentF</span>&nbsp;::&nbsp;(<span style="color:blue;">PaymentService</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(<span style="color:blue;">PaymentService</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(<span style="color:blue;">ChildPaymentService</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">Fix&nbsp;PaymentTypeF</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c paymentF&nbsp;fi&nbsp;fp&nbsp;fc&nbsp;=&nbsp;cata&nbsp;alg &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;(IndividualF&nbsp;ps)&nbsp;=&nbsp;fi&nbsp;ps &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(ParentF&nbsp;ps)&nbsp;=&nbsp;fp&nbsp;ps &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(ChildF&nbsp;cps)&nbsp;=&nbsp;fc&nbsp;cps</pre> </p> <p> This works. Since <code>cata</code> has the type <code>Functor f =&gt; (f a -&gt; a) -&gt; Fix f -&gt; a</code>, that means that <code>alg</code> has the type <code>f a -&gt; a</code>. In the case of <code>PaymentTypeF</code>, the compiler infers that the <code>alg</code> function has the type <code>PaymentTypeF c -&gt; c</code>, which is just what you need! </p> <p> You can now see what the carrier type <code>c</code> is for. It's the type that the algebra extracts, and thus the type that the catamorphism returns. </p> <p> This, then, is the catamorphism for the payment types. Except for the <a href="/2019/06/10/tree-catamorphism">tree catamorphism</a>, all catamorphisms so far have been pairs, but this one is a triplet of functions. This is because the sum type has three cases instead of two. </p> <p> As you've seen repeatedly, this isn't the only possible catamorphism, since you can, for example, trivially reorder the arguments to <code>paymentF</code>. The version shown here is, however, equivalent to the above C# <code>Match</code> method. </p> <h3 id="e6248a9ea34148c79c2b03acc92de5f7"> Usage <a href="#e6248a9ea34148c79c2b03acc92de5f7" title="permalink">#</a> </h3> <p> You can use the catamorphism as a basis for other functionality. If, for example, you want to convert a <code>Fix PaymentTypeF</code> value to JSON, you can first define an <a href="http://hackage.haskell.org/package/aeson/docs/Data-Aeson.html">Aeson</a> record type for that purpose: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;PaymentJson&nbsp;=&nbsp;PaymentJson&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;name&nbsp;::&nbsp;String &nbsp;&nbsp;,&nbsp;action&nbsp;::&nbsp;String &nbsp;&nbsp;,&nbsp;startRecurrent&nbsp;::&nbsp;Bool &nbsp;&nbsp;,&nbsp;transactionKey&nbsp;::&nbsp;Maybe&nbsp;String &nbsp;&nbsp;}&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Generic</span>) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">ToJSON</span>&nbsp;<span style="color:blue;">PaymentJson</span></pre> </p> <p> Subsequently, you can use <code>paymentF</code> to implement a conversion from <code>Fix PaymentTypeF</code> to <code>PaymentJson</code>, as in the previous articles: </p> <p> <pre><span style="color:#2b91af;">toJson</span>&nbsp;::&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">PaymentTypeF</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">PaymentJson</span> toJson&nbsp;= &nbsp;&nbsp;paymentF &nbsp;&nbsp;&nbsp;&nbsp;(\(PaymentService&nbsp;n&nbsp;a)&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;-&gt;&nbsp;PaymentJson&nbsp;n&nbsp;a&nbsp;False&nbsp;Nothing) &nbsp;&nbsp;&nbsp;&nbsp;(\(PaymentService&nbsp;n&nbsp;a)&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;-&gt;&nbsp;PaymentJson&nbsp;n&nbsp;a&nbsp;True&nbsp;Nothing) &nbsp;&nbsp;&nbsp;&nbsp;(\(ChildPaymentService&nbsp;k&nbsp;(PaymentService&nbsp;n&nbsp;a))&nbsp;-&gt;&nbsp;PaymentJson&nbsp;n&nbsp;a&nbsp;False&nbsp;$&nbsp;Just&nbsp;k)</pre> </p> <p> Testing it in GHCi, it works as it's supposed to: </p> <p> <pre>Prelude Data.Aeson B Payment&gt; B.putStrLn $ encode $ toJson $ parentF $ PaymentService "Visa" "Pay" {"transactionKey":null,"startRecurrent":true,"action":"Pay","name":"Visa"}</pre> </p> <p> Clearly, it would have been easier to define the payment types shown here as a regular Haskell sum type and just use standard pattern matching, but the purpose of this article isn't to present useful code; the only purpose of the code here is to demonstrate how to identify the catamorphism for a custom domain-specific sum type. </p> <h3 id="153479fffaf647f6ad6f5fc6a63fe025"> Summary <a href="#153479fffaf647f6ad6f5fc6a63fe025" title="permalink">#</a> </h3> <p> Even custom, domain-specific sum types have catamorphisms. This article presented the catamorphism for a custom payment sum type. Because this particular sum type has three cases, the catamorphism is a triplet, instead of a pair, which has otherwise been the most common shape of catamorphisms in previous articles. </p> <p> <strong>Next:</strong> <a href="/2018/03/05/some-design-patterns-as-universal-abstractions">Some design patterns as universal abstractions</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/07/08/payment-types-catamorphism Yes silver bullet https://blog.ploeh.dk/2019/07/01/yes-silver-bullet/ Mon, 01 Jul 2019 07:38:00 UTC <div id="post"> <p> <em>Since Fred Brooks published his essay, I believe that we, contrary to his prediction, have witnessed several silver bullets.</em> </p> <p> I've been rereading <a href="https://en.wikipedia.org/wiki/Fred_Brooks">Fred Brooks</a>'s 1986 essay <a href="https://en.wikipedia.org/wiki/No_Silver_Bullet">No Silver Bullet</a> because I've become increasingly concerned that people seem to draw the wrong conclusions from it. <a href="https://martinfowler.com/bliki/SemanticDiffusion.html">Semantic diffusion</a> seems to have set in. These days, when people state something along the lines that there's <em>no silver bullet in software development</em>, I often get the impression that they mean that there's no panacea. </p> <p> Indeed; I agree. There's no miracle cure that will magically make all problems in software development go away. That's not what the essay states, however. It is, fortunately, more subtle than that. </p> <h3 id="712292e6c9c34663801dd40b4f278d3d"> No silver bullet reread <a href="#712292e6c9c34663801dd40b4f278d3d" title="permalink">#</a> </h3> <p> It's a great essay. It's not my intent to dispute the central argument of the essay, but I think that Brooks made one particular assumption that I disagree with. That doesn't make me smarter in any way. He wrote the essay in 1986. I'm writing this in 2019, with the benefit of the experience of all the years in-between. Hindsight is 20-20, so anyone could make the observations that I do here. </p> <p> Before we get to that, though, a brief summary of the essence of the essay is in order. In short, the conclusion is this: <blockquote> <p> "There is no single development, in either technology or management technique, which by itself promises even one order-of-magnitude improvement within a decade in productivity, in reliability, in simplicity." </p> <footer><cite>Fred Brooks, <em>No Silver Bullet</em>, 1986</cite></footer> </blockquote> The beginning of the essay is a brilliant analysis of the reasons why software development is inherently difficult. If you read this together with Jack Reeves <em>What Is Software Design?</em> (available various places on the internet, or as an appendix in <a href="http://amzn.to/19W4JHk">APPP</a>), you'll probably agree that there's an inherent complexity to software development that no invention is likely to dispel. </p> <p> Ostensibly in the tradition of <a href="https://en.wikipedia.org/wiki/Aristotle">Aristotle</a>, Brooks distinguishes between <em>essential</em> and <em>accidental</em> complexity. This distinction is central to his argument, so it's worth discussing for a minute. </p> <p> Software development problems are complex, i.e. made up of many interacting sub-problems. Some of that complexity is <em>accidental</em>. This doesn't imply randomness or sloppiness, but only that the complexity isn't inherent to the problem; that it's only the result of our (human) failure to achieve perfection. </p> <p> If you imagine that you could whittle away all the accidental complexity, you'd ultimately reach a point where, in the words of Saint Exupéry, <em>there is nothing more to remove</em>. What's left is the <em>essential</em> complexity. </p> <p> Brooks' conjecture is that a typical software development project comes with both essential and accidental complexity. In his 1995 reflections <em>"No Silver Bullet" Refired</em> (available in <a href="http://bit.ly/mythical-man-month">The Mythical Man-Month</a>), he clarifies what he already implied in 1986: <blockquote> <p> "It is my opinion, and that is all, that the accidental or representational part of the work is now down to about half or less of the total." </p> <footer><cite>Fred Brooks, <em>"No Silver Bullet" Refired</em>, 1995</cite></footer> </blockquote> This I fundamentally disagree with, but more on that later. It makes sense to me to graphically represent the argument like this: </p> <p> <img src="/content/binary/essential-accidental-complexity-shells-brooks-scenario.png" alt="Some, but not much, accidental complexity as a shell around essential complexity."> </p> <p> The way that I think of Brooks' argument is that any software project contains some essential and some accidental complexity. For a given project, the size of the essential complexity is fixed. </p> <p> Brooks believes that less than half of the overall complexity is accidental: </p> <p> <img src="/content/binary/essential-accidental-complexity-pie-chart-brooks-scenario.png" alt="Essential and accidental complexity pie chart."> </p> <p> While a pie chart better illustrates the supposed ratio between the two types of complexity, I prefer to view Brooks' arguments as the first diagram, above. In that visualisation, the essential complexity is a core of fixed size, while accidental complexity is something you can work at removing. If you keep improving your process and technology, you may, conceptually, be able to remove (almost) all of it. </p> <p> <img src="/content/binary/essential-almost-no-accidental-complexity-shells.png" alt="Essential complexity with a very thin shell of accidental complexity."> </p> <p> Brooks' point, with which I agree, is that if the essential complexity is inherent, then you can't reduce the size of it. The only way to decrease the overall complexity is to reduce the accidental complexity. </p> <p> If you agree with the assessment that less than half of the overall complexity in modern software development is accidental, then it follows that no dramatic improvements are available. Even if you remove all accidental complexity, you've only reduced overall complexity by, say, forty percent. </p> <h3 id="d8e6f84d104b4ff6ad6b5473e46a4e30"> Accidental complexity abounds <a href="#d8e6f84d104b4ff6ad6b5473e46a4e30" title="permalink">#</a> </h3> <p> I find Brooks' arguments compelling. I do not, however, accept the premise that there's only little accidental complexity left. Instead of the above diagrams, I believe that the situation looks more like this (not to scale): </p> <p> <img src="/content/binary/accidental-complexity-with-tiny-core-of-essential-complexity.png" alt="Accidental complexity with a tiny core of essential complexity."> </p> <p> I think that most of the complexity in software development is accidental. I'm not sure about today, but I believe that I have compelling evidence that this was the case in 1986, so I don't see why it shouldn't still be the case. </p> <p> To be clear, this is all anecdotal, since I don't believe that software development is quantifiable. In the essay, Brooks explicitly talks about the <em>invisibility</em> of software. Software is pure <em>thought stuff;</em> you can't measure it. I discuss this in my <a href="https://cleancoders.com/episode/humane-code-real-episode-1/show">Humane Code video</a>, but I also recommend that you read <a href="http://bit.ly/leprechauns-of-software-engineering">The Leprechauns of Software Engineering</a> if you have any illusions that we, as an industry, have any reliable measurements of productivity. </p> <p> Brooks predicts that, within the decade (from 1986 to 1996), there would be no single development that would increase productivity with an order of magnitude, i.e. by a factor of at least ten. Ironically, when he wrote <em>"No Silver Bullet" Refired</em> in 1995, at least two such developments were already in motion. </p> <p> We can't blame Brooks for not identifying those developments, because in 1995, their impact was not yet apparent. Again, hindsight is 20-20. </p> <p> Neither of these two developments are purely technological, although technology plays a role. Notice, though, that Brooks' prediction included <em>technology or management technique</em>. It's in the interaction between technology and the humane that the orders-of-magnitude developments emerged. </p> <h3 id="1d23f6fb89884b6d9833ce09d68a3b0f"> World Wide Web <a href="#1d23f6fb89884b6d9833ce09d68a3b0f" title="permalink">#</a> </h3> <p> I have a dirty little secret. In the beginning of my programming career, I became quite the expert on a programming framework called <a href="https://en.wikipedia.org/wiki/Microsoft_Commerce_Server">Microsoft Commerce Server</a>. In fact, I co-authored a chapter of <a href="https://amzn.to/2CpE4rr">Professional Commerce Server 2000 Programming</a>, and in 2003 I received an <a href="https://mvp.microsoft.com">MVP</a> award as an acknowledgement of my work in the Commerce Server community (such as it were; it was mostly on <a href="https://en.wikipedia.org/wiki/Usenet">Usenet</a>). </p> <p> The Commerce Server framework was a black box. This was long before Microsoft embraced open source, and while there was a bit of official documentation, it was superficial; it was mostly of the <em>getting-started</em> kind. </p> <p> Over several years, I managed to figure out how the framework really worked, and thus, how one could extend it. This was a painstaking process. Since it was a black box, I couldn't just go and read the code to figure out how it worked. The framework was written in C++ and Visual Basic, so there wasn't even IL code to decompile. </p> <p> I had one window into the framework. It relied on SQL Server, and I could attach the profiler tool to spy on its interaction with the database. Painstakingly, over several years, I managed to wrest the framework's secrets from it. </p> <p> I wasted much time doing detective work like that. </p> <p> In general, programming in the late nineties and early two-thousands was less productive, not because the languages or tools were orders-of-magnitude worse than today, but because when you hit a snag, you were in trouble. </p> <p> These days, if you run into a problem beyond your abilities, you can ask for help on the World Wide Web. Usually, you'll find an existing answer on <a href="https://stackoverflow.com">Stack Overflow</a>, and you'll be able to proceed without too much delay. </p> <p> Compared to twenty years ago, I believe that the World Wide Web has increased my productivity more than ten-fold. While it also existed in 1995, there wasn't much content. It's not the technology itself that provides the productivity increase, but rather the synergy of technology and human knowledge. </p> <p> I think that Brooks vastly underestimated how much time one can waste when one is stuck. That's a sort of accidental complexity, although in the development process rather than in the technology itself. </p> <h3 id="a3b19483cd6a4c509d8c3a77fe324872"> Automated testing <a href="#a3b19483cd6a4c509d8c3a77fe324872" title="permalink">#</a> </h3> <p> In the late nineties, I was developing web sites (with Commerce Server). When I wanted to run my code to see if it worked, I'd launch the web site on my laptop, log in, click around and enter data until I was convinced that the functionality was working as it should. Most of the time, however, it wasn't, so I'd change a bit of the code, and go through the same process again. </p> <p> I think that's a common way to 'test' software; at least, it was back then. </p> <p> While you could get good at going through these motions quickly, verifying a single, or a handful of related functionalities, could easily take at least a couple of seconds, and usually more like half a minute. </p> <p> If you had dozens, or even hundreds, of different scenarios to address, you obviously wouldn't run through them all every time you changed the code. At the very best, you'd click your way through three of four usage scenarios that you thought were relevant to the change you'd made. Other functionality, earlier declared <em>done</em>, you just considered to be unaffected. </p> <p> Needless to say, regressions were regular occurrences. </p> <p> In 2003 I discovered test-driven development, and through that, automated testing. While you can't directly compare unit tests with whole usage scenarios, I think it's fair to compare something like automated integration tests or user-scenario tests (whatever you want to call them) with manually clicking through an application. </p> <p> Even an integration test, if written properly, can verify a scenario <em>at least</em> ten times faster than you can do it by hand. A more realistic estimate is probably hundred times faster, or more. </p> <p> Granted, you have to write the automated test as well, and I know that it's not always trivial. Still, once you have an automated test suite in place, you can run it all the time. </p> <p> I never ran through <em>all</em> usage scenarios when I manually 'tested' my software. With automated tests, I do. This saves me from most regressions. </p> <p> This improvement is, in my opinion, a no-brainer. It's easily a factor ten improvement. All the time wasted manually 'testing' the software, plus the time wasted fixing regressions, can be put to better use. </p> <p> At the time Brooks was writing his own retrospective (in 1995), Kent Beck was beginning to talk to other people about test-driven development. As is a common theme in this article, hindsight is 20-20. </p> <h3 id="c7ca9269cce04b3ab934c97bc8cf0328"> Honourable mentions <a href="#c7ca9269cce04b3ab934c97bc8cf0328" title="permalink">#</a> </h3> <p> There's been other improvements in software development since 1986. I considered including several other improvements as bona fide orders-of-magnitude improvements, but I think that's probably going too far. Each of the following developments have, however, offered significant improvements: <ul> <li> <strong>Git.</strong> It's surprising how much more productive Git can make you. While it's somewhat better than centralised source control systems at the functionality also available with those other systems, the productivity increase comes from all the new, unanticipated workflows it enables. Before I started using DVCS, I'd have lots of code that was commented out, so that I could experiment with various alternatives. With Git, I just create a new branch, or stash my changes, and experiment with abandon. While it's probably not a ten-fold increase in productivity, I believe it's the simplest technology change you can make to dramatically increase your productivity. </li> <li> <strong>Garbage collection.</strong> Since I've admitted that I worked with Microsoft Commerce Server, I've probably lost all credibility with my reader already, but let's see if I can win back a little. While Commerce Server programming involved <a href="https://en.wikipedia.org/wiki/VBScript">VBScript</a> programming, it also often involved <a href="https://en.wikipedia.org/wiki/Component_Object_Model">COM</a> programming, and I did quite a bit of that in C++. Having to make sure that you've cleaned up all memory after use is a bother. Garbage collection just makes this work go away. It's hardly a ten-fold improvement in productivity, but I do find it significant. </li> <li> <strong>Agile software development.</strong> The methodology of decreasing the feedback time between implementation and deployment has made me much more productive. I'm not interested in peddling any particular methodology like Scrum as much as just the general concept of getting rapid feedback. Particularly if you combine continuous delivery with Git, you have a powerful combination. Brooks already talked about incremental software development, and had some hopes attached to this as well. My personal experience can only agree with his sentiment. Again, probably not in itself a ten-fold increase in productivity, but enough that I wouldn't want to work on a project where rapid feedback and incremental development wasn't valued. </li> </ul> I'm probably forgetting lots of other improvements that have happened in the last decades. That's fine. The purpose of this article isn't to produce an exhaustive list, but rather to make the argument that significant improvements have been made since Brooks wrote his essay. I think it'd be folly, then, to believe that we've seen the last of such improvements. </p> <p> Personally, I'm inclined to believe another order-of-magnitude improvement is right at our feet. </p> <h3 id="bd2d47d8dac2401e936ca7902bc9109d"> Statically typed functional programming <a href="#bd2d47d8dac2401e936ca7902bc9109d" title="permalink">#</a> </h3> <p> This section is conjecture on my part. The improvements I've so far covered are already realised (at least for those who choose to take advantage of them). The improvement I'll cover here is more speculative. </p> <p> I believe that statically typed functional programming offers another order-of-magnitude improvement over existing software development. Twenty years ago, I believed that object-oriented programming was a good idea. I now believe that I was wrong about that, so it's possible that in another twenty years, I'll also believe that I was wrong about functional programming. Take the following for what it is. </p> <p> When I carefully reread <em>No Silver Bullet</em>, I got the distinct impression that Brooks considered low-level details of programming part of its essential complexity: <blockquote> <p> "Much of the complexity in a software construct is, however, not due to conformity to the external world but rather to the implementation itself - its data structures, its algorithms, its connectivity." </p> <footer><cite>Fred Brooks, <em>"No Silver Bullet" Refired</em>, 1995</cite></footer> </blockquote> It's unreasonable to blame anyone writing in 1986, or 1995 for that matter, to think that <code>for</code> loops, variables, program state, and such other programming stables were anything but essential parts of the complexity of developing software. </p> <p> Someone, unfortunately I forget who, once made the point that all mainstream programming languages are layers of abstractions of how a CPU works. Assembly language is basically just mnemonics on top of a CPU instruction set, then C can be thought of as an abstraction over assembly language, C++ as the next step in abstraction, Java and C# as sort of abstractions of C++, and so on. The origin of the design is the physical CPU. You could say that these languages are designed in a bottom-up fashion. </p> <p> <img src="/content/binary/imperative-bottom-up-functional-top-down.png" alt="Imperative languages depicted as designed bottom-up, and functional languages as designed top-down."> </p> <p> Some functional languages (perhaps most famously <a href="https://www.haskell.org">Haskell</a>, but also <a href="https://en.wikipedia.org/wiki/APL_(programming_language)">APL</a>, and, possibly, <a href="https://en.wikipedia.org/wiki/Lisp_(programming_language)">Lisp</a>) are designed in a much more top-down fashion. You start with mathematical abstractions like <a href="https://en.wikipedia.org/wiki/Category_theory">category theory</a> and then figure out how to crystallise the theory into a programming language, and then again, via more layers of abstractions, how to turn the abstract language into machine code. </p> <p> The more you learn about the <a href="https://en.wikipedia.org/wiki/Pure_function">pure</a> functional alternative to programming, the more you begin to see mutable program state, variables, <code>for</code> loops, and similar language constructs merely as artefacts of the underlying model. Brooks, I think, thought of these as part of the essential complexity of programming. I don't think that that's the case. You can get by just fine with other abstractions instead. </p> <p> Besides, Brooks writes, under the heading of <em>Complexity:</em> <blockquote> <p> "From the complexity comes the difficulty of enumerating, much less understanding, all the possible states of the program, and from that comes the unreliability. From the complexity of the functions comes the difficulty of invoking those functions, which makes programs hard to use." </p> <footer><cite>Fred Brooks, <em>No Silver Bullet</em>, 1986</cite></footer> </blockquote> When he writes <em>functions</em>, I don't think that he means functions in the Haskell sense. I think that he means <em>operations</em>, <em>procedures</em>, or <em>methods</em>. </p> <p> Indeed, when you look at a C# method signature like the following, it's hard to enumerate, understand, or remember, all that it does: </p> <p> <pre><span style="color:blue;">int</span>?&nbsp;TryAccept(<span style="color:#2b91af;">Reservation</span>&nbsp;reservation);</pre> </p> <p> If this is a high-level function, many things could happen when you call that method. It could change the state of a database. It could send an email. It could mutate a variable. Not only that, but the behaviour could depend on non-deterministic factors, such as the date, time of day, or just raw randomness. Finally, how should you handle the return value? What does it mean if the return value is <em>null</em>? What if it's not? Is <code>0</code> a valid value? Are negative numbers valid? Are they different from positive values? </p> <p> It is, indeed, difficult to enumerate all the possible states of such a function. </p> <p> Consider, instead, a Haskell function with a type like this: </p> <p> <pre><span style="color:#2b91af;">tryAccept</span>&nbsp;::&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Reservation</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">MaybeT</span>&nbsp;<span style="color:blue;">ReservationsProgram</span>&nbsp;<span style="color:#2b91af;">Int</span></pre> </p> <p> What happens if you invoke this function? It returns a value. Does it send any emails? Does it mutate any state? No, it can't, because the static type informs us that this is a pure function. If any programmer, anywhere inside of the function, or the functions it calls, or functions they call, etc. tried to do something impure, it wouldn't have compiled. </p> <p> Can we enumerate the states of the program? Certainly. We just have to figure out what <code>ReservationsProgram</code> is. After following a few types, we find this statically typed enumeration: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;ReservationsInstruction&nbsp;next&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;IsReservationInFuture&nbsp;Reservation&nbsp;(Bool&nbsp;-&gt;&nbsp;next) &nbsp;&nbsp;|&nbsp;ReadReservations&nbsp;UTCTime&nbsp;([Reservation]&nbsp;-&gt;&nbsp;next) &nbsp;&nbsp;|&nbsp;Create&nbsp;Reservation&nbsp;(Int&nbsp;-&gt;&nbsp;next) &nbsp;&nbsp;<span style="color:blue;">deriving</span>&nbsp;Functor</pre> </p> <p> Essentially, there's three 'actions' that this type enables. The <code>tryAccept</code> function returns the <code>ReservationsProgram</code> inside of a <code>MaybeT</code> container, so there's a fourth option that something short-circuits along the way. </p> <p> You don't even have to keep track of this yourself. The compiler keeps you honest. Whenever you invoke the <code>tryAccept</code> function, the compiler will insist that you write code that can handle all possible outcomes. If you turn on the right compiler flags, the code is not going to compile if you don't. </p> <p> (Both code examples are taken from <a href="https://github.com/ploeh/dependency-injection-revisited">the same repository</a>.) </p> <p> Haskellers jokingly declare that <em>if Haskell code compiles, it works</em>. While humorous, there's a kernel of truth in that. An advanced type system can carry much information about the behaviour of a program. Some people, particularly programmers who come from a dynamically typed background, find Haskell's type system rigid. That's not an unreasonable criticism, but often, in dynamically typed languages, you have to write many automated tests to ensure that your program behaves as desired, and that it correctly handles various edge cases. A type system like Haskell's, on the other hand, embeds those rules in types instead of in tests. </p> <p> While you should still write automated tests for Haskell programs, fewer are needed. How many fewer? Compared to C-based languages, a factor ten isn't an unreasonable guess. </p> <p> After a few false starts, in 2014 I finally decided that <a href="https://fsharp.org">F#</a> would be my default choice of language on .NET. The reason for that decision was that I felt so much more productive in F# compared to C#. While F#'s type system doesn't embed information about pure versus impure functions, it does support <a href="https://en.wikipedia.org/wiki/Tagged_union">sum types</a>, which is what enables the sort of compile-time <em>enumeration</em> that Brooks discusses. </p> <p> F# is still my .NET language of choice, but I find that I mostly 'think in' Haskell these days. My conjecture is that a sufficiently advanced type system (like Haskell's) could easily represent another order-of-magnitude improvement over mainstream imperative languages. </p> <h3 id="a75ae35933314755b1a0cdb665262bc5"> Improvements for those who want them <a href="#a75ae35933314755b1a0cdb665262bc5" title="permalink">#</a> </h3> <p> The essay <em>No Silver Bullet</em> is a perspicacious work. I think more people should read at least the first part, where Brooks explains why software development is hard. I find that analysis brilliant, and I agree: software development presupposes essential complexity. It's inherently hard. </p> <p> There's no reason to make it harder than it has to be, though. </p> <p> More than once, I've discussed productivity improvements with people, only to be met with the dismissal that 'there's no silver bullet'. </p> <p> Granted, there's no magical solution that will solve all problems with software development, but that doesn't mean that improvements can't be had. </p> <p> Consider the improvements I've argued for here. Everyone now uses the World Wide Web and sites like Stack Overflow for research; that particular improvement is firmly embedded in all organisations. On the other hand, I still regularly talk to organisations that don't routinely use automated testing. </p> <p> People still use centralised version control (like TFS or SVN). If there was ever a low-hanging fruit, changing to Git is one. Git is <em>free</em>, and there's plenty of tools you can use to migrate your version history to it. There's also plenty of training and help to be had. Yes, it'll require a small investment to make the change, but the productivity increase is significant. <blockquote> <p> "The future is already here — it's just not very evenly distributed." </p> <footer><cite>William Gibson</cite></footer> </blockquote> So it is with technology improvements. Automated testing is available, but not ubiquitous. Git is free, but still organisations stick to suboptimal version control. Haskell and F# are mature languages, yet programmers still program in C# or Java. </p> <h3 id="864e39a22bc84129bfecaafe33dd1757"> Summary <a href="#864e39a22bc84129bfecaafe33dd1757" title="permalink">#</a> </h3> <p> The essay <em>No Silver Bullet</em> was written in 1986, but seems to me to be increasingly misunderstood. When people today talk about it at all, it's mostly as an excuse to stay where they are. "There's no silver bullets," they'll say. </p> <p> The essay, however, doesn't argue that no improvements can be had. It only argues that no more order-of-magnitude improvements can be had. </p> <p> In the present essay I argue that, since Brooks wrote <em>No Silver Bullet</em>, more than one such improvement happened. Once the World Wide Web truly began furnishing <em>information at your fingertips</em>, you could be more productive because you wouldn't be <em>stuck</em> for days or weeks. Automated testing reduces the work that manual testers used to perform, as well as limiting regressions. </p> <p> If you accept my argument, that order-of-magnitude improvements appeared after 1986, this implies that Brooks' premise was wrong. In that case, there's no reason to believe that we've seen the last significant improvement to software development. </p> <p> I think that more such improvements await us. I suggest that statically typed functional programming offers such an advance, but if history teaches us anything, it seems that breakthroughs tend to be unpredictable. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="7e7e932f5eea47f3bab328c58e9d164a"> <div class="comment-author"><a href="http://blog.strobaek.org">Karsten Strøbæk</a></div> <div class="comment-content"> <p> As always I enjoy reading your blog, even though I don't understand half of it most of the time. Or is that most of it half of the time? Allow me to put a few observations forward. </p> <p> First I should confess, that I have actually not read the whole of Brook's essay. When I initially tried I got about half way through; it sounds like I should make another go at it. That of course will not stop me from commenting on the above. </p> <p> Brook talks about complexity. To me designing and implementing a software system is not complex. Quantum physics is complex. Flying an airplane is difficult. Software development may be difficult depending on the task at hand (and unfortunately the qualifications of the team), but I would argue that it at most falls into the same category as flying an airplane. </p> <p> I would properly also state, that there are no silver bullets. But like you I feel that people understand it incorrectly and there is definetely no reason for making things harder than they are. I think the examples of technology that helps are excellent and exactly describe that things do move forward. </p> <p> That being said, it does not take away the creativity of the right decomposition, the responsibility for getting the use cases right, and especially the liability for getting it wrong. Sadly especially the last of overlooked. People should be reminded of where the phrase 'live under the bridge' comes from. </p> <p> To end my ramblins, I would also look a little into the future. As you know I am somewhat sceptial about machine learning and AI. However, looking at the recent break throughs and use cases in these areas, I would not be surprised of a future where software development is done by 'an AI' assemblying pre-defined 'entities' to create the software we need. Like an F16 cannot be flown without a computer, future software cannot be created by a human. </p> </div> <div class="comment-date">2019-07-04 18:29:00 UTC</div> </div> <div class="comment" id="756066e5cb0e42368ff9eeb9569fa47f"> <div class="comment-author"><a href="/">Mark Seemann</a></div> <div class="comment-content"> <p> Karsten, thank you for writing. I'm not inclined to agree that software development falls into the same category of complexity as flying a plane. It seems to me to be orders of magnitudes more complex. </p> <p> Just look at error rates. </p> <p> Would you ever board an air plane if flying had error rates similar to those observed in software development? Would you fly even if only one percent of all flights ended with plane crash? </p> <p> In reality, flying is extremely safe. Would you claim that software development is as safe, predictable, and manageable as flying? </p> <p> I see no evidence of that. </p> <p> Are pilots significantly more capable human beings than software developers, or does something else explain the discrepancy in failure rates? </p> </div> <div class="comment-date">2019-07-05 15:47 UTC</div> </div> <div class="comment" id="7e7e932f5eea47f3bab328c58e9d164b"> <div class="comment-author"><a href="http://blog.strobaek.org">Karsten Strøbæk</a></div> <div class="comment-content"> <p> Hi Mark. The fact that error rates are higher in software development is more a statement to the bad state our industry is in and has been for a milinium or more. </p> <p> Why do we except that we produce crappy systems or in your words software that is no safe, predictable, and manageble? The list of excuses is very long and the list of results is very short. We as an industry are simply doing it wrong, but most people prefers hand waving and marketing than simple and plausible heuristic. </p> <p> To use your analogy about planes I could ask if you would fly with a place that had (only) been unit tested? Properly not as it is never the unit that fails, but always the integration. Should be test all integrations then? Yes, why not? </p> <p> The used of planes or pilots (or whatever) may have been bad. My point was, the I do not see software development as complex. </p> </div> <div class="comment-date">2019-07-05 20:12 UTC</div> </div> <div class="comment" id="0df7412992fb499d915e6f4cdbb644a0"> <div class="comment-author"><a href="/">Mark Seemann</a></div> <div class="comment-content"> <p> Karsten, if we, as an industry, are doing it wrong, then why are we doing that? </p> <p> And what should we be doing instead? </p> </div> <div class="comment-date">2019-07-06 16:00 UTC</div> </div> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/07/01/yes-silver-bullet Full binary tree catamorphism https://blog.ploeh.dk/2019/06/24/full-binary-tree-catamorphism/ Mon, 24 Jun 2019 06:00:00 UTC <div id="post"> <p> <em>The catamorphism for a full binary tree is a pair of functions.</em> </p> <p> This article is part of an <a href="/2019/04/29/catamorphisms">article series about catamorphisms</a>. A catamorphism is a <a href="/2017/10/04/from-design-patterns-to-category-theory">universal abstraction</a> that describes how to digest a data structure into a potentially more compact value. </p> <p> This article presents the catamorphism for a full <a href="https://en.wikipedia.org/wiki/Binary_tree">binary tree</a>, as well as how to identify it. The beginning of this article presents the catamorphism in C#, with examples. The rest of the article describes how to deduce the catamorphism. This part of the article presents my work in <a href="https://www.haskell.org">Haskell</a>. Readers not comfortable with Haskell can just read the first part, and consider the rest of the article as an optional appendix. </p> <p> A <em>full binary tree</em> (also known as a <em>proper</em> or <em>plane</em> binary tree) is a tree in which each node has either two or no branches. </p> <p> <img src="/content/binary/full-binary-tree-example.png" alt="A full binary tree example diagram, with each node containing integers."> </p> <p> The diagram shows an example of a tree of integers. The left branch contains two children, of which the right branch again contains two sub-branches. The rest of the nodes are leaf-nodes with no sub-branches. </p> <h3 id="d6b9699fa3894a4383f9b2b2992a9e8f"> C# catamorphism <a href="#d6b9699fa3894a4383f9b2b2992a9e8f" title="permalink">#</a> </h3> <p> As a C# representation of a full binary tree, I'll start with the <code>IBinaryTree&lt;T&gt;</code> API from <a href="/2018/08/13/a-visitor-functor">A Visitor functor</a>. The catamorphism is the <code>Accept</code> method: </p> <p> <pre><span style="color:#2b91af;">TResult</span>&nbsp;Accept&lt;<span style="color:#2b91af;">TResult</span>&gt;(<span style="color:#2b91af;">IBinaryTreeVisitor</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;visitor);</pre> </p> <p> So far in this article series, you've mostly seen <a href="/2018/05/22/church-encoding">Church-encoded</a> catamorphisms, so a catamorphism represented as a <a href="https://en.wikipedia.org/wiki/Visitor_pattern">Visitor</a> may be too big of a cognitive leap. We know, however, from <a href="/2018/06/25/visitor-as-a-sum-type">Visitor as a sum type</a> that a Visitor representation is isomorphic to a Church encoding. Since these are isomorphic, it's possible to refactor <code>IBinaryTree&lt;T&gt;</code> to a Church encoding. The <a href="https://github.com/ploeh/ChurchEncoding">GitHub repository</a> contains a series of commits that demonstrates how that refactoring works. Once you're done, you arrive at this <code>Match</code> method, which is the refactored <code>Accept</code> method: </p> <p> <pre><span style="color:#2b91af;">TResult</span>&nbsp;Match&lt;<span style="color:#2b91af;">TResult</span>&gt;(<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">TResult</span>,&nbsp;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;node,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;leaf);</pre> </p> <p> This method takes a pair of functions as arguments. The <code>node</code> function deals with an internal node in the tree (the blue nodes in the above diagram), whereas the <code>leaf</code> function deals with the leaf nodes (the green nodes in the diagram). </p> <p> The <code>leaf</code> function may be the easiest one to understand. A leaf node only contains a value of the type <code>T</code>, so the only operation the function has to support is translating the <code>T</code> value to a <code>TResult</code> value. This is also the premise of the <code>Leaf</code> class' implementation of the method: </p> <p> <pre><span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">T</span>&nbsp;item; <span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">TResult</span>&nbsp;Match&lt;<span style="color:#2b91af;">TResult</span>&gt;(<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">TResult</span>,&nbsp;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;node,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;leaf) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;leaf(item); }</pre> </p> <p> The <code>node</code> function is more tricky. It takes three input arguments, of the types <code>TResult</code>, <code>T</code>, and <code>TResult</code>. The roles of these are respectively <em>left</em>, <em>item</em>, and <em>right</em>. This is a typical representation of a binary node. Since there's always a left and a right branch, you put the node's value in the middle. As was the case with the <a href="/2019/06/10/tree-catamorphism">tree catamorphism</a>, the catamorphism function receives the branches as already-translated values; that is, both the left and right branch have already been translated to <code>TResult</code> when <code>node</code> is called. While it looks like magic, as always it's just the result of recursion: </p> <p> <pre><span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">IBinaryTree</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;left; <span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">T</span>&nbsp;item; <span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">IBinaryTree</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;right; <span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">TResult</span>&nbsp;Match&lt;<span style="color:#2b91af;">TResult</span>&gt;(<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">TResult</span>,&nbsp;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;node,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;leaf) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;node(left.Match(node,&nbsp;leaf),&nbsp;item,&nbsp;right.Match(node,&nbsp;leaf)); }</pre> </p> <p> This is the <code>Node&lt;T&gt;</code> class implementation of the <code>Match</code> method. It calls <code>node</code> and returns whatever it returns, but notice that as the <code>left</code> and <code>right</code> arguments, if first, recursively, calls <code>left.Match</code> and <code>right.Match</code>. This is how it can call <code>node</code> with the translated branches, as well as with the basic <code>item</code>. </p> <p> The recursion stops and unwinds on <code>left</code> and <code>right</code> whenever one of those are <code>Leaf</code> instances. </p> <h3 id="c64210d585c94cb78653b96380cbf0e6"> Examples <a href="#c64210d585c94cb78653b96380cbf0e6" title="permalink">#</a> </h3> <p> You can use <code>Match</code> to implement most other behaviour you'd like <code>IBinaryTree&lt;T&gt;</code> to have. In <a href="/2018/08/13/a-visitor-functor">the original article on the full binary tree functor</a> you saw how to implement <code>Select</code> with a Visitor, but now that the API is Church-encoded, you can derive <code>Select</code> from <code>Match</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IBinaryTree</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;Select&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;">IBinaryTree</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;tree, &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;">if</span>&nbsp;(tree&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>(tree)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(selector&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>(selector)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;tree.Match( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node:&nbsp;(l,&nbsp;x,&nbsp;r)&nbsp;=&gt;&nbsp;Create(l,&nbsp;selector(x),&nbsp;r), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;leaf:&nbsp;x&nbsp;=&gt;&nbsp;Leaf(selector(x))); }</pre> </p> <p> In the <code>leaf</code> case, the <code>Select</code> method simply calls <code>selector</code> with the <code>x</code> value it receives, and puts the resulting <code>TResult</code> object into a new <code>Leaf</code> object. </p> <p> In the <code>node</code> case, the lambda expression receives three arguments: <code>l</code> and <code>r</code> are the <em>already-translated</em> left and right branches, so you only need to call <code>selector</code> on <code>x</code> and call the <code>Create</code> helper method to produce a new <code>Node</code> object. </p> <p> You can also implement more specialised functionality, like calculating the sum of nodes, measuring the depth of the tree, and similar functions. You saw equivalent examples in the <a href="/2019/06/10/tree-catamorphism">previous article</a>. </p> <p> For the examples in this article, I'll use the tree shown in the above diagram. Using static helper methods, you can write it like this: </p> <p> <pre><span style="color:blue;">var</span>&nbsp;tree&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">BinaryTree</span>.Create( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">BinaryTree</span>.Create( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">BinaryTree</span>.Leaf(42), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1337, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">BinaryTree</span>.Create( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">BinaryTree</span>.Leaf(2112), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;5040, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">BinaryTree</span>.Leaf(1984))), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">BinaryTree</span>.Leaf(90125));</pre> </p> <p> To calculate the sum of all nodes, you can write a function like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">int</span>&nbsp;Sum(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IBinaryTree</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;tree) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;tree.Match((l,&nbsp;x,&nbsp;r)&nbsp;=&gt;&nbsp;l&nbsp;+&nbsp;x&nbsp;+&nbsp;r,&nbsp;x&nbsp;=&gt;&nbsp;x); }</pre> </p> <p> The <code>leaf</code> function just returns the value of the node, while the <code>node</code> function adds the numbers together. It works for the above <code>tree</code>: </p> <p> <pre>&gt; tree.Sum() 100642</pre> </p> <p> To find the maximum value, you can write another extension method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">int</span>&nbsp;Max(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IBinaryTree</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;tree) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;tree.Match((l,&nbsp;x,&nbsp;r)&nbsp;=&gt;&nbsp;<span style="color:#2b91af;">Math</span>.Max(<span style="color:#2b91af;">Math</span>.Max(l,&nbsp;r),&nbsp;x),&nbsp;x&nbsp;=&gt;&nbsp;x); }</pre> </p> <p> Again, the <code>leaf</code> function just returns the value of the node. The <code>node</code> function receives the value of the current node <code>x</code>, as well as the already-found maximum value of the left branch and the right branch; it then returns the maximum of these three values: </p> <p> <pre>&gt; tree.Max() 90125</pre> </p> <p> As was also the case for trees, both of these operations are part of the standard repertoire available via a data structure's <em>fold</em>. That's not the case for the next two functions, which can't be implemented using a fold, but which can be defined with the catamorphism. The first is a function to count the leaves of a tree: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">int</span>&nbsp;CountLeaves&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IBinaryTree</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;tree) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;tree.Match((l,&nbsp;_,&nbsp;r)&nbsp;=&gt;&nbsp;l&nbsp;+&nbsp;r,&nbsp;_&nbsp;=&gt;&nbsp;1); }</pre> </p> <p> Since the <code>leaf</code> function handles a leaf node, the number of leaf nodes in a leaf node is, by definition, <em>one</em>. Thus, that function can ignore the value of the node and always return <code>1</code>. The <code>node</code> function, on the other hand, receives the number of leaf nodes on the left-hand side (<code>l</code>), the value of the current node, and the number of leaf nodes on the right-hand side (<code>r</code>). Notice that since an internal node is never a leaf node, it doesn't count; instead, just add <code>l</code> and <code>r</code> together. Notice that, again, the value of the node itself is irrelevant. </p> <p> How many leaf nodes does the above tree have? </p> <p> <pre>&gt; tree.CountLeaves() 4</pre> </p> <p> You can also measure the maximum depth of a tree: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">int</span>&nbsp;MeasureDepth&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IBinaryTree</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;tree) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;tree.Match((l,&nbsp;_,&nbsp;r)&nbsp;=&gt;&nbsp;1&nbsp;+&nbsp;<span style="color:#2b91af;">Math</span>.Max(l,&nbsp;r),&nbsp;_&nbsp;=&gt;&nbsp;0); }</pre> </p> <p> Like in the previous article, I've arbitrarily decided that the depth of a leaf node is <em>zero</em>; therefore, the <code>leaf</code> function always returns <code>0</code>. The <code>node</code> function receives the depth of the left and right branches, and returns the maximum of those two values, plus one, since the current node adds one level of depth. </p> <p> <pre>&gt; tree.MeasureDepth() 3</pre> </p> <p> You may not have much need for working with full binary trees in your normal, day-to-day C# work, but I found it worthwhile to include this example for a couple of reasons. First, because the original of the API shows that a catamorphism may be hiding in a Visitor. Second, because binary trees are interesting, in that they're foldable <a href="/2018/03/22/functors">functors</a>, but not monads. </p> <p> Where does the catamorphism come from, though? How can you trust that the <code>Match</code> method is the catamorphism? </p> <h3 id="d015bcc9afe742408d7c8ba6c6edce2a"> Binary tree F-Algebra <a href="#d015bcc9afe742408d7c8ba6c6edce2a" title="permalink">#</a> </h3> <p> As in the <a href="/2019/06/10/tree-catamorphism">previous article</a>, I'll use <code>Fix</code> and <code>cata</code> as explained in <a href="https://bartoszmilewski.com">Bartosz Milewski</a>'s excellent <a href="https://bartoszmilewski.com/2017/02/28/f-algebras/">article on F-Algebras</a>. </p> <p> As always, start with the underlying endofunctor. You can think of this one as a specialisation of the rose tree from the previous article: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;FullBinaryTreeF&nbsp;a&nbsp;c&nbsp;=&nbsp;LeafF&nbsp;a&nbsp;|&nbsp;NodeF&nbsp;c&nbsp;a&nbsp;c&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;(<span style="color:blue;">FullBinaryTreeF</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;_&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(LeafF&nbsp;x)&nbsp;=&nbsp;LeafF&nbsp;x &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;f&nbsp;(NodeF&nbsp;l&nbsp;x&nbsp;r)&nbsp;=&nbsp;NodeF&nbsp;(f&nbsp;l)&nbsp;x&nbsp;(f&nbsp;r)</pre> </p> <p> As usual, I've called the 'data' type <code>a</code> and the carrier type <code>c</code> (for <em>carrier</em>). The <code>Functor</code> instance as usual translates the carrier type; the <code>fmap</code> function has the type <code>(c -&gt; c1) -&gt; FullBinaryTreeF a c -&gt; FullBinaryTreeF a c1</code>. </p> <p> As was the case when deducing the recent catamorphisms, Haskell isn't too happy about defining instances for a type like <code>Fix (FullBinaryTreeF a)</code>. To address that problem, you can introduce a <code>newtype</code> wrapper: </p> <p> <pre><span style="color:blue;">newtype</span>&nbsp;FullBinaryTreeFix&nbsp;a&nbsp;= &nbsp;&nbsp;FullBinaryTreeFix&nbsp;{&nbsp;unFullBinaryTreeFix&nbsp;::&nbsp;Fix&nbsp;(FullBinaryTreeF&nbsp;a)&nbsp;} &nbsp;&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> You can define <code>Functor</code>, <code>Foldable</code>, and <code>Traversable</code> instances (but not <code>Monad</code>) for this type without resorting to any funky GHC extensions. Keep in mind that ultimately, the purpose of all this code is just to figure out what the catamorphism looks like. This code isn't intended for actual use. </p> <p> A pair of helper functions make it easier to define <code>FullBinaryTreeFix</code> values: </p> <p> <pre><span style="color:#2b91af;">fbtLeafF</span>&nbsp;::&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">FullBinaryTreeFix</span>&nbsp;a fbtLeafF&nbsp;=&nbsp;FullBinaryTreeFix&nbsp;.&nbsp;Fix&nbsp;.&nbsp;LeafF <span style="color:#2b91af;">fbtNodeF</span>&nbsp;::&nbsp;<span style="color:blue;">FullBinaryTreeFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">FullBinaryTreeFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">FullBinaryTreeFix</span>&nbsp;a fbtNodeF&nbsp;(FullBinaryTreeFix&nbsp;l)&nbsp;x&nbsp;(FullBinaryTreeFix&nbsp;r)&nbsp;=&nbsp;FullBinaryTreeFix&nbsp;$&nbsp;Fix&nbsp;$&nbsp;NodeF&nbsp;l&nbsp;x&nbsp;r</pre> </p> <p> In order to distinguish these helper functions from the ones that create <code>TreeFix a</code> values, I prefixed them with <code>fbt</code> (for <em>Full Binary Tree</em>). <code>fbtLeafF</code> creates a leaf node: </p> <p> <pre>Prelude Fix FullBinaryTree&gt; fbtLeafF "fnaah" FullBinaryTreeFix {unFullBinaryTreeFix = Fix (LeafF "fnaah")}</pre> </p> <p> <code>fbtNodeF</code> is a helper function to create an internal node: </p> <p> <pre>Prelude Fix FullBinaryTree&gt; fbtNodeF (fbtLeafF 1337) 42 (fbtLeafF 2112) FullBinaryTreeFix {unFullBinaryTreeFix = Fix (NodeF (Fix (LeafF 1337)) 42 (Fix (LeafF 2112)))}</pre> </p> <p> The <code>FullBinaryTreeFix</code> type, or rather the underlying <code>FullBinaryTreeF a</code> functor, is all you need to identify the catamorphism. </p> <h3 id="ced0da7dc61943b0be872ec79b4e3651"> Haskell catamorphism <a href="#ced0da7dc61943b0be872ec79b4e3651" title="permalink">#</a> </h3> <p> At this point, you have two out of three elements of an F-Algebra. You have an endofunctor (<code>FullBinaryTreeF a</code>), and an object <code>c</code>, but you still need to find a morphism <code>FullBinaryTreeF a c -&gt; c</code>. Notice that the algebra you have to find is the function that reduces the functor to its <em>carrier type</em> <code>c</code>, not the 'data type' <code>a</code>. This takes some time to get used to, but that's how catamorphisms work. This doesn't mean, however, that you get to ignore <code>a</code>, as you'll see. </p> <p> As in the previous articles, start by writing a function that will become the catamorphism, based on <code>cata</code>: </p> <p> <pre>fullBinaryTreeF&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unFullBinaryTreeFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(LeafF&nbsp;x)&nbsp;=&nbsp;<span style="color:blue;">undefined</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(NodeF&nbsp;l&nbsp;x&nbsp;r)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> While this compiles, with its <code>undefined</code> implementation of <code>alg</code>, it obviously doesn't do anything useful. I find, however, that it helps me think. How can you return a value of the type <code>c</code> from <code>alg</code>? You could pass a function argument to the <code>fullBinaryTreeF</code> function and use it with <code>x</code>: </p> <p> <pre>fullBinaryTreeF&nbsp;fl&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unFullBinaryTreeFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(LeafF&nbsp;x)&nbsp;=&nbsp;fl&nbsp;x &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(NodeF&nbsp;l&nbsp;x&nbsp;r)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> I called the function <code>fl</code> for <em>function, leaf</em>, because we're also going to need a function for the <code>NodeF</code> case: </p> <p> <pre><span style="color:#2b91af;">fullBinaryTreeF</span>&nbsp;::&nbsp;(c&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">FullBinaryTreeFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c fullBinaryTreeF&nbsp;fn&nbsp;fl&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unFullBinaryTreeFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(LeafF&nbsp;x)&nbsp;=&nbsp;fl&nbsp;x &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(NodeF&nbsp;l&nbsp;x&nbsp;r)&nbsp;=&nbsp;fn&nbsp;l&nbsp;x&nbsp;r</pre> </p> <p> This works. Since <code>cata</code> has the type <code>Functor f =&gt; (f a -&gt; a) -&gt; Fix f -&gt; a</code>, that means that <code>alg</code> has the type <code>f a -&gt; a</code>. In the case of <code>FullBinaryTreeF</code>, the compiler infers that the <code>alg</code> function has the type <code>FullBinaryTreeF a c -&gt; c</code>, which is just what you need! </p> <p> You can now see what the carrier type <code>c</code> is for. It's the type that the algebra extracts, and thus the type that the catamorphism returns. </p> <p> This, then, is the catamorphism for a full binary tree. As always, it's not the only possible catamorphism, since you can easily reorder the arguments to both <code>fullBinaryTreeF</code>, <code>fn</code>, and <code>fl</code>. These would all be isomorphic, though. </p> <h3 id="3f87d49db58f4cd59dec76a97d31c0d2"> Basis <a href="#3f87d49db58f4cd59dec76a97d31c0d2" title="permalink">#</a> </h3> <p> You can implement most other useful functionality with <code>treeF</code>. Here's the <code>Functor</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;<span style="color:blue;">FullBinaryTreeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;f&nbsp;=&nbsp;fullBinaryTreeF&nbsp;(\l&nbsp;x&nbsp;r&nbsp;-&gt;&nbsp;fbtNodeF&nbsp;l&nbsp;(f&nbsp;x)&nbsp;r)&nbsp;(fbtLeafF&nbsp;.&nbsp;f)</pre> </p> <p> The <code>fl</code> function first invokes <code>f</code>, followed by <code>fbtLeafF</code>. The <code>fn</code> function uses the <code>fbtNodeF</code> helper function to create a new internal node. <code>l</code> and <code>r</code> are already-translated branches, so you just need to call <code>f</code> with the node value <code>x</code>. </p> <p> There's no <code>Monad</code> instance for binary trees, because you can't flatten a binary tree of binary trees. You can, on the other hand, define a <code>Foldable</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Foldable</span>&nbsp;<span style="color:blue;">FullBinaryTreeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;foldMap&nbsp;f&nbsp;=&nbsp;fullBinaryTreeF&nbsp;(\l&nbsp;x&nbsp;r&nbsp;-&gt;&nbsp;l&nbsp;&lt;&gt;&nbsp;f&nbsp;x&nbsp;&lt;&gt;&nbsp;r)&nbsp;f</pre> </p> <p> The <code>f</code> function passed to <code>foldMap</code> has the type <code>Monoid m =&gt; (a -&gt; m)</code>, so the <code>fl</code> function that handles leaf nodes simply calls <code>f</code> with the contents of the node. The <code>fn</code> function receives two branches already translated to <code>m</code>, so it just has to call <code>f</code> with <code>x</code> and combine all the <code>m</code> values using the <code>&lt;&gt;</code> operator. </p> <p> The <code>Traversable</code> instance follows right on the heels of <code>Foldable</code>: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Traversable</span>&nbsp;<span style="color:blue;">FullBinaryTreeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;sequenceA&nbsp;=&nbsp;fullBinaryTreeF&nbsp;(liftA3&nbsp;fbtNodeF)&nbsp;(<span style="color:blue;">fmap</span>&nbsp;fbtLeafF)</pre> </p> <p> There are operations on binary trees that you can implement with a fold, but some that you can't. Consider the tree shown in the diagram at the beginning of the article. This is also the tree that the above C# examples use. In Haskell, using <code>FullBinaryTreeFix</code>, you can define that tree like this: </p> <p> <pre>tree&nbsp;=&nbsp; &nbsp;&nbsp;fbtNodeF &nbsp;&nbsp;&nbsp;&nbsp;(fbtNodeF &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(fbtLeafF&nbsp;42) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1337 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(fbtNodeF &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(fbtLeafF&nbsp;2112) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;5040 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(fbtLeafF&nbsp;1984))) &nbsp;&nbsp;&nbsp;&nbsp;2 &nbsp;&nbsp;&nbsp;&nbsp;(fbtLeafF&nbsp;90125)</pre> </p> <p> Since <code>FullBinaryTreeFix</code> is <code>Foldable</code>, and that type class already comes with <code>sum</code> and <code>maximum</code> functions, no further work is required to repeat the first two of the above C# examples: </p> <p> <pre>Prelude Fix FullBinaryTree&gt; sum tree 100642 Prelude Fix FullBinaryTree&gt; maximum tree 90125</pre> </p> <p> Counting leaves, or measuring the depth of a tree, on the other hand, is impossible with the <code>Foldable</code> instance, but can be implemented using the catamorphism: </p> <p> <pre><span style="color:#2b91af;">countLeaves</span>&nbsp;::&nbsp;<span style="color:blue;">Num</span>&nbsp;n&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;<span style="color:blue;">FullBinaryTreeFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;n countLeaves&nbsp;=&nbsp;fullBinaryTreeF&nbsp;(\l&nbsp;_&nbsp;r&nbsp;-&gt;&nbsp;l&nbsp;+&nbsp;r)&nbsp;(<span style="color:blue;">const</span>&nbsp;1) <span style="color:#2b91af;">treeDepth</span>&nbsp;::&nbsp;(<span style="color:blue;">Ord</span>&nbsp;n,&nbsp;<span style="color:blue;">Num</span>&nbsp;n)&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;<span style="color:blue;">FullBinaryTreeFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;n treeDepth&nbsp;=&nbsp;fullBinaryTreeF&nbsp;(\l&nbsp;_&nbsp;r&nbsp;-&gt;&nbsp;1&nbsp;+&nbsp;<span style="color:blue;">max</span>&nbsp;l&nbsp;r)&nbsp;(<span style="color:blue;">const</span>&nbsp;0)</pre> </p> <p> The reasoning is the same as already explained in the above C# examples. The functions also produce the same results: </p> <p> <pre>Prelude Fix FullBinaryTree&gt; countLeaves tree 4 Prelude Fix FullBinaryTree&gt; treeDepth tree 3</pre> </p> <p> This, hopefully, illustrates that the catamorphism is more capable, and that the fold is just a (list-biased) specialisation. </p> <h3 id="81b3e77b6fbe4760bc8c74805e4edba8"> Summary <a href="#81b3e77b6fbe4760bc8c74805e4edba8" title="permalink">#</a> </h3> <p> The catamorphism for a full binary tree is a pair of functions. One function handles internal nodes, while the other function handles leaf nodes. </p> <p> I thought it was interesting to show this example for two reasons: First, the original example was a Visitor implementation, and I think it's worth realising that a Visitor's <code>Accept</code> method can also be viewed as a catamorphism. Second, a binary tree is an example of a data structure that has a fold, but isn't a monad. </p> <p> All articles in the article series have, so far, covered data structures well-known from computer science. The next example will, on the other hand, demonstrate that even completely ad-hoc domain-specific data structures have catamorphisms. </p> <p> <strong>Next:</strong> <a href="/2019/07/08/payment-types-catamorphism">Payment types catamorphism</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/06/24/full-binary-tree-catamorphism Composition Root location https://blog.ploeh.dk/2019/06/17/composition-root-location/ Mon, 17 Jun 2019 05:55:00 UTC <div id="post"> <p> <em>A Composition Root should be located near the point where user code first executes.</em> </p> <p> Prompted by a recent Internet discussion, my <a href="https://amzn.to/2TE8tJx">DIPPP</a> co-author <a href="https://blogs.cuttingedge.it/steven/">Steven van Deursen</a> wrote to me in order to help clarify the <a href="/2011/07/28/CompositionRoot">Composition Root</a> pattern. </p> <p> In the email, Steven ponders whether it's defensible to use an API that <a href="/2010/11/01/PatternRecognitionAbstractFactoryorServiceLocator">looks like a Service Locator</a> from within a unit test. He specifically calls out my article that describes the <a href="/2013/03/11/auto-mocking-container">Auto-mocking Container design pattern</a>. </p> <p> In that article, I show how to use Castle Windsor's <code>Resolve</code> method from within a unit test: </p> <p> <pre style="margin: 0px;">[<span style="color: #2b91af;">Fact</span>] <span style="color: blue;">public</span> <span style="color: blue;">void</span> SutIsController() { &nbsp;&nbsp;&nbsp; <span style="color: blue;">var</span> container = <span style="color: blue;">new</span> <span style="color: #2b91af;">WindsorContainer</span>().Install(<span style="color: blue;">new</span> <span style="color: #2b91af;">ShopFixture</span>()); &nbsp;&nbsp;&nbsp; <span style="color: blue;">var</span> sut = container.Resolve&lt;<span style="color: #2b91af;">BasketController</span>&gt;(); &nbsp;&nbsp;&nbsp; <span style="color: #2b91af;">Assert</span>.IsAssignableFrom&lt;<span style="color: #2b91af;">IHttpController</span>&gt;(sut); }</pre> </p> <p> Is the test using a <a href="/2010/02/03/ServiceLocatorisanAnti-Pattern">Service Locator</a>? If so, why is that okay? If not, why isn't it a Service Locator? </p> <p> This article argues that that this use of <code>Resolve</code> isn't a Service Locator. </p> <h3 id="e9a6c124fa1d4610ae57b3cba83254b0"> Entry points defined <a href="#e9a6c124fa1d4610ae57b3cba83254b0" title="permalink">#</a> </h3> <p> The <a href="/2011/07/28/CompositionRoot">original article about the Composition Root pattern</a> defines a Composition Root as the place where you compose your object graph(s). It repeatedly describes how this ought to happen in, or as close as possible to, the application's entry point. I believe that this definition is compatible with the pattern description given in <a href="https://amzn.to/2TE8tJx">our book</a>. </p> <p> I do realise, however, that we may never have explicitly defined what an <em>entry point</em> is. </p> <p> In order to do so, it may be helpful to establish a bit of terminology. In the following, I'll use the terms <em>user code</em> as opposed to <em>framework code</em>. </p> <p> Much of the code you write probably runs within some sort of framework. If you're writing a web application, you're probably using a web framework. If you're writing a message-based application, you might be using some message bus, or actor, framework. If you're writing an app for a mobile device, you're probably using some sort of framework for that, too. </p> <p> Even as a programmer, you're a <em>user</em> of frameworks. </p> <p> As I usually do, I'll use <a href="http://tomasp.net">Tomas Petricek</a>'s distinction between <a href="http://tomasp.net/blog/2015/library-frameworks">libraries and frameworks</a>. A library is a collection of APIs that you can call. A framework is a software system that calls your code. </p> <p> <img src="/content/binary/user-code-in-framework.png" alt="User code running in a framework."> </p> <p> The reality is often more complex, as illustrated by the figure. While a framework will call your code, you can also invoke APIs afforded by the framework. </p> <p> The point, however, is that <em>user code</em> is code that you write, while <em>framework code</em> is code that someone else wrote to develop the framework. The framework starts up first, and at some point in its lifetime, it calls your code. </p> <p class="text-center"> <strong>Definition:</strong> The <em>entry point</em> is the user code that the framework calls first. </p> <p> As an example, in ASP.NET Core, the (conventional) <code>Startup</code> class is the first user code that the framework calls. (If you follow Tomas Petricek's definition to the letter, ASP.NET Core isn't a framework, but a library, because you have to write a <code>Main</code> method and call <code>WebHost.CreateDefaultBuilder(args).UseStartup&lt;Startup&gt;().Build().Run()</code>. In reality, though, you're supposed to configure the application from your <code>Startup</code> class, making it the <em>de facto</em> entry point.) </p> <h3 id="61e3f212e0e244f18ac998f4b9fbb635"> Unit testing endpoints <a href="#61e3f212e0e244f18ac998f4b9fbb635" title="permalink">#</a> </h3> <p> Most .NET-based unit testing packages are frameworks. There's typically little explicit configuration. Instead, you just write a method and adorn it with an attribute: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">async</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;ReservationSucceeds() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;repo&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">FakeReservationsRepository</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;sut&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ReservationsController</span>(10,&nbsp;repo); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;reservation&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;date:&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTimeOffset</span>(2018,&nbsp;8,&nbsp;13,&nbsp;16,&nbsp;53,&nbsp;0,&nbsp;<span style="color:#2b91af;">TimeSpan</span>.FromHours(2)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;email:&nbsp;<span style="color:#a31515;">&quot;mark@example.com&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;name:&nbsp;<span style="color:#a31515;">&quot;Mark&nbsp;Seemann&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;quantity:&nbsp;4); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;actual&nbsp;=&nbsp;<span style="color:blue;">await</span>&nbsp;sut.Post(reservation); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.True(repo.Contains(reservation.Accept())); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;expectedId&nbsp;=&nbsp;repo.GetId(reservation.Accept()); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;ok&nbsp;=&nbsp;<span style="color:#2b91af;">Assert</span>.IsAssignableFrom&lt;<span style="color:#2b91af;">OkActionResult</span>&gt;(actual); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(expectedId,&nbsp;ok.Value); } [<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">async</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;ReservationFails() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;repo&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">FakeReservationsRepository</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;sut&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ReservationsController</span>(10,&nbsp;repo); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;reservation&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Reservation</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;date:&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTimeOffset</span>(2018,&nbsp;8,&nbsp;13,&nbsp;16,&nbsp;53,&nbsp;0,&nbsp;<span style="color:#2b91af;">TimeSpan</span>.FromHours(2)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;email:&nbsp;<span style="color:#a31515;">&quot;mark@example.com&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;name:&nbsp;<span style="color:#a31515;">&quot;Mark&nbsp;Seemann&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;quantity:&nbsp;11); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;actual&nbsp;=&nbsp;<span style="color:blue;">await</span>&nbsp;sut.Post(reservation); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.False(reservation.IsAccepted); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.False(repo.Contains(reservation)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.IsAssignableFrom&lt;<span style="color:#2b91af;">InternalServerErrorActionResult</span>&gt;(actual); }</pre> </p> <p> With <a href="https://xunit.net">xUnit.net</a>, the attribute is called <code>[Fact]</code>, but the principle is the same in <a href="https://nunit.org">NUnit</a> and MSTest, only that names are different. </p> <p> Where's the entry point? </p> <p> Each test is it's own entry point. The test is (typically) the first user code that the test runner executes. Furthermore, each test runs independently of any other. </p> <p> For the sake of argument, you could write each test case in a new application, and run all your test applications in parallel. It would be impractical, but it oughtn't change the way you organise the tests. Each test method is, conceptually, a mini-application. </p> <p> A test method is its own Composition Root; or, more generally, each test has its own Composition Root. In fact, xUnit.net has various extensibility points that enable you to hook into the framework before each test method executes. You can, for example, <a href="/2010/10/08/AutoDataTheorieswithAutoFixture">combine a <code>[Theory]</code> attribute with a custom <code>AutoDataAttribute</code></a>, or you can adorn your tests with a <code>BeforeAfterTestAttribute</code>. This doesn't change that the test runner will run each test case independently of all the other tests. Those pre-execution hooks play the same role as middleware in real applications. </p> <p> You can, therefore, consider the <a href="/2013/06/24/a-heuristic-for-formatting-code-according-to-the-aaa-pattern">Arrange phase</a> the Composition Root for each test. </p> <p> Thus, I don't consider the use of an Auto-mocking Container to be a Service Locator, since <a href="/2011/08/25/ServiceLocatorrolesvs.mechanics">its role is to resolve object graphs at the entry point instead of locating services from arbitrary locations in the code base</a>. </p> <h3 id="200be4483e4b4369abe5912b2a8213c3"> Summary <a href="#200be4483e4b4369abe5912b2a8213c3" title="permalink">#</a> </h3> <p> A Composition Root is located at, or near, the <em>entry point</em>. An entry point is where <em>user code</em> is first executed by a framework. Each unit test method constitutes a separate, independent entry point. Therefore, it's consistent with these definitions to use an Auto-mocking Container in a unit test. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/06/17/composition-root-location Tree catamorphism https://blog.ploeh.dk/2019/06/10/tree-catamorphism/ Mon, 10 Jun 2019 09:10:00 UTC <div id="post"> <p> <em>The catamorphism for a tree is just a single function with a particular type.</em> </p> <p> This article is part of an <a href="/2019/04/29/catamorphisms">article series about catamorphisms</a>. A catamorphism is a <a href="/2017/10/04/from-design-patterns-to-category-theory">universal abstraction</a> that describes how to digest a data structure into a potentially more compact value. </p> <p> This article presents the catamorphism for a <a href="https://en.wikipedia.org/wiki/Tree_(data_structure)">tree</a>, as well as how to identify it. The beginning of this article presents the catamorphism in C#, with examples. The rest of the article describes how to deduce the catamorphism. This part of the article presents my work in <a href="https://www.haskell.org">Haskell</a>. Readers not comfortable with Haskell can just read the first part, and consider the rest of the article as an optional appendix. </p> <p> A tree is a general-purpose data structure where each node in a tree has an associated value. Each node can have an arbitrary number of branches, including none. </p> <p> <img src="/content/binary/tree-example.png" alt="A tree example diagram, with each node containing integers."> </p> <p> The diagram shows an example of a tree of integers. The left branch contains a sub-tree with only a single branch, whereas the right branch contains a sub-tree with three branches. Each of the leaf nodes are trees in their own right, but they all have zero branches. </p> <p> In this example, each branch at the 'same level' has the same depth, but this isn't required. </p> <h3 id="7d3f657d0c6b443f83eac89370e0c660"> C# catamorphism <a href="#7d3f657d0c6b443f83eac89370e0c660" title="permalink">#</a> </h3> <p> As a C# representation of a tree, I'll use the <code>Tree&lt;T&gt;</code> class from <a href="/2018/08/06/a-tree-functor">A Tree functor</a>. The catamorphism is this instance method on <code>Tree&lt;T&gt;</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">TResult</span>&nbsp;Cata&lt;<span style="color:#2b91af;">TResult</span>&gt;(<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;func) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;func(Item,&nbsp;children.Select(c&nbsp;=&gt;&nbsp;c.Cata(func)).ToArray()); }</pre> </p> <p> Contrary to previous articles, I didn't call this method <code>Match</code>, but simply <code>Cata</code> (for <em>catamorphism</em>). The reason is that those other methods are called <code>Match</code> for a particular reason. The data structures for which they are catamorphisms are all <a href="/2018/05/22/church-encoding">Church-encoded</a> <a href="https://en.wikipedia.org/wiki/Tagged_union">sum types</a>. For those types, the <code>Match</code> methods enable a syntax similar to pattern matching in <a href="https://fsharp.org">F#</a>. That's not the case for <code>Tree&lt;T&gt;</code>. It's not a sum type, and it isn't Church-encoded. </p> <p> The method takes a single function as an input argument. This is the first catamorphism in this article series that isn't made up of a pair of some sort. The <a href="/2019/05/06/boolean-catamorphism">Boolean catamorphism</a> is a pair of values, the <a href="/2019/05/20/maybe-catamorphism">Maybe catamorphism</a> is a pair made up of a value and a function, and the <a href="/2019/06/03/either-catamorphism">Either catamorphism</a> is a pair of functions. The tree catamorphism, in contrast, is just a single function. </p> <p> The first argument to the function is a value of the type <code>T</code>. This will be an <code>Item</code> value. The second argument to the function is a finite collection of <code>TResult</code> values. This may take a little time getting used to, but it's a collection of already reduced sub-trees. When you supply such a function to <code>Cata</code>, that function must return a single value of the type <code>TResult</code>. Thus, the function must be able to digest a finite collection of <code>TResult</code> values, as well as a <code>T</code> value, to a single <code>TResult</code> value. </p> <p> The <code>Cata</code> method accomplishes this by calling <code>func</code> with the current <code>Item</code>, as well as by recursively applying itself to each of the sub-trees. Eventually, <code>Cata</code> will recurse into leaf nodes, which means that <code>children</code> will be empty. When that happens, the lambda expression inside <code>children.Select</code> never runs, and recursion stops and unwinds. </p> <h3 id="167ba023ee654db39fb5eb448d35a8df"> Examples <a href="#167ba023ee654db39fb5eb448d35a8df" title="permalink">#</a> </h3> <p> You can use <code>Cata</code> to implement most other behaviour you'd like <code>Tree&lt;T&gt;</code> to have. In <a href="/2018/08/06/a-tree-functor">the original article on the Tree functor</a> you saw an ad-hoc implementation of <code>Select</code>, but instead, you can derive <code>Select</code> from <code>Cata</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Tree</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;Select&lt;<span style="color:#2b91af;">TResult</span>&gt;(<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;Cata&lt;<span style="color:#2b91af;">Tree</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&gt;((x,&nbsp;nodes)&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Tree</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;(selector(x),&nbsp;nodes)); }</pre> </p> <p> The lambda expression receives <code>x</code>, an object of the type <code>T</code>, as well as <code>nodes</code>, which is a finite collection of already translated sub-trees. It simply translates <code>x</code> with <code>selector</code> and returns a <code>new Tree&lt;TResult&gt;</code> with the translated value and the already translated <code>nodes</code>. </p> <p> This works just as well as the ad-hoc implementation; it passes all the same tests as shown in the previous article. </p> <p> If you have a tree of numbers, you can add them all together: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">int</span>&nbsp;Sum(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Tree</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;tree) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;tree.Cata&lt;<span style="color:blue;">int</span>&gt;((x,&nbsp;xs)&nbsp;=&gt;&nbsp;x&nbsp;+&nbsp;xs.Sum()); }</pre> </p> <p> This uses the built-in <a href="https://docs.microsoft.com/dotnet/api/system.linq.enumerable.sum">Sum method</a> for <code>IEnumerable&lt;T&gt;</code> to add all the partly calculated sub-trees together, and then adds the value of the current node. In this and remaining examples, I'll use the tree shown in the above diagram: </p> <p> <pre><span style="color:#2b91af;">Tree</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;tree&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Tree</span>.Create(42, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Tree</span>.Create(1337, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Tree</span>.Leaf(-3)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Tree</span>.Create(7, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Tree</span>.Leaf(-99), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Tree</span>.Leaf(100), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Tree</span>.Leaf(0)));</pre> </p> <p> You can now calculate the sum of all these nodes: </p> <p> <pre>&gt; tree.Sum() 1384</pre> </p> <p> Another option is to find the maximum value anywhere in a tree: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">int</span>&nbsp;Max(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Tree</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;tree) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;tree.Cata&lt;<span style="color:blue;">int</span>&gt;((x,&nbsp;xs)&nbsp;=&gt;&nbsp;xs.Any()&nbsp;?&nbsp;<span style="color:#2b91af;">Math</span>.Max(x,&nbsp;xs.Max())&nbsp;:&nbsp;x); }</pre> </p> <p> This method again utilises one of the LINQ methods available via the .NET base class library: <a href="https://docs.microsoft.com/dotnet/api/system.linq.enumerable.max">Max</a>. It is, however, necessary to first check whether the partially reduced <code>xs</code> is empty or not, because the <code>Max</code> extension method on <code>IEnumerable&lt;int&gt;</code> doesn't know how to deal with an empty collection (it throws an exception). When <code>xs</code> is empty that implies a leaf node, in which case you can simply return <code>x</code>; otherwise, you'll first have to use the <code>Max</code> method on <code>xs</code> to find the maximum value there, and then use <code>Math.Max</code> to find the maximum of those two. (I'll here remind the attentive reader that finding the maximum number forms a <a href="/2017/11/27/semigroups">semigroup</a> and that <a href="/2017/12/11/semigroups-accumulate">semigroups accumulate</a> when collections are non-empty. It all fits together. Isn't maths lovely?) </p> <p> Using the same <code>tree</code> as before, you can see that this method, too, works as expected: </p> <p> <pre>&gt; tree.Max() 1337</pre> </p> <p> So far, these two extension methods are just specialised <em>folds</em>. In Haskell, <code>Foldable</code> is a specific type class, and <code>sum</code> and <code>max</code> are available for all instances. As promised in <a href="/2019/04/29/catamorphisms">the introduction to the series</a>, though, there are some functions on trees that you can't implement using a fold. One of these is to count all the leaf nodes. You can still derive that functionality from the catamorphism, though: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">int</span>&nbsp;CountLeaves() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;Cata&lt;<span style="color:blue;">int</span>&gt;((x,&nbsp;xs)&nbsp;=&gt;&nbsp;xs.Any()&nbsp;?&nbsp;xs.Sum()&nbsp;:&nbsp;1); }</pre> </p> <p> Like <code>Max</code>, the lambda expression used to implement <code>CountLeaves</code> uses <a href="https://docs.microsoft.com/dotnet/api/system.linq.enumerable.any">Any</a> to detect whether or not <code>xs</code> is empty, which is when <code>Any</code> is <code>false</code>. Empty <code>xs</code> indicates that you've found a leaf node, so return <code>1</code>. When <code>xs</code> isn't empty, it contains a collection of <code>1</code> values - one for each leaf node recursively found; add them together with <code>Sum</code>. </p> <p> This also works for the same <code>tree</code> as before: </p> <p> <pre>&gt; tree.CountLeaves() 4</pre> </p> <p> You can also measure the maximum depth of a tree: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">int</span>&nbsp;MeasureDepth() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;Cata&lt;<span style="color:blue;">int</span>&gt;((x,&nbsp;xs)&nbsp;=&gt;&nbsp;xs.Any()&nbsp;?&nbsp;1&nbsp;+&nbsp;xs.Max()&nbsp;:&nbsp;0); }</pre> </p> <p> This implementation considers a leaf node to have no depth: </p> <p> <pre>&gt; <span style="color:#2b91af;">Tree</span>.Leaf(<span style="color:#a31515;">&quot;foo&quot;</span>).MeasureDepth() 0</pre> </p> <p> This is a discretionary definition; you could also argue that, by definition, a leaf node ought to have a depth of one. If you think so, you'll need to change the <code>0</code> to <code>1</code> in the above <code>MeasureDepth</code> implementation. </p> <p> Once more, you can use <code>Any</code> to detect leaf nodes. Whenever you find a leaf node, you return its depth, which, by definition, is <code>0</code>. Otherwise, you find the maximum depth already found among <code>xs</code>, and add <code>1</code>, because <code>xs</code> contains the maximum depths of all immediate sub-trees. </p> <p> Using the same <code>tree</code> again: </p> <p> <pre>&gt; tree.MeasureDepth() 2</pre> </p> <p> The above <code>tree</code> has the same depth for all sub-trees, so here's an example of a tilted tree: </p> <p> <pre>&gt; <span style="color:#2b91af;">Tree</span>.Create(3, . <span style="color:#2b91af;">Tree</span>.Create(1, . <span style="color:#2b91af;">Tree</span>.Leaf(0), . <span style="color:#2b91af;">Tree</span>.Leaf(0)), . <span style="color:#2b91af;">Tree</span>.Leaf(0), . <span style="color:#2b91af;">Tree</span>.Leaf(0), . <span style="color:#2b91af;">Tree</span>.Create(2, . <span style="color:#2b91af;">Tree</span>.Create(1, . <span style="color:#2b91af;">Tree</span>.Leaf(0)))) . .MeasureDepth() 3</pre> </p> <p> To make it easier to understand, I've labelled all the leaf nodes with <code>0</code>, because that's their depth. I've then labelled the other nodes with the maximum number 'under' them, plus one. That's the algorithm used. </p> <h3 id="82e5042d05534db2a67c8f7c37f78419"> Tree F-Algebra <a href="#82e5042d05534db2a67c8f7c37f78419" title="permalink">#</a> </h3> <p> As in the <a href="/2019/06/03/either-catamorphism">previous article</a>, I'll use <code>Fix</code> and <code>cata</code> as explained in <a href="https://bartoszmilewski.com">Bartosz Milewski</a>'s excellent <a href="https://bartoszmilewski.com/2017/02/28/f-algebras/">article on F-Algebras</a>. </p> <p> As always, start with the underlying endofunctor. I've taken some inspiration from <code>Tree a</code> from <code>Data.Tree</code>, but changed some names: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;TreeF&nbsp;a&nbsp;c&nbsp;=&nbsp;NodeF&nbsp;{&nbsp;nodeValue&nbsp;::&nbsp;a,&nbsp;nodes&nbsp;::&nbsp;ListFix&nbsp;c&nbsp;}&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;(<span style="color:blue;">TreeF</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;f&nbsp;(NodeF&nbsp;x&nbsp;ns)&nbsp;=&nbsp;NodeF&nbsp;x&nbsp;$&nbsp;<span style="color:blue;">fmap</span>&nbsp;f&nbsp;ns</pre> </p> <p> Instead of using Haskell's standard list (<code>[]</code>) for the sub-forest, I've used <code>ListFix</code> from <a href="/2019/05/27/list-catamorphism">the article on list catamorphism</a>. This should, hopefully, demonstrate how you can build on already established definitions derived from first principles. </p> <p> As usual, I've called the 'data' type <code>a</code> and the carrier type <code>c</code> (for <em>carrier</em>). The <code>Functor</code> instance as usual translates the carrier type; the <code>fmap</code> function has the type <code>(c -&gt; c1) -&gt; TreeF a c -&gt; TreeF a c1</code>. </p> <p> As was the case when deducing the recent catamorphisms, Haskell isn't too happy about defining instances for a type like <code>Fix (TreeF a)</code>. To address that problem, you can introduce a <code>newtype</code> wrapper: </p> <p> <pre><span style="color:blue;">newtype</span>&nbsp;TreeFix&nbsp;a&nbsp;=&nbsp;TreeFix&nbsp;{&nbsp;unTreeFix&nbsp;::&nbsp;Fix&nbsp;(TreeF&nbsp;a)&nbsp;}&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> You can define <code>Functor</code>, <code>Applicative</code>, <code>Monad</code>, etc. instances for this type without resorting to any funky GHC extensions. Keep in mind that ultimately, the purpose of all this code is just to figure out what the catamorphism looks like. This code isn't intended for actual use. </p> <p> A pair of helper functions make it easier to define <code>TreeFix</code> values: </p> <p> <pre><span style="color:#2b91af;">leafF</span>&nbsp;::&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;a leafF&nbsp;x&nbsp;=&nbsp;TreeFix&nbsp;$&nbsp;Fix&nbsp;$&nbsp;NodeF&nbsp;x&nbsp;nilF <span style="color:#2b91af;">nodeF</span>&nbsp;::&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;(<span style="color:blue;">TreeFix</span>&nbsp;a)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;a nodeF&nbsp;x&nbsp;=&nbsp;TreeFix&nbsp;.&nbsp;Fix&nbsp;.&nbsp;NodeF&nbsp;x&nbsp;.&nbsp;<span style="color:blue;">fmap</span>&nbsp;unTreeFix</pre> </p> <p> <code>leafF</code> creates a leaf node: </p> <p> <pre>Prelude Fix List Tree&gt; leafF "ploeh" TreeFix {unTreeFix = Fix (NodeF "ploeh" (ListFix (Fix NilF)))}</pre> </p> <p> <code>nodeF</code> is a helper function to create a non-leaf node: </p> <p> <pre>Prelude Fix List Tree&gt; nodeF 4 (consF (leafF 9) nilF) TreeFix {unTreeFix = Fix (NodeF 4 (ListFix (Fix (ConsF (Fix (NodeF 9 (ListFix (Fix NilF)))) (Fix NilF)))))}</pre> </p> <p> Even with helper functions, construction of <code>TreeFix</code> values is cumbersome, but keep in mind that the code shown here isn't meant to be used in practice. The goal is only to deduce catamorphisms from more basic universal abstractions, and you now have all you need to do that. </p> <h3 id="ca5669298d814809a3f0d4b0422b860f"> Haskell catamorphism <a href="#ca5669298d814809a3f0d4b0422b860f" title="permalink">#</a> </h3> <p> At this point, you have two out of three elements of an F-Algebra. You have an endofunctor (<code>TreeF a</code>), and an object <code>c</code>, but you still need to find a morphism <code>TreeF a c -&gt; c</code>. Notice that the algebra you have to find is the function that reduces the functor to its <em>carrier type</em> <code>c</code>, not the 'data type' <code>a</code>. This takes some time to get used to, but that's how catamorphisms work. This doesn't mean, however, that you get to ignore <code>a</code>, as you'll see. </p> <p> As in the previous articles, start by writing a function that will become the catamorphism, based on <code>cata</code>: </p> <p> <pre>treeF&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unTreeFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;(NodeF&nbsp;x&nbsp;ns)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> While this compiles, with its <code>undefined</code> implementation of <code>alg</code>, it obviously doesn't do anything useful. I find, however, that it helps me think. How can you return a value of the type <code>c</code> from <code>alg</code>? You could pass a function argument to the <code>treeF</code> function and use it with <code>x</code> and <code>ns</code>: </p> <p> <pre><span style="color:#2b91af;">treeF</span>&nbsp;::&nbsp;(a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;c&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c treeF&nbsp;f&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unTreeFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;(NodeF&nbsp;x&nbsp;ns)&nbsp;=&nbsp;f&nbsp;x&nbsp;ns</pre> </p> <p> This works. Since <code>cata</code> has the type <code>Functor f =&gt; (f a -&gt; a) -&gt; Fix f -&gt; a</code>, that means that <code>alg</code> has the type <code>f a -&gt; a</code>. In the case of <code>TreeF</code>, the compiler infers that the <code>alg</code> function has the type <code>TreeF a c -&gt; c</code>, which is just what you need! </p> <p> You can now see what the carrier type <code>c</code> is for. It's the type that the algebra extracts, and thus the type that the catamorphism returns. </p> <p> This, then, is the catamorphism for a tree. So far in this article series, all previous catamorphisms have been pairs, but this one is just a single function. It's still not the only possible catamorphism, since you could trivially flip the arguments to <code>f</code>. </p> <p> I've chosen the representation shown here because it's isomorphic to the <code>foldTree</code> function from Haskell's built-in <code>Data.Tree</code> module, which explicitly documents that the function "is also known as the catamorphism on trees." <code>foldTree</code> is defined using Haskell's standard list type (<code>[]</code>), so the type is simpler: <code>(a -&gt; [b] -&gt; b) -&gt; Tree a -&gt; b</code>. The two representations of trees, <code>TreeFix</code> and <code>Tree</code> are, however, isomorphic, so <code>foldTree</code> is equivalent to <code>treeF</code>. Notice how both of these functions are also equivalent to the above C# <code>Cata</code> method. </p> <h3 id="8647c7bd03aa4d4b8a01a8252058830f"> Basis <a href="#8647c7bd03aa4d4b8a01a8252058830f" title="permalink">#</a> </h3> <p> You can implement most other useful functionality with <code>treeF</code>. Here's the <code>Functor</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;f&nbsp;=&nbsp;treeF&nbsp;(nodeF&nbsp;.&nbsp;f)</pre> </p> <p> <code>nodeF . f</code> is just the <a href="https://en.wikipedia.org/wiki/Tacit_programming">point-free</a> version of <code>\x ns -&gt; nodeF (f x) ns</code>, which follows the exact same implementation logic as the above C# <code>Select</code> implementation. </p> <p> The <code>Applicative</code> instance is, I'm afraid, the most complex code you've seen so far in this article series: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Applicative</span>&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;pure&nbsp;=&nbsp;leafF &nbsp;&nbsp;ft&nbsp;&lt;*&gt;&nbsp;xt&nbsp;=&nbsp;treeF&nbsp;(\f&nbsp;ts&nbsp;-&gt;&nbsp;addNodes&nbsp;ts&nbsp;$&nbsp;f&nbsp;&lt;$&gt;&nbsp;xt)&nbsp;ft &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;addNodes&nbsp;ns&nbsp;(TreeFix&nbsp;(Fix&nbsp;(NodeF&nbsp;x&nbsp;xs)))&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;TreeFix&nbsp;(Fix&nbsp;(NodeF&nbsp;x&nbsp;(xs&nbsp;&lt;&gt;&nbsp;(unTreeFix&nbsp;&lt;$&gt;&nbsp;ns))))</pre> </p> <p> I'd be surprised if it's impossible to make this terser, but I thought that it was just complicated enough that I needed to make one of the steps explicit. The <code>addNodes</code> helper function has the type <code>ListFix (TreeFix a) -&gt; TreeFix a -&gt; TreeFix a</code>, and it adds a list of sub-trees to the top node of a tree. It looks worse than it is, but it really just peels off the wrappers (<code>TreeFix</code>, <code>Fix</code>, and <code>NodeF</code>) to access the data (<code>x</code> and <code>xs</code>) of the top node. It then concatenates <code>xs</code> with <code>ns</code>, and puts all the wrappers back on. </p> <p> I have to admit, though, that the <code>Applicative</code> and <code>Monad</code> instance in general are mind-binding to me. The <code>&lt;*&gt;</code> operation, particularly, takes a <em>tree of functions</em> and has to combine it with a <em>tree of values</em>. What does that even mean? How does one do that? </p> <p> Like the above, apparently. I took the <code>Applicative</code> behaviour from <code>Data.Tree</code> and made sure that my implementation is isomorphic. I even have a property to make 'sure' that's the case: </p> <p> <pre>testProperty&nbsp;<span style="color:#a31515;">&quot;Applicative&nbsp;behaves&nbsp;like&nbsp;Data.Tree&quot;</span>&nbsp;$&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;<span style="color:#2b91af;">xt</span>&nbsp;::&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;<span style="color:#2b91af;">Integer</span>&nbsp;&lt;-&nbsp;fromTree&nbsp;&lt;$&gt;&nbsp;resize&nbsp;10&nbsp;arbitrary &nbsp;&nbsp;<span style="color:#2b91af;">ft</span>&nbsp;::&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;(<span style="color:#2b91af;">Integer</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">String</span>)&nbsp;&lt;-&nbsp;fromTree&nbsp;&lt;$&gt;&nbsp;resize&nbsp;5&nbsp;arbitrary &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;ft&nbsp;&lt;*&gt;&nbsp;xt &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;expected&nbsp;=&nbsp;toTree&nbsp;ft&nbsp;&lt;*&gt;&nbsp;toTree&nbsp;xt &nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;expected&nbsp;===&nbsp;toTree&nbsp;actual</pre> </p> <p> The <code>Monad</code> instance looks similar to the <code>Applicative</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Monad</span>&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;t&nbsp;&gt;&gt;=&nbsp;f&nbsp;=&nbsp;treeF&nbsp;(\x&nbsp;ns&nbsp;-&gt;&nbsp;addNodes&nbsp;ns&nbsp;$&nbsp;f&nbsp;x)&nbsp;t &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;addNodes&nbsp;ns&nbsp;(TreeFix&nbsp;(Fix&nbsp;(NodeF&nbsp;x&nbsp;xs)))&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;TreeFix&nbsp;(Fix&nbsp;(NodeF&nbsp;x&nbsp;(xs&nbsp;&lt;&gt;&nbsp;(unTreeFix&nbsp;&lt;$&gt;&nbsp;ns))))</pre> </p> <p> The <code>addNodes</code> helper function is the same as for <code>&lt;*&gt;</code>, so you may wonder why I didn't extract that as a separate, reusable function. I decided, however, to apply the <a href="https://en.wikipedia.org/wiki/Rule_of_three_(computer_programming)">rule of three</a>, and since, ultimately, <code>addNodes</code> appear only twice, I left them as the implementation details they are. </p> <p> Fortunately, the <code>Foldable</code> instance is easier on the eyes: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Foldable</span>&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;foldMap&nbsp;f&nbsp;=&nbsp;treeF&nbsp;(\x&nbsp;xs&nbsp;-&gt;&nbsp;f&nbsp;x&nbsp;&lt;&gt;&nbsp;fold&nbsp;xs)</pre> </p> <p> Since <code>f</code> is a function of the type <code>a -&gt; m</code>, where <code>m</code> is a <code>Monoid</code> instance, you can use <code>fold</code> and <code>&lt;&gt;</code> to accumulate everything to a single <code>m</code> value. </p> <p> The <code>Traversable</code> instance is similarly terse: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Traversable</span>&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;sequenceA&nbsp;=&nbsp;treeF&nbsp;(\x&nbsp;ns&nbsp;-&gt;&nbsp;nodeF&nbsp;&lt;$&gt;&nbsp;x&nbsp;&lt;*&gt;&nbsp;sequenceA&nbsp;ns)</pre> </p> <p> Finally, you can implement conversions to and from the <code>Tree</code> type from <code>Data.Tree</code>, using <code>ana</code> as the dual of <code>cata</code>: </p> <p> <pre><span style="color:#2b91af;">toTree</span>&nbsp;::&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Tree</span>&nbsp;a toTree&nbsp;=&nbsp;treeF&nbsp;(\x&nbsp;ns&nbsp;-&gt;&nbsp;Node&nbsp;x&nbsp;$&nbsp;toList&nbsp;ns) <span style="color:#2b91af;">fromTree</span>&nbsp;::&nbsp;<span style="color:blue;">Tree</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;a fromTree&nbsp;=&nbsp;TreeFix&nbsp;.&nbsp;ana&nbsp;coalg &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;coalg&nbsp;(Node&nbsp;x&nbsp;ns)&nbsp;=&nbsp;NodeF&nbsp;x&nbsp;(fromList&nbsp;ns)</pre> </p> <p> This demonstrates that <code>TreeFix</code> is isomorphic to <code>Tree</code>, which again establishes that <code>treeF</code> and <code>foldTree</code> are equivalent. </p> <h3 id="7180d37efb404a70b707f8c9b8639a35"> Relationships <a href="#7180d37efb404a70b707f8c9b8639a35" title="permalink">#</a> </h3> <p> In this series, you've seen various examples of catamorphisms of structures that have no folds, catamorphisms that coincide with folds, and catamorphisms that are more general than the fold. The introduction to the series included this diagram: </p> <p> <img src="/content/binary/catamorphism-and-fold-relations.png" alt="Catamorphisms and folds as sets, for various sum types."> </p> <p> The <a href="/2019/06/03/either-catamorphism">Either catamorphism</a> is another example of a catamorphism that is more general than the fold, but that one turned out to be identical to the <em>bifold</em>. That's not the case here, because <code>TreeFix</code> isn't a <code>Bifoldable</code> instance at all. </p> <p> There are operations on trees that you can implement with a fold, but some that you can't. Consider the tree in shown in the diagram at the beginning of the article. This is also the tree that the above C# examples use. In Haskell, using <code>TreeFix</code>, you can define that tree like this: </p> <p> <pre>tree&nbsp;= &nbsp;&nbsp;nodeF&nbsp;42 &nbsp;&nbsp;&nbsp;&nbsp;(consF&nbsp;(nodeF&nbsp;1337 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(consF&nbsp;(leafF&nbsp;(-3))&nbsp;nilF))&nbsp;$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;consF&nbsp;(nodeF&nbsp;7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(consF&nbsp;(leafF&nbsp;(-99))&nbsp;$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;consF&nbsp;(leafF&nbsp;100)&nbsp;$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;consF&nbsp;(leafF&nbsp;0)&nbsp;nilF)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nilF)</pre> </p> <p> Yes, that almost looks like some Lisp dialect... </p> <p> Since <code>TreeFix</code> is <code>Foldable</code>, and that type class already comes with <code>sum</code> and <code>maximum</code> functions, no further work is required to repeat the first two of the above C# examples: </p> <p> <pre>*Tree Fix List Tree&gt; sum tree 1384 *Tree Fix List Tree&gt; maximum tree 1337</pre> </p> <p> Counting leaves, or measuring the depth of a tree, on the other hand, is impossible with the <code>Foldable</code> instance, but can be implemented using the catamorphism: </p> <p> <pre><span style="color:#2b91af;">countLeaves</span>&nbsp;::&nbsp;<span style="color:blue;">Num</span>&nbsp;n&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;n countLeaves&nbsp;=&nbsp;treeF&nbsp;(\_&nbsp;xs&nbsp;-&gt;&nbsp;<span style="color:blue;">if</span>&nbsp;<span style="color:blue;">null</span>&nbsp;xs&nbsp;<span style="color:blue;">then</span>&nbsp;1&nbsp;<span style="color:blue;">else</span>&nbsp;<span style="color:blue;">sum</span>&nbsp;xs) <span style="color:#2b91af;">treeDepth</span>&nbsp;::&nbsp;(<span style="color:blue;">Ord</span>&nbsp;n,&nbsp;<span style="color:blue;">Num</span>&nbsp;n)&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;<span style="color:blue;">TreeFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;n treeDepth&nbsp;=&nbsp;treeF&nbsp;(\_&nbsp;xs&nbsp;-&gt;&nbsp;<span style="color:blue;">if</span>&nbsp;<span style="color:blue;">null</span>&nbsp;xs&nbsp;<span style="color:blue;">then</span>&nbsp;0&nbsp;<span style="color:blue;">else</span>&nbsp;1&nbsp;+&nbsp;<span style="color:blue;">maximum</span>&nbsp;xs)</pre> </p> <p> The reasoning is the same as already explained in the above C# examples. The functions also produce the same results: </p> <p> <pre>*Tree Fix List Tree&gt; countLeaves tree 4 *Tree Fix List Tree&gt; treeDepth tree 2</pre> </p> <p> This, hopefully, illustrates that the catamorphism is more capable, and that the fold is just a (list-biased) specialisation. </p> <h3 id="66f69ba33cef4ed58d01f1f0bafef14a"> Summary <a href="#66f69ba33cef4ed58d01f1f0bafef14a" title="permalink">#</a> </h3> <p> The catamorphism for a tree is just a single function, which is recursively evaluated. It enables you to translate, traverse, and reduce trees in many interesting ways. </p> <p> You can use the catamorphism to implement a (list-biased) fold, including enumerating all nodes as a flat list, but there are operations (such as counting leaves) that you can implement with the catamorphism, but not with the fold. </p> <p> This article series has so far covered progressively more complex data structures. The first examples (<a href="/2019/05/06/boolean-catamorphism">Boolean catamorphism</a> and <a href="/2019/05/13/peano-catamorphism">Peano catamorphism</a>) were neither <a href="/2018/03/22/functors">functors</a>, <a href="/2018/10/01/applicative-functors">applicatives</a>, nor monads. All subsequent examples, on the other hand, are all of these, and more. The next example presents a functor that's neither applicative nor monad, yet still foldable. Obviously, what functionality it offers is still based on a catamorphism. </p> <p> <strong>Next:</strong> <a href="/2019/06/24/full-binary-tree-catamorphism">Full binary tree catamorphism</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/06/10/tree-catamorphism Either catamorphism https://blog.ploeh.dk/2019/06/03/either-catamorphism/ Mon, 03 Jun 2019 06:05:00 UTC <div id="post"> <p> <em>The catamorphism for Either is a generalisation of its fold. The catamorphism enables operations not available via fold.</em> </p> <p> This article is part of an <a href="/2019/04/29/catamorphisms">article series about catamorphisms</a>. A catamorphism is a <a href="/2017/10/04/from-design-patterns-to-category-theory">universal abstraction</a> that describes how to digest a data structure into a potentially more compact value. </p> <p> This article presents the catamorphism for <a href="/2018/06/11/church-encoded-either">Either</a> (also known as <em>Result</em>), as well as how to identify it. The beginning of this article presents the catamorphism in C#, with examples. The rest of the article describes how to deduce the catamorphism. This part of the article presents my work in <a href="https://www.haskell.org">Haskell</a>. Readers not comfortable with Haskell can just read the first part, and consider the rest of the article as an optional appendix. </p> <p> <em>Either</em> is a <a href="https://bartoszmilewski.com/2014/01/14/functors-are-containers">data container</a> that models two mutually exclusive results. It's often used to return values that may be either correct (<em>right</em>), or incorrect (<em>left</em>). In statically typed functional programming with a preference for total functions, Either offers a saner, more reasonable way to model success and error results than throwing exceptions. </p> <h3 id="d8214c38aac04ee7b80b9352d57d3bd1"> C# catamorphism <a href="#d8214c38aac04ee7b80b9352d57d3bd1" title="permalink">#</a> </h3> <p> This article uses <a href="/2018/06/11/church-encoded-either">the Church encoding of Either</a>. The catamorphism for Either is the <code>Match</code> method: </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> Until this article, all previous catamorphisms have been a pair made from an initial value and a function. The Either catamorphism is a generalisation, since it's a pair of functions. One function handles the case where there's a <em>left</em> value, and the other function handles the case where there's a <em>right</em> value. Both functions must return the same, unifying type, which is often a string or something similar that can be shown in a user interface: </p> <p> <pre>&gt; <span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">TimeSpan</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;e&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Left</span>&lt;<span style="color:#2b91af;">TimeSpan</span>,&nbsp;<span style="color:blue;">int</span>&gt;(<span style="color:#2b91af;">TimeSpan</span>.FromMinutes(3)); &gt; e.Match(ts&nbsp;=&gt;&nbsp;ts.ToString(),&nbsp;i&nbsp;=&gt;&nbsp;i.ToString()) "00:03:00" &gt; <span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">TimeSpan</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;e&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Right</span>&lt;<span style="color:#2b91af;">TimeSpan</span>,&nbsp;<span style="color:blue;">int</span>&gt;(42); &gt; e.Match(ts&nbsp;=&gt;&nbsp;ts.ToString(),&nbsp;i&nbsp;=&gt;&nbsp;i.ToString()) "42"</pre> </p> <p> You'll often see examples like the above that turns both left and right cases into strings or something that can be represented as a unifying response type, but this is in no way required. If you can come up with a unifying type, you can convert both cases to that type: </p> <p> <pre>&gt; <span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">Guid</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;e&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Left</span>&lt;<span style="color:#2b91af;">Guid</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#2b91af;">Guid</span>.NewGuid()); &gt; e.Match(g&nbsp;=&gt;&nbsp;g.ToString().Count(c&nbsp;=&gt;&nbsp;<span style="color:#a31515;">&#39;a&#39;</span>&nbsp;&lt;=&nbsp;c),&nbsp;s&nbsp;=&gt;&nbsp;s.Length) 12 &gt; <span style="color:#2b91af;">IEither</span>&lt;<span style="color:#2b91af;">Guid</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;e&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Right</span>&lt;<span style="color:#2b91af;">Guid</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;foo&quot;</span>); &gt; e.Match(g&nbsp;=&gt;&nbsp;g.ToString().Count(c&nbsp;=&gt;&nbsp;<span style="color:#a31515;">&#39;a&#39;</span>&nbsp;&lt;=&nbsp;c),&nbsp;s&nbsp;=&gt;&nbsp;s.Length) 3</pre> </p> <p> In the two above examples, you use two different functions that both reduce respectively <code>Guid</code> and <code>string</code> values to a number. The function that turns <code>Guid</code> values into a number counts how many of the hexadecimal digits that are greater than or equal to A (10). The other function simply returns the length of the <code>string</code>, if it's there. That example makes little sense, but the <code>Match</code> method doesn't care about that. </p> <p> In practical use, Either is often used for error handling. The <a href="/2018/06/11/church-encoded-either">article on the Church encoding of Either</a> contains an example. </p> <h3 id="99e1027823114e95bebf81c08d35779f"> Either F-Algebra <a href="#99e1027823114e95bebf81c08d35779f" title="permalink">#</a> </h3> <p> As in the <a href="/2019/05/27/list-catamorphism">previous article</a>, I'll use <code>Fix</code> and <code>cata</code> as explained in <a href="https://bartoszmilewski.com">Bartosz Milewski</a>'s excellent <a href="https://bartoszmilewski.com/2017/02/28/f-algebras/">article on F-Algebras</a>. </p> <p> While F-Algebras and fixed points are mostly used for recursive data structures, you can also define an F-Algebra for a non-recursive data structure. You already saw an example of that in the articles about <a href="/2019/05/06/boolean-catamorphism">Boolean catamorphism</a> and <a href="/2019/05/20/maybe-catamorphism">Maybe catamorphism</a>. The difference between e.g. Maybe values and Either is that both cases of Either carry a value. You can model this as a <code>Functor</code> with both a carrier type and two type arguments for the data that Either may contain: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;EitherF&nbsp;l&nbsp;r&nbsp;c&nbsp;=&nbsp;LeftF&nbsp;l&nbsp;|&nbsp;RightF&nbsp;r&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;(<span style="color:blue;">EitherF</span>&nbsp;l&nbsp;r)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;_&nbsp;&nbsp;(LeftF&nbsp;l)&nbsp;=&nbsp;LeftF&nbsp;l &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;_&nbsp;(RightF&nbsp;r)&nbsp;=&nbsp;RightF&nbsp;r</pre> </p> <p> I chose to call the 'data types' <code>l</code> (for <em>left</em>) and <code>r</code> (for <em>right</em>), and the carrier type <code>c</code> (for <em>carrier</em>). As was also the case with <code>BoolF</code> and <code>MaybeF</code>, the <code>Functor</code> instance ignores the map function because the carrier type is missing from both the <code>LeftF</code> case and the <code>RightF</code> case. Like the <code>Functor</code> instances for <code>BoolF</code> and <code>MaybeF</code>, it'd seem that nothing happens, but at the type level, this is still a translation from <code>EitherF l r c</code> to <code>EitherF l r c1</code>. Not much of a function, perhaps, but definitely an <em>endofunctor</em>. </p> <p> As was also the case when deducing the Maybe and List catamorphisms, Haskell isn't too happy about defining instances for a type like <code>Fix (EitherF l r)</code>. To address that problem, you can introduce a <code>newtype</code> wrapper: </p> <p> <pre><span style="color:blue;">newtype</span>&nbsp;EitherFix&nbsp;l&nbsp;r&nbsp;=&nbsp;EitherFix&nbsp;{&nbsp;unEitherFix&nbsp;::&nbsp;Fix&nbsp;(EitherF&nbsp;l&nbsp;r)&nbsp;}&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> You can define <code>Functor</code>, <code>Applicative</code>, <code>Monad</code>, etc. instances for this type without resorting to any funky GHC extensions. Keep in mind that ultimately, the purpose of all this code is just to figure out what the catamorphism looks like. This code isn't intended for actual use. </p> <p> A pair of helper functions make it easier to define <code>EitherFix</code> values: </p> <p> <pre><span style="color:#2b91af;">leftF</span>&nbsp;::&nbsp;l&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">EitherFix</span>&nbsp;l&nbsp;r leftF&nbsp;=&nbsp;EitherFix&nbsp;.&nbsp;Fix&nbsp;.&nbsp;LeftF <span style="color:#2b91af;">rightF</span>&nbsp;::&nbsp;r&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">EitherFix</span>&nbsp;l&nbsp;r rightF&nbsp;=&nbsp;EitherFix&nbsp;.&nbsp;Fix&nbsp;.&nbsp;RightF</pre> </p> <p> With those functions, you can create <code>EitherFix</code> values: </p> <p> <pre>Prelude Data.UUID Data.UUID.V4 Fix Either&gt; leftF &lt;$&gt; nextRandom EitherFix {unEitherFix = Fix (LeftF e65378c2-0d6e-47e0-8bcb-7cc29d185fad)} Prelude Data.UUID Data.UUID.V4 Fix Either&gt; rightF "foo" EitherFix {unEitherFix = Fix (RightF "foo")}</pre> </p> <p> That's all you need to identify the catamorphism. </p> <h3 id="67d13d05a8564f3481e181d0c32b3165"> Haskell catamorphism <a href="#67d13d05a8564f3481e181d0c32b3165" title="permalink">#</a> </h3> <p> At this point, you have two out of three elements of an F-Algebra. You have an endofunctor (<code>EitherF l r</code>), and an object <code>c</code>, but you still need to find a morphism <code>EitherF l r c -&gt; c</code>. Notice that the algebra you have to find is the function that reduces the functor to its <em>carrier type</em> <code>c</code>, not the 'data types' <code>l</code> and <code>r</code>. This takes some time to get used to, but that's how catamorphisms work. This doesn't mean, however, that you get to ignore <code>l</code> and <code>r</code>, as you'll see. </p> <p> As in the previous articles, start by writing a function that will become the catamorphism, based on <code>cata</code>: </p> <p> <pre>eitherF&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unEitherFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;(LeftF&nbsp;l)&nbsp;=&nbsp;<span style="color:blue;">undefined</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(RightF&nbsp;r)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> While this compiles, with its <code>undefined</code> implementations, it obviously doesn't do anything useful. I find, however, that it helps me think. How can you return a value of the type <code>c</code> from the <code>LeftF</code> case? You could pass an argument to the <code>eitherF</code> function: </p> <p> <pre>eitherF&nbsp;fl&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unEitherFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;(LeftF&nbsp;l)&nbsp;=&nbsp;fl&nbsp;l &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(RightF&nbsp;r)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> While you could, technically, pass an argument of the type <code>c</code> to <code>eitherF</code> and then return that value from the <code>LeftF</code> case, that would mean that you would ignore the <code>l</code> value. This would be incorrect, so instead, make the argument a function and call it with <code>l</code>. Likewise, you can deal with the <code>RightF</code> case in the same way: </p> <p> <pre><span style="color:#2b91af;">eitherF</span>&nbsp;::&nbsp;(l&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(r&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">EitherFix</span>&nbsp;l&nbsp;r&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c eitherF&nbsp;fl&nbsp;fr&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unEitherFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;(LeftF&nbsp;l)&nbsp;=&nbsp;fl&nbsp;l &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(RightF&nbsp;r)&nbsp;=&nbsp;fr&nbsp;r</pre> </p> <p> This works. Since <code>cata</code> has the type <code>Functor f =&gt; (f a -&gt; a) -&gt; Fix f -&gt; a</code>, that means that <code>alg</code> has the type <code>f a -&gt; a</code>. In the case of <code>EitherF</code>, the compiler infers that the <code>alg</code> function has the type <code>EitherF l r c -&gt; c</code>, which is just what you need! </p> <p> You can now see what the carrier type <code>c</code> is for. It's the type that the algebra extracts, and thus the type that the catamorphism returns. </p> <p> This, then, is the catamorphism for Either. As has been consistent so far, it's a pair, but now made from two functions. As you've seen repeatedly, this isn't the only possible catamorphism, since you can, for example, trivially flip the arguments to <code>eitherF</code>. </p> <p> I've chosen the representation shown here because it's isomorphic to the <code>either</code> function from Haskell's built-in <code>Data.Either</code> module, which calls the function the "Case analysis for the <code>Either</code> type". Both of these functions (<code>eitherF</code> and <code>either</code>) are equivalent to the above C# <code>Match</code> method. </p> <h3 id="77731d63c79543b0994c06721521b6f3"> Basis <a href="#77731d63c79543b0994c06721521b6f3" title="permalink">#</a> </h3> <p> You can implement most other useful functionality with <code>eitherF</code>. Here's the <code>Bifunctor</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Bifunctor</span>&nbsp;<span style="color:blue;">EitherFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;bimap&nbsp;f&nbsp;s&nbsp;=&nbsp;eitherF&nbsp;(leftF&nbsp;.&nbsp;f)&nbsp;(rightF&nbsp;.&nbsp;s)</pre> </p> <p> From that instance, the <code>Functor</code> instance trivially follows: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;(<span style="color:blue;">EitherFix</span>&nbsp;l)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;=&nbsp;second</pre> </p> <p> On top of <code>Functor</code> you can add <code>Applicative</code>: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Applicative</span>&nbsp;(<span style="color:blue;">EitherFix</span>&nbsp;l)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;pure&nbsp;=&nbsp;rightF &nbsp;&nbsp;f&nbsp;&lt;*&gt;&nbsp;x&nbsp;=&nbsp;eitherF&nbsp;leftF&nbsp;(&lt;$&gt;&nbsp;x)&nbsp;f</pre> </p> <p> Notice that the <code>&lt;*&gt;</code> implementation is similar to to the <code>&lt;*&gt;</code> implementation for <code>MaybeFix</code>. The same is the case for the <code>Monad</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Monad</span>&nbsp;(<span style="color:blue;">EitherFix</span>&nbsp;l)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;x&nbsp;&gt;&gt;=&nbsp;f&nbsp;=&nbsp;eitherF&nbsp;leftF&nbsp;f&nbsp;x</pre> </p> <p> Not only is <code>EitherFix</code> <code>Foldable</code>, it's <code>Bifoldable</code>: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Bifoldable</span>&nbsp;<span style="color:blue;">EitherFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;bifoldMap&nbsp;=&nbsp;eitherF</pre> </p> <p> Notice, interestingly, that <code>bifoldMap</code> is identical to <code>eitherF</code>. </p> <p> The <code>Bifoldable</code> instance enables you to trivially implement the <code>Foldable</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Foldable</span>&nbsp;(<span style="color:blue;">EitherFix</span>&nbsp;l)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;foldMap&nbsp;=&nbsp;bifoldMap&nbsp;mempty</pre> </p> <p> You may find the presence of <code>mempty</code> puzzling, since <code>bifoldMap</code> (or <code>eitherF</code>; they're identical) takes as arguments two functions. Is <code>mempty</code> a function? </p> <p> Yes, <code>mempty</code> can be a function. Here, it is. There's a <code>Monoid</code> instance for any function <code>a -&gt; m</code>, where <code>m</code> is a <code>Monoid</code> instance, and <code>mempty</code> is the identity for that monoid. That's the instance in use here. </p> <p> Just as <code>EitherFix</code> is <code>Bifoldable</code>, it's also <code>Bitraversable</code>: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Bitraversable</span>&nbsp;<span style="color:blue;">EitherFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;bitraverse&nbsp;fl&nbsp;fr&nbsp;=&nbsp;eitherF&nbsp;(<span style="color:blue;">fmap</span>&nbsp;leftF&nbsp;.&nbsp;fl)&nbsp;(<span style="color:blue;">fmap</span>&nbsp;rightF&nbsp;.&nbsp;fr)</pre> </p> <p> You can comfortably implement the <code>Traversable</code> instance based on the <code>Bitraversable</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Traversable</span>&nbsp;(<span style="color:blue;">EitherFix</span>&nbsp;l)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;sequenceA&nbsp;=&nbsp;bisequenceA&nbsp;.&nbsp;first&nbsp;pure</pre> </p> <p> Finally, you can implement conversions to and from the standard <code>Either</code> type, using <code>ana</code> as the dual of <code>cata</code>: </p> <p> <pre><span style="color:#2b91af;">toEither</span>&nbsp;::&nbsp;<span style="color:blue;">EitherFix</span>&nbsp;l&nbsp;r&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Either</span>&nbsp;l&nbsp;r toEither&nbsp;=&nbsp;eitherF&nbsp;Left&nbsp;Right <span style="color:#2b91af;">fromEither</span>&nbsp;::&nbsp;<span style="color:#2b91af;">Either</span>&nbsp;a&nbsp;b&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">EitherFix</span>&nbsp;a&nbsp;b fromEither&nbsp;=&nbsp;EitherFix&nbsp;.&nbsp;ana&nbsp;coalg &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;coalg&nbsp;&nbsp;(Left&nbsp;l)&nbsp;=&nbsp;&nbsp;LeftF&nbsp;l &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;coalg&nbsp;(Right&nbsp;r)&nbsp;=&nbsp;RightF&nbsp;r</pre> </p> <p> This demonstrates that <code>EitherFix</code> is isomorphic to <code>Either</code>, which again establishes that <code>eitherF</code> and <code>either</code> are equivalent. </p> <h3 id="00a274a2317548538521d4a171191230"> Relationships <a href="#00a274a2317548538521d4a171191230" title="permalink">#</a> </h3> <p> In this series, you've seen various examples of catamorphisms of structures that have no folds, catamorphisms that coincide with folds, and now a catamorphism that is more general than the fold. The introduction to the series included this diagram: </p> <p> <img src="/content/binary/catamorphism-and-fold-relations.png" alt="Catamorphisms and folds as sets, for various sum types."> </p> <p> This shows that Boolean values and Peano numbers have catamorphisms, but no folds, whereas for Maybe and List, the fold and the catamorphism is the same. For Either, however, the fold is a special case of the catamorphism. The fold for Either 'pretends' that the left side doesn't exist. Instead, the left value is interpreted as a missing right value. Thus, in order to fold Either values, you must supply a 'fallback' value that will be used in case an Either value isn't a <em>right</em> value: </p> <p> <pre>Prelude Fix Either&gt; e = rightF LT :: EitherFix Integer Ordering Prelude Fix Either&gt; foldr (const . show) "" e "LT" Prelude Fix Either&gt; e = leftF 42 :: EitherFix Integer Ordering Prelude Fix Either&gt; foldr (const . show) "" e ""</pre> </p> <p> In a GHCi session like the above, you can create two Either values of the same type. The <em>right</em> case is an <code>Ordering</code> value, while the <em>left</em> case is an <code>Integer</code> value. </p> <p> With <code>foldr</code>, there's no way to access the <em>left</em> case. While you can access and transform the right <code>Ordering</code> value, the number <code>42</code> is simply ignored during the fold. Instead, the default value <code>""</code> is returned. </p> <p> Contrast this with the catamorphism, which can access both cases: </p> <p> <pre>Prelude Fix Either&gt; e = rightF LT :: EitherFix Integer Ordering Prelude Fix Either&gt; eitherF show show e "LT" Prelude Fix Either&gt; e = leftF 42 :: EitherFix Integer Ordering Prelude Fix Either&gt; eitherF show show e "42"</pre> </p> <p> In a session like this, you recreate the same values, but using the catamorphism <code>eitherF</code>, you can now access and transform both the <em>left</em> and the <em>right</em> cases. In other words, the catamorphism enables you to perform operations not possible with the fold. </p> <p> It's interesting, however, to note that while the fold is a specialisation of the catamorphism, the <em>bifold</em> is identical to the catamorphism. </p> <h3 id="7512bca753b747ad9accde04bf13b6ca"> Summary <a href="#7512bca753b747ad9accde04bf13b6ca" title="permalink">#</a> </h3> <p> The catamorphism for Either is a pair of functions. One function transforms the <em>left</em> case, while the other function transforms the <em>right</em> case. For any Either value, only one of those functions will be used. </p> <p> When I originally encountered the concept of a <em>catamorphism</em>, I found it difficult to distinguish between catamorphism and fold. My problem was, I think, that the tutorials I ran into mostly used linked lists to demonstrate how, <a href="/2019/05/27/list-catamorphism">in that case</a>, the fold <em>is</em> the catamorphism. It turns out, however, that this isn't always the case. A catamorphism is a general abstraction. A fold, on the other hand, seems to me to be mostly related to collections. </p> <p> In this article you saw the first example of a catamorphism that can do more than the fold. For Either, the fold is just a special case of the catamorphism. You also saw, however, how the catamorphism was identical to the <em>bifold</em>. Thus, it's still not entirely clear how these concepts relate. Therefore, in the next article, you'll get an example of a <a href="https://bartoszmilewski.com/2014/01/14/functors-are-containers">container</a> where there's no bifold, and where the catamorphism is, indeed, a generalisation of the fold. </p> <p> <strong>Next:</strong> <a href="/2019/06/10/tree-catamorphism">Tree catamorphism</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/06/03/either-catamorphism List catamorphism https://blog.ploeh.dk/2019/05/27/list-catamorphism/ Mon, 27 May 2019 06:10:00 UTC <div id="post"> <p> <em>The catamorphism for a list is the same as its fold.</em> </p> <p> This article is part of an <a href="/2019/04/29/catamorphisms">article series about catamorphisms</a>. A catamorphism is a <a href="/2017/10/04/from-design-patterns-to-category-theory">universal abstraction</a> that describes how to digest a data structure into a potentially more compact value. </p> <p> This article presents the catamorphism for (linked) lists, and other collections in general. It also shows how to identify it. The beginning of this article presents the catamorphism in C#, with an example. The rest of the article describes how to deduce the catamorphism. This part of the article presents my work in <a href="https://www.haskell.org">Haskell</a>. Readers not comfortable with Haskell can just read the first part, and consider the rest of the article as an optional appendix. </p> <p> The C# part of the article will discuss <code>IEnumerable&lt;T&gt;</code>, while the Haskell part will deal specifically with linked lists. Since C# is a less strict language anyway, we have to make some concessions when we consider how concepts translate. In my experience, the functionality of <code>IEnumerable&lt;T&gt;</code> closely mirrors that of Haskell lists. </p> <h3 id="3190f7181a954b6388d77f61a1dbb928"> C# catamorphism <a href="#3190f7181a954b6388d77f61a1dbb928" title="permalink">#</a> </h3> <p> The .NET base class library defines this <a href="https://docs.microsoft.com/dotnet/api/system.linq.enumerable.aggregate">Aggregate</a> overload: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">TAccumulate</span>&nbsp;Aggregate&lt;<span style="color:#2b91af;">TSource</span>,&nbsp;<span style="color:#2b91af;">TAccumulate</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">TSource</span>&gt;&nbsp;source, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">TAccumulate</span>&nbsp;seed, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">TAccumulate</span>,&nbsp;<span style="color:#2b91af;">TSource</span>,&nbsp;<span style="color:#2b91af;">TAccumulate</span>&gt;&nbsp;func);</pre> </p> <p> This is the catamorphism for linked lists (and, I'll conjecture, for <code>IEnumerable&lt;T&gt;</code> in general). The <a href="/2019/04/29/catamorphisms">introductory article</a> already used it to show several motivating examples, of which I'll only repeat the last: </p> <p> <pre>&gt; <span style="color:blue;">new</span>[]&nbsp;{&nbsp;42,&nbsp;1337,&nbsp;2112,&nbsp;90125,&nbsp;5040,&nbsp;7,&nbsp;1984&nbsp;} . .Aggregate(<span style="color:#2b91af;">Angle</span>.Identity,&nbsp;(a,&nbsp;i)&nbsp;=&gt;&nbsp;a.Add(<span style="color:#2b91af;">Angle</span>.FromDegrees(i))) [{ Angle = 207° }]</pre> </p> <p> In short, the catamorphism is, similar to the previous catamorphisms covered in this article series, a pair made from an initial value and a function. This has been true for both the <a href="/2019/05/13/peano-catamorphism">Peano catamorphism</a> and the <a href="/2019/05/20/maybe-catamorphism">Maybe catamorphism</a>. An initial value is just a value in all three cases, but you may notice that the function in question becomes increasingly elaborate. For <code>IEnumerable&lt;T&gt;</code>, it's a function that takes two values. One of the values are of the type of the input list, i.e. for <code>IEnumerable&lt;TSource&gt;</code> it would be <code>TSource</code>. By elimination you can deduce that this value must come from the input list. The other value is of the type <code>TAccumulate</code>, which implies that it could be the <code>seed</code>, or the result from a previous call to <code>func</code>. </p> <h3 id="46afb325e03743d9ac2c2cf391607f82"> List F-Algebra <a href="#46afb325e03743d9ac2c2cf391607f82" title="permalink">#</a> </h3> <p> As in the <a href="/2019/05/20/maybe-catamorphism">previous article</a>, I'll use <code>Fix</code> and <code>cata</code> as explained in <a href="https://bartoszmilewski.com">Bartosz Milewski</a>'s excellent <a href="https://bartoszmilewski.com/2017/02/28/f-algebras/">article on F-Algebras</a>. The <code>ListF</code> type comes from his article as well, although I've renamed the type arguments: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;ListF&nbsp;a&nbsp;c&nbsp;=&nbsp;NilF&nbsp;|&nbsp;ConsF&nbsp;a&nbsp;c&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;(<span style="color:blue;">ListF</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;_&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NilF&nbsp;&nbsp;=&nbsp;NilF &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;f&nbsp;(ConsF&nbsp;a&nbsp;c)&nbsp;=&nbsp;ConsF&nbsp;a&nbsp;$&nbsp;f&nbsp;c</pre> </p> <p> Like I did with <code>MaybeF</code>, I've named the 'data' type argument <code>a</code>, and the carrier type <code>c</code> (for <em>carrier</em>). Once again, notice that the <code>Functor</code> instance maps over the carrier type <code>c</code>; not over the 'data' type <code>a</code>. </p> <p> As was also the case when deducing the Maybe catamorphism, Haskell isn't too happy about defining instances for a type like <code>Fix (ListF a)</code>. To address that problem, you can introduce a <code>newtype</code> wrapper: </p> <p> <pre><span style="color:blue;">newtype</span>&nbsp;ListFix&nbsp;a&nbsp;=&nbsp;ListFix&nbsp;{&nbsp;unListFix&nbsp;::&nbsp;Fix&nbsp;(ListF&nbsp;a)&nbsp;}&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> You can define <code>Functor</code>, <code>Applicative</code>, <code>Monad</code>, etc. instances for this type without resorting to any funky GHC extensions. Keep in mind that ultimately, the purpose of all this code is just to figure out what the catamorphism looks like. This code isn't intended for actual use. </p> <p> A few helper functions make it easier to define <code>ListFix</code> values: </p> <p> <pre><span style="color:#2b91af;">nilF</span>&nbsp;::&nbsp;<span style="color:blue;">ListFix</span>&nbsp;a nilF&nbsp;=&nbsp;ListFix&nbsp;$&nbsp;Fix&nbsp;NilF <span style="color:#2b91af;">consF</span>&nbsp;::&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;a consF&nbsp;x&nbsp;=&nbsp;ListFix&nbsp;.&nbsp;Fix&nbsp;.&nbsp;ConsF&nbsp;x&nbsp;.&nbsp;unListFix</pre> </p> <p> With those functions, you can create <code>ListFix</code> linked lists: </p> <p> <pre>Prelude Fix List&gt; nilF ListFix {unListFix = Fix NilF} Prelude Fix List&gt; consF 42 $ consF 1337 $ consF 2112 nilF ListFix {unListFix = Fix (ConsF 42 (Fix (ConsF 1337 (Fix (ConsF 2112 (Fix NilF))))))}</pre> </p> <p> The first example creates an empty list, whereas the second creates a list of three integers, corresponding to <code>[42,1337,2112]</code>. </p> <p> That's all you need to identify the catamorphism. </p> <h3 id="db44e85b27fb40d0b570c53cf4ce1843"> Haskell catamorphism <a href="#db44e85b27fb40d0b570c53cf4ce1843" title="permalink">#</a> </h3> <p> At this point, you have two out of three elements of an F-Algebra. You have an endofunctor (<code>ListF</code>), and an object <code>a</code>, but you still need to find a morphism <code>ListF a c -&gt; c</code>. Notice that the algebra you have to find is the function that reduces the functor to its <em>carrier type</em> <code>c</code>, not the 'data type' <code>a</code>. This takes some time to get used to, but that's how catamorphisms work. This doesn't mean, however, that you get to ignore <code>a</code>, as you'll see. </p> <p> As in the previous article, start by writing a function that will become the catamorphism, based on <code>cata</code>: </p> <p> <pre>listF&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unListFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NilF&nbsp;&nbsp;=&nbsp;<span style="color:blue;">undefined</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(ConsF&nbsp;h&nbsp;t)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> While this compiles, with its <code>undefined</code> implementations, it obviously doesn't do anything useful. I find, however, that it helps me think. How can you return a value of the type <code>c</code> from the <code>NilF</code> case? You could pass an argument to the <code>listF</code> function: </p> <p> <pre>listF&nbsp;n&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unListFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NilF&nbsp;&nbsp;=&nbsp;n &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(ConsF&nbsp;h&nbsp;t)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> The <code>ConsF</code> case, contrary to <code>NilF</code>, contains both a head <code>h</code> (of type <code>a</code>) and a tail <code>t</code> (of type <code>c</code>). While you could make the code compile by simply returning <code>t</code>, it'd be incorrect to ignore <code>h</code>. In order to deal with both, you'll need a function that turns both <code>h</code> and <code>t</code> into a value of the type <code>c</code>. You can do this by passing a function to <code>listF</code> and using it: </p> <p> <pre><span style="color:#2b91af;">listF</span>&nbsp;::&nbsp;(a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c listF&nbsp;f&nbsp;n&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unListFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NilF&nbsp;&nbsp;=&nbsp;n &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(ConsF&nbsp;h&nbsp;t)&nbsp;=&nbsp;f&nbsp;h&nbsp;t</pre> </p> <p> This works. Since <code>cata</code> has the type <code>Functor f =&gt; (f a -&gt; a) -&gt; Fix f -&gt; a</code>, that means that <code>alg</code> has the type <code>f a -&gt; a</code>. In the case of <code>ListF</code>, the compiler infers that the <code>alg</code> function has the type <code>ListF a c -&gt; c</code>, which is just what you need! </p> <p> You can now see what the carrier type <code>c</code> is for. It's the type that the algebra extracts, and thus the type that the catamorphism returns. </p> <p> This, then, is the catamorphism for lists. As has been consistent so far, it's a pair made from an initial value and a function. Once more, this isn't the only possible catamorphism, since you can, for example, trivially flip the arguments to <code>listF</code>: </p> <p> <pre><span style="color:#2b91af;">listF</span>&nbsp;::&nbsp;c&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c listF&nbsp;n&nbsp;f&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unListFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NilF&nbsp;&nbsp;=&nbsp;n &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(ConsF&nbsp;h&nbsp;t)&nbsp;=&nbsp;f&nbsp;h&nbsp;t</pre> </p> <p> You can also flip the arguments of <code>f</code>: </p> <p> <pre><span style="color:#2b91af;">listF</span>&nbsp;::&nbsp;c&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(c&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c listF&nbsp;n&nbsp;f&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unListFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NilF&nbsp;&nbsp;=&nbsp;n &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(ConsF&nbsp;h&nbsp;t)&nbsp;=&nbsp;f&nbsp;t&nbsp;h</pre> </p> <p> These representations are all isomorphic to each other, but notice that the last variation is similar to the above C# <code>Aggregate</code> overload. The initial <code>n</code> value is the <code>seed</code>, and the function <code>f</code> has the same shape as <code>func</code>. Thus, I consider it reasonable to conjecture that that <code>Aggregate</code> overload is the catamorphism for <code>IEnumerable&lt;T&gt;</code>. </p> <h3 id="3ba9143e87544443b713727eb4ea60ba"> Basis <a href="#3ba9143e87544443b713727eb4ea60ba" title="permalink">#</a> </h3> <p> You can implement most other useful functionality with <code>listF</code>. The rest of this article uses the first of the variations shown above, with the type <code>(a -&gt; c -&gt; c) -&gt; c -&gt; ListFix a -&gt; c</code>. Here's the <code>Semigroup</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Semigroup</span>&nbsp;(<span style="color:blue;">ListFix</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;xs&nbsp;&lt;&gt;&nbsp;ys&nbsp;=&nbsp;listF&nbsp;consF&nbsp;ys&nbsp;xs</pre> </p> <p> The initial value passed to <code>listF</code> is <code>ys</code>, and the function to apply is simply the <code>consF</code> function, thus 'consing' the two lists together. Here's an example of the operation in action: </p> <p> <pre>Prelude Fix List&gt; consF 42 $ consF 1337 nilF &lt;&gt; (consF 2112 $ consF 1 nilF) ListFix {unListFix = Fix (ConsF 42 (Fix (ConsF 1337 (Fix (ConsF 2112 (Fix (ConsF 1 (Fix NilF))))))))}</pre> </p> <p> With a <code>Semigroup</code> instance, it's trivial to also implement the <code>Monoid</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Monoid</span>&nbsp;(<span style="color:blue;">ListFix</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;mempty&nbsp;=&nbsp;nilF</pre> </p> <p> While you <em>could</em> implement <code>mempty</code> with <code>listF</code> (<code>mempty = listF (const id) nilF nilF</code>), that'd be overcomplicated. Just because you can implement all functionality using <code>listF</code>, it doesn't mean that you should, if a simpler alternative exists. </p> <p> You can, on the other hand, use <code>listF</code> for the <code>Functor</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;f&nbsp;=&nbsp;listF&nbsp;(\h&nbsp;l&nbsp;-&gt;&nbsp;consF&nbsp;(f&nbsp;h)&nbsp;l)&nbsp;nilF</pre> </p> <p> You could write the function you pass to <code>listF</code> in a point-free fashion as <code>consF . f</code>, but I thought it'd be easier to follow what happens when written as an explicit lambda expression. The function receives a 'current value' <code>h</code>, as well as the part of the list which has already been translated <code>l</code>. Use <code>f</code> to translate <code>h</code>, and <code>consF</code> the result unto <code>l</code>. </p> <p> You can add <code>Applicative</code> and <code>Monad</code> instances in a similar fashion: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Applicative</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;pure&nbsp;x&nbsp;=&nbsp;consF&nbsp;x&nbsp;nilF &nbsp;&nbsp;fs&nbsp;&lt;*&gt;&nbsp;xs&nbsp;=&nbsp;listF&nbsp;(\f&nbsp;acc&nbsp;-&gt;&nbsp;(f&nbsp;&lt;$&gt;&nbsp;xs)&nbsp;&lt;&gt;&nbsp;acc)&nbsp;nilF&nbsp;fs <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Monad</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;xs&nbsp;&gt;&gt;=&nbsp;f&nbsp;=&nbsp;listF&nbsp;(\x&nbsp;acc&nbsp;-&gt;&nbsp;f&nbsp;x&nbsp;&lt;&gt;&nbsp;acc)&nbsp;nilF&nbsp;xs</pre> </p> <p> What may be more interesting, however, is the <code>Foldable</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Foldable</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">foldr</span>&nbsp;=&nbsp;listF</pre> </p> <p> The demonstrates that <code>listF</code> and <code>foldr</code> is the same. </p> <p> Next, you can also add a <code>Traversable</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Traversable</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;sequenceA&nbsp;=&nbsp;listF&nbsp;(\x&nbsp;acc&nbsp;-&gt;&nbsp;consF&nbsp;&lt;$&gt;&nbsp;x&nbsp;&lt;*&gt;&nbsp;acc)&nbsp;(pure&nbsp;nilF)</pre> </p> <p> Finally, you can implement conversions to and from the standard list <code>[]</code> type, using <code>ana</code> as the dual of <code>cata</code>: </p> <p> <pre><span style="color:#2b91af;">toList</span>&nbsp;::&nbsp;<span style="color:blue;">ListFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;[a] toList&nbsp;=&nbsp;listF&nbsp;<span style="color:#2b91af;">(:)</span>&nbsp;<span style="color:blue;">[]</span> <span style="color:#2b91af;">fromList</span>&nbsp;::&nbsp;[a]&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;a fromList&nbsp;=&nbsp;ListFix&nbsp;.&nbsp;ana&nbsp;coalg &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;coalg&nbsp;&nbsp;&nbsp;<span style="color:blue;">[]</span>&nbsp;&nbsp;=&nbsp;NilF &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;coalg&nbsp;(h:t)&nbsp;=&nbsp;ConsF&nbsp;h&nbsp;t</pre> </p> <p> This demonstrates that <code>ListFix</code> is isomorphic to <code>[]</code>, which again establishes that <code>listF</code> and <code>foldr</code> are equivalent. </p> <h3 id="616c31c72b1f43cca647760d9fa8b226"> Summary <a href="#616c31c72b1f43cca647760d9fa8b226" title="permalink">#</a> </h3> <p> The catamorphism for lists is a pair made from an initial value and a function. One variation is equal to <code>foldr</code>. Like Maybe, the catamorphism is the same as the fold. </p> <p> In C#, this function corresponds to the <code>Aggregate</code> extension method identified above. </p> <p> You've now seen two examples where the catamorphism coincides with the fold. You've also seen examples (<a href="/2019/05/06/boolean-catamorphism">Boolean catamorphism</a> and <a href="/2019/05/13/peano-catamorphism">Peano catamorphism</a>) where there's a catamorphism, but no fold at all. In the next article, you'll see an example of a <a href="https://bartoszmilewski.com/2014/01/14/functors-are-containers">container</a> that has both catamorphism and fold, but where the catamorphism is more general than the fold. </p> <p> <strong>Next:</strong> <a href="/2019/06/03/either-catamorphism">Either catamorphism</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/05/27/list-catamorphism Maybe catamorphism https://blog.ploeh.dk/2019/05/20/maybe-catamorphism/ Mon, 20 May 2019 06:04:00 UTC <div id="post"> <p> <em>The catamorphism for Maybe is just a simplification of its fold.</em> </p> <p> This article is part of an <a href="/2019/04/29/catamorphisms">article series about catamorphisms</a>. A catamorphism is a <a href="/2017/10/04/from-design-patterns-to-category-theory">universal abstraction</a> that describes how to digest a data structure into a potentially more compact value. </p> <p> This article presents the catamorphism for <a href="/2018/03/26/the-maybe-functor">Maybe</a>, as well as how to identify it. The beginning of this article presents the catamorphism in C#, with examples. The rest of the article describes how to deduce the catamorphism. This part of the article presents my work in <a href="https://www.haskell.org">Haskell</a>. Readers not comfortable with Haskell can just read the first part, and consider the rest of the article as an optional appendix. </p> <p> <em>Maybe</em> is a <a href="https://bartoszmilewski.com/2014/01/14/functors-are-containers">data container</a> that models the absence or presence of a value. <a href="/2015/11/13/null-has-no-type-but-maybe-has">Contrary to null, Maybe has a type</a>, so offers a sane and reasonable way to model that situation. </p> <h3 id="1feeee3382ff44d182e0a28a33f8f80a"> C# catamorphism <a href="#1feeee3382ff44d182e0a28a33f8f80a" title="permalink">#</a> </h3> <p> This article uses <a href="/2018/06/04/church-encoded-maybe">Church-encoded Maybe</a>. Other, <a href="/2018/03/26/the-maybe-functor">alternative implementations of Maybe are possible</a>. The catamorphism for Maybe is the <code>Match</code> method: </p> <p> <pre><span style="color:#2b91af;">TResult</span>&nbsp;Match&lt;<span style="color:#2b91af;">TResult</span>&gt;(<span style="color:#2b91af;">TResult</span>&nbsp;nothing,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;just);</pre> </p> <p> Like the <a href="/2019/05/13/peano-catamorphism">Peano catamorphism</a>, the Maybe catamorphism is a pair of a value and a function. The <code>nothing</code> value corresponds to the absence of data, whereas the <code>just</code> function handles the presence of data. </p> <p> Given, for example, a Maybe containing a number, you can use <code>Match</code> to <a href="/2019/02/04/how-to-get-the-value-out-of-the-monad">get the value out of the Maybe</a>: </p> <p> <pre>&gt; <span style="color:#2b91af;">IMaybe</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;maybe&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Just</span>&lt;<span style="color:blue;">int</span>&gt;(42); &gt; maybe.Match(0,&nbsp;x&nbsp;=&gt;&nbsp;x) 42 &gt; <span style="color:#2b91af;">IMaybe</span>&lt;<span style="color:blue;">int</span>&gt;&nbsp;maybe&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Nothing</span>&lt;<span style="color:blue;">int</span>&gt;(); &gt; maybe.Match(0,&nbsp;x&nbsp;=&gt;&nbsp;x) 0</pre> </p> <p> The functionality is, however, more useful than a simple <em>get-value-or-default</em> operation. Often, you don't have a good default value for the type potentially wrapped in a Maybe object. In the core of your application architecture, it may not be clear how to deal with, say, the absence of a <code>Reservation</code> object, whereas at the boundary of your system, it's evident how to convert both absence and presence of data into a unifying type, such as an HTTP response: </p> <p> <pre><span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&nbsp;maybe&nbsp;=&nbsp;<span style="color:green;">//&nbsp;...</span> <span style="color:blue;">return</span>&nbsp;maybe &nbsp;&nbsp;&nbsp;&nbsp;.Select(r&nbsp;=&gt;&nbsp;Repository.Create(r)) &nbsp;&nbsp;&nbsp;&nbsp;.Match&lt;<span style="color:#2b91af;">IHttpActionResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nothing:&nbsp;Content( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">HttpStatusCode</span>.InternalServerError, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HttpError</span>(<span style="color:#a31515;">&quot;Couldn&#39;t&nbsp;accept.&quot;</span>)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;just:&nbsp;id&nbsp;=&gt;&nbsp;Ok(id));</pre> </p> <p> This enables you to avoid special cases, such as null <code>Reservation</code> objects, or magic numbers like <code>-1</code> to indicate the absence of <code>id</code> values. At the boundary of an HTTP-based application, you know that you must return an HTTP response. That's the unifying type, so you can return <code>200 OK</code> with a reservation ID in the response body when data is present, and <code>500 Internal Server Error</code> when data is absent. </p> <h3 id="87d91da8944f4eb5b8b24e9ea20d3e1b"> Maybe F-Algebra <a href="#87d91da8944f4eb5b8b24e9ea20d3e1b" title="permalink">#</a> </h3> <p> As in the <a href="/2019/05/13/peano-catamorphism">previous article</a>, I'll use <code>Fix</code> and <code>cata</code> as explained in <a href="https://bartoszmilewski.com">Bartosz Milewski</a>'s excellent <a href="https://bartoszmilewski.com/2017/02/28/f-algebras/">article on F-Algebras</a>. </p> <p> While F-Algebras and fixed points are mostly used for recursive data structures, you can also define an F-Algebra for a non-recursive data structure. You already saw an example of that in the article about <a href="/2019/05/06/boolean-catamorphism">Boolean catamorphism</a>. The difference between Boolean values and Maybe is that the <em>just</em> case of Maybe carries a value. You can model this as a <code>Functor</code> with both a carrier type and a type argument for the data that Maybe may contain: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;MaybeF&nbsp;a&nbsp;c&nbsp;=&nbsp;NothingF&nbsp;|&nbsp;JustF&nbsp;a&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;(<span style="color:blue;">MaybeF</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;_&nbsp;&nbsp;NothingF&nbsp;=&nbsp;NothingF &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;_&nbsp;(JustF&nbsp;x)&nbsp;=&nbsp;JustF&nbsp;x</pre> </p> <p> I chose to call the 'data type' <code>a</code> and the carrier type <code>c</code> (for <em>carrier</em>). As was also the case with <code>BoolF</code>, the <code>Functor</code> instance ignores the map function because the carrier type is missing from both the <code>NothingF</code> case and the <code>JustF</code> case. Like the <code>Functor</code> instance for <code>BoolF</code>, it'd seem that nothing happens, but at the type level, this is still a translation from <code>MaybeF a c</code> to <code>MaybeF a c1</code>. Not much of a function, perhaps, but definitely an <em>endofunctor</em>. </p> <p> In the previous articles, it was possible to work directly with the fixed points of both functors; i.e. <code>Fix BoolF</code> and <code>Fix NatF</code>. Haskell isn't happy about attempts to define various instances for <code>Fix (MaybeF a)</code>, so in order to make this easier, you can define a <code>newtype</code> wrapper: </p> <p> <pre><span style="color:blue;">newtype</span>&nbsp;MaybeFix&nbsp;a&nbsp;= &nbsp;&nbsp;MaybeFix&nbsp;{&nbsp;unMaybeFix&nbsp;::&nbsp;Fix&nbsp;(MaybeF&nbsp;a)&nbsp;}&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> In order to make it easier to work with <code>MaybeFix</code> you can add helper functions to create values: </p> <p> <pre><span style="color:#2b91af;">nothingF</span>&nbsp;::&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;a nothingF&nbsp;=&nbsp;MaybeFix&nbsp;$&nbsp;Fix&nbsp;NothingF <span style="color:#2b91af;">justF</span>&nbsp;::&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;a justF&nbsp;=&nbsp;MaybeFix&nbsp;.&nbsp;Fix&nbsp;.&nbsp;JustF</pre> </p> <p> You can now create <code>MaybeFix</code> values to your heart's content: </p> <p> <pre>Prelude Fix Maybe&gt; justF 42 MaybeFix {unMaybeFix = Fix (JustF 42)} Prelude Fix Maybe&gt; nothingF MaybeFix {unMaybeFix = Fix NothingF}</pre> </p> <p> That's all you need to identify the catamorphism. </p> <h3 id="24db4c715d1f4540bd8f87604819952f"> Haskell catamorphism <a href="#24db4c715d1f4540bd8f87604819952f" title="permalink">#</a> </h3> <p> At this point, you have two out of three elements of an F-Algebra. You have an endofunctor (<code>MaybeF</code>), and an object <code>a</code>, but you still need to find a morphism <code>MaybeF a c -&gt; c</code>. Notice that the algebra you have to find is the function that reduces the functor to its <em>carrier type</em> <code>c</code>, not the 'data type' <code>a</code>. This takes some time to get used to, but that's how catamorphisms work. This doesn't mean, however, that you get to ignore <code>a</code>, as you'll see. </p> <p> As in the previous article, start by writing a function that will become the catamorphism, based on <code>cata</code>: </p> <p> <pre>maybeF&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unMaybeFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;NothingF&nbsp;=&nbsp;<span style="color:blue;">undefined</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(JustF&nbsp;x)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> While this compiles, with its <code>undefined</code> implementations, it obviously doesn't do anything useful. I find, however, that it helps me think. How can you return a value of the type <code>c</code> from the <code>NothingF</code> case? You could pass an argument to the <code>maybeF</code> function: </p> <p> <pre>maybeF&nbsp;n&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unMaybeFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;NothingF&nbsp;=&nbsp;n &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(JustF&nbsp;x)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> The <code>JustF</code> case, contrary to <code>NothingF</code>, already contains a value, and it'd be incorrect to ignore it. On the other hand, <code>x</code> is a value of type <code>a</code>, and you need to return a value of type <code>c</code>. You'll need a function to perform the conversion, so pass such a function as an argument to <code>maybeF</code> as well: </p> <p> <pre><span style="color:#2b91af;">maybeF</span>&nbsp;::&nbsp;c&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c maybeF&nbsp;n&nbsp;f&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unMaybeFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;NothingF&nbsp;=&nbsp;n &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(JustF&nbsp;x)&nbsp;=&nbsp;f&nbsp;x</pre> </p> <p> This works. Since <code>cata</code> has the type <code>Functor f =&gt; (f a -&gt; a) -&gt; Fix f -&gt; a</code>, that means that <code>alg</code> has the type <code>f a -&gt; a</code>. In the case of <code>MaybeF</code>, the compiler infers that the <code>alg</code> function has the type <code>MaybeF a c -&gt; c</code>, which is just what you need! </p> <p> You can now see what the carrier type <code>c</code> is for. It's the type that the algebra extracts, and thus the type that the catamorphism returns. </p> <p> Notice that <code>maybeF</code>, like the above C# <code>Match</code> method, takes as arguments a pair of a value and a function (together with the Maybe value itself). Those are two representations of the same idea. Furthermore, this is nearly identical to the <code>maybe</code> function in Haskell's <code>Data.Maybe</code> module. I found if fitting, therefore, to name the function <code>maybeF</code>. </p> <h3 id="d8a0eed800de48a994085c419b7b5379"> Basis <a href="#d8a0eed800de48a994085c419b7b5379" title="permalink">#</a> </h3> <p> You can implement most other useful functionality with <code>maybeF</code>. Here's the <code>Functor</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;f&nbsp;=&nbsp;maybeF&nbsp;nothingF&nbsp;(justF&nbsp;.&nbsp;f)</pre> </p> <p> Since <code>fmap</code> should be a structure-preserving map, you'll have to map the <em>nothing</em> case to the <em>nothing</em> case, and <em>just</em> to <em>just</em>. When calling <code>maybeF</code>, you must supply a value for the <em>nothing</em> case and a function to deal with the <em>just</em> case. The <em>nothing</em> case is easy to handle: just use <code>nothingF</code>. </p> <p> In the <em>just</em> case, first apply the function <code>f</code> to map from <code>a</code> to <code>b</code>, and then use <code>justF</code> to wrap the <code>b</code> value in a new <code>MaybeFix</code> container to get <code>MaybeFix b</code>. </p> <p> <code>Applicative</code> is a little harder, but not much: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Applicative</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;pure&nbsp;=&nbsp;justF &nbsp;&nbsp;f&nbsp;&lt;*&gt;&nbsp;x&nbsp;=&nbsp;maybeF&nbsp;nothingF&nbsp;(&lt;$&gt;&nbsp;x)&nbsp;f</pre> </p> <p> The <code>pure</code> function is just <em>justF</em> (pun intended). The <em>apply</em> operator <code>&lt;*&gt;</code> is more complex. </p> <p> Both <code>f</code> and <code>x</code> surrounding <code>&lt;*&gt;</code> are <code>MaybeFix</code> values: <code>f</code> is <code>MaybeFix (a -&gt; b)</code>, and <code>x</code> is <code>MaybeFix a</code>. While it's becoming increasingly clear that you can use a catamorphism like <code>maybeF</code> to implement most other functionality, to which <code>MaybeFix</code> value should you apply it? To <code>f</code> or <code>x</code>? </p> <p> Both are possible, but the code looks (in my opinion) more readable if you apply it to <code>f</code>. Again, when <code>f</code> is <em>nothing</em>, return <code>nothingF</code>. When <code>f</code> is <em>just</em>, use the functor instance to map <code>x</code> (using the infix <code>fmap</code> alias <code>&lt;$&gt;</code>). </p> <p> The <code>Monad</code> instance, on the other hand, is almost trivial: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Monad</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;x&nbsp;&gt;&gt;=&nbsp;f&nbsp;=&nbsp;maybeF&nbsp;nothingF&nbsp;f&nbsp;x</pre> </p> <p> As usual, map <em>nothing</em> to <em>nothing</em> by supplying <code>nothingF</code>. <code>f</code> is already a function that returns a <code>MaybeFix b</code> value, so just use that. </p> <p> The <code>Foldable</code> instance is likewise trivial (although, as you'll see below, you can make it even more trivial): </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Foldable</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;foldMap&nbsp;=&nbsp;maybeF&nbsp;mempty</pre> </p> <p> The <code>foldMap</code> function must return a <code>Monoid</code> instance, so for the <em>nothing</em> case, simply return the identity, <em>mempty</em>. Furthermore, <code>foldMap</code> takes a function <code>a -&gt; m</code>, but since the <code>foldMap</code> implementation is <a href="https://en.wikipedia.org/wiki/Tacit_programming">point-free</a>, you can't 'see' that function as an argument. </p> <p> Finally, for the sake of completeness, here's the <code>Traversable</code> instance: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Traversable</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;sequenceA&nbsp;=&nbsp;maybeF&nbsp;(pure&nbsp;nothingF)&nbsp;(justF&nbsp;&lt;$&gt;)</pre> </p> <p> In the <em>nothing</em> case, you can put <code>nothingF</code> into the desired <code>Applicative</code> with <code>pure</code>. In the <em>just</em> case you can take advantage of the desired <code>Applicative</code> being also a <code>Functor</code> by simply mapping the inner value(s) with <code>justF</code>. </p> <p> Since the <code>Applicative</code> instance for <code>MaybeFix</code> equals <code>pure</code> to <code>justF</code>, you could alternatively write the <code>Traversable</code> instance like this: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Traversable</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;sequenceA&nbsp;=&nbsp;maybeF&nbsp;(pure&nbsp;nothingF)&nbsp;(pure&nbsp;&lt;$&gt;)</pre> </p> <p> I like this alternative less, since I find it confusing. The two appearances of <code>pure</code> relate to two different types. The <code>pure</code> in <code>pure nothingF</code> has the type <code>MaybeFix a -&gt; f (MaybeFix a)</code>, while the <code>pure</code> in <code>pure&nbsp;&lt;$&gt;</code> has the type <code>a -&gt; MaybeFix a</code>! </p> <p> Both implementations work the same, though: </p> <p> <pre>Prelude Fix Maybe&gt; sequenceA (justF ("foo", 42)) ("foo",MaybeFix {unMaybeFix = Fix (JustF 42)})</pre> </p> <p> Here, I'm using the <code>Applicative</code> instance of <code>(,) String</code>. </p> <p> Finally, you can implement conversions to and from the standard <code>Maybe</code> type, using <code>ana</code> as the dual of <code>cata</code>: </p> <p> <pre><span style="color:#2b91af;">toMaybe</span>&nbsp;::&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&nbsp;a toMaybe&nbsp;=&nbsp;maybeF&nbsp;Nothing&nbsp;<span style="color:blue;">return</span> <span style="color:#2b91af;">fromMaybe</span>&nbsp;::&nbsp;<span style="color:#2b91af;">Maybe</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;a fromMaybe&nbsp;=&nbsp;MaybeFix&nbsp;.&nbsp;ana&nbsp;coalg &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;coalg&nbsp;&nbsp;Nothing&nbsp;=&nbsp;NothingF &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;coalg&nbsp;(Just&nbsp;x)&nbsp;=&nbsp;JustF&nbsp;x</pre> </p> <p> This demonstrates that <code>MaybeFix</code> is isomorphic to <code>Maybe</code>, which again establishes that <code>maybeF</code> and <code>maybe</code> are equivalent. </p> <h3 id="2ec047e5122b4750a10cbe2012285524"> Alternatives <a href="#2ec047e5122b4750a10cbe2012285524" title="permalink">#</a> </h3> <p> As usual, the above <code>maybeF</code> isn't the only possible catamorphism. A trivial variation is to flip its arguments, but other variations exist. </p> <p> It's a recurring observation that a catamorphism is just a generalisation of a <em>fold</em>. In the above code, the <code>Foldable</code> instance already looked as simple as anyone could desire, but another variation of a catamorphism for Maybe is this gratuitously embellished definition: </p> <p> <pre><span style="color:#2b91af;">maybeF</span>&nbsp;::&nbsp;(a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c maybeF&nbsp;f&nbsp;n&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unMaybeFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;&nbsp;NothingF&nbsp;=&nbsp;n &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(JustF&nbsp;x)&nbsp;=&nbsp;f&nbsp;x&nbsp;n</pre> </p> <p> This variation redundantly passes <code>n</code> as an argument to <code>f</code>, thereby changing the type of <code>f</code> to <code>a -&gt; c -&gt; c</code>. There's no particular motivation for doing this, apart from establishing that this catamorphism is exactly the same as the fold: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Foldable</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">foldr</span>&nbsp;=&nbsp;maybeF</pre> </p> <p> You can still implement the other instances as well, but the rest of the code suffers in clarity. Here's a few examples: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;f&nbsp;=&nbsp;maybeF&nbsp;(<span style="color:blue;">const</span>&nbsp;.&nbsp;justF&nbsp;.&nbsp;f)&nbsp;nothingF <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Applicative</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;pure&nbsp;=&nbsp;justF &nbsp;&nbsp;f&nbsp;&lt;*&gt;&nbsp;x&nbsp;=&nbsp;maybeF&nbsp;(<span style="color:blue;">const</span>&nbsp;.&nbsp;(&lt;$&gt;&nbsp;x))&nbsp;nothingF&nbsp;f <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Monad</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;x&nbsp;&gt;&gt;=&nbsp;f&nbsp;=&nbsp;maybeF&nbsp;(<span style="color:blue;">const</span>&nbsp;.&nbsp;f)&nbsp;nothingF&nbsp;x</pre> </p> <p> I find that the need to compose with <code>const</code> does nothing to improve the readability of the code, so this variation is mostly, I think, of academic interest. It does show, though, that the catamorphism of Maybe is isomorphic to its fold, as the diagram in the overview article indicated: </p> <p> <img src="/content/binary/catamorphism-and-fold-relations.png" alt="Catamorphisms and folds as sets, for various sum types."> </p> <p> You can demonstrate that this variation, too, is isomorphic to <code>Maybe</code> with a set of conversion: </p> <p> <pre><span style="color:#2b91af;">toMaybe</span>&nbsp;::&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&nbsp;a toMaybe&nbsp;=&nbsp;maybeF&nbsp;(<span style="color:blue;">const</span>&nbsp;.&nbsp;<span style="color:blue;">return</span>)&nbsp;Nothing <span style="color:#2b91af;">fromMaybe</span>&nbsp;::&nbsp;<span style="color:#2b91af;">Maybe</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">MaybeFix</span>&nbsp;a fromMaybe&nbsp;=&nbsp;MaybeFix&nbsp;.&nbsp;ana&nbsp;coalg &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;coalg&nbsp;&nbsp;Nothing&nbsp;=&nbsp;NothingF &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;coalg&nbsp;(Just&nbsp;x)&nbsp;=&nbsp;JustF&nbsp;x</pre> </p> <p> Only <code>toMaybe</code> has changed, compared to above; the <code>fromMaybe</code> function remains the same. The only change to <code>toMaybe</code> is that the arguments have been flipped, and <code>return</code> is now composed with <code>const</code>. </p> <p> Since (according to <a href="http://amzn.to/13tGJ0f">Conceptual Mathematics</a>) isomorphisms are transitive this means that the two variations of <code>maybeF</code> are isomorphic. The latter, more complex, variation of <code>maybeF</code> is identical <code>foldr</code>, so we can consider the simpler, more frequently encountered variation a simplification of <em>fold</em>. </p> <h3 id="f88757d425a04e97956d89270b32c0c0"> Summary <a href="#f88757d425a04e97956d89270b32c0c0" title="permalink">#</a> </h3> <p> The catamorphism for Maybe is the same as its Church encoding: a pair made from a default value and a function. In Haskell's base library, this is simply called <code>maybe</code>. In the above C# code, it's called <code>Match</code>. </p> <p> This function is total, and you can implement any other functionality you need with it. I therefore consider it the canonical representation of Maybe, which is also why it annoys me that most Maybe implementations come equipped with partial functions like <code>fromJust</code>, or F#'s <code>Option.get</code>. Those functions shouldn't be part of a sane and reasonable Maybe API. You shouldn't need them. </p> <p> In this series of articles about catamorphisms, you've now seen the first example of catamorphism and fold coinciding. In the next article, you'll see another such example - probably the most well-known catamorphism example of them all. </p> <p> <strong>Next:</strong> <a href="/2019/05/27/list-catamorphism">List catamorphism</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/05/20/maybe-catamorphism Peano catamorphism https://blog.ploeh.dk/2019/05/13/peano-catamorphism/ Mon, 13 May 2019 05:10:00 UTC <div id="post"> <p> <em>The catamorphism for Peano numbers involves a base value and a successor function.</em> </p> <p> This article is part of an <a href="/2019/04/29/catamorphisms">article series about catamorphisms</a>. A catamorphism is a <a href="/2017/10/04/from-design-patterns-to-category-theory">universal abstraction</a> that describes how to digest a data structure into a potentially more compact value. </p> <p> This article presents the catamorphism for <a href="https://en.wikipedia.org/wiki/Natural_number">natural numbers</a>, as well as how to identify it. The beginning of the article presents the catamorphism in C#, with examples. The rest of the article describes how I deduced the catamorphism. This part of the article presents my work in <a href="https://www.haskell.org">Haskell</a>. Readers not comfortable with Haskell can just read the first part, and consider the rest of the article as an optional appendix. </p> <h3 id="742f4b9c0c014152a933961c10f98b66"> C# catamorphism <a href="#742f4b9c0c014152a933961c10f98b66" title="permalink">#</a> </h3> <p> In this article, I model natural numbers using <a href="https://en.wikipedia.org/wiki/Peano_axioms">Peano's model</a>, and I'll reuse the <a href="/2018/05/28/church-encoded-natural-numbers">Church-encoded implementation you've seen before</a>. The catamorphism for <code>INaturalNumber</code> is: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">T</span>&nbsp;Cata&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">INaturalNumber</span>&nbsp;n,&nbsp;<span style="color:#2b91af;">T</span>&nbsp;zero,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">T</span>&gt;&nbsp;succ) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;n.Match(zero,&nbsp;p&nbsp;=&gt;&nbsp;p.Cata(succ(zero),&nbsp;succ)); }</pre> </p> <p> Notice that this is an extension method on <code>INaturalNumber</code>, taking two other arguments: a <code>zero</code> argument which will be returned when the number is <em>zero</em>, and a successor function to return the 'next' value based on a previous value. </p> <p> The <code>zero</code> argument is the easiest to understand. It's simply passed to <code>Match</code> so that this is the value that <code>Cata</code> returns when <code>n</code> is <em>zero</em>. </p> <p> The other argument to <code>Match</code> must be a <code>Func&lt;INaturalNumber, T&gt;</code>; that is, a function that takes an <code>INaturalNumber</code> as input and returns a value of the type <code>T</code>. You can supply such a function by using a lambda expression. This expression receives a predecessor <code>p</code> as input, and has to return a value of the type <code>T</code>. The only function available in this context, however, is <code>succ</code>, which has the type <code>Func&lt;T, T&gt;</code>. How can you make that work? </p> <p> As is often the case when programming with generics, it pays to <em>follow the types</em>. A <code>Func&lt;T, T&gt;</code> requires an input of the type <code>T</code>. Do you have any <code>T</code> objects around? </p> <p> The only available <code>T</code> object is <code>zero</code>, so you could call <code>succ(zero)</code> to produce another <code>T</code> value. While you could return that immediately, that'd ignore the predecessor <code>p</code>, so that's not going to work. Another option, which is the one that works, is to recursively call <code>Cata</code> with <code>succ(zero)</code> as the <code>zero</code> value, and <code>succ</code> as the second argument. </p> <p> What this accomplishes is that <code>Cata</code> keeps recursively calling itself until <code>n</code> is <em>zero</em>. The <code>zero</code> object, however, will be the result of repeated applications of <code>succ(zero)</code>. In other words, <code>succ</code> will be called as many times as the natural number. If <code>n</code> is 7, then <code>succ</code> will be called seven times, the first time with the original <code>zero</code> value, the next time with the result of <code>succ(zero)</code>, the third time with the result of <code>succ(succ(zero))</code>, and so on. If the number is 42, <code>succ</code> will be called 42 times. </p> <h3 id="633dae2048cd45ebaa17962710048c67"> Arithmetic <a href="#633dae2048cd45ebaa17962710048c67" title="permalink">#</a> </h3> <p> You can implement all the functionality you saw in the article on Church-encoded natural numbers. You can start gently by converting a Peano number into a normal C# <code>int</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">int</span>&nbsp;Count(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">INaturalNumber</span>&nbsp;n) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;n.Cata(0,&nbsp;x&nbsp;=&gt;&nbsp;1&nbsp;+&nbsp;x); }</pre> </p> <p> You can play with the functionality in <em>C# Interactive</em> to get a feel for how it works: </p> <p> <pre>&gt; <span style="color:#2b91af;">NaturalNumber</span>.Eight.Count() 8 &gt; <span style="color:#2b91af;">NaturalNumber</span>.Five.Count() 5</pre> </p> <p> The <code>Count</code> extension method uses <code>Cata</code> to count the level of recursion. The <code>zero</code> value is, not surprisingly, <code>0</code>, and the successor function simply adds one to the previous number. Since the successor function runs as many times as encoded by the Peano number, and since the initial value is <code>0</code>, you get the integer value of the number when <code>Cata</code> exits. </p> <p> A useful building block you can write using <code>Cata</code> is a function to increment a natural number by one: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">INaturalNumber</span>&nbsp;Increment(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">INaturalNumber</span>&nbsp;n) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;n.Cata(One,&nbsp;p&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Successor</span>(p)); }</pre> </p> <p> This, again, works as you'd expect: </p> <p> <pre>&gt; <span style="color:#2b91af;">NaturalNumber</span>.Zero.Increment().Count() 1 &gt; <span style="color:#2b91af;">NaturalNumber</span>.Eight.Increment().Count() 9</pre> </p> <p> With the <code>Increment</code> method and <code>Cata</code>, you can easily implement addition: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">INaturalNumber</span>&nbsp;Add(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">INaturalNumber</span>&nbsp;x,&nbsp;<span style="color:#2b91af;">INaturalNumber</span>&nbsp;y) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;x.Cata(y,&nbsp;p&nbsp;=&gt;&nbsp;p.Increment()); }</pre> </p> <p> The trick here is to use <code>y</code> as the <code>zero</code> case for <code>x</code>. In other words, if <code>x</code> is <em>zero</em>, then <code>Add</code> should return <code>y</code>. If <code>x</code> isn't <em>zero</em>, then <code>Increment</code> it as many times as the number encodes, but starting at <code>y</code>. In other words, start with <code>y</code> and <code>Increment</code> <code>x</code> times. </p> <p> The catamorphism makes it much easier to implement arithmetic operation. Just consider multiplication, which wasn't the simplest implementation in the previous article. Now, it's as simple as this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">INaturalNumber</span>&nbsp;Multiply(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">INaturalNumber</span>&nbsp;x,&nbsp;<span style="color:#2b91af;">INaturalNumber</span>&nbsp;y) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;x.Cata(Zero,&nbsp;p&nbsp;=&gt;&nbsp;p.Add(y)); }</pre> </p> <p> Start at <code>0</code> and simply <code>Add(y)</code> <code>x</code> times. </p> <p> <pre>&gt; <span style="color:#2b91af;">NaturalNumber</span>.Nine.Multiply(<span style="color:#2b91af;">NaturalNumber</span>.Four).Count() 36</pre> </p> <p> Finally, you can also implement some common predicates: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IChurchBoolean</span>&nbsp;IsZero(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">INaturalNumber</span>&nbsp;n) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;n.Cata&lt;<span style="color:#2b91af;">IChurchBoolean</span>&gt;(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ChurchTrue</span>(),&nbsp;_&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ChurchFalse</span>()); } <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IChurchBoolean</span>&nbsp;IsEven(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">INaturalNumber</span>&nbsp;n) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;n.Cata&lt;<span style="color:#2b91af;">IChurchBoolean</span>&gt;(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ChurchTrue</span>(),&nbsp;b&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ChurchNot</span>(b)); } <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IChurchBoolean</span>&nbsp;IsOdd(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">INaturalNumber</span>&nbsp;n) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ChurchNot</span>(n.IsEven()); }</pre> </p> <p> Particularly <code>IsEven</code> is elegant: It considers <code>zero</code> even, so simply uses a <code>new ChurchTrue()</code> object for that case. In all other cases, it alternates between <em>false</em> and <em>true</em> by negating the predecessor. </p> <p> <pre>&gt; <span style="color:#2b91af;">NaturalNumber</span>.Three.IsEven().ToBool() false</pre> </p> <p> It seems convincing that we can use <code>Cata</code> to implement all the other functionality we need. That seems to be a characteristic of a catamorphism. Still, how do we know that <code>Cata</code> is, in fact, the catamorphism for natural numbers? </p> <h3 id="05dbca489b8a49be830df87e13bfcae3"> Peano F-Algebra <a href="#05dbca489b8a49be830df87e13bfcae3" title="permalink">#</a> </h3> <p> As in the <a href="/2019/05/06/boolean-catamorphism">previous article</a>, I'll use <code>Fix</code> and <code>cata</code> as explained in <a href="https://bartoszmilewski.com">Bartosz Milewski</a>'s excellent <a href="https://bartoszmilewski.com/2017/02/28/f-algebras/">article on F-Algebras</a>. The <code>NatF</code> type comes from his article as well: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;NatF&nbsp;a&nbsp;=&nbsp;ZeroF&nbsp;|&nbsp;SuccF&nbsp;a&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Read</span>) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;<span style="color:blue;">NatF</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;_&nbsp;ZeroF&nbsp;=&nbsp;ZeroF &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;f&nbsp;(SuccF&nbsp;x)&nbsp;=&nbsp;SuccF&nbsp;$&nbsp;f&nbsp;x</pre> </p> <p> You can use the fixed point of this functor to define numbers with a shared type. Here's just the first ten: </p> <p> <pre><span style="color:#2b91af;">zeroF</span>,&nbsp;<span style="color:#2b91af;">oneF</span>,&nbsp;<span style="color:#2b91af;">twoF</span>,&nbsp;<span style="color:#2b91af;">threeF</span>,&nbsp;<span style="color:#2b91af;">fourF</span>,&nbsp;<span style="color:#2b91af;">fiveF</span>,&nbsp;<span style="color:#2b91af;">sixF</span>,&nbsp;<span style="color:#2b91af;">sevenF</span>,&nbsp;<span style="color:#2b91af;">eightF</span>,&nbsp;<span style="color:#2b91af;">nineF</span>&nbsp;::&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span> zeroF&nbsp;&nbsp;=&nbsp;Fix&nbsp;ZeroF oneF&nbsp;&nbsp;&nbsp;=&nbsp;Fix&nbsp;$&nbsp;SuccF&nbsp;zeroF twoF&nbsp;&nbsp;&nbsp;=&nbsp;Fix&nbsp;$&nbsp;SuccF&nbsp;oneF threeF&nbsp;=&nbsp;Fix&nbsp;$&nbsp;SuccF&nbsp;twoF fourF&nbsp;&nbsp;=&nbsp;Fix&nbsp;$&nbsp;SuccF&nbsp;threeF fiveF&nbsp;&nbsp;=&nbsp;Fix&nbsp;$&nbsp;SuccF&nbsp;fourF sixF&nbsp;&nbsp;&nbsp;=&nbsp;Fix&nbsp;$&nbsp;SuccF&nbsp;fiveF sevenF&nbsp;=&nbsp;Fix&nbsp;$&nbsp;SuccF&nbsp;sixF eightF&nbsp;=&nbsp;Fix&nbsp;$&nbsp;SuccF&nbsp;sevenF nineF&nbsp;&nbsp;=&nbsp;Fix&nbsp;$&nbsp;SuccF&nbsp;eightF</pre> </p> <p> That's all you need to identify the catamorphism. </p> <h3 id="f0e66c873a034830a4b069229971299a"> Haskell catamorphism <a href="#f0e66c873a034830a4b069229971299a" title="permalink">#</a> </h3> <p> At this point, you have two out of three elements of an F-Algebra. You have an endofunctor (<code>NatF</code>), and an object <code>a</code>, but you still need to find a morphism <code>NatF a -&gt; a</code>. </p> <p> As in the previous article, start by writing a function that will become the catamorphism, based on <code>cata</code>: </p> <p> <pre>natF&nbsp;=&nbsp;cata&nbsp;alg &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;ZeroF&nbsp;=&nbsp;<span style="color:blue;">undefined</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(SuccF&nbsp;predecessor)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> While this compiles, with its <code>undefined</code> implementations, it obviously doesn't do anything useful. I find, however, that it helps me think. How can you return a value of the type <code>a</code> from the <code>ZeroF</code> case? You could pass an argument to the <code>natF</code> function: </p> <p> <pre>natF&nbsp;z&nbsp;=&nbsp;cata&nbsp;alg &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;ZeroF&nbsp;=&nbsp;z &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(SuccF&nbsp;predecessor)&nbsp;=&nbsp;<span style="color:blue;">undefined</span></pre> </p> <p> In the <code>SuccF</code> case, <code>predecessor</code> is already of the polymorphic type <code>a</code>, so instead of returning a constant value, you can supply a function as an argument to <code>natF</code> and use it in that case: </p> <p> <pre><span style="color:#2b91af;">natF</span>&nbsp;::&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;a)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;a natF&nbsp;z&nbsp;next&nbsp;=&nbsp;cata&nbsp;alg &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;ZeroF&nbsp;=&nbsp;z &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;(SuccF&nbsp;predecessor)&nbsp;=&nbsp;next&nbsp;predecessor</pre> </p> <p> This works. Since <code>cata</code> has the type <code>Functor f =&gt; (f a -&gt; a) -&gt; Fix f -&gt; a</code>, that means that <code>alg</code> has the type <code>f a -&gt; a</code>. In the case of <code>NatF</code>, the compiler infers that the <code>alg</code> function has the type <code>NatF a -&gt; a</code>, which is just what you need! </p> <p> For good measure, I should point out that, as usual, the above <code>natF</code> function isn't the only possible catamorphism. Trivially, you can flip the order of the arguments, and this would also be a catamorphism. These two alternatives are isomorphic. </p> <p> The <code>natF</code> function identifies the Peano number catamorphism, which is equivalent to the C# representation in the beginning of the article. I called the function <code>natF</code>, because there's a tendency in Haskell to name the 'case analysis' or catamorphism after the type, just with a lower-case initial letter. </p> <h3 id="e78ae79059e14f4b92f525393cc74861"> Basis <a href="#e78ae79059e14f4b92f525393cc74861" title="permalink">#</a> </h3> <p> A catamorphism can be used to implement most (if not all) other useful functionality, like all of the above C# functionality. In fact, I wrote the Haskell code first, and then translated my implementations into the above C# extension methods. This means that the following functions apply the same reasoning: </p> <p> <pre><span style="color:#2b91af;">evenF</span>&nbsp;::&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">BoolF</span> evenF&nbsp;=&nbsp;natF&nbsp;trueF&nbsp;notF <span style="color:#2b91af;">oddF</span>&nbsp;::&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">BoolF</span> oddF&nbsp;=&nbsp;notF&nbsp;.&nbsp;evenF <span style="color:#2b91af;">incF</span>&nbsp;::&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span> incF&nbsp;=&nbsp;natF&nbsp;oneF&nbsp;$&nbsp;Fix&nbsp;.&nbsp;SuccF <span style="color:#2b91af;">addF</span>&nbsp;::&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span> addF&nbsp;x&nbsp;y&nbsp;=&nbsp;natF&nbsp;y&nbsp;incF&nbsp;x <span style="color:#2b91af;">multiplyF</span>&nbsp;::&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span> multiplyF&nbsp;x&nbsp;y&nbsp;=&nbsp;natF&nbsp;zeroF&nbsp;(addF&nbsp;y)&nbsp;x</pre> </p> <p> Here are some GHCi usage examples: </p> <p> <pre>Prelude Boolean Nat&gt; evenF eightF Fix TrueF Prelude Boolean Nat&gt; toNum $ multiplyF sevenF sixF 42</pre> </p> <p> The <code>toNum</code> function corresponds to the above <code>Count</code> C# method. It is, again, based on <code>cata</code>. You can use <code>ana</code> to convert the other way: </p> <p> <pre><span style="color:#2b91af;">toNum</span>&nbsp;::&nbsp;<span style="color:blue;">Num</span>&nbsp;a&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;a toNum&nbsp;=&nbsp;natF&nbsp;0&nbsp;(+&nbsp;1) <span style="color:#2b91af;">fromNum</span>&nbsp;::&nbsp;(<span style="color:blue;">Eq</span>&nbsp;a,&nbsp;<span style="color:blue;">Num</span>&nbsp;a)&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Fix</span>&nbsp;<span style="color:blue;">NatF</span> fromNum&nbsp;=&nbsp;ana&nbsp;coalg &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;coalg&nbsp;0&nbsp;=&nbsp;ZeroF &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;coalg&nbsp;x&nbsp;=&nbsp;SuccF&nbsp;$&nbsp;x&nbsp;-&nbsp;1</pre> </p> <p> This demonstrates that <code>Fix NatF</code> is isomorphic to <code>Num</code> instances, such as <code>Integer</code>. </p> <h3 id="d09e79446af14875a42f66869e10f33a"> Summary <a href="#d09e79446af14875a42f66869e10f33a" title="permalink">#</a> </h3> <p> The catamorphism for Peano numbers is a pair consisting of a zero value and a successor function. The most common description of catamorphisms that I've found emphasise how a catamorphism is like a <em>fold;</em> an operation you can use to reduce a data structure like a list or a tree to a single value. This is what happens here, but even so, the <code>Fix NatF</code> type isn't a <code>Foldable</code> instance. The reason is that while <code>NatF</code> is a polymorphic type, its fixed point <code>Fix NatF</code> isn't. Haskell's <code>Foldable</code> type class requires foldable containers to be polymorphic (what C# programmers would call 'generic'). </p> <p> When I first ran into the concept of a <em>catamorphism</em>, it was invariably described as a 'generalisation of fold'. The examples shown were always how the catamorphism for linked list is the same as its <em>fold</em>. I found such explanations unhelpful, because I couldn't understand how those two concepts differ. </p> <p> The purpose with this article series is to show just how much more general the abstraction of a catamorphism is. In this article you saw how an infinitely recursive data structure like Peano numbers have a catamorphism, even though it isn't a parametrically polymorphic type. In the next article, though, you'll see the first example of a polymorphic type where the catamorphism coincides with the fold. </p> <p> <strong>Next:</strong> <a href="/2019/05/20/maybe-catamorphism">Maybe catamorphism</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/05/13/peano-catamorphism