ploeh blog https://blog.ploeh.dk danish software design en-us Mark Seemann Mon, 16 Sep 2019 13:23:58 UTC Mon, 16 Sep 2019 13:23:58 UTC Picture archivist in F# https://blog.ploeh.dk/2019/09/16/picture-archivist-in-f/ Mon, 16 Sep 2019 05:59:00 UTC <div id="post"> <p> <em>A comprehensive code example showing how to implement a functional architecture in F#.</em> </p> <p> This article shows how to implement the <a href="/2019/08/26/functional-file-system">picture archivist architecture described in a previous article</a>. In short, the task is to move some image files to directories based on their date-taken metadata. The architectural idea is to load a directory structure from disk into an in-memory tree, manipulate that tree, and use the resulting tree to perform the desired actions: </p> <p> <img src="/content/binary/functional-file-system-interaction.png" alt="A functional program typically loads data, transforms it, and stores it again."> </p> <p> Much of the program will manipulate the tree data, which is immutable. </p> <p> The previous article showed how to implement the <a href="/2019/09/09/picture-archivist-in-haskell">picture archivist architecture in Haskell</a>. In this article, you'll see how to do it in <a href="https://fsharp.org">F#</a>. This is essentially a port of the <a href="https://www.haskell.org">Haskell</a> code. </p> <h3 id="949a876ffec843e09d4faa5ae1c1b4c5"> Tree <a href="#949a876ffec843e09d4faa5ae1c1b4c5" title="permalink">#</a> </h3> <p> You can start by defining a <a href="https://en.wikipedia.org/wiki/Rose_tree">rose tree</a>: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;Tree&lt;&#39;a,&nbsp;&#39;b&gt;&nbsp;=&nbsp;Node&nbsp;<span style="color:blue;">of</span>&nbsp;&#39;a&nbsp;*&nbsp;Tree&lt;&#39;a,&nbsp;&#39;b&gt;&nbsp;list&nbsp;|&nbsp;Leaf&nbsp;<span style="color:blue;">of</span>&nbsp;&#39;b</pre> </p> <p> If you wanted to, you could put all the <code>Tree</code> code in a reusable library, because none of it is coupled to a particular application, such as <a href="https://amzn.to/2V06Kji">moving pictures</a>. You could also write a comprehensive test suite for the following functions, but in this article, I'll skip that. </p> <p> Notice that this sort of tree explicitly distinguishes between internal and leaf nodes. This is necessary because you'll need to keep track of the directory names (the internal nodes), while at the same time you'll want to enrich the leaves with additional data - data that you can't meaningfully add to the internal nodes. You'll see this later in the article. </p> <p> While I typically tend to define F# types outside of modules (so that you don't have to, say, prefix the type name with the module name - <code>Tree.Tree</code> is so awkward), the rest of the tree code goes into a module, including two helper functions: </p> <p> <pre><span style="color:blue;">module</span>&nbsp;Tree&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;&#39;b&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;leaf&nbsp;=&nbsp;Leaf &nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;&#39;a&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;list&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;node&nbsp;x&nbsp;xs&nbsp;=&nbsp;Node&nbsp;(x,&nbsp;xs)</pre> </p> <p> The <code>leaf</code> function doesn't add much value, but the <code>node</code> function offers a curried alternative to the <code>Node</code> case constructor. That's occasionally useful. </p> <p> The rest of the code related to trees is also defined in the <code>Tree</code> module, but I'm going to present it formatted as free-standing functions. If you're confused about the layout of the code, the entire code base is <a href="https://github.com/ploeh/picture-archivist">available on GitHub</a>. </p> <p> The <a href="/2019/08/05/rose-tree-catamorphism">rose tree catamorphism</a> is this <code>cata</code> function: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;c&nbsp;list&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;(&#39;b&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;&#39;c</span> <span style="color:blue;">let</span>&nbsp;<span style="color:blue;">rec</span>&nbsp;cata&nbsp;fd&nbsp;ff&nbsp;=&nbsp;<span style="color:blue;">function</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;Leaf&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;ff&nbsp;x &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;Node&nbsp;(x,&nbsp;xs)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;xs&nbsp;|&gt;&nbsp;List.map&nbsp;(cata&nbsp;fd&nbsp;ff)&nbsp;|&gt;&nbsp;fd&nbsp;x</pre> </p> <p> In the corresponding Haskell implementation of this architecture, I called this function <code>foldTree</code>, so why not retain that name? The short answer is that the naming conventions differ between Haskell and F#, and while I favour learning from Haskell, I still want my F# code to be as <a href="/2015/08/03/idiomatic-or-idiosyncratic">idiomatic</a> as possible. </p> <p> While I don't enforce that client code <em>must</em> use the <code>Tree</code> module name to access the functions within, I prefer to name the functions so that they make sense when used with qualified access. Having to write <code>Tree.foldTree</code> seems redundant. A more idiomatic name would be <code>fold</code>, so that you could write <code>Tree.fold</code>. The problem with that name, though, is that <code>fold</code> usually implies a list-biased <em>fold</em> (corresponding to <code>foldl</code> in Haskell), and I'll actually need that name for that particular purpose later. </p> <p> So, <code>cata</code> it is. </p> <p> In this article, tree functionality is (with one exception) directly or transitively implemented with <code>cata</code>. </p> <h3 id="3f30722983ad47bd83c88cec4ba80983"> Filtering trees <a href="#3f30722983ad47bd83c88cec4ba80983" title="permalink">#</a> </h3> <p> It'll be useful to be able to filter the contents of a tree. For example, the picture archivist program will only move image files with valid metadata. This means that it'll need to filter out all files that aren't image files, as well as image files without valid metadata. </p> <p> It turns out that it'll be useful to supply a function that throws away <code>None</code> values from a tree of <code>option</code> leaves. This is similar to <a href="https://msdn.microsoft.com/en-us/visualfsharpdocs/conceptual/list.choose%5B't%2C'u%5D-function-%5Bfsharp%5D">List.choose</a>, so I call it <code>Tree.choose</code>: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b&nbsp;option)&nbsp;-&gt;&nbsp;Tree&lt;&#39;c,&#39;a&gt;&nbsp;-&gt;&nbsp;Tree&lt;&#39;c,&#39;b&gt;&nbsp;option</span> <span style="color:blue;">let</span>&nbsp;choose&nbsp;f&nbsp;=&nbsp;cata&nbsp;(<span style="color:blue;">fun</span>&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;List.choose&nbsp;id&nbsp;&gt;&gt;&nbsp;node&nbsp;x&nbsp;&gt;&gt;&nbsp;Some)&nbsp;(f&nbsp;&gt;&gt;&nbsp;Option.map&nbsp;Leaf)</pre> </p> <p> You may find the type of the function surprising. Why does it return a <code>Tree option</code>, instead of simply a <code>Tree</code>? </p> <p> While <code>List.choose</code> simply returns a list, it can do this because lists can be empty. This <code>Tree</code> type, on the other hand, can't be empty. If the purpose of <code>Tree.choose</code> is to throw away all <code>None</code> values, then how do you return a tree from <code>Leaf None</code>? </p> <p> You can't return a <code>Leaf</code> because you have no value to put in the leaf. Similarly, you can't return a <code>Node</code> because, again, you have no value to put in the node. </p> <p> In order to handle this edge case, then, you'll have to return <code>None</code>: </p> <p> <pre>&gt; let l : Tree&lt;string, int option&gt; = Leaf None;; val l : Tree&lt;string,int option&gt; = Leaf None &gt; Tree.choose id l;; val it : Tree&lt;string,int&gt; option = None</pre> </p> <p> If you have anything other than a <code>None</code> leaf, though, you'll get a proper tree, but wrapped in an <code>option</code>: </p> <p> <pre>&gt; Tree.node "Foo" [Leaf (Some 42); Leaf None; Leaf (Some 2112)] |&gt; Tree.choose id;; val it : Tree&lt;string,int&gt; option = Some (Node ("Foo",[Leaf 42; Leaf 2112]))</pre> </p> <p> While the resulting tree is wrapped in a <code>Some</code> case, the leaves contain unwrapped values. </p> <h3 id="32f46f2c16cf428abc39c3d79433caa6"> Bifunctor, functor, and folds <a href="#32f46f2c16cf428abc39c3d79433caa6" title="permalink">#</a> </h3> <p> Through its type class language feature, Haskell has formal definitions of <a href="/2018/03/22/functors">functors</a>, <a href="/2018/12/24/bifunctors">bifunctors</a>, and other types of <em>folds</em> (list-biased <a href="/2019/04/29/catamorphisms">catamorphisms</a>). F# doesn't have a similar degree of formalism, which means that while you can still implement the corresponding functionality, you'll have to rely on conventions to make the functions recognisable. </p> <p> It's straighforward to start with the bifunctor functionality: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b)&nbsp;-&gt;&nbsp;(&#39;c&nbsp;-&gt;&nbsp;&#39;d)&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;c&gt;&nbsp;-&gt;&nbsp;Tree&lt;&#39;b,&#39;d&gt;</span> <span style="color:blue;">let</span>&nbsp;bimap&nbsp;f&nbsp;g&nbsp;=&nbsp;cata&nbsp;(f&nbsp;&gt;&gt;&nbsp;node)&nbsp;(g&nbsp;&gt;&gt;&nbsp;leaf)</pre> </p> <p> This is, apart from the syntax differences, the same implementation as in Haskell. Based on <code>bimap</code>, you can also trivially implement <code>mapNode</code> and <code>mapLeaf</code> functions if you'd like, but you're not going to need those for the code in this article. You do need, however, a function that we could consider an alias of a hypothetical <code>mapLeaf</code> function: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;b&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;c&gt;</span> <span style="color:blue;">let</span>&nbsp;map&nbsp;f&nbsp;=&nbsp;bimap&nbsp;id&nbsp;f</pre> </p> <p> This makes <code>Tree</code> a functor. </p> <p> It'll also be useful to reduce a tree to a potentially more compact value, so you can add some specialised folds: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;c&nbsp;-&gt;&nbsp;&#39;a&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;(&#39;c&nbsp;-&gt;&nbsp;&#39;b&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;&#39;c</span> <span style="color:blue;">let</span>&nbsp;bifold&nbsp;f&nbsp;g&nbsp;z&nbsp;t&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;flip&nbsp;f&nbsp;x&nbsp;y&nbsp;=&nbsp;f&nbsp;y&nbsp;x &nbsp;&nbsp;&nbsp;&nbsp;cata&nbsp;(<span style="color:blue;">fun</span>&nbsp;x&nbsp;xs&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;flip&nbsp;f&nbsp;x&nbsp;&gt;&gt;&nbsp;List.fold&nbsp;(&gt;&gt;)&nbsp;id&nbsp;xs)&nbsp;(flip&nbsp;g)&nbsp;t&nbsp;z <span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;(&#39;b&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;&#39;c</span> <span style="color:blue;">let</span>&nbsp;bifoldBack&nbsp;f&nbsp;g&nbsp;t&nbsp;z&nbsp;=&nbsp;cata&nbsp;(<span style="color:blue;">fun</span>&nbsp;x&nbsp;xs&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;List.foldBack&nbsp;(&lt;&lt;)&nbsp;xs&nbsp;id&nbsp;&gt;&gt;&nbsp;f&nbsp;x)&nbsp;g&nbsp;t&nbsp;z</pre> </p> <p> In an attempt to emulate the F# naming conventions, I named the functions as I did. There are similar functions in the <code>List</code> and <code>Option</code> modules, for instance. If you're comparing the F# code with the Haskell code in the previous article, <code>Tree.bifold</code> corresponds to <code>bifoldl</code>, and <code>Tree.bifoldBack</code> corresponds to <code>bifoldr</code>. </p> <p> These enable you to implement folds over leaves only: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;c&nbsp;-&gt;&nbsp;&#39;b&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;&#39;c</span> <span style="color:blue;">let</span>&nbsp;fold&nbsp;f&nbsp;=&nbsp;bifold&nbsp;(<span style="color:blue;">fun</span>&nbsp;x&nbsp;_&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;x)&nbsp;f <span style="color:green;">//&nbsp;(&#39;b&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;&#39;c</span> <span style="color:blue;">let</span>&nbsp;foldBack&nbsp;f&nbsp;=&nbsp;bifoldBack&nbsp;(<span style="color:blue;">fun</span>&nbsp;_&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;x)&nbsp;f</pre> </p> <p> These, again, enable you to implement another function that'll turn out to be useful in this article: </p> <p> <pre><span style="color:green;">//&nbsp;(&#39;b&nbsp;-&gt;&nbsp;unit)&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,&#39;b&gt;&nbsp;-&gt;&nbsp;unit</span> <span style="color:blue;">let</span>&nbsp;iter&nbsp;f&nbsp;=&nbsp;fold&nbsp;(<span style="color:blue;">fun</span>&nbsp;()&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;f&nbsp;x)&nbsp;()</pre> </p> <p> The picture archivist program isn't going to explicitly need all of these, but transitively, it will. </p> <h3 id="8a9a50c69a2d461cac5bb87fa4cf3cd9"> Moving pictures <a href="#8a9a50c69a2d461cac5bb87fa4cf3cd9" title="permalink">#</a> </h3> <p> So far, all the code shown here could be in a general-purpose reusable library, since it contains no functionality specifically related to image files. The rest of the code in this article, however, will be specific to the program. I'll put the domain model code in another module that I call <code>Archive</code>. Later in the article, we'll look at how to load a tree from the file system, but for now, we'll just pretend that we have such a tree. </p> <p> The major logic of the program is to create a destination tree based on a source tree. The leaves of the tree will have to carry some extra information apart from a file path, so you can introduce a specific type to capture that information: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;PhotoFile&nbsp;=&nbsp;{&nbsp;File&nbsp;:&nbsp;FileInfo;&nbsp;TakenOn&nbsp;:&nbsp;DateTime&nbsp;}</pre> </p> <p> A <code>PhotoFile</code> not only contains the file path for an image file, but also the date the photo was taken. This date can be extracted from the file's metadata, but that's an impure operation, so we'll delegate that work to the start of the program. We'll return to that later. </p> <p> Given a source tree of <code>PhotoFile</code> leaves, though, the program must produce a destination tree of files: </p> <p> <pre><span style="color:green;">//&nbsp;string&nbsp;-&gt;&nbsp;Tree&lt;&#39;a,PhotoFile&gt;&nbsp;-&gt;&nbsp;Tree&lt;string,FileInfo&gt;</span> <span style="color:blue;">let</span>&nbsp;moveTo&nbsp;destination&nbsp;t&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;dirNameOf&nbsp;(dt&nbsp;:&nbsp;DateTime)&nbsp;=&nbsp;sprintf&nbsp;<span style="color:#a31515;">&quot;%d-%02d&quot;</span>&nbsp;dt.Year&nbsp;dt.Month &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;groupByDir&nbsp;pf&nbsp;m&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;key&nbsp;=&nbsp;dirNameOf&nbsp;pf.TakenOn &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;dir&nbsp;=&nbsp;Map.tryFind&nbsp;key&nbsp;m&nbsp;|&gt;&nbsp;Option.defaultValue&nbsp;[] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Map.add&nbsp;key&nbsp;(pf.File&nbsp;::&nbsp;dir)&nbsp;m &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;addDir&nbsp;name&nbsp;files&nbsp;dirs&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Tree.node&nbsp;name&nbsp;(List.map&nbsp;Leaf&nbsp;files)&nbsp;::&nbsp;dirs &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;m&nbsp;=&nbsp;Tree.foldBack&nbsp;groupByDir&nbsp;t&nbsp;Map.empty &nbsp;&nbsp;&nbsp;&nbsp;Map.foldBack&nbsp;addDir&nbsp;m&nbsp;[]&nbsp;|&gt;&nbsp;Tree.node&nbsp;destination</pre> </p> <p> This <code>moveTo</code> function looks, perhaps, overwhelming, but it's composed of three conceptual steps: <ol> <li>Create a map of destination folders (<code>m</code>).</li> <li>Create a list of branches from the map (<code>Map.foldBack addDir m []</code>).</li> <li>Create a tree from the list (<code>Tree.node destination</code>).</li> </ol> The <code>moveTo</code> function starts by folding the input data into a map <code>m</code>. The map is keyed by the directory name, which is formatted by the <code>dirNameOf</code> function. This function takes a <code>DateTime</code> as input and formats it to a <code>YYYY-MM</code> format. For example, December 20, 2018 becomes <code>"2018-12"</code>. </p> <p> The entire mapping step groups the <code>PhotoFile</code> values into a map of the type <code>Map&lt;string,FileInfo list&gt;</code>. All the image files taken in April 2014 are added to the list with the <code>"2014-04"</code> key, all the image files taken in July 2011 are added to the list with the <code>"2011-07"</code> key, and so on. </p> <p> In the next step, the <code>moveTo</code> function converts the map to a list of trees. This will be the branches (or sub-directories) of the <code>destination</code> directory. Because of the desired structure of the destination tree, this is a list of shallow branches. Each node contains only leaves. </p> <p> <img src="/content/binary/shallow-photo-destination-directories.png" alt="Shallow photo destination directories."> </p> <p> The only remaining step is to add that list of branches to a <code>destination</code> node. This is done by piping (<code>|&gt;</code>) the list of sub-directories into <code>Tree.node destination</code>. </p> <p> Since this is a <a href="https://en.wikipedia.org/wiki/Pure_function">pure function</a>, it's <a href="/2015/05/07/functional-design-is-intrinsically-testable">easy to unit test</a>. Just create some test cases and call the function. First, the test cases. </p> <p> In this code base, I'm using <a href="https://xunit.github.io">xUnit.net</a> 2.4.1, so I'll first create a set of test cases as a test-specific class: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;MoveToDestinationTestData&nbsp;()&nbsp;<span style="color:blue;">as</span>&nbsp;this&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">inherit</span>&nbsp;TheoryData&lt;Tree&lt;string,&nbsp;PhotoFile&gt;,&nbsp;string,&nbsp;Tree&lt;string,&nbsp;string&gt;&gt;&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;photoLeaf&nbsp;name&nbsp;(y,&nbsp;mth,&nbsp;d,&nbsp;h,&nbsp;m,&nbsp;s)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;{&nbsp;File&nbsp;=&nbsp;FileInfo&nbsp;name;&nbsp;TakenOn&nbsp;=&nbsp;DateTime&nbsp;(y,&nbsp;mth,&nbsp;d,&nbsp;h,&nbsp;m,&nbsp;s)&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;(2018,&nbsp;11,&nbsp;9,&nbsp;11,&nbsp;47,&nbsp;17), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>,&nbsp;[Node&nbsp;(<span style="color:#a31515;">&quot;2018-11&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>])])) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;S&quot;</span>,&nbsp;[photoLeaf&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>&nbsp;(1972,&nbsp;6,&nbsp;6,&nbsp;16,&nbsp;15,&nbsp;0)]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;D&quot;</span>,&nbsp;[Node&nbsp;(<span style="color:#a31515;">&quot;1972-06&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>])])) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;S&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;L&quot;</span>&nbsp;(2002,&nbsp;10,&nbsp;12,&nbsp;17,&nbsp;16,&nbsp;15); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;J&quot;</span>&nbsp;(2007,&nbsp;4,&nbsp;21,&nbsp;17,&nbsp;18,&nbsp;19)]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;D&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2002-10&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;L&quot;</span>]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2007-04&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;J&quot;</span>])])) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;(2010,&nbsp;1,&nbsp;12,&nbsp;17,&nbsp;16,&nbsp;15); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;(2010,&nbsp;3,&nbsp;12,&nbsp;17,&nbsp;16,&nbsp;15); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>&nbsp;(2010,&nbsp;1,&nbsp;21,&nbsp;17,&nbsp;18,&nbsp;19)]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2010-01&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>;&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2010-03&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>])])) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;bar&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;(2010,&nbsp;1,&nbsp;12,&nbsp;17,&nbsp;16,&nbsp;15); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;(2010,&nbsp;3,&nbsp;12,&nbsp;17,&nbsp;16,&nbsp;15); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>&nbsp;(2010,&nbsp;1,&nbsp;21,&nbsp;17,&nbsp;18,&nbsp;19)]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;baz&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;d&quot;</span>&nbsp;(2010,&nbsp;3,&nbsp;1,&nbsp;2,&nbsp;3,&nbsp;4); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;photoLeaf&nbsp;<span style="color:#a31515;">&quot;e&quot;</span>&nbsp;(2011,&nbsp;3,&nbsp;4,&nbsp;3,&nbsp;2,&nbsp;1)])]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#a31515;">&quot;qux&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;qux&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2010-01&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>;&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2010-03&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>;&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;d&quot;</span>]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;2011-03&quot;</span>,&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;e&quot;</span>])]))</pre> </p> <p> That looks like a lot of code, but is really just a list of test cases. Each test case is a triple of a source tree, a destination directory name, and an expected result (another tree). </p> <p> The test itself, on the other hand, is compact: </p> <p> <pre>[&lt;Theory;&nbsp;ClassData(typeof&lt;MoveToDestinationTestData&gt;)&gt;] <span style="color:blue;">let</span>&nbsp;Move&nbsp;to&nbsp;destination&nbsp;source&nbsp;destination&nbsp;expected&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;Archive.moveTo&nbsp;destination&nbsp;source &nbsp;&nbsp;&nbsp;&nbsp;expected&nbsp;=!&nbsp;Tree.map&nbsp;string&nbsp;actual</pre> </p> <p> The <code>=!</code> operator comes from <a href="https://github.com/SwensenSoftware/unquote">Unquote</a> and means something like <em>must equal</em>. It's an assertion that will throw an exception if <code>expected</code> isn't equal to <code>Tree.map string actual</code>. </p> <p> The reason that the assertion maps <code>actual</code> to a tree of strings is that <code>actual</code> is a <code>Tree&lt;string,FileInfo&gt;</code>, but <code>FileInfo</code> doesn't have structural equality. So either I had to implement a test-specific equality comparer for <code>FileInfo</code> (and for <code>Tree&lt;string,FileInfo&gt;</code>), or map the tree to something with proper equality, such as a <code>string</code>. I chose the latter. </p> <h3 id="abe95ba6865745bc9df8004079d8a250"> Calculating moves <a href="#abe95ba6865745bc9df8004079d8a250" title="permalink">#</a> </h3> <p> One pure step remains. The result of calling the <code>moveTo</code> function is a tree with the desired structure. In order to actually move the files, though, for each file you'll need to keep track of both the source path and the destination path. To make that explicit, you can define a type for that purpose: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;Move&nbsp;=&nbsp;{&nbsp;Source&nbsp;:&nbsp;FileInfo;&nbsp;Destination&nbsp;:&nbsp;FileInfo&nbsp;}</pre> </p> <p> A <code>Move</code> is simply a data structure. Contrast this with typical object-oriented design, where it would be a (possibly polymorphic) method on an object. In functional programming, you'll regularly model <em>intent</em> with a data structure. As long as intents remain data, you can easily manipulate them, and once you're done with that, you can run an interpreter over your data structure to perform the work you want accomplished. </p> <p> The unit test cases for the <code>moveTo</code> function suggest that file names are local file names like <code>"L"</code>, <code>"J"</code>, <code>"a"</code>, and so on. That was only to make the tests as compact as possible, since the function actually doesn't manipulate the specific <code>FileInfo</code> objects. </p> <p> In reality, the file names will most likely be longer, and they could also contain the full path, instead of the local path: <code>"C:\foo\bar\a.jpg"</code>. </p> <p> If you call <code>moveTo</code> with a tree where each leaf has a fully qualified path, the output tree will have the desired structure of the destination tree, but the leaves will still contain the full path to each source file. That means that you can calculate a <code>Move</code> for each file: </p> <p> <pre><span style="color:green;">//&nbsp;Tree&lt;string,FileInfo&gt;&nbsp;-&gt;&nbsp;Tree&lt;string,Move&gt;</span> <span style="color:blue;">let</span>&nbsp;calculateMoves&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;replaceDirectory&nbsp;(f&nbsp;:&nbsp;FileInfo)&nbsp;d&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;FileInfo&nbsp;(Path.Combine&nbsp;(d,&nbsp;f.Name)) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:blue;">rec</span>&nbsp;imp&nbsp;path&nbsp;=&nbsp;<span style="color:blue;">function</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;Leaf&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;{&nbsp;Source&nbsp;=&nbsp;x;&nbsp;Destination&nbsp;=&nbsp;replaceDirectory&nbsp;x&nbsp;path&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;Node&nbsp;(x,&nbsp;xs)&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;newNPath&nbsp;=&nbsp;Path.Combine&nbsp;(path,&nbsp;x) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Tree.node&nbsp;newNPath&nbsp;(List.map&nbsp;(imp&nbsp;newNPath)&nbsp;xs) &nbsp;&nbsp;&nbsp;&nbsp;imp&nbsp;<span style="color:#a31515;">&quot;&quot;</span></pre> </p> <p> This function takes as input a <code>Tree&lt;string,FileInfo&gt;</code>, which is compatible with the output of <code>moveTo</code>. It returns a <code>Tree&lt;string,Move&gt;</code>, i.e. a tree where the leaves are <code>Move</code> values. </p> <p> Earlier, I wrote that you can implement desired <code>Tree</code> functionality with the <code>cata</code> function, but that was a simplification. If you can implement the functionality of <code>calculateMoves</code> with <code>cata</code>, I don't know how. You can, however, implement it using explicit pattern matching and simple recursion. </p> <p> The <code>imp</code> function builds up a file path as it recursively negotiates the tree. All <code>Leaf</code> nodes are converted to a <code>Move</code> value using the leaf node's current <code>FileInfo</code> value as the <code>Source</code>, and the <code>path</code> to figure out the desired <code>Destination</code>. </p> <p> This code is still easy to unit test. First, test cases: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;CalculateMovesTestData&nbsp;()&nbsp;<span style="color:blue;">as</span>&nbsp;this&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">inherit</span>&nbsp;TheoryData&lt;Tree&lt;string,&nbsp;FileInfo&gt;,&nbsp;Tree&lt;string,&nbsp;(string&nbsp;*&nbsp;string)&gt;&gt;&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;(Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>),&nbsp;Leaf&nbsp;(<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>)) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;[Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>)]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;[Leaf&nbsp;(<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>))])) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;[Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>);&nbsp;Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>)]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(<span style="color:#a31515;">&quot;2&quot;</span>,&nbsp;Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>))])) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do</span>&nbsp;this.Add&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;b&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>)]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;c&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(FileInfo&nbsp;<span style="color:#a31515;">&quot;3&quot;</span>)])]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>),&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(<span style="color:#a31515;">&quot;2&quot;</span>,&nbsp;Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>))]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>),&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;(<span style="color:#a31515;">&quot;3&quot;</span>,&nbsp;Path.Combine&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;3&quot;</span>))])]))</pre> </p> <p> The test cases in this parametrised test are tuples of an input tree and the expected tree. For each test case, the test calls the <code>Archive.calculateMoves</code> function with <code>tree</code> and asserts that the <code>actual</code> tree is equal to the <code>expected</code> tree: </p> <p> <pre>[&lt;Theory;&nbsp;ClassData(typeof&lt;CalculateMovesTestData&gt;)&gt;] <span style="color:blue;">let</span>&nbsp;Calculate&nbsp;moves&nbsp;tree&nbsp;expected&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;Archive.calculateMoves&nbsp;tree &nbsp;&nbsp;&nbsp;&nbsp;expected&nbsp;=!&nbsp;Tree.map&nbsp;(<span style="color:blue;">fun</span>&nbsp;m&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(m.Source.ToString&nbsp;(),&nbsp;m.Destination.ToString&nbsp;()))&nbsp;actual</pre> </p> <p> Again, the test maps <code>FileInfo</code> objects to <code>strings</code> to support easy comparison. </p> <p> That's all the pure code you need in order to implement the desired functionality. Now you only need to write some code that loads a tree from disk, and imprints a destination tree to disk, as well as the code that composes it all. </p> <h3 id="bac6be79cf8c44a7b47923e2ec90d99f"> Loading a tree from disk <a href="#bac6be79cf8c44a7b47923e2ec90d99f" title="permalink">#</a> </h3> <p> The remaining code in this article is impure. You could put it in dedicated modules, but for this program, you're only going to need three functions and a bit of composition code, so you could also just put it all in the <code>Program</code> module. That's what I did. </p> <p> To load a tree from disk, you'll need a root directory, under which you load the entire tree. Given a directory path, you read a tree using a recursive function like this: </p> <p> <pre><span style="color:green;">//&nbsp;string&nbsp;-&gt;&nbsp;Tree&lt;string,string&gt;</span> <span style="color:blue;">let</span>&nbsp;<span style="color:blue;">rec</span>&nbsp;readTree&nbsp;path&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;File.Exists&nbsp;path &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">then</span>&nbsp;Leaf&nbsp;path &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;dirsAndFiles&nbsp;=&nbsp;Directory.EnumerateFileSystemEntries&nbsp;path &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;branches&nbsp;=&nbsp;Seq.map&nbsp;readTree&nbsp;dirsAndFiles&nbsp;|&gt;&nbsp;Seq.toList &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(path,&nbsp;branches)</pre> </p> <p> This recursive function starts by checking whether the <code>path</code> is a file that exists. If it does, the path is a file, so it creates a new <code>Leaf</code> with that path. </p> <p> If <code>path</code> isn't a file, it's a directory. In that case, use <code>Directory.EnumerateFileSystemEntries</code> to enumerate all the directories and files in that directory, and map all those directory entries recursively. That produces all the <code>branches</code> for the current node. Finally, return a new <code>Node</code> with the <code>path</code> and the <code>branches</code>. </p> <h3 id="7f5e06eb61024264ad214d41b63a8a74"> Loading metadata <a href="#7f5e06eb61024264ad214d41b63a8a74" title="permalink">#</a> </h3> <p> The <code>readTree</code> function only produces a tree with <code>string</code> leaves, while the program requires a tree with <code>PhotoFile</code> leaves. You'll need to read the <a href="https://en.wikipedia.org/wiki/Exif">Exif</a> metadata from each file and enrich the tree with the <em>date-taken</em> data. </p> <p> In this code base, I've written a little <code>Photo</code> module to extract the desired metadata from an image file. I'm not going to list all the code here; if you're interested, the code is <a href="https://github.com/ploeh/picture-archivist">available on GitHub</a>. The <code>Photo</code> module enables you to write an impure operation like this: </p> <p> <pre><span style="color:green;">//&nbsp;FileInfo&nbsp;-&gt;&nbsp;PhotoFile&nbsp;option</span> <span style="color:blue;">let</span>&nbsp;readPhoto&nbsp;file&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;Photo.extractDateTaken&nbsp;file &nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;Option.map&nbsp;(<span style="color:blue;">fun</span>&nbsp;dateTaken&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;{&nbsp;File&nbsp;=&nbsp;file;&nbsp;TakenOn&nbsp;=&nbsp;dateTaken&nbsp;})</pre> </p> <p> This operation can fail for various reasons: <ul> <li>The file may not exist.</li> <li>The file exists, but has no metadata.</li> <li>The file has metadata, but no <em>date-taken</em> metadata.</li> <li>The <em>date-taken</em> metadata string is malformed.</li> </ul> When you traverse a <code>Tree&lt;string,string&gt;</code> with <code>readPhoto</code>, you'll get a <code>Tree&lt;string,PhotoFile option&gt;</code>. That's when you'll need <code>Tree.choose</code>. You'll see this soon. </p> <h3 id="59159ef499884e10ae92e5ef6e666c36"> Writing a tree to disk <a href="#59159ef499884e10ae92e5ef6e666c36" title="permalink">#</a> </h3> <p> The above <code>calculateMoves</code> function creates a <code>Tree&lt;string,Move&gt;</code>. The final piece of impure code you'll need to write is an operation that traverses such a tree and executes each <code>Move</code>. </p> <p> <pre><span style="color:green;">//&nbsp;Tree&lt;&#39;a,Move&gt;&nbsp;-&gt;&nbsp;unit</span> <span style="color:blue;">let</span>&nbsp;writeTree&nbsp;t&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;copy&nbsp;m&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Directory.CreateDirectory&nbsp;m.Destination.DirectoryName&nbsp;|&gt;&nbsp;ignore &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m.Source.CopyTo&nbsp;m.Destination.FullName&nbsp;|&gt;&nbsp;ignore &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printfn&nbsp;<span style="color:#a31515;">&quot;Copied&nbsp;to&nbsp;%s&quot;</span>&nbsp;m.Destination.FullName &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;compareFiles&nbsp;m&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;sourceStream&nbsp;=&nbsp;File.ReadAllBytes&nbsp;m.Source.FullName &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;destinationStream&nbsp;=&nbsp;File.ReadAllBytes&nbsp;m.Destination.FullName &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sourceStream&nbsp;=&nbsp;destinationStream &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;move&nbsp;m&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;copy&nbsp;m &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;compareFiles&nbsp;m&nbsp;<span style="color:blue;">then</span>&nbsp;m.Source.Delete&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;Tree.iter&nbsp;move&nbsp;t</pre> </p> <p> The <code>writeTree</code> function traverses the input tree, and for each <code>Move</code>, it first copies the file, then it verifies that the copy was successful, and finally, if that's the case, it deletes the source file. </p> <h3 id="f30093164b184bbf877f307fa4cf4c63"> Composition <a href="#f30093164b184bbf877f307fa4cf4c63" title="permalink">#</a> </h3> <p> You can now compose an <em>impure-pure-impure sandwich</em> from all the Lego pieces: </p> <p> <pre><span style="color:green;">//&nbsp;string&nbsp;-&gt;&nbsp;string&nbsp;-&gt;&nbsp;unit</span> <span style="color:blue;">let</span>&nbsp;movePhotos&nbsp;source&nbsp;destination&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;sourceTree&nbsp;=&nbsp;readTree&nbsp;source&nbsp;|&gt;&nbsp;Tree.map&nbsp;FileInfo &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;photoTree&nbsp;=&nbsp;Tree.choose&nbsp;readPhoto&nbsp;sourceTree &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;destinationTree&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Option.map&nbsp;(Archive.moveTo&nbsp;destination&nbsp;&gt;&gt;&nbsp;Archive.calculateMoves)&nbsp;photoTree &nbsp;&nbsp;&nbsp;&nbsp;Option.iter&nbsp;writeTree&nbsp;destinationTree</pre> </p> <p> First, you load the <code>sourceTree</code> using the <code>readTree</code> operation. This returns a <code>Tree&lt;string,string&gt;</code>, so map the leaves to <code>FileInfo</code> objects. You then load the image metatadata by traversing <code>sourceTree</code> with <code>Tree.choose readPhoto</code>. Each call to <code>readPhoto</code> produces a <code>PhotoFile option</code>, so this is where you want to use <code>Tree.choose</code> to throw all the <code>None</code> values away. </p> <p> Those two lines of code is the initial impure step of the sandwich (yes: mixed metaphors, I know). </p> <p> The pure part of the sandwich is the composition of the pure functions <code>moveTo</code> and <code>calculateMoves</code>. Since <code>photoTree</code> is a <code>Tree&lt;string,PhotoFile&gt; option</code>, you'll need to perform that transformation inside of <code>Option.map</code>. The resulting <code>destinationTree</code> is a <code>Tree&lt;string,Move&gt; option</code>. </p> <p> The final, impure step of the sandwich, then, is to apply all the moves with <code>writeTree</code>. </p> <h3 id="ab0013f79c184586a10aa014db496bef"> Execution <a href="#ab0013f79c184586a10aa014db496bef" title="permalink">#</a> </h3> <p> The <code>movePhotos</code> operation takes <code>source</code> and <code>destination</code> arguments. You could hypothetically call it from a rich client or a background process, but here I'll just call if from a command-line program. The <code>main</code> operation will have to parse the input arguments and call <code>movePhotos</code>: </p> <p> <pre>[&lt;EntryPoint&gt;] <span style="color:blue;">let</span>&nbsp;main&nbsp;argv&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">match</span>&nbsp;argv&nbsp;<span style="color:blue;">with</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;[|source;&nbsp;destination|]&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;movePhotos&nbsp;source&nbsp;destination &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;_&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;printfn&nbsp;<span style="color:#a31515;">&quot;Please&nbsp;provide&nbsp;source&nbsp;and&nbsp;destination&nbsp;directories&nbsp;as&nbsp;arguments.&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;0&nbsp;<span style="color:green;">//&nbsp;return&nbsp;an&nbsp;integer&nbsp;exit&nbsp;code</span></pre> </p> <p> You could write more sophisticated parsing of the program arguments, but that's not the topic of this article, so I only wrote the bare minimum required to get the program working. </p> <p> You can now compile and run the program: </p> <p> <pre>$./ArchivePictures "C:\Users\mark\Desktop\Test" "C:\Users\mark\Desktop\Test-Out" Copied to C:\Users\mark\Desktop\Test-Out\2003-04\2003-04-29 15.11.50.jpg Copied to C:\Users\mark\Desktop\Test-Out\2011-07\2011-07-10 13.09.36.jpg Copied to C:\Users\mark\Desktop\Test-Out\2014-04\2014-04-18 14.05.02.jpg Copied to C:\Users\mark\Desktop\Test-Out\2014-04\2014-04-17 17.11.40.jpg Copied to C:\Users\mark\Desktop\Test-Out\2014-05\2014-05-23 16.07.20.jpg Copied to C:\Users\mark\Desktop\Test-Out\2014-06\2014-06-21 16.48.40.jpg Copied to C:\Users\mark\Desktop\Test-Out\2014-06\2014-06-30 15.44.52.jpg Copied to C:\Users\mark\Desktop\Test-Out\2016-05\2016-05-01 09.25.23.jpg Copied to C:\Users\mark\Desktop\Test-Out\2017-08\2017-08-22 19.53.28.jpg</pre> </p> <p> This does indeed produce the expected destination directory structure. </p> <p> <img src="/content/binary/picture-archivist-destination-directory.png" alt="Seven example directories with pictures."> </p> <p> It's always nice when something turns out to work in practice, as well as in theory. </p> <h3 id="3e4503b89d8f4b81b8b9cac9d1f39021"> Summary <a href="#3e4503b89d8f4b81b8b9cac9d1f39021" title="permalink">#</a> </h3> <p> <a href="/2018/11/19/functional-architecture-a-definition">Functional software architecture</a> involves separating pure from impure code so that no pure functions invoke impure operations. Often, you can achieve that with what I call the <em>impure-pure-impure sandwich</em> architecture. In this example, you saw how to model the file system as a tree. This enables you to separate the impure file interactions from the pure program logic. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/09/16/picture-archivist-in-f Picture archivist in Haskell https://blog.ploeh.dk/2019/09/09/picture-archivist-in-haskell/ Mon, 09 Sep 2019 08:19:00 UTC <div id="post"> <p> <em>A comprehensive code example showing how to implement a functional architecture in Haskell.</em> </p> <p> This article shows how to implement the <a href="/2019/08/26/functional-file-system">picture archivist architecture described in the previous article</a>. In short, the task is to move some image files to directories based on their date-taken metadata. The architectural idea is to load a directory structure from disk into an in-memory tree, manipulate that tree, and use the resulting tree to perform the desired actions: </p> <p> <img src="/content/binary/functional-file-system-interaction.png" alt="A functional program typically loads data, transforms it, and stores it again."> </p> <p> Much of the program will manipulate the tree data, which is immutable. </p> <h3 id="770cf37f0e3c457782ea20b53257f2d1"> Tree <a href="#770cf37f0e3c457782ea20b53257f2d1" title="permalink">#</a> </h3> <p> You can start by defining a <a href="https://en.wikipedia.org/wiki/Rose_tree">rose tree</a>: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;Tree&nbsp;a&nbsp;b&nbsp;=&nbsp;Node&nbsp;a&nbsp;[Tree&nbsp;a&nbsp;b]&nbsp;|&nbsp;Leaf&nbsp;b&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> If you wanted to, you could put all the <code>Tree</code> code in a reusable library, because none of it is coupled to a particular application, such as <a href="https://amzn.to/2V06Kji">moving pictures</a>. You could also write a comprehensive test suite for the following functions, but in this article, I'll skip that. </p> <p> Notice that this sort of tree explicitly distinguishes between internal and leaf nodes. This is necessary because you'll need to keep track of the directory names (the internal nodes), while at the same time you'll want to enrich the leaves with additional data - data that you can't meaningfully add to the internal nodes. You'll see this later in the article. </p> <p> The <a href="/2019/08/05/rose-tree-catamorphism">rose tree catamorphism</a> is this <code>foldTree</code> function: </p> <p> <pre><span style="color:#2b91af;">foldTree</span>&nbsp;::&nbsp;(a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;[c]&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(b&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Tree</span>&nbsp;a&nbsp;b&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c foldTree&nbsp;&nbsp;_&nbsp;fl&nbsp;(Leaf&nbsp;x)&nbsp;=&nbsp;fl&nbsp;x foldTree&nbsp;fn&nbsp;fl&nbsp;(Node&nbsp;x&nbsp;xs)&nbsp;=&nbsp;fn&nbsp;x&nbsp;$&nbsp;foldTree&nbsp;fn&nbsp;fl&nbsp;&lt;$&gt;&nbsp;xs</pre> </p> <p> Sometimes I name the catamorphism <code>cata</code>, sometimes something like <code>tree</code>, but using a library like <code>Data.Tree</code> as another source of inspiration, in this article I chose to name it <code>foldTree</code>. </p> <p> In this article, tree functionality is (with one exception) directly or transitively implemented with <code>foldTree</code>. </p> <h3 id="f5541d8a36b04cf9a455824c5f3a21c7"> Filtering trees <a href="#f5541d8a36b04cf9a455824c5f3a21c7" title="permalink">#</a> </h3> <p> It'll be useful to be able to filter the contents of a tree. For example, the picture archivist program will only move image files with valid metadata. This means that it'll need to filter out all files that aren't image files, as well as image files without valid metadata. </p> <p> It turns out that it'll be useful to supply a function that throws away <code>Nothing</code> values from a tree of <code>Maybe</code> leaves. This is similar to the <code>catMaybes</code> function from <code>Data.Maybe</code>, so I call it <code>catMaybeTree</code>: </p> <p> <pre><span style="color:#2b91af;">catMaybeTree</span>&nbsp;::&nbsp;<span style="color:blue;">Tree</span>&nbsp;a&nbsp;(<span style="color:#2b91af;">Maybe</span>&nbsp;b)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&nbsp;(<span style="color:blue;">Tree</span>&nbsp;a&nbsp;b) catMaybeTree&nbsp;=&nbsp;foldTree&nbsp;(\x&nbsp;-&gt;&nbsp;Just&nbsp;.&nbsp;Node&nbsp;x&nbsp;.&nbsp;catMaybes)&nbsp;(<span style="color:blue;">fmap</span>&nbsp;Leaf)</pre> </p> <p> You may find the type of the function surprising. Why does it return a <code>Maybe Tree</code>, instead of simply a <code>Tree</code>? And if you accept the type as given, isn't this simply the <code>sequence</code> function? </p> <p> While <code>catMaybes</code> simply returns a list, it can do this because lists can be empty. This <code>Tree</code> type, on the other hand, can't be empty. If the purpose of <code>catMaybeTree</code> is to throw away all <code>Nothing</code> values, then how do you return a tree from <code>Leaf Nothing</code>? </p> <p> You can't return a <code>Leaf</code> because you have no value to put in the leaf. Similarly, you can't return a <code>Node</code> because, again, you have no value to put in the node. </p> <p> In order to handle this edge case, then, you'll have to return <code>Nothing</code>: </p> <p> <pre>Prelude Tree&gt; catMaybeTree$ Leaf Nothing Nothing</pre> </p> <p> Isn't this the same as <code>sequence</code>, then? It's not, because <code>sequence</code> short-circuits all data, as this list example shows: </p> <p> <pre>Prelude&gt; sequence [Just 42, Nothing, Just 2112] Nothing</pre> </p> <p> Contrast this with the behaviour of <code>catMaybes</code>: </p> <p> <pre>Prelude Data.Maybe&gt; catMaybes [Just 42, Nothing, Just 2112] [42,2112]</pre> </p> <p> You've yet to see the <code>Traversable</code> instance for <code>Tree</code>, but it behaves in the same way: </p> <p> <pre>Prelude Tree&gt; sequence $Node "Foo" [Leaf (Just 42), Leaf Nothing, Leaf (Just 2112)] Nothing</pre> </p> <p> The <code>catMaybeTree</code> function, on the other hand, returns a filtered tree: </p> <p> <pre>Prelude Tree&gt; catMaybeTree$ Node "Foo" [Leaf (Just 42), Leaf Nothing, Leaf (Just 2112)] Just (Node "Foo" [Leaf 42,Leaf 2112])</pre> </p> <p> While the resulting tree is wrapped in a <code>Just</code> case, the leaves contain unwrapped values. </p> <h3 id="5f0287c6d6fe42f3ad73a8e31ba9b3c4"> Instances <a href="#5f0287c6d6fe42f3ad73a8e31ba9b3c4" title="permalink">#</a> </h3> <p> The <a href="/2019/08/05/rose-tree-catamorphism">article about the rose tree catamorphism</a> already covered how to add instances of <code>Bifunctor</code>, <code>Bifoldable</code>, and <code>Bitraversable</code>, so I'll give this only cursory treatment. Refer to that article for a more detailed treatment. The code that accompanies that article also has <a href="http://hackage.haskell.org/package/QuickCheck">QuickCheck</a> properties that verify the various laws associated with those instances. Here, I'll just list the instances without further comment: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Bifunctor</span>&nbsp;<span style="color:blue;">Tree</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;bimap&nbsp;f&nbsp;s&nbsp;=&nbsp;foldTree&nbsp;(Node&nbsp;.&nbsp;f)&nbsp;(Leaf&nbsp;.&nbsp;s) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Bifoldable</span>&nbsp;<span style="color:blue;">Tree</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;bifoldMap&nbsp;f&nbsp;=&nbsp;foldTree&nbsp;(\x&nbsp;xs&nbsp;-&gt;&nbsp;f&nbsp;x&nbsp;&lt;&gt;&nbsp;mconcat&nbsp;xs) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Bitraversable</span>&nbsp;<span style="color:blue;">Tree</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;bitraverse&nbsp;f&nbsp;s&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;foldTree&nbsp;(\x&nbsp;xs&nbsp;-&gt;&nbsp;Node&nbsp;&lt;$&gt;&nbsp;f&nbsp;x&nbsp;&lt;*&gt;&nbsp;sequenceA&nbsp;xs)&nbsp;(<span style="color:blue;">fmap</span>&nbsp;Leaf&nbsp;.&nbsp;s) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;(<span style="color:blue;">Tree</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;=&nbsp;second <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Foldable</span>&nbsp;(<span style="color:blue;">Tree</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;foldMap&nbsp;=&nbsp;bifoldMap&nbsp;mempty <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Traversable</span>&nbsp;(<span style="color:blue;">Tree</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;sequenceA&nbsp;=&nbsp;bisequenceA&nbsp;.&nbsp;first&nbsp;pure</pre> </p> <p> The picture archivist program isn't going to explicitly need all of these, but transitively, it will. </p> <h3 id="d1bbd6ef895f45619822126f44bf6bfb"> Moving pictures <a href="#d1bbd6ef895f45619822126f44bf6bfb" title="permalink">#</a> </h3> <p> So far, all the code shown here could be in a general-purpose reusable library, since it contains no functionality specifically related to image files. The rest of the code in this article, however, will be specific to the program. I'll put the domain model code in another module and import some functionality: </p> <p> <pre><span style="color:blue;">module</span>&nbsp;Archive&nbsp;<span style="color:blue;">where</span> <span style="color:blue;">import</span>&nbsp;Data.Time <span style="color:blue;">import</span>&nbsp;Text.Printf <span style="color:blue;">import</span>&nbsp;System.FilePath <span style="color:blue;">import</span>&nbsp;<span style="color:blue;">qualified</span>&nbsp;Data.Map.Strict&nbsp;<span style="color:blue;">as</span>&nbsp;Map <span style="color:blue;">import</span>&nbsp;Tree</pre> </p> <p> Notice that <code>Tree</code> is one of the imported modules. </p> <p> Later, we'll look at how to load a tree from the file system, but for now, we'll just pretend that we have such a tree. </p> <p> The major logic of the program is to create a destination tree based on a source tree. The leaves of the tree will have to carry some extra information apart from a file path, so you can introduce a specific type to capture that information: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;PhotoFile&nbsp;= &nbsp;&nbsp;PhotoFile&nbsp;{&nbsp;photoFileName&nbsp;::&nbsp;FilePath,&nbsp;takenOn&nbsp;::&nbsp;LocalTime&nbsp;} &nbsp;&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> A <code>PhotoFile</code> not only contains the file path for an image file, but also the date the photo was taken. This date can be extracted from the file's metadata, but that's an impure operation, so we'll delegate that work to the start of the program. We'll return to that later. </p> <p> Given a source tree of <code>PhotoFile</code> leaves, though, the program must produce a destination tree of files: </p> <p> <pre><span style="color:#2b91af;">moveTo</span>&nbsp;::&nbsp;(<span style="color:blue;">Foldable</span>&nbsp;t,&nbsp;<span style="color:blue;">Ord</span>&nbsp;a,&nbsp;<span style="color:blue;">PrintfType</span>&nbsp;a)&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;t&nbsp;<span style="color:blue;">PhotoFile</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Tree</span>&nbsp;a&nbsp;<span style="color:#2b91af;">FilePath</span> moveTo&nbsp;destination&nbsp;= &nbsp;&nbsp;Node&nbsp;destination&nbsp;.&nbsp;Map.foldrWithKey&nbsp;addDir&nbsp;<span style="color:blue;">[]</span>&nbsp;.&nbsp;<span style="color:blue;">foldr</span>&nbsp;groupByDir&nbsp;Map.empty &nbsp;&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;&nbsp;&nbsp;dirNameOf&nbsp;(LocalTime&nbsp;d&nbsp;_)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;(y,&nbsp;m,&nbsp;_)&nbsp;=&nbsp;toGregorian&nbsp;d&nbsp;<span style="color:blue;">in</span>&nbsp;printf&nbsp;<span style="color:#a31515;">&quot;%d-%02d&quot;</span>&nbsp;y&nbsp;m &nbsp;&nbsp;&nbsp;&nbsp;groupByDir&nbsp;(PhotoFile&nbsp;fileName&nbsp;t)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Map.insertWith&nbsp;<span style="color:#2b91af;">(++)</span>&nbsp;(dirNameOf&nbsp;t)&nbsp;[fileName] &nbsp;&nbsp;&nbsp;&nbsp;addDir&nbsp;name&nbsp;files&nbsp;dirs&nbsp;=&nbsp;Node&nbsp;name&nbsp;(Leaf&nbsp;&lt;$&gt;&nbsp;files)&nbsp;:&nbsp;dirs</pre> </p> <p> This <code>moveTo</code> function looks, perhaps, overwhelming, but it's composed of only three steps: <ol> <li>Create a map of destination folders (<code>foldr groupByDir Map.empty</code>).</li> <li>Create a list of branches from the map (<code>Map.foldrWithKey addDir []</code>).</li> <li>Create a tree from the list (<code>Node destination</code>).</li> </ol> Recall that when Haskell functions are composed with the <code>.</code> operator, you'll have to read the composition from right to left. </p> <p> Notice that this function works with any <code>Foldable</code> data container, so it'd work with lists and other data structures besides trees. </p> <p> The <code>moveTo</code> function starts by folding the input data into a map. The map is keyed by the directory name, which is formatted by the <code>dirNameOf</code> function. This function takes a <code>LocalTime</code> as input and formats it to a <code>YYYY-MM</code> format. For example, December 20, 2018 becomes <code>"2018-12"</code>. </p> <p> The entire mapping step groups the <code>PhotoFile</code> values into a map of the type <code>Map a [FilePath]</code>. All the image files taken in April 2014 are added to the list with the <code>"2014-04"</code> key, all the image files taken in July 2011 are added to the list with the <code>"2011-07"</code> key, and so on. </p> <p> In the next step, the <code>moveTo</code> function converts the map to a list of trees. This will be the branches (or sub-directories) of the <code>destination</code> directory. Because of the desired structure of the destination tree, this is a list of shallow branches. Each node contains only leaves. </p> <p> <img src="/content/binary/shallow-photo-destination-directories.png" alt="Shallow photo destination directories."> </p> <p> The only remaining step is to add that list of branches to a <code>destination</code> node. </p> <p> Since this is a <a href="https://en.wikipedia.org/wiki/Pure_function">pure function</a>, it's <a href="/2015/05/07/functional-design-is-intrinsically-testable">easy to unit test</a>. Just create some input values and call the function: </p> <p> <pre><span style="color:#a31515;">&quot;Move&nbsp;to&nbsp;destination&quot;</span>&nbsp;~:&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;(source,&nbsp;destination,&nbsp;expected)&nbsp;&lt;- &nbsp;&nbsp;&nbsp;&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;$&nbsp;lt&nbsp;2018&nbsp;11&nbsp;9&nbsp;11&nbsp;47&nbsp;17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;<span style="color:#a31515;">&quot;D&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>&nbsp;[Node&nbsp;<span style="color:#a31515;">&quot;2018-11&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>]]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;S&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>&nbsp;$&nbsp;lt&nbsp;1972&nbsp;6&nbsp;6&nbsp;16&nbsp;15&nbsp;00] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;<span style="color:#a31515;">&quot;D&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>&nbsp;[Node&nbsp;<span style="color:#a31515;">&quot;1972-06&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;4&quot;</span>]]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;S&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;L&quot;</span>&nbsp;$&nbsp;lt&nbsp;2002&nbsp;10&nbsp;12&nbsp;17&nbsp;16&nbsp;15, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;J&quot;</span>&nbsp;$&nbsp;lt&nbsp;2007&nbsp;4&nbsp;21&nbsp;17&nbsp;18&nbsp;19] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;<span style="color:#a31515;">&quot;D&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;D&quot;</span>&nbsp;[Node&nbsp;<span style="color:#a31515;">&quot;2002-10&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;L&quot;</span>],&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2007-04&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;J&quot;</span>]]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;1&nbsp;12&nbsp;17&nbsp;16&nbsp;15, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;3&nbsp;12&nbsp;17&nbsp;16&nbsp;15, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;1&nbsp;21&nbsp;17&nbsp;18&nbsp;19] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;<span style="color:#a31515;">&quot;2&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2010-01&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>], &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2010-03&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>]]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;foo&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;bar&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;1&nbsp;12&nbsp;17&nbsp;16&nbsp;15, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;3&nbsp;12&nbsp;17&nbsp;16&nbsp;15, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;1&nbsp;21&nbsp;17&nbsp;18&nbsp;19], &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;baz&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;d&quot;</span>&nbsp;$&nbsp;lt&nbsp;2010&nbsp;3&nbsp;1&nbsp;2&nbsp;3&nbsp;4, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;PhotoFile&nbsp;<span style="color:#a31515;">&quot;e&quot;</span>&nbsp;$&nbsp;lt&nbsp;2011&nbsp;3&nbsp;4&nbsp;3&nbsp;2&nbsp;1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;]] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;<span style="color:#a31515;">&quot;qux&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;,&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;qux&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2010-01&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>,&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>], &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2010-03&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>,&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;d&quot;</span>], &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;2011-03&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;e&quot;</span>]]) &nbsp;&nbsp;&nbsp;&nbsp;] &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;moveTo&nbsp;destination&nbsp;source &nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;expected&nbsp;~=?&nbsp;actual</pre> </p> <p> This is an <a href="/2018/05/07/inlined-hunit-test-lists">inlined</a> <a href="/2018/04/30/parametrised-unit-tests-in-haskell">parametrised HUnit test</a>. While it looks like a big unit test, it still follows my <a href="/2013/06/24/a-heuristic-for-formatting-code-according-to-the-aaa-pattern">test formatting heuristic</a>. There's only three expressions, but the <em>arrange</em> expression is big because it creates a list of test cases. </p> <p> Each test case is a triple of a <code>source</code> tree, a <code>destination</code> directory name, and an <code>expected</code> result. In order to make the test data code more compact, it utilises this test-specific helper function: </p> <p> <pre>lt&nbsp;y&nbsp;mth&nbsp;d&nbsp;h&nbsp;m&nbsp;s&nbsp;=&nbsp;LocalTime&nbsp;(fromGregorian&nbsp;y&nbsp;mth&nbsp;d)&nbsp;(TimeOfDay&nbsp;h&nbsp;m&nbsp;s)</pre> </p> <p> For each test case, the test calls the <code>moveTo</code> function with the <code>destination</code> directory name and the <code>source</code> tree. It then asserts that the <code>expected</code> value is equal to the <code>actual</code> value. </p> <h3 id="bcf9e8fd9d1b42bbb47b811be75385d0"> Calculating moves <a href="#bcf9e8fd9d1b42bbb47b811be75385d0" title="permalink">#</a> </h3> <p> One pure step remains. The result of calling the <code>moveTo</code> function is a tree with the desired structure. In order to actually move the files, though, for each file you'll need to keep track of both the source path and the destination path. To make that explicit, you can define a type for that purpose: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;Move&nbsp;= &nbsp;&nbsp;Move&nbsp;{&nbsp;sourcePath&nbsp;::&nbsp;FilePath,&nbsp;destinationPath&nbsp;::&nbsp;FilePath&nbsp;} &nbsp;&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Read</span>)</pre> </p> <p> A <code>Move</code> is simply a data structure. Contrast this with typical object-oriented design, where it would be a (possibly polymorphic) method on an object. In functional programming, you'll regularly model <em>intent</em> with a data structure. As long as intents remain data, you can easily manipulate them, and once you're done with that, you can run an interpreter over your data structure to perform the work you want accomplished. </p> <p> The unit test cases for the <code>moveTo</code> function suggest that file names are local file names like <code>"L"</code>, <code>"J"</code>, <code>"a"</code>, and so on. That was only to make the tests as compact as possible, since the function actually doesn't manipulate the specific <code>FilePath</code> values. </p> <p> In reality, the file names will most likely be longer, and they could also contain the full path, instead of the local path: <code>"C:\foo\bar\a.jpg"</code>. </p> <p> If you call <code>moveTo</code> with a tree where each leaf has a fully qualified path, the output tree will have the desired structure of the destination tree, but the leaves will still contain the full path to each source file. That means that you can calculate a <code>Move</code> for each file: </p> <p> <pre><span style="color:#2b91af;">calculateMoves</span>&nbsp;::&nbsp;<span style="color:blue;">Tree</span>&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Tree</span>&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:blue;">Move</span> calculateMoves&nbsp;=&nbsp;imp&nbsp;<span style="color:#a31515;">&quot;&quot;</span> &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;imp&nbsp;path&nbsp;&nbsp;&nbsp;&nbsp;(Leaf&nbsp;x)&nbsp;=&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;x&nbsp;$&nbsp;replaceDirectory&nbsp;x&nbsp;path &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;imp&nbsp;path&nbsp;(Node&nbsp;x&nbsp;xs)&nbsp;=&nbsp;Node&nbsp;(path&nbsp;&lt;/&gt;&nbsp;x)&nbsp;$&nbsp;imp&nbsp;(path&nbsp;&lt;/&gt;&nbsp;x)&nbsp;&lt;$&gt;&nbsp;xs</pre> </p> <p> This function takes as input a <code>Tree FilePath FilePath</code>, which is compatible with the output of <code>moveTo</code>. It returns a <code>Tree FilePath Move</code>, i.e. a tree where the leaves are <code>Move</code> values. </p> <p> To be fair, returning a tree is overkill. A <code>[Move]</code> (list of moves) would have been just as useful, but in this article, I'm trying to describe how to write code with a <a href="/2018/11/19/functional-architecture-a-definition">functional architecture</a>. In the overview article, I explained how you can model a file system using a rose tree, and in order to emphasise that point, I'll stick with that model a little while longer. </p> <p> Earlier, I wrote that you can implement desired <code>Tree</code> functionality with the <code>foldTree</code> function, but that was a simplification. If you can implement the functionality of <code>calculateMoves</code> with <code>foldTree</code>, I don't know how. You can, however, implement it using explicit pattern matching and simple recursion. </p> <p> The <code>imp</code> function builds up a file path (using the <code>&lt;/&gt;</code> path combinator) as it recursively negotiates the tree. All <code>Leaf</code> nodes are converted to a <code>Move</code> value using the leaf node's current <code>FilePath</code> value as the <code>sourcePath</code>, and the <code>path</code> to figure out the desired <code>destinationPath</code>. </p> <p> This code is still easy to unit test: </p> <p> <pre><span style="color:#a31515;">&quot;Calculate&nbsp;moves&quot;</span>&nbsp;~:&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;(tree,&nbsp;expected)&nbsp;&lt;- &nbsp;&nbsp;&nbsp;&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Leaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Node&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>],&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;[Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Node&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>],&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>]), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(Node&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;[Node&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;Leaf&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>],&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>&nbsp;[Leaf&nbsp;<span style="color:#a31515;">&quot;3&quot;</span>]], &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>)&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;b&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>], &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;(<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>)&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Leaf&nbsp;$&nbsp;Move&nbsp;<span style="color:#a31515;">&quot;3&quot;</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;a&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;c&quot;</span>&nbsp;&lt;/&gt;&nbsp;<span style="color:#a31515;">&quot;3&quot;</span>]]) &nbsp;&nbsp;&nbsp;&nbsp;] &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;calculateMoves&nbsp;tree &nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;expected&nbsp;~=?&nbsp;actual</pre> </p> <p> The test cases in this parametrised test are tuples of an input <code>tree</code> and the <code>expected</code> tree. For each test case, the test calls the <code>calculateMoves</code> function with <code>tree</code> and asserts that the <code>actual</code> tree is equal to the <code>expected</code> tree. </p> <p> That's all the pure code you need in order to implement the desired functionality. Now you only need to write some code that loads a tree from disk, and imprints a destination tree to disk, as well as the code that composes it all. </p> <h3 id="062fff475b2b47e188dbd2bc930aa882"> Loading a tree from disk <a href="#062fff475b2b47e188dbd2bc930aa882" title="permalink">#</a> </h3> <p> The remaining code in this article is impure. You could put it in dedicated modules, but for this program, you're only going to need three functions and a bit of composition code, so you could also just put it all in the <code>Main</code> module. That's what I did. </p> <p> To load a tree from disk, you'll need a root directory, under which you load the entire tree. Given a directory path, you read a tree using a recursive function like this: </p> <p> <pre><span style="color:#2b91af;">readTree</span>&nbsp;::&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;(<span style="color:blue;">Tree</span>&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:#2b91af;">FilePath</span>) readTree&nbsp;path&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;isFile&nbsp;&lt;-&nbsp;doesFileExist&nbsp;path &nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;isFile &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">then</span>&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;Leaf&nbsp;path &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span>&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dirsAndfiles&nbsp;&lt;-&nbsp;listDirectory&nbsp;path &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;paths&nbsp;=&nbsp;<span style="color:blue;">fmap</span>&nbsp;(path&nbsp;&lt;/&gt;)&nbsp;dirsAndfiles &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;branches&nbsp;&lt;-&nbsp;traverse&nbsp;readTree&nbsp;paths &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;Node&nbsp;path&nbsp;branches</pre> </p> <p> This recursive function starts by checking whether the <code>path</code> is a file or a directory. If it's a file, it creates a new <code>Leaf</code> with that <code>FilePath</code>. </p> <p> If <code>path</code> isn't a file, it's a directory. In that case, use <code>listDirectory</code> to enumerate all the directories and files in that directory. These are only local names, so prefix them with <code>path</code> to create full paths, then <code>traverse</code> all those directory entries recursively. That produces all the <code>branches</code> for the current node. Finally, return a new <code>Node</code> with the <code>path</code> and the <code>branches</code>. </p> <h3 id="5ba31d6e6e7f4eee942e39349a45e1ed"> Loading metadata <a href="#5ba31d6e6e7f4eee942e39349a45e1ed" title="permalink">#</a> </h3> <p> The <code>readTree</code> function only produces a tree with <code>FilePath</code> leaves, while the program requires a tree with <code>PhotoFile</code> leaves. You'll need to read the <a href="https://en.wikipedia.org/wiki/Exif">Exif</a> metadata from each file and enrich the tree with the <em>date-taken</em> data. </p> <p> In this code base, I've used the <a href="http://hackage.haskell.org/package/hsexif">hsexif</a> library for this. That enables you to write an impure operation like this: </p> <p> <pre><span style="color:#2b91af;">readPhoto</span>&nbsp;::&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;(<span style="color:#2b91af;">Maybe</span>&nbsp;<span style="color:blue;">PhotoFile</span>) readPhoto&nbsp;path&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;exifData&nbsp;&lt;-&nbsp;parseFileExif&nbsp;path &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;dateTaken&nbsp;=&nbsp;either&nbsp;(<span style="color:blue;">const</span>&nbsp;Nothing)&nbsp;Just&nbsp;exifData&nbsp;&gt;&gt;=&nbsp;getDateTimeOriginal &nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;PhotoFile&nbsp;path&nbsp;&lt;$&gt;&nbsp;dateTaken</pre> </p> <p> This operation can fail for various reasons: <ul> <li>The file may not exist.</li> <li>The file exists, but has no metadata.</li> <li>The file has metadata, but no <em>date-taken</em> metadata.</li> <li>The <em>date-taken</em> metadata string is malformed.</li> </ul> The program is just going to skip all files from which it can't extract <em>date-taken</em> metadata, so <code>readPhoto</code> converts the <code>Either</code> value returned by <code>parseFileExif</code> to <code>Maybe</code> and binds the result with <code>getDateTimeOriginal</code>. </p> <p> When you <code>traverse</code> a <code>Tree FilePath FilePath</code> with <code>readPhoto</code>, you'll get a <code>Tree FilePath (Maybe PhotoFile)</code>. That's when you'll need <code>catMaybeTree</code>. You'll see this soon. </p> <h3 id="8b8d1709f9ed4fe2bc78e4ea9b2a2508"> Writing a tree to disk <a href="#8b8d1709f9ed4fe2bc78e4ea9b2a2508" title="permalink">#</a> </h3> <p> The above <code>calculateMoves</code> function creates a <code>Tree FilePath Move</code>. The final piece of impure code you'll need to write is an operation that traverses such a tree and executes each <code>Move</code>. </p> <p> <pre><span style="color:#2b91af;">applyMoves</span>&nbsp;::&nbsp;<span style="color:blue;">Foldable</span>&nbsp;t&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;t&nbsp;<span style="color:blue;">Move</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;() applyMoves&nbsp;=&nbsp;traverse_&nbsp;move &nbsp;&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;&nbsp;&nbsp;move&nbsp;m&nbsp;=&nbsp;copy&nbsp;m&nbsp;&gt;&gt;&nbsp;compareFiles&nbsp;m&nbsp;&gt;&gt;=&nbsp;deleteSource &nbsp;&nbsp;&nbsp;&nbsp;copy&nbsp;(Move&nbsp;s&nbsp;d)&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;createDirectoryIfMissing&nbsp;True&nbsp;$&nbsp;takeDirectory&nbsp;d &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;copyFileWithMetadata&nbsp;s&nbsp;d &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">putStrLn</span>&nbsp;$&nbsp;<span style="color:#a31515;">&quot;Copied&nbsp;to&nbsp;&quot;</span>&nbsp;++&nbsp;<span style="color:blue;">show</span>&nbsp;d &nbsp;&nbsp;&nbsp;&nbsp;compareFiles&nbsp;m@(Move&nbsp;s&nbsp;d)&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sourceBytes&nbsp;&lt;-&nbsp;B.<span style="color:blue;">readFile</span>&nbsp;s &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;destinationBytes&nbsp;&lt;-&nbsp;B.<span style="color:blue;">readFile</span>&nbsp;d &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;<span style="color:blue;">if</span>&nbsp;sourceBytes&nbsp;==&nbsp;destinationBytes&nbsp;<span style="color:blue;">then</span>&nbsp;Just&nbsp;m&nbsp;<span style="color:blue;">else</span>&nbsp;Nothing &nbsp;&nbsp;&nbsp;&nbsp;deleteSource&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Nothing&nbsp;=&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">()</span> &nbsp;&nbsp;&nbsp;&nbsp;deleteSource&nbsp;(Just&nbsp;(Move&nbsp;s&nbsp;_))&nbsp;=&nbsp;removeFile&nbsp;s</pre> </p> <p> As I wrote above, a tree of <code>Move</code> values is, to be honest, overkill. Any <code>Foldable</code> container will do, as the <code>applyMoves</code> operation demonstrates. It traverses the data structure, and for each <code>Move</code>, it first copies the file, then it verifies that the copy was successful, and finally, if that's the case, it deletes the source file. </p> <p> All of the operations invoked by these three steps are defined in various libraries part of the base GHC installation. You're welcome to peruse <a href="https://github.com/ploeh/picture-archivist">the source code repository</a> if you're interested in the details. </p> <h3 id="d336cf55dc9746c08cbed32041803173"> Composition <a href="#d336cf55dc9746c08cbed32041803173" title="permalink">#</a> </h3> <p> You can now compose an <em>impure-pure-impure sandwich</em> from all the Lego pieces: </p> <p> <pre><span style="color:#2b91af;">movePhotos</span>&nbsp;::&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">FilePath</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;() movePhotos&nbsp;source&nbsp;destination&nbsp;=&nbsp;<span style="color:blue;">fmap</span>&nbsp;fold&nbsp;$&nbsp;runMaybeT&nbsp;$&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;sourceTree&nbsp;&lt;-&nbsp;lift&nbsp;$&nbsp;readTree&nbsp;source &nbsp;&nbsp;photoTree&nbsp;&lt;-&nbsp;MaybeT&nbsp;$&nbsp;catMaybeTree&nbsp;&lt;$&gt;&nbsp;traverse&nbsp;readPhoto&nbsp;sourceTree &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;destinationTree&nbsp;=&nbsp;calculateMoves&nbsp;$&nbsp;moveTo&nbsp;destination&nbsp;photoTree &nbsp;&nbsp;lift&nbsp;$&nbsp;applyMoves&nbsp;destinationTree</pre> </p> <p> First, you load the <code>sourceTree</code> using the <code>readTree</code> operation. This is a <code>Tree FilePath FilePath</code> value, because the code is written in <code>do</code> notation, and the context is <code>MaybeT IO ()</code>. You then load the image metatadata by traversing <code>sourceTree</code> with <code>readPhoto</code>. This produces a <code>Tree FilePath (Maybe PhotoFile)</code> that you then filter with <code>catMaybeTree</code>. Again, because of <code>do</code> notation and monad transformer shenanigans, <code>photoTree</code> is a <code>Tree FilePath PhotoFile</code> value. </p> <p> Those two lines of code is the initial impure step of the sandwich (yes: mixed metaphors, I know). </p> <p> The pure part of the sandwich is the composition of the pure functions <code>moveTo</code> and <code>calculateMoves</code>. The result is a <code>Tree FilePath Move</code> value. </p> <p> The final, impure step of the sandwich, then, is to <code>applyMoves</code>. </p> <h3 id="8b44f4d2cd2241e18bff6d40c1ad9ee9"> Execution <a href="#8b44f4d2cd2241e18bff6d40c1ad9ee9" title="permalink">#</a> </h3> <p> The <code>movePhotos</code> operation takes <code>source</code> and <code>destination</code> arguments. You could hypothetically call it from a rich client or a background process, but here I'll just call if from a command-line program. The <code>main</code> operation will have to parse the input arguments and call <code>movePhotos</code>: </p> <p> <pre><span style="color:#2b91af;">main</span>&nbsp;::&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;() main&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;args&nbsp;&lt;-&nbsp;getArgs &nbsp;&nbsp;<span style="color:blue;">case</span>&nbsp;args&nbsp;<span style="color:blue;">of</span> &nbsp;&nbsp;&nbsp;&nbsp;[source,&nbsp;destination]&nbsp;-&gt;&nbsp;movePhotos&nbsp;source&nbsp;destination &nbsp;&nbsp;&nbsp;&nbsp;_&nbsp;-&gt;&nbsp;<span style="color:blue;">putStrLn</span>&nbsp;<span style="color:#a31515;">&quot;Please&nbsp;provide&nbsp;source&nbsp;and&nbsp;destination&nbsp;directories&nbsp;as&nbsp;arguments.&quot;</span></pre> </p> <p> You could write more sophisticated parsing of the program arguments, but that's not the topic of this article, so I only wrote the bare minimum required to get the program working. </p> <p> You can now compile and run the program: </p> <p> <pre>$ ./archpics "C:\Users\mark\Desktop\Test" "C:\Users\mark\Desktop\Test-Out" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2003-04\\2003-04-29 15.11.50.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2011-07\\2011-07-10 13.09.36.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2014-04\\2014-04-17 17.11.40.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2014-04\\2014-04-18 14.05.02.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2014-05\\2014-05-23 16.07.20.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2014-06\\2014-06-30 15.44.52.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2014-06\\2014-06-21 16.48.40.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2016-05\\2016-05-01 09.25.23.jpg" Copied to "C:\\Users\\mark\\Desktop\\Test-Out\\2017-08\\2017-08-22 19.53.28.jpg"</pre> </p> <p> This does indeed produce the expected destination directory structure. </p> <p> <img src="/content/binary/picture-archivist-destination-directory.png" alt="Seven example directories with pictures."> </p> <p> It's always nice when something turns out to work in practice, as well as in theory. </p> <h3 id="c50c7ac1276146d79715a5e7ddadfe6d"> Summary <a href="#c50c7ac1276146d79715a5e7ddadfe6d" title="permalink">#</a> </h3> <p> Functional software architecture involves separating pure from impure code so that no pure functions invoke impure operations. Often, you can achieve that with what I call the <em>impure-pure-impure sandwich</em> architecture. In this example, you saw how to model the file system as a tree. This enables you to separate the impure file interactions from the pure program logic. </p> <p> The Haskell type system enforces the <em>functional interaction law</em>, which implies that the architecture is, indeed, properly functional. Other languages, like <a href="https://fsharp.org">F#</a>, don't enforce the law via the compiler, but that doesn't prevent you doing functional programming. Now that we've verified that the architecture is, indeed, functional, we can port it to F#. </p> <p> <strong>Next:</strong> <a href="/2019/09/16/picture-archivist-in-f">Picture archivist in F#</a>. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="f237d98d453a4bcb9a3d58a05bf21d34"> <div class="comment-author"><a href="https://majiehong.com">Jiehong</a></div> <div class="comment-content"> <p> This seems a fair architecture. </p> <p> However, at first glance it does not seem very memory efficient, because everything might be loaded in RAM, and that poses a strict limit. </p> <p> But then, I remember that Haskell does lazy evaluation, so is it the case here? Are path and the tree lazily loaded and processed? </p> <p> In "traditional" architectures, IO would be scattered inside the program, and as each file might be read one at a time, and handled. This sandwich of purity with impure buns forces not to do that. </p> </div> <div class="comment-date">2019-09-09 11:47 UTC</div> </div> <div class="comment" id="ca660cdc1f094bfb8cc9896bb1084460"> <div class="comment-author"><a href="/">Mark Seemann</a></div> <div class="comment-content"> <p> Jiehong, thank you for writing. It's true that Haskell is lazily evaluated, but some strictness rules apply to <code>IO</code>, so it's not so simple. </p> <p> Just running a quick experiment with the code base shown here, when I try to move thousands of files, the program sits and thinks for quite some time before it starts to output progress. This indicates to me that it does, indeed, load at least the <em>structure</em> of the tree into memory before it starts moving the files. Once it does that, though, it looks like it runs at constant memory. </p> <p> There's an interplay of laziness and <code>IO</code> in Haskell that I still don't sufficiently master. When I publish the port to F#, however, it should be clear that you could replace all the nodes of the tree with explicitly lazy values. I'd be surprised if something like that isn't possible in Haskell as well, but here I'll solicit help from readers more well-versed in these matters than I am. </p> </div> <div class="comment-date">2019-09-09 19:16 UTC</div> </div> <div class="comment" id="dd26f6d047b5492b8a012b30d96ad18b"> <div class="comment-author">André Cardoso</div> <div class="comment-content"> <p> I really like your posts and I'm really liking this series. But I struggle with Haskell syntax, specially the difference between the operators $, &lt;$&gt;, &lt;&gt;, &lt;*&gt;. Is there a cheat sheet explaining these operators? </p> </div> <div class="comment-date">2019-09-12 13:51 UTC</div> </div> <div class="comment" id="2e71f695ed9f4cfa8467df818f072da8"> <div class="comment-author"><a href="/">Mark Seemann</a></div> <div class="comment-content"> <p> André, thank you for writing. I've written about why <a href="/2018/07/02/terse-operators-make-business-code-more-readable">I think that terse operators make the code overall more readable</a>, but that's obviously not an explanation of any of those operators. </p> <p> I'm not aware of any cheat sheets for Haskell, although a Google search seems to indicate that many exist. I'm not sure that a cheat sheet will help much if one doesn't know Haskell, and if one does know Haskell, one is likely to also know those operators. </p> <p> <a href="https://hackage.haskell.org/package/base/docs/Prelude.html#v:-36-">$</a> is a sort of delimiter that often saves you from having to nest other function calls in brackets. </p> <p> <a href="https://hackage.haskell.org/package/base/docs/Prelude.html#v:-60--36--62-">&lt;$&gt;</a> is just an infix alias for <code>fmap</code>. In C#, that <a href="/2018/03/22/functors">corresponds to the <code>Select</code> method</a>. </p> <p> <code>&lt;&gt;</code> is a generalised associative binary operation as defined by <a href="http://hackage.haskell.org/package/base/docs/Data-Semigroup.html">Data.Semigroup</a> or <a href="http://hackage.haskell.org/package/base/docs/Data-Monoid.html">Data.Monoid</a>. You can <a href="/2017/10/05/monoids-semigroups-and-friends">read more about monoids and semigroups here on the blog</a>. </p> <p> <a href="http://hackage.haskell.org/package/base/docs/Control-Applicative.html">&lt;*&gt;</a> is part of the <code>Applicative</code> type class. It's hard to translate to other languages, but <a href="/2018/10/01/applicative-functors">when I make the attempt</a>, I usually call it <code>Apply</code>. </p> </div> <div class="comment-date">2019-09-12 15:45 UTC</div> </div> </div> <hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/09/09/picture-archivist-in-haskell Naming newtypes for QuickCheck Arbitraries https://blog.ploeh.dk/2019/09/02/naming-newtypes-for-quickcheck-arbitraries/ Mon, 02 Sep 2019 13:07:00 UTC <div id="post"> <p> <em>A simple naming scheme for newtypes to add Arbitrary instances.</em> </p> <p> Naming is one of those recurring difficult problems in software development. How do you come up with good names? </p> <p> I'm not aware of any <em>general</em> heuristic for that, but sometimes, in specific contexts, a naming scheme presents itself. Here's one. </p> <h3 id="c7391ad662e943f1bbe2b52d6b8bde59"> Orphan instances <a href="#c7391ad662e943f1bbe2b52d6b8bde59" title="permalink">#</a> </h3> <p> When you write <a href="http://hackage.haskell.org/package/QuickCheck">QuickCheck</a> properties that involve your own custom types, you'll have to add <code>Arbitrary</code> instances for those types. As an example, here's a restaurant reservation record type: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;Reservation&nbsp;=&nbsp;Reservation &nbsp;&nbsp;{&nbsp;reservationId&nbsp;::&nbsp;UUID &nbsp;&nbsp;,&nbsp;reservationDate&nbsp;::&nbsp;LocalTime &nbsp;&nbsp;,&nbsp;reservationName&nbsp;::&nbsp;String &nbsp;&nbsp;,&nbsp;reservationEmail&nbsp;::&nbsp;String &nbsp;&nbsp;,&nbsp;reservationQuantity&nbsp;::&nbsp;Int &nbsp;&nbsp;}&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Show</span>,&nbsp;<span style="color:#2b91af;">Read</span>,&nbsp;<span style="color:#2b91af;">Generic</span>)</pre> </p> <p> You can easily add an Arbitrary instance to such a type: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Arbitrary</span>&nbsp;<span style="color:blue;">Reservation</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;arbitrary&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;liftM5&nbsp;Reservation&nbsp;arbitrary&nbsp;arbitrary&nbsp;arbitrary&nbsp;arbitrary&nbsp;arbitrary</pre> </p> <p> The type itself is part of your domain model, while the <code>Arbitrary</code> instance only belongs to your test code. You shouldn't add the <code>Arbitrary</code> instance to the domain model, but that means that you'll have to define the instance apart from the type definition. That, however, is an orphan instance, and the compiler will complain: </p> <p> <pre>test\ReservationAPISpec.hs:31:1: <span style="color:red;">warning:</span> [<span style="color:red;">-Worphans</span>] Orphan instance: instance Arbitrary Reservation To avoid this move the instance declaration to the module of the class or of the type, or wrap the type with a newtype and declare the instance on the new type. <span style="color:blue;">|</span> <span style="color:blue;">31 |</span> <span style="color:red;">instance Arbitrary Reservation where</span> <span style="color:blue;">|</span> <span style="color:red;">^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...</span></pre> </p> <p> Technically, this isn't a difficult problem to solve. The warning even suggests remedies. Moving the instance to the module that declares the type is, however, inappropriate, since test-specific instances don't belong in the domain model. Wrapping the type in a <code>newtype</code> is more appropriate, but what should you call the type? </p> <h3 id="c192d6524b4b4444a35121443f9a61a8"> Suppress the warning <a href="#c192d6524b4b4444a35121443f9a61a8" title="permalink">#</a> </h3> <p> I had trouble coming up with good names for such <code>newtype</code> wrappers, so at first I decided to just suppress that particular compiler warning. I simply added the <code>-fno-warn-orphans</code> flag <em>exclusively to my test code</em>. </p> <p> That solved the immediate problem, but I felt a little dirty. It's okay, though, because you're not supposed to reuse test libraries anyway, so the usual problems with orphan instances don't apply. </p> <p> After having worked a little like this, however, it dawned on me that I needed more than one <code>Arbitrary</code> instance, and a naming scheme presented itself. </p> <h3 id="a946b2c622c6403cb69a3f224551514c"> Naming scheme <a href="#a946b2c622c6403cb69a3f224551514c" title="permalink">#</a> </h3> <p> For some of the properties I wrote, I needed a <em>valid</em> <code>Reservation</code> value. In this case, <em>valid</em> means that the <code>reservationQuantity</code> is a positive number, and that the <code>reservationDate</code> is in the future. It seemed natural to signify these constraints with a <code>newtype</code>: </p> <p> <pre><span style="color:blue;">newtype</span>&nbsp;ValidReservation&nbsp;=&nbsp;ValidReservation&nbsp;Reservation&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Show</span>) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Arbitrary</span>&nbsp;<span style="color:blue;">ValidReservation</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;arbitrary&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;rid&nbsp;&lt;-&nbsp;arbitrary &nbsp;&nbsp;&nbsp;&nbsp;d&nbsp;&lt;-&nbsp;(\dt&nbsp;-&gt;&nbsp;addLocalTime&nbsp;(getPositive&nbsp;dt)&nbsp;now2019)&nbsp;&lt;$&gt;&nbsp;arbitrary &nbsp;&nbsp;&nbsp;&nbsp;n&nbsp;&lt;-&nbsp;arbitrary &nbsp;&nbsp;&nbsp;&nbsp;e&nbsp;&lt;-&nbsp;arbitrary &nbsp;&nbsp;&nbsp;&nbsp;(Positive&nbsp;q)&nbsp;&lt;-&nbsp;arbitrary &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;ValidReservation&nbsp;$&nbsp;Reservation&nbsp;rid&nbsp;d&nbsp;n&nbsp;e&nbsp;q</pre> </p> <p> The <code>newtype</code> is, naturally, called <code>ValidReservation</code> and can, for example, be used like this: </p> <p> <pre>it&nbsp;<span style="color:#a31515;">&quot;responds&nbsp;with&nbsp;200&nbsp;after&nbsp;reservation&nbsp;is&nbsp;added&quot;</span>&nbsp;$&nbsp;WQC.property&nbsp;$&nbsp;\ &nbsp;&nbsp;(ValidReservation&nbsp;r)&nbsp;-&gt;&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;_&nbsp;&lt;-&nbsp;postJSON&nbsp;<span style="color:#a31515;">&quot;/reservations&quot;</span>&nbsp;$&nbsp;encode&nbsp;r &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;get&nbsp;$&nbsp;<span style="color:#a31515;">&quot;/reservations/&quot;</span>&nbsp;&lt;&gt;&nbsp;toASCIIBytes&nbsp;(reservationId&nbsp;r) &nbsp;&nbsp;actual&nbsp;shouldRespondWith&nbsp;200</pre> </p> <p> For the few properties where <em>any</em> <code>Reservation</code> goes, a name for a <code>newtype</code> now also suggests itself: </p> <p> <pre><span style="color:blue;">newtype</span>&nbsp;AnyReservation&nbsp;=&nbsp;AnyReservation&nbsp;Reservation&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Eq</span>,&nbsp;<span style="color:#2b91af;">Show</span>) <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Arbitrary</span>&nbsp;<span style="color:blue;">AnyReservation</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;arbitrary&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;AnyReservation&nbsp;&lt;$&gt; &nbsp;&nbsp;&nbsp;&nbsp;liftM5&nbsp;Reservation&nbsp;arbitrary&nbsp;arbitrary&nbsp;arbitrary&nbsp;arbitrary&nbsp;arbitrary</pre> </p> <p> The only use I've had for that particular instance so far, though, is to ensure that any <code>Reservation</code> correctly serialises to, and deserialises from, JSON: </p> <p> <pre>it&nbsp;<span style="color:#a31515;">&quot;round-trips&quot;</span>&nbsp;$&nbsp;property&nbsp;$&nbsp;\(AnyReservation&nbsp;r)&nbsp;-&gt;&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;json&nbsp;=&nbsp;encode&nbsp;r &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;decode&nbsp;json &nbsp;&nbsp;actual&nbsp;shouldBe&nbsp;Just&nbsp;r</pre> </p> <p> With those two <code>newtype</code> wrappers, I no longer have any orphan instances. </p> <h3 id="758fef8609784b998c3fad65b2fe6e2f"> Summary <a href="#758fef8609784b998c3fad65b2fe6e2f" title="permalink">#</a> </h3> <p> A simple naming scheme for <code>newtype</code> wrappers for QuickCheck <code>Arbitrary</code> instances, then, is: <ul> <li>If the instance is truly unbounded, prefix the wrapper name with <em>Any</em></li> <li>If the instance only produces valid values, prefix the wrapper name with <em>Valid</em></li> </ul> This strikes me as a practical naming scheme. Other variations seem natural. If, for example, you need an <em>invalid</em> value, you can prefix the wrapper name with <em>Invalid</em>. Why you'd need that, though, I'm not sure. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/09/02/naming-newtypes-for-quickcheck-arbitraries Functional file system https://blog.ploeh.dk/2019/08/26/functional-file-system/ Mon, 26 Aug 2019 06:00:00 UTC <div id="post"> <p> <em>How do you model file systems in a functional manner, so that unit testing is enabled? An overview.</em> </p> <p> One of the many reasons that I like functional programming is that it's <a href="/2015/05/07/functional-design-is-intrinsically-testable">intrinsically testable</a>. In object-oriented programming, you often have to jump through hoops to enable testing. This is also the case whenever you need to interact with the computer's file system. Just try to search the web for <em>file system interface</em>, or <em>mock file system</em>. I'm not going to give you any links, because I think such questions are <a href="https://en.wikipedia.org/wiki/XY_problem">XY problems</a>. I don't think that the most common suggestions are proper solutions. </p> <p> In functional programming, anyway, <a href="/2017/01/30/partial-application-is-dependency-injection">Dependency Injection isn't functional, because it makes everything impure</a>. How, then, do you model the file system in such a way that it's pure, decoupled from the logic you'd like to add on top of it, and still has enough fidelity that you can perform most tasks? </p> <p> You model the file system as a tree, or a forest. </p> <h3 id="4920bedd948d4f7487a13fa96f836371"> File systems are hierarchies <a href="#4920bedd948d4f7487a13fa96f836371" title="permalink">#</a> </h3> <p> It should come as no surprise that file systems are hierarchies, or trees. Each logical drive is the root of a tree. Files are leaves, and directories are internal nodes. Does that sound familiar? That sounds like a <a href="/2019/07/29/church-encoded-rose-tree">rose tree</a>. </p> <p> Rose trees are immutable data structures. It doesn't get much more functional than that. Why not using a rose tree (or a forest) to model the file system? </p> <p> What about interaction with the actual file system? Usually, when you encounter object-oriented attempts at decoupling an abstraction from the actual file system, you'll find polymorphic operations such as <code>WriteAllText</code>, <code>GetFileSystemEntries</code>, <code>CreateDirectory</code>, and so on. These would be the (mockable) methods that you have to implement, usually as <a href="http://xunitpatterns.com/Humble%20Object.html">Humble Objects</a>. </p> <p> If you, instead of a set of interfaces, model the file system as a forest, interacting with the actual file system is not even part of the abstraction. That's a typical shift of perspective from object-oriented design to functional programming. </p> <p> <img src="/content/binary/ood-and-fp-views-on-fily-system-abstraction.png" alt="Object-oriented and functional ways to abstractly model file systems."> </p> <p> In object-oriented design, you typically attempt to model <em>data with behaviour</em>. Sometimes that fits the underlying reality well, but in this case it doesn't. While you have file and directory objects with behaviour, the actual structure of a file system is implicit. It's hidden in the interactions between the objects. </p> <p> By modelling the file system as a tree, you explicitly use the structure of the data. How you load a tree into program memory, or how you imprint a tree unto the file system isn't part of the abstraction. When it comes to input and output, you're free to do what you want. </p> <p> Once you have a model of a directory structure in memory, you can manipulate it to your heart's content. Since <a href="/2019/08/19/a-rose-tree-functor">rose trees are functors</a>, you know that all transformations are structure-preserving. That means that you don't even need to write tests for those parts of your application. </p> <p> You'll appreciate an example, I'm sure. </p> <h3 id="5e19438122b94e059c155509e96c964f"> Picture archivist example <a href="#5e19438122b94e059c155509e96c964f" title="permalink">#</a> </h3> <p> As an example, I'll attempt to answer <a href="https://codereview.stackexchange.com/q/99271/3878">an old Code Review question</a>. I already gave <a href="https://codereview.stackexchange.com/a/99290/3878">an answer</a> in 2015, but I'm not so happy with it today as I was back then. The question is great, though, because it explicitly demonstrates how people have a hard time escaping the notion that abstraction is only available via interfaces or abstract base classes. In 2015, I had long since figured out that <a href="/2009/05/28/DelegatesAreAnonymousInterfaces">delegates (and thus functions) are anonymous interfaces</a>, but I still hadn't figured out how to separate pure from impure behaviour. </p> <p> The question's scenario is how to implement a small program that can inspect a collection of image files, extract the date-taken metadata from each file, and move the files to a new directory structure based on that information. </p> <p> For example, you could have files organised in various directories according to motive. </p> <p> <img src="/content/binary/picture-archivist-source-directory.png" alt="Three example directories with pictures."> </p> <p> You soon realise, however, that that archiving strategy is untenable, because what do you do if there's more than one type of motive in a picture? Instead, you decide to organise the files according to month and year. </p> <p> <img src="/content/binary/picture-archivist-destination-directory.png" alt="Seven example directories with pictures."> </p> <p> Clearly, there's some input and output involved in this application, but there's also some logic that you'd like to unit test. You need to parse the metadata, figure out where to move each image file, filter out files that are not images, and so on. </p> <h3 id="e3bc8b23a3494628a44348749a0369ca"> Object-oriented picture archivist <a href="#e3bc8b23a3494628a44348749a0369ca" title="permalink">#</a> </h3> <p> If you were to implement such a picture archivist program with an object-oriented design, you may use Dependency Injection so that you can 'mock' the file system during unit testing. A typical program might then work like this at run time: </p> <p> <img src="/content/binary/object-oriented-file-system-interaction.png" alt="An object-oriented program typically has busy interaction with the file system."> </p> <p> The program has fine-grained, busy interaction with the file system (through a polymorphic interface). It'll typically read one file, load its metadata, decide where to put the file, and copy it there. Then it'll move on to the next file, although it might also do this in parallel. Throughout the program execution, there's input and output going on, which makes it difficult to isolate the pure from the impure code. </p> <p> Even if you write a program like that in <a href="https://fsharp.org">F#</a>, it's hardly a <a href="/2018/11/19/functional-architecture-a-definition">functional architecture</a>. </p> <p> Such an architecture is, in theory, testable, but my experience is that if you attempt to reproduce such busy, fine-grained interaction with mocks and stubs, you're likely to end up with brittle tests. </p> <h3 id="6cddf0e7ca3549c49a87006bfba5d349"> Functional picture archivist <a href="#6cddf0e7ca3549c49a87006bfba5d349" title="permalink">#</a> </h3> <p> In functional programming, you'll have to <a href="/2017/02/02/dependency-rejection">reject the notion of dependencies</a>. Instead, you can often resort to the simple architecture I call an <em>impure-pure-impure sandwich</em>; here, specifically: <ol> <li>Load data from disk (impure)</li> <li>Transform the data (pure)</li> <li>Write data to disk (impure)</li> </ol> A typical program might then work like this at run time: </p> <p> <img src="/content/binary/functional-file-system-interaction.png" alt="A functional program typically loads data, transforms it, and stores it again."> </p> <p> When the program starts, it loads data from disk into a tree. It then manipulates the in-memory model of the files in question, and once it's done, it traverses the entire tree and applies the changes. </p> <p> This gives you a much clearer separation between the pure and impure parts of the code base. The pure part is bigger, and easier to unit test. </p> <h3 id="09d2184be64a428d85b4f01f1149ea7a"> Example code <a href="#09d2184be64a428d85b4f01f1149ea7a" title="permalink">#</a> </h3> <p> This article gave you an overview of the functional architecture. In the next two articles, you'll see how to do this in practice. First, I'll implement the above architecture in <a href="https://www.haskell.org">Haskell</a>, so that we know that if it works there, the architecture does, indeed, respect <a href="/2018/11/19/functional-architecture-a-definition">the functional interaction law</a>. </p> <p> Based on the Haskell implementation, you'll then see a port to F#. <ul> <li><a href="/2019/09/09/picture-archivist-in-haskell">Picture archivist in Haskell</a></li> <li><a href="/2019/09/16/picture-archivist-in-f">Picture archivist in F#</a></li> </ul> These two articles share the same architecture. You can read both, or one of them, as you like. The source code is available on GitHub. </p> <h3 id="09e32b681b7a48aa808965bd66c4794b"> Summary <a href="#09e32b681b7a48aa808965bd66c4794b" title="permalink">#</a> </h3> <p> One of the hardest problems in transitioning from object-oriented programming to functional programming is that the design approach is so different. Many well-understood design patterns and principles don't translate easily. Dependency Injection is one of those. Often, you'll have to flip the model on its head, so to speak, before you can take it on in a functional manner. </p> <p> While most object-oriented programmers would say that object-oriented design involves focusing on 'the nouns', in practice, it often revolves around interactions and behaviour. Sometimes, that's appropriate, but often, it's not. </p> <p> Functional programming, in contrast, tends to take a more data-oriented perspective. Load some data, manipulate it, and publish it. If you can come up with an appropriate data structure for the data, you're probably on your way to implementing a functional architecture. </p> <p> <strong>Next:</strong> <a href="/2019/09/09/picture-archivist-in-haskell">Picture archivist in Haskell</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/08/26/functional-file-system A rose tree functor https://blog.ploeh.dk/2019/08/19/a-rose-tree-functor/ Mon, 19 Aug 2019 08:08:00 UTC <div id="post"> <p> <em>Rose trees form normal functors. A place-holder article for object-oriented programmers.</em> </p> <p> This article is an instalment in <a href="/2018/03/22/functors">an article series about functors</a>. As another article explains, <a href="/2019/08/12/rose-tree-bifunctor">a rose tree is a bifunctor</a>. This makes it trivially a functor. As such, this article is mostly a place-holder to fit the spot in the <em>functor table of contents</em>, thereby indicating that rose trees are functors. </p> <p> Since a rose tree is a bifunctor, it's actually not one, but two, functors. Many languages, C# included, are best equipped to deal with unambiguous functors. This is also true in <a href="https://haskell.org">Haskell</a>, where you'd usally define the <code>Functor</code> instance over a bifunctor's right, or second, side. Likewise, in C#, you can make <code>IRoseTree&lt;N, L&gt;</code> a functor by implementing <code>Select</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;&nbsp;Select&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&nbsp;source, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;&nbsp;selector) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;source.SelectLeaf(selector); }</pre> </p> <p> This method simply delegates all implementation to the <code>SelectLeaf</code> method; it's just <code>SelectLeaf</code> by another name. It obeys the functor laws, since these are just specializations of the bifunctor laws, and we know that a rose tree is a proper bifunctor. </p> <p> It would have been technically possible to instead implement a <code>Select</code> method by calling <code>SelectNode</code>, but it seems marginally more useful to enable syntactic sugar for mapping over the leaves. </p> <h3 id="134b75d98069421e9fe70a8630ac140f"> Menu example <a href="#134b75d98069421e9fe70a8630ac140f" title="permalink">#</a> </h3> <p> As an example, imagine that you're defining part of a menu bar for an old-fashioned desktop application. Perhaps you're even loading the structure of the menu from a text file. Doing so, you could create a simple tree that represents the <em>edit</em> menu: </p> <p> <pre><span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;editMenuTemplate&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(<span style="color:#a31515;">&quot;Edit&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(<span style="color:#a31515;">&quot;Find&nbsp;and&nbsp;Replace&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;Find&quot;</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;Replace&quot;</span>)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(<span style="color:#a31515;">&quot;Case&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;Upper&quot;</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;Lower&quot;</span>)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;Cut&quot;</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;Copy&quot;</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;Paste&quot;</span>));</pre> </p> <p> At this point, you have an <code>IRoseTree&lt;string, string&gt;</code>, so you might as well have used a <a href="/2018/08/06/a-tree-functor">'normal' tree</a> instead of a rose tree. The above template, however, is only a first step, because you have this <a href="https://en.wikipedia.org/wiki/Command_pattern">Command</a> class: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">Command</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;Command(<span style="color:blue;">string</span>&nbsp;name) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Name&nbsp;=&nbsp;name; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">string</span>&nbsp;Name&nbsp;{&nbsp;<span style="color:blue;">get</span>;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">virtual</span>&nbsp;<span style="color:blue;">void</span>&nbsp;Execute() &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> Apart from this base class, you also have classes that derive from it: <code>FindCommand</code>, <code>ReplaceCommand</code>, and so on. These classes override the <code>Execute</code> method by implenting <em>find</em>, <em>replace</em>, etc. functionality. Imagine that you also have a store or dictionary of these derived objects. This enables you to transform the template tree into a useful user menu: </p> <p> <pre><span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:#2b91af;">Command</span>&gt;&nbsp;editMenu&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">from</span>&nbsp;name&nbsp;<span style="color:blue;">in</span>&nbsp;editMenuTemplate &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">select</span>&nbsp;commandStore.Lookup(name);</pre> </p> <p> Notice how this transforms only the leaves, using the command store's <code>Lookup</code> method. This example uses C# query syntax, because this is what the <code>Select</code> method enables, but you could also have written the translation by just calling the <code>Select</code> method. </p> <p> The internal nodes in a menu have no behavious, so it makes little sense to attempt to turn them into <code>Command</code> objects as well. They're only there to provide structure to the menu. With a 'normal' tree, you wouldn't have been able to enrich only the leaves, while leaving the internal nodes untouched, but with a rose tree you can. </p> <p> The above example uses the <code>Select</code> method (via query syntax) to translate the nodes, thereby providing a demonstration of how to use the rose tree as the functor it is. </p> <h3 id="c77f1f9491b246f1bdb7c75d93eaa4ff"> Summary <a href="#c77f1f9491b246f1bdb7c75d93eaa4ff" title="permalink">#</a> </h3> <p> The <code>Select</code> doesn't implement any behaviour not already provided by <code>SelectLeaf</code>, but it enables C# query syntax. The C# compiler understands functors, but not bifunctors, so when you have a bifunctor, you might as well light up that language feature as well by adding a <code>Select</code> method. </p> <p> <strong>Next:</strong> <a href="/2018/08/13/a-visitor-functor">A Visitor functor</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/08/19/a-rose-tree-functor Rose tree bifunctor https://blog.ploeh.dk/2019/08/12/rose-tree-bifunctor/ Mon, 12 Aug 2019 10:33:00 UTC <div id="post"> <p> <em>A rose tree forms a bifunctor. An article for object-oriented developers.</em> </p> <p> This article is an instalment in <a href="/2018/12/24/bifunctors">an article series about bifunctors</a>. While the overview article explains that there's essentially two practically useful bifunctors, here's a third one. <a href="https://en.wikipedia.org/wiki/Rose_tree">rose trees</a>. </p> <h3 id="985e3bc5291c4f8ba98ce258e78f4ec8"> Mapping both dimensions <a href="#985e3bc5291c4f8ba98ce258e78f4ec8" title="permalink">#</a> </h3> <p> Like in the <a href="/2019/01/07/either-bifunctor">previous article on the Either bifunctor</a>, I'll start by implementing the simultaneous two-dimensional translation <code>SelectBoth</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N1</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;&nbsp;SelectBoth&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">N1</span>,&nbsp;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&nbsp;source, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">N1</span>&gt;&nbsp;selectNode, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;&nbsp;selectLeaf) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;source.Cata( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node:&nbsp;(n,&nbsp;branches)&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseNode</span>&lt;<span style="color:#2b91af;">N1</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;(selectNode(n),&nbsp;branches), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;leaf:&nbsp;l&nbsp;=&gt;&nbsp;(<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N1</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;)<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:#2b91af;">N1</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;(selectLeaf(l))); }</pre> </p> <p> This article uses the previously shown <a href="/2019/07/29/church-encoded-rose-tree">Church-encoded rose tree</a> and <a href="/2019/08/05/rose-tree-catamorphism">its catamorphism</a> <code>Cata</code>. </p> <p> In the <code>leaf</code> case, the <code>l</code> argument received by the lambda expression is an object of the type <code>L</code>, since the <code>source</code> tree is an <code>IRoseTree&lt;N, L&gt;</code> object; i.e. a tree with leaves of the type <code>L</code> and nodes of the type <code>N</code>. The <code>selectLeaf</code> argument is a function that converts an <code>L</code> object to an <code>L1</code> object. Since <code>l</code> is an <code>L</code> object, you can call <code>selectLeaf</code> with it to produce an <code>L1</code> object. You can use this resulting object to create a new <code>RoseLeaf&lt;N1, L1&gt;</code>. Keep in mind that while the <code>RoseLeaf</code> class requires two type arguments, it never requires an object of its <code>N</code> type argument, which means that you can create an object with any <em>node</em> type argument, including <code>N1</code>, even if you don't have an object of that type. </p> <p> In the <code>node</code> case, the lambda expression receives two objects: <code>n</code> and <code>branches</code>. The <code>n</code> object has the type <code>N</code>, while the <code>branches</code> object has the type <code>IEnumerable&lt;IRoseTree&lt;N1, L1&gt;&gt;</code>. In other words, the <code>branches</code> have already been translated to the desired result type. That's how the catamorphism works. This means that you only have to figure out how to translate the <code>N</code> object <code>n</code> to an <code>N1</code> object. The <code>selectNode</code> function argument can do that, so you can then create a new <code>RoseNode&lt;N1, L1&gt;</code> and return it. </p> <p> This works as expected: </p> <p> <pre>&gt; <span style="color:blue;">var</span>&nbsp;tree&nbsp;=&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(42),&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(1337)); &gt; tree RoseNode&lt;string, int&gt;("foo", IRoseTree&lt;string, int&gt;[2] { 42, 1337 }) &gt; tree.SelectBoth(s&nbsp;=&gt;&nbsp;s.Length,&nbsp;i&nbsp;=&gt;&nbsp;i.ToString()) RoseNode&lt;int, string&gt;(3, IRoseTree&lt;int, string&gt;[2] { "42", "1337" })</pre> </p> <p> This <em>C# Interactive</em> example shows how to convert a tree with internal string nodes and integer leaves to a tree of internal integer nodes and string leaves. The strings are converted to strings by counting their <code>Length</code>, while the integers are turned into strings using the standard <code>ToString</code> method available on all objects. </p> <h3 id="c0ea04cfe7d3412c86b9ba3953812025"> Mapping nodes <a href="#c0ea04cfe7d3412c86b9ba3953812025" title="permalink">#</a> </h3> <p> When you have <code>SelectBoth</code>, you can trivially implement the translations for each dimension in isolation. For <a href="/2018/12/31/tuple-bifunctor">tuple bifunctors</a>, I called these methods <code>SelectFirst</code> and <code>SelectSecond</code>, while for <a href="/2019/01/07/either-bifunctor">Either bifunctors</a>, I chose to name them <code>SelectLeft</code> and <code>SelectRight</code>. Continuing the trend of naming the translations after what they translate, instead of their positions, I'll name the corresponding methods here <code>SelectNode</code> and <code>SelectLeaf</code>. In <a href="https://www.haskell.org">Haskell</a>, the functions associated with <code>Data.Bifunctor</code> are always called <code>first</code> and <code>second</code>, but I see no reason to preserve such abstract naming in C#. In Haskell, these functions are part of the <code>Bifunctor</code> type class; the abstract names serve an actual purpose. This isn't the case in C#, so there's no reason to retain the abstract names. You might as well use names that communicate intent, which is what I've tried to do here. </p> <p> If you want to map only the internal nodes, you can implement a <code>SelectNode</code> method based on <code>SelectBoth</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N1</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&nbsp;SelectNode&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">N1</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&nbsp;source, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">N1</span>&gt;&nbsp;selector) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;source.SelectBoth(selector,&nbsp;l&nbsp;=&gt;&nbsp;l); }</pre> </p> <p> This simply uses the <code>l =&gt; l</code> lambda expression as an ad-hoc <em>identity</em> function, while passing <code>selector</code> as the <code>selectNode</code> argument to the <code>SelectBoth</code> method. </p> <p> You can use this to map the above <code>tree</code> to a tree made entirely of numbers: </p> <p> <pre>&gt; <span style="color:blue;">var</span>&nbsp;tree&nbsp;=&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(42),&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(1337)); &gt; tree.SelectNode(s =&gt; s.Length) RoseNode&lt;int, int&gt;(3, IRoseTree&lt;int, int&gt;[2] { 42, 1337 })</pre> </p> <p> Such a tree is, incidentally, isomorphic to a <a href="/2018/08/06/a-tree-functor">'normal' tree</a>. It might be a good exercise, if you need one, to demonstrate the isormorphism by writing functions that convert a <code>Tree&lt;T&gt;</code> into an <code>IRoseTree&lt;T, T&gt;</code>, and vice versa. </p> <h3 id="baa9136b506241e39e13639e43679b31"> Mapping leaves <a href="#baa9136b506241e39e13639e43679b31" title="permalink">#</a> </h3> <p> Similar to <code>SelectNode</code>, you can also trivially implement <code>SelectLeaf</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;&nbsp;SelectLeaf&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&nbsp;source, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">L1</span>&gt;&nbsp;selector) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;source.SelectBoth(n&nbsp;=&gt;&nbsp;n,&nbsp;selector); }</pre> </p> <p> This is another one-liner calling <code>SelectBoth</code>, with the difference that the identity function <code>n =&gt; n</code> is passed as the first argument, instead of as the last. This ensures that only <code>RoseLeaf</code> values are mapped: </p> <p> <pre>&gt; <span style="color:blue;">var</span>&nbsp;tree&nbsp;=&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(42),&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(1337)); &gt; tree.SelectLeaf(i =&gt; i % 2 == 0) RoseNode&lt;string, bool&gt;("foo", IRoseTree&lt;string, bool&gt;[2] { true, false })</pre> </p> <p> In the above <em>C# Interactive</em> session, the leaves are mapped to Boolean values, indicating whether they're even or odd. </p> <h3 id="afddb846bd244f4aa8f658fb5716b392"> Identity laws <a href="#afddb846bd244f4aa8f658fb5716b392" title="permalink">#</a> </h3> <p> Rose trees obey all the bifunctor laws. While it's formal work to prove that this is the case, you can get an intuition for it via examples. Often, I use a property-based testing library like <a href="https://fscheck.github.io/FsCheck">FsCheck</a> or <a href="https://github.com/hedgehogqa/fsharp-hedgehog">Hedgehog</a> to demonstrate (not prove) that laws hold, but in this article, I'll keep it simple and only cover each law with a parametrised test. </p> <p> <pre><span style="color:blue;">private</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">T</span>&nbsp;Id&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:#2b91af;">T</span>&nbsp;x)&nbsp;=&gt;&nbsp;x; <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:blue;">object</span>[]&gt;&nbsp;BifunctorLawsData { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">get</span> &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">yield</span>&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;&quot;</span>)&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">yield</span>&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;foo&quot;</span>)&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">yield</span>&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(42)&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">yield</span>&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(42,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;bar&quot;</span>))&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">yield</span>&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;exampleTree&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;} } [<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SelectNodeObeysFirstFunctorLaw(<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;t) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(t,&nbsp;t.SelectNode(Id)); }</pre> </p> <p> This test uses <a href="https://xunit.github.io">xUnit.net</a>'s <code>[Theory]</code> feature to supply a small set of example input values. The input values are defined by the <code>BifunctorLawsData</code> property, since I'll reuse the same values for all the bifunctor law demonstration tests. The <code>exampleTree</code> object is the tree shown in <a href="/2019/07/29/church-encoded-rose-tree">Church-encoded rose tree</a>. </p> <p> The tests also use the identity function implemented as a <code>private</code> function called <code>Id</code>, since C# doesn't come equipped with such a function in the Base Class Library. </p> <p> For all the <code>IRoseTree&lt;int, string&gt;</code> objects <code>t</code>, the test simply verifies that the original tree <code>t</code> is equal to the tree projected over the first axis with the <code>Id</code> function. </p> <p> Likewise, the first functor law applies when translating over the second dimension: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SelectLeafObeysFirstFunctorLaw(<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;t) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(t,&nbsp;t.SelectLeaf(Id)); }</pre> </p> <p> This is the same test as the previous test, with the only exception that it calls <code>SelectLeaf</code> instead of <code>SelectNode</code>. </p> <p> Both <code>SelectNode</code> and <code>SelectLeaf</code> are implemented by <code>SelectBoth</code>, so the real test is whether this method obeys the identity law: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SelectBothObeysIdentityLaw(<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;t) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(t,&nbsp;t.SelectBoth(Id,&nbsp;Id)); }</pre> </p> <p> Projecting over both dimensions with the identity function does, indeed, return an object equal to the input object. </p> <h3 id="bfaa0b763e5346c488f4bd9576ab894c"> Consistency law <a href="#bfaa0b763e5346c488f4bd9576ab894c" title="permalink">#</a> </h3> <p> In general, it shouldn't matter whether you map with <code>SelectBoth</code> or a combination of <code>SelectNode</code> and <code>SelectLeaf</code>: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;ConsistencyLawHolds(<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;t) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">DateTime</span>&nbsp;f(<span style="color:blue;">int</span>&nbsp;i)&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DateTime</span>(i); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">bool</span>&nbsp;g(<span style="color:blue;">string</span>&nbsp;s)&nbsp;=&gt;&nbsp;<span style="color:blue;">string</span>.IsNullOrWhiteSpace(s); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal(t.SelectBoth(f,&nbsp;g),&nbsp;t.SelectLeaf(g).SelectNode(f)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectNode(f).SelectLeaf(g), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectLeaf(g).SelectNode(f)); }</pre> </p> <p> This example creates two local functions <code>f</code> and <code>g</code>. The first function, <code>f</code>, creates a new <code>DateTime</code> object from an integer, using one of the <code>DateTime</code> constructor overloads. The second function, <code>g</code>, just delegates to <code>string.IsNullOrWhiteSpace</code>, although I want to stress that this is just an example. The law should hold for any two (<a href="https://en.wikipedia.org/wiki/Pure_function">pure</a>) functions. </p> <p> The test then verifies that you get the same result from calling <code>SelectBoth</code> as when you call <code>SelectNode</code> followed by <code>SelectLeaf</code>, or the other way around. </p> <h3 id="dd3046c49d564991bb47924b6e8e65fb"> Composition laws <a href="#dd3046c49d564991bb47924b6e8e65fb" title="permalink">#</a> </h3> <p> The composition laws insist that you can compose functions, or translations, and that again, the choice to do one or the other doesn't matter. Along each of the axes, it's just the second functor law applied. This parametrised test demonstrates that the law holds for <code>SelectNode</code>: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SecondFunctorLawHoldsForSelectNode(<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;t) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">char</span>&nbsp;f(<span style="color:blue;">bool</span>&nbsp;b)&nbsp;=&gt;&nbsp;b&nbsp;?&nbsp;<span style="color:#a31515;">&#39;T&#39;</span>&nbsp;:&nbsp;<span style="color:#a31515;">&#39;F&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">bool</span>&nbsp;g(<span style="color:blue;">int</span>&nbsp;i)&nbsp;=&gt;&nbsp;i&nbsp;%&nbsp;2&nbsp;==&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectNode(x&nbsp;=&gt;&nbsp;f(g(x))), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectNode(g).SelectNode(f)); }</pre> </p> <p> Here, <code>f</code> is a local function that returns the the character <code>'T'</code> for <code>true</code>, and <code>'F'</code> for <code>false</code>; <code>g</code> is the <em>even</em> function. The second functor law states that mapping <code>f(g(x))</code> in a single step is equivalent to first mapping over <code>g</code> and then map the result of that using <code>f</code>. </p> <p> The same law applies if you fix the first dimension and translate over the second: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SecondFunctorLawHoldsForSelectLeaf(<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;t) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">bool</span>&nbsp;f(<span style="color:blue;">int</span>&nbsp;x)&nbsp;=&gt;&nbsp;x&nbsp;%&nbsp;2&nbsp;==&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;g(<span style="color:blue;">string</span>&nbsp;s)&nbsp;=&gt;&nbsp;s.Length; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectLeaf(x&nbsp;=&gt;&nbsp;f(g(x))), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectLeaf(g).SelectLeaf(f)); }</pre> </p> <p> Here, <code>f</code> is the <em>even</em> function, whereas <code>g</code> is a local function that returns the length of a string. Again, the test demonstrates that the output is the same whether you map over an intermediary step, or whether you map using only a single step. </p> <p> This generalises to the composition law for <code>SelectBoth</code>: </p> <p> <pre>[<span style="color:#2b91af;">Theory</span>,&nbsp;<span style="color:#2b91af;">MemberData</span>(<span style="color:blue;">nameof</span>(BifunctorLawsData))] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;SelectBothCompositionLawHolds(<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;t) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">char</span>&nbsp;f(<span style="color:blue;">bool</span>&nbsp;b)&nbsp;=&gt;&nbsp;b&nbsp;?&nbsp;<span style="color:#a31515;">&#39;T&#39;</span>&nbsp;:&nbsp;<span style="color:#a31515;">&#39;F&#39;</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">bool</span>&nbsp;g(<span style="color:blue;">int</span>&nbsp;x)&nbsp;=&gt;&nbsp;x&nbsp;%&nbsp;2&nbsp;==&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">bool</span>&nbsp;h(<span style="color:blue;">int</span>&nbsp;x)&nbsp;=&gt;&nbsp;x&nbsp;%&nbsp;2&nbsp;==&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;i(<span style="color:blue;">string</span>&nbsp;s)&nbsp;=&gt;&nbsp;s.Length; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.Equal( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectBoth(x&nbsp;=&gt;&nbsp;f(g(x)),&nbsp;y&nbsp;=&gt;&nbsp;h(i(y))), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t.SelectBoth(g,&nbsp;i).SelectBoth(f,&nbsp;h)); }</pre> </p> <p> Again, whether you translate in one or two steps shouldn't affect the outcome. </p> <p> As all of these tests demonstrate, the bifunctor laws hold for rose trees. The tests only showcase five examples, but I hope it gives you an intuition how any rose tree is a bifunctor. After all, the <code>SelectNode</code>, <code>SelectLeaf</code>, and <code>SelectBoth</code> methods are all generic, and they behave the same for all generic type arguments. </p> <h3 id="a1a5dea3d85d4ed1a3ee3fb0a4dca820"> Summary <a href="#a1a5dea3d85d4ed1a3ee3fb0a4dca820" title="permalink">#</a> </h3> <p> Rose trees are bifunctors. You can translate the node and leaf dimension of a rose tree independently of each other, and the bifunctor laws hold for any pure translation, no matter how you compose the projections. </p> <p> As always, there can be performance differences between the various compositions, but the outputs will be the same regardless of composition. </p> <p> A functor, and by extension, a bifunctor, is a structure-preserving map. This means that any projection preserves the structure of the underlying container. For rose trees this means that the shape of the tree remains the same. The number of leaves remain the same, as does the number of internal nodes. </p> <p> <strong>Next:</strong> <a href="/2018/01/08/software-design-isomorphisms">Software design isomorphisms</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2019/08/12/rose-tree-bifunctor Rose tree catamorphism https://blog.ploeh.dk/2019/08/05/rose-tree-catamorphism/ Mon, 05 Aug 2019 08:30:00 UTC <div id="post"> <p> <em>The catamorphism for a tree with different types of nodes and leaves is made up from two 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 <a href="https://en.wikipedia.org/wiki/Rose_tree">rose 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 rose 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. The distinguishing feature from a rose tree and just any <a href="https://en.wikipedia.org/wiki/Tree_(data_structure)">tree</a> is that internal nodes can hold values of a different type than leaf values. </p> <p> <img src="/content/binary/rose-tree-example.png" alt="A rose tree example diagram, with internal nodes containing integers, and leafs containing strings."> </p> <p> The diagram shows an example of a tree of internal integers and leaf strings. All internal nodes contain integer values, and all leaves contain strings. Each node can have an arbitrary number of branches. </p> <h3 id="078386d5f3924a63add86ff199fd88d0"> C# catamorphism <a href="#078386d5f3924a63add86ff199fd88d0" title="permalink">#</a> </h3> <p> As a C# representation of a rose tree, I'll use the <a href="/2019/07/29/church-encoded-rose-tree">Church-encoded rose tree I've previously described</a>. The catamorphism is this extension method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">TResult</span>&nbsp;Cata&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&nbsp;tree, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;node, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;leaf) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;tree.Match( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node:&nbsp;(n,&nbsp;branches)&nbsp;=&gt;&nbsp;node(n,&nbsp;branches.Select(t&nbsp;=&gt;&nbsp;t.Cata(node,&nbsp;leaf))), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;leaf:&nbsp;leaf); }</pre> </p> <p> Like most of the other catamorphisms shown in this article series, this one consists of two functions. One that handles the <em>leaf</em> case, and one that handles the partially reduced <em>node</em> case. Compare it with the <a href="/2019/06/10/tree-catamorphism">tree catamorphism</a>: notice that the rose tree catamorphism's <code>node</code> function is identical to the the tree catamorphism. The <code>leaf</code> function, however, is new. </p> <p> In previous articles, you've seen other examples of catamorphisms for <a href="/2018/05/22/church-encoding">Church-encoded</a> types. The most common pattern has been that the Church encoding (the <code>Match</code> method) was also the catamorphism, with the <a href="/2019/05/13/peano-catamorphism">Peano catamorphism</a> being the only exception so far. When it comes to the Peano catamorphism, however, I'm not entirely confident that the difference between Church encoding and catamorphism is real, or whether it's just an artefact of the way I originally designed the Church encoding. </p> <p> When it comes to the present rose tree, however, notice that the catamorphisms is distinctly different from the Church encoding. That's the reason I called the method <code>Cata</code> instead of <code>Match</code>. </p> <p> The method simply delegates the <code>leaf</code> handler to <code>Match</code>, while it adds behaviour to the <code>node</code> case. It works the same way as for the 'normal' tree catamorphism. </p> <h3 id="87e2c79711c24c63a5ed82fbe4f7b581"> Examples <a href="#87e2c79711c24c63a5ed82fbe4f7b581" title="permalink">#</a> </h3> <p> You can use <code>Cata</code> to implement most other behaviour you'd like <code>IRoseTree&lt;N, L&gt;</code> to have. In a future article, you'll see how to <a href="/2019/08/12/rose-tree-bifunctor">turn the rose tree into a bifunctor</a> and <a href="/2019/08/19/a-rose-tree-functor">functor</a>, so here, we'll look at some other, more ad hoc, examples. As is also the case for the 'normal' tree, you can calculate the sum of all nodes, if you can associate a number with each node. </p> <p> Consider the example tree in the above diagram. You can create it as an <code>IRoseTree&lt;int, string&gt;</code> object like this: </p> <p> <pre><span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;exampleTree&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(42, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(1337, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;foo&quot;</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;bar&quot;</span>)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(2112, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(90125, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;baz&quot;</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;qux&quot;</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;quux&quot;</span>)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;quuz&quot;</span>)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;corge&quot;</span>));</pre> </p> <p> If you want to calculate a sum for a tree like that, you can use the integers for the internal nodes, and perhaps the length of the strings of the leaves. That hardly makes much sense, but is technically possible: </p> <p> <pre>&gt; exampleTree.Cata((x,&nbsp;xs)&nbsp;=&gt;&nbsp;x&nbsp;+&nbsp;xs.Sum(),&nbsp;x&nbsp;=&gt;&nbsp;x.Length) 93641</pre> </p> <p> Perhaps slightly more useful is to count the number of leaves: </p> <p> <pre>&gt; exampleTree.Cata((_,&nbsp;xs)&nbsp;=&gt;&nbsp;xs.Sum(),&nbsp;_&nbsp;=&gt;&nbsp;1) 7</pre> </p> <p> A leaf node has, by definition, exactly one leaf node, so the <code>leaf</code> lambda expression always returns <code>1</code>. In the <code>node</code> case, <code>xs</code> contains the partially summed leaf node count, so just <code>Sum</code> those together while ignoring the value of the internal node. </p> <p> You can also measure the maximum depth of the tree: </p> <p> <pre>&gt; exampleTree.Cata((_,&nbsp;xs)&nbsp;=&gt;&nbsp;1&nbsp;+&nbsp;xs.Max(),&nbsp;_&nbsp;=&gt;&nbsp;0) 3</pre> </p> <p> Consistent with the example for 'normal' trees, you can arbitrarily decide that the depth of a leaf node is <code>0</code>, so again, the <code>leaf</code> lambda expression just returns a constant value. The <code>node</code> lambda expression takes the <code>Max</code> of the partially reduced <code>xs</code> and adds <code>1</code>, since an internal node represents another level of depth in a tree. </p> <h3 id="9e673c50edc14c1790a9e89a67d069d1"> Rose tree F-Algebra <a href="#9e673c50edc14c1790a9e89a67d069d1" 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: </p> <p> <pre><span style="color:blue;">data</span>&nbsp;RoseTreeF&nbsp;a&nbsp;b&nbsp;c&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;NodeF&nbsp;{&nbsp;nodeValue&nbsp;::&nbsp;a,&nbsp;nodes&nbsp;::&nbsp;ListFix&nbsp;c&nbsp;} &nbsp;&nbsp;|&nbsp;LeafF&nbsp;{&nbsp;leafValue&nbsp;::&nbsp;b&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;">instance</span>&nbsp;<span style="color:blue;">Functor</span>&nbsp;(<span style="color:blue;">RoseTreeF</span>&nbsp;a&nbsp;b)&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 &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;_&nbsp;&nbsp;&nbsp;&nbsp;(LeafF&nbsp;x)&nbsp;=&nbsp;LeafF&nbsp;x</pre> </p> <p> Instead of using Haskell's standard list (<code>[]</code>) for the nodes, 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' types <code>a</code> and <code>b</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; RoseTreeF a b c -&gt; RoseTreeF a b 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 (RoseTreeF a b)</code>. To address that problem, you can introduce a <code>newtype</code> wrapper: </p> <p> <pre><span style="color:blue;">newtype</span>&nbsp;RoseTreeFix&nbsp;a&nbsp;b&nbsp;= &nbsp;&nbsp;RoseTreeFix&nbsp;{&nbsp;unRoseTreeFix&nbsp;::&nbsp;Fix&nbsp;(RoseTreeF&nbsp;a&nbsp;b)&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>Bifunctor</code>, <code>Bifoldable</code>, <code>Bitraversable</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>RoseTreeFix</code> values: </p> <p> <pre><span style="color:#2b91af;">roseLeafF</span>&nbsp;::&nbsp;b&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">RoseTreeFix</span>&nbsp;a&nbsp;b roseLeafF&nbsp;=&nbsp;RoseTreeFix&nbsp;.&nbsp;Fix&nbsp;.&nbsp;LeafF <span style="color:#2b91af;">roseNodeF</span>&nbsp;::&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">ListFix</span>&nbsp;(<span style="color:blue;">RoseTreeFix</span>&nbsp;a&nbsp;b)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">RoseTreeFix</span>&nbsp;a&nbsp;b roseNodeF&nbsp;x&nbsp;=&nbsp;RoseTreeFix&nbsp;.&nbsp;Fix&nbsp;.&nbsp;NodeF&nbsp;x&nbsp;.&nbsp;<span style="color:blue;">fmap</span>&nbsp;unRoseTreeFix</pre> </p> <p> <code>roseLeafF</code> creates a leaf node: </p> <p> <pre>Prelude Fix List RoseTree&gt; roseLeafF "ploeh" RoseTreeFix {unRoseTreeFix = Fix (LeafF "ploeh")}</pre> </p> <p> <code>roseNodeF</code> is a helper function to create internal nodes: </p> <p> <pre>Prelude Fix List RoseTree&gt; roseNodeF 6 (consF (roseLeafF 0) nilF) RoseTreeFix {unRoseTreeFix = Fix (NodeF 6 (ListFix (Fix (ConsF (Fix (LeafF 0)) (Fix NilF)))))}</pre> </p> <p> Even with helper functions, construction of <code>RoseTreeFix</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="0bfc3f600a9e43eea1026f1a4a3b7604"> Haskell catamorphism <a href="#0bfc3f600a9e43eea1026f1a4a3b7604" title="permalink">#</a> </h3> <p> At this point, you have two out of three elements of an F-Algebra. You have an endofunctor (<code>RoseTreeF a b</code>), and an object <code>c</code>, but you still need to find a morphism <code>RoseTreeF a b 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 any of the 'data types' <code>a</code> or <code>b</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> or <code>b</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>roseTreeF&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unRoseTreeFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;(NodeF&nbsp;x&nbsp;ns)&nbsp;=&nbsp;<span style="color:blue;">undefined</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;(LeafF&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>LeafF</code> case? You could pass a function argument to the <code>roseTreeF</code> function and use it with <code>x</code>: </p> <p> <pre>roseTreeF&nbsp;fl&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unRoseTreeFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;(NodeF&nbsp;x&nbsp;ns)&nbsp;=&nbsp;<span style="color:blue;">undefined</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;(LeafF&nbsp;x)&nbsp;=&nbsp;fl&nbsp;x</pre> </p> <p> While you could, technically, pass an argument of the type <code>c</code> to <code>roseTreeF</code> and then return that value from the <code>LeafF</code> case, that would mean that you would ignore the <code>x</code> value. This would be incorrect, so instead, make the argument a function and call it with <code>x</code>. Likewise, you can deal with the <code>NodeF</code> case in the same way: </p> <p> <pre><span style="color:#2b91af;">roseTreeF</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;(b&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">RoseTreeFix</span>&nbsp;a&nbsp;b&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;c roseTreeF&nbsp;fn&nbsp;fl&nbsp;=&nbsp;cata&nbsp;alg&nbsp;.&nbsp;unRoseTreeFix &nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;alg&nbsp;(NodeF&nbsp;x&nbsp;ns)&nbsp;=&nbsp;fn&nbsp;x&nbsp;ns &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alg&nbsp;&nbsp;&nbsp;&nbsp;(LeafF&nbsp;x)&nbsp;=&nbsp;fl&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>RoseTreeF</code>, the compiler infers that the <code>alg</code> function has the type <code>RoseTreeF a b 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 rose tree. As has been the most common pattern so far, it's a pair, made from two functions. It's still not the only possible catamorphism, since you could trivially flip the arguments to <code>roseTreeF</code>, or the arguments to <code>fn</code>. </p> <p> I've chosen the representation shown here because it's similar to the catamorphism I've shown for a 'normal' tree, just with the added function for leaves. </p> <h3 id="256fd0a09c4a4651b6c27b5626b0fb33"> Basis <a href="#256fd0a09c4a4651b6c27b5626b0fb33" title="permalink">#</a> </h3> <p> You can implement most other useful functionality with <code>roseTreeF</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;">RoseTreeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;bimap&nbsp;f&nbsp;s&nbsp;=&nbsp;roseTreeF&nbsp;(roseNodeF&nbsp;.&nbsp;f)&nbsp;(roseLeafF&nbsp;.&nbsp;s)</pre> </p> <p> Notice how naturally the catamorphism implements <code>bimap</code>. </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;">RoseTreeFix</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;=&nbsp;second</pre> </p> <p> You could probably also add <code>Applicative</code> and <code>Monad</code> instances, but I find those hard to grasp, so I'm going to skip them in favour of <code>Bifoldable</code>: </p> <p> <pre><span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Bifoldable</span>&nbsp;<span style="color:blue;">RoseTreeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;bifoldMap&nbsp;f&nbsp;=&nbsp;roseTreeF&nbsp;(\x&nbsp;xs&nbsp;-&gt;&nbsp;f&nbsp;x&nbsp;&lt;&gt;&nbsp;fold&nbsp;xs)</pre> </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;">RoseTreeFix</span>&nbsp;a)&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> takes two functions as arguments. 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>RoseTreeFix</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;">RoseTreeFix</span>&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;bitraverse&nbsp;f&nbsp;s&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;roseTreeF&nbsp;(\x&nbsp;xs&nbsp;-&gt;&nbsp;roseNodeF&nbsp;&lt;$&gt;&nbsp;f&nbsp;x&nbsp;&lt;*&gt;&nbsp;sequenceA&nbsp;xs)&nbsp;(<span style="color:blue;">fmap</span>&nbsp;roseLeafF&nbsp;.&nbsp;s)</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;">RoseTreeFix</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;sequenceA&nbsp;=&nbsp;bisequenceA&nbsp;.&nbsp;first&nbsp;pure</pre> </p> <p> That rose trees are <code>Traversable</code> turns out to be useful, as a future article will show. </p> <h3 id="c02950d3b4954435b384b1f7520d24d4"> Relationships <a href="#c02950d3b4954435b384b1f7520d24d4" title="permalink">#</a> </h3> <p> As was the case for 'normal' trees, the catamorphism for rose trees is more powerful than the <em>fold</em>. There are operations that you can express with the <code>Foldable</code> instance, but other operations 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>RoseTreeFix</code>, you can define that tree like this: </p> <p> <pre>exampleTree&nbsp;= &nbsp;&nbsp;roseNodeF&nbsp;42&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;consF&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;roseNodeF&nbsp;1337&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;consF&nbsp;(roseLeafF&nbsp;<span style="color:#a31515;">&quot;foo&quot;</span>)&nbsp;$&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;consF&nbsp;(roseLeafF&nbsp;<span style="color:#a31515;">&quot;bar&quot;</span>)&nbsp;nilF))&nbsp;$ &nbsp;&nbsp;&nbsp;&nbsp;consF&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;roseNodeF&nbsp;2112&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;consF&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;roseNodeF&nbsp;90125&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;consF&nbsp;(roseLeafF&nbsp;<span style="color:#a31515;">&quot;baz&quot;</span>)&nbsp;$&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;consF&nbsp;(roseLeafF&nbsp;<span style="color:#a31515;">&quot;qux&quot;</span>)&nbsp;$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;consF&nbsp;(roseLeafF&nbsp;<span style="color:#a31515;">&quot;quux&quot;</span>)&nbsp;nilF))&nbsp;$&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;consF&nbsp;(roseLeafF&nbsp;<span style="color:#a31515;">&quot;quuz&quot;</span>)&nbsp;nilF))&nbsp;$ &nbsp;&nbsp;&nbsp;&nbsp;consF&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;roseLeafF&nbsp;<span style="color:#a31515;">&quot;corge&quot;</span>) &nbsp;&nbsp;&nbsp;&nbsp;nilF)</pre> </p> <p> You can trivially calculate the sum of string lengths of all leaves, using only the <code>Foldable</code> instance: </p> <p> <pre>Prelude RoseTree&gt; sum $length &lt;$&gt; exampleTree 25</pre> </p> <p> You can also fairly easily calculate a sum of all nodes, using the length of the strings as in the above C# example, but that requires the <code>Bifoldable</code> instance: </p> <p> <pre>Prelude Data.Bifoldable Data.Semigroup RoseTree&gt; bifoldMap Sum (Sum . length) exampleTree Sum {getSum = 93641}</pre> </p> <p> Fortunately, we get the same result as above. </p> <p> Counting leaves, or measuring the depth of a tree, on the other hand, is impossible with the <code>Foldable</code> instance, but interestingly, it turns out that counting leaves is possible with the <code>Bifoldable</code> instance: </p> <p> <pre><span style="color:#2b91af;">countLeaves</span>&nbsp;::&nbsp;(<span style="color:blue;">Bifoldable</span>&nbsp;p,&nbsp;<span style="color:blue;">Num</span>&nbsp;n)&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;p&nbsp;a&nbsp;b&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;n countLeaves&nbsp;=&nbsp;getSum&nbsp;.&nbsp;bifoldMap&nbsp;(<span style="color:blue;">const</span>&nbsp;$&nbsp;Sum&nbsp;0)&nbsp;(<span style="color:blue;">const</span>&nbsp;$&nbsp;Sum&nbsp;1)</pre> </p> <p> This works well with the example tree: </p> <p> <pre>Prelude RoseTree&gt; countLeaves exampleTree 7</pre> </p> <p> Notice, however, that <code>countLeaves</code> works for any <code>Bifoldable</code> instance. Does that mean that you can 'count the leaves' of a tuple? Yes, it does: </p> <p> <pre>Prelude RoseTree&gt; countLeaves ("foo", "bar") 1 Prelude RoseTree&gt; countLeaves (1, 42) 1</pre> </p> <p> Or what about <code>EitherFix</code>: </p> <p> <pre>Prelude RoseTree Either&gt; countLeaves $leftF "foo" 0 Prelude RoseTree Either&gt; countLeaves$ rightF "bar" 1</pre> </p> <p> Notice that 'counting the leaves' of tuples always returns <code>1</code>, while 'counting the leaves' of <code>Either</code> always returns <code>0</code> for <code>Left</code> values, and <code>1</code> for <code>Right</code> values. This is because <code>countLeaves</code> considers the left, or <em>first</em>, data type to represent internal nodes, and the right, or <em>second</em>, data type to indicate leaves. </p> <p> You can further follow that train of thought to realise that you can convert both tuples and <code>EitherFix</code> values to small rose trees: </p> <p> <pre><span style="color:#2b91af;">fromTuple</span>&nbsp;::&nbsp;(a,&nbsp;b)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">RoseTreeFix</span>&nbsp;a&nbsp;b fromTuple&nbsp;(x,&nbsp;y)&nbsp;=&nbsp;roseNodeF&nbsp;x&nbsp;(consF&nbsp;(roseLeafF&nbsp;y)&nbsp;nilF) <span style="color:#2b91af;">fromEitherFix</span>&nbsp;::&nbsp;<span style="color:blue;">EitherFix</span>&nbsp;a&nbsp;b&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">RoseTreeFix</span>&nbsp;a&nbsp;b fromEitherFix&nbsp;=&nbsp;eitherF&nbsp;(roseNodeF&nbsp;nilF)&nbsp;roseLeafF</pre> </p> <p> The <code>fromTuple</code> function creates a small rose tree with one internal node and one leaf. The label of the internal node is the first value of the tuple, and the label of the leaf is the second value. Here's an example: </p> <p> <pre>Prelude RoseTree&gt; fromTuple ("foo", 42) RoseTreeFix {unRoseTreeFix = Fix (NodeF "foo" (ListFix (Fix (ConsF (Fix (LeafF 42)) (Fix NilF)))))}</pre> </p> <p> The <code>fromEitherFix</code> function turns a <em>left</em> value into an internal node with no leaves, and a <em>right</em> value into a leaf. Here are some examples: </p> <p> <pre>Prelude RoseTree Either&gt; fromEitherFix $leftF "foo" RoseTreeFix {unRoseTreeFix = Fix (NodeF "foo" (ListFix (Fix NilF)))} Prelude RoseTree Either&gt; fromEitherFix$ rightF 42 RoseTreeFix {unRoseTreeFix = Fix (LeafF 42)}</pre> </p> <p> While counting leaves can be implemented using <code>Bifoldable</code>, that's not the case for measuring the depths of trees (I think; leave a comment if you know of a way to do this with one of the instances shown here). You can, however, measure tree depth with the catamorphism: </p> <p> <pre><span style="color:#2b91af;">treeDepth</span>&nbsp;::&nbsp;<span style="color:blue;">RoseTreeFix</span>&nbsp;a&nbsp;b&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Integer</span> treeDepth&nbsp;=&nbsp;roseTreeF&nbsp;(\_&nbsp;xs&nbsp;-&gt;&nbsp;1&nbsp;+&nbsp;<span style="color:blue;">maximum</span>&nbsp;xs)&nbsp;(<span style="color:blue;">const</span>&nbsp;0)</pre> </p> <p> The implementation is similar to the implementation for 'normal' trees. I've arbitrarily decided that leaves have a depth of zero, so the function that handles leaves always returns <code>0</code>. The function that handles internal nodes receives <code>xs</code> as a partially reduced list of depths below the node in question. Take the maximum of those and add <code>1</code>, since each internal node has a depth of one. </p> <p> <pre>Prelude RoseTree&gt; treeDepth exampleTree 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="4276c6f8fab248c0acc52a7f14462e41"> Summary <a href="#4276c6f8fab248c0acc52a7f14462e41" title="permalink">#</a> </h3> <p> The catamorphism for rose trees is a pair of functions. One function transforms internal nodes with their partially reduced branches, while the other function transforms leaves. </p> <p> For a realistic example of using a rose tree in a real program, see <a href="/2019/09/09/picture-archivist-in-haskell">Picture archivist in Haskell</a>. </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/08/05/rose-tree-catamorphism Church-encoded rose tree https://blog.ploeh.dk/2019/07/29/church-encoded-rose-tree/ Mon, 29 Jul 2019 13:14:00 UTC <div id="post"> <p> <em>A rose tree is a tree with leaf nodes of one type, and internal nodes of another.</em> </p> <p> This article is part of <a href="/2018/05/22/church-encoding">a series of articles about Church encoding</a>. In the previous articles, you've seen <a href="/2018/06/04/church-encoded-maybe">how to implement a Maybe container</a>, and <a href="/2018/06/11/church-encoded-either">how to implement an Either container</a>. Through these examples, you've learned how to model <a href="https://en.wikipedia.org/wiki/Tagged_union">sum types</a> without explicit language support. In this article, you'll see how to model a <a href="https://en.wikipedia.org/wiki/Rose_tree">rose tree</a>. </p> <p> A rose 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. The distinguishing feature from a rose tree and just any <a href="https://en.wikipedia.org/wiki/Tree_(data_structure)">tree</a> is that internal nodes can hold values of a different type than leaf values. </p> <p> <img src="/content/binary/rose-tree-example.png" alt="A rose tree example diagram, with internal nodes containing integers, and leaves containing strings."> </p> <p> The diagram shows an example of a tree of internal integers and leaf strings. All internal nodes contain integer values, and all leaves contain strings. Each node can have an arbitrary number of branches. </p> <h3 id="5255946728c14810a5aaef3c1022d126"> Contract <a href="#5255946728c14810a5aaef3c1022d126" title="permalink">#</a> </h3> <p> In C#, you can represent the fundamental structure of a rose tree with a Church encoding, starting with an interface: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">interface</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt; { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">TResult</span>&nbsp;Match&lt;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&gt;,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;node, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;leaf); }</pre> </p> <p> The structure of a rose tree includes two mutually exclusive cases: internal nodes and leaf nodes. Since there's two cases, the <code>Match</code> method takes two arguments, one for each case. </p> <p> The interface is generic, with two type arguments: <code>N</code> (for <em>Node</em>) and <code>L</code> (for <em>leaf</em>). Any consumer of an <code>IRoseTree&lt;N, L&gt;</code> object must supply two functions when calling the <code>Match</code> method: a function that turns a node into a <code>TResult</code> value, and a function that turns a leaf into a <code>TResult</code> value. </p> <p> Both cases must have a corresponding implementation. </p> <h3 id="89c4833c4e4d46cc8eef2d5eb546f61d"> Leaves <a href="#89c4833c4e4d46cc8eef2d5eb546f61d" title="permalink">#</a> </h3> <p> The <em>leaf</em> implementation is the simplest: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">sealed</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&nbsp;:&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt; { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">L</span>&nbsp;value; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;RoseLeaf(<span style="color:#2b91af;">L</span>&nbsp;value) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.value&nbsp;=&nbsp;value; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">TResult</span>&nbsp;Match&lt;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&gt;,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;node, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;leaf) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;leaf(value); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">override</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;Equals(<span style="color:blue;">object</span>&nbsp;obj) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(!(obj&nbsp;<span style="color:blue;">is</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&nbsp;other)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">false</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;Equals(value,&nbsp;other.value); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">override</span>&nbsp;<span style="color:blue;">int</span>&nbsp;GetHashCode() &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;value.GetHashCode(); &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> The <code>RoseLeaf</code> class is an <a href="https://en.wikipedia.org/wiki/Adapter_pattern">Adapter</a> over a value of the generic type <code>L</code>. As is always the case with Church encoding, it implements the <code>Match</code> method by unconditionally calling one of the arguments, in this case the <code>leaf</code> function, with its adapted <code>value</code>. </p> <p> While it doesn't have to do this, it also overrides <code>Equals</code> and <code>GetHashCode</code>. This is an immutable class, so it's a great candidate to be a <a href="https://martinfowler.com/bliki/ValueObject.html">Value Object</a>. Making it a Value Object makes it easier to compare expected and actual values in unit tests, among other benefits. </p> <h3 id="f211476563fe40379eac66ee887ed75b"> Nodes <a href="#f211476563fe40379eac66ee887ed75b" title="permalink">#</a> </h3> <p> The <em>node</em> implementation is slightly more complex: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">sealed</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">RoseNode</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&nbsp;:&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt; { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">N</span>&nbsp;value; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&gt;&nbsp;branches; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;RoseNode(<span style="color:#2b91af;">N</span>&nbsp;value,&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&gt;&nbsp;branches) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.value&nbsp;=&nbsp;value; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.branches&nbsp;=&nbsp;branches; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">TResult</span>&nbsp;Match&lt;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&gt;,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;node, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;leaf) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;node(value,&nbsp;branches); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">override</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;Equals(<span style="color:blue;">object</span>&nbsp;obj) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(!(obj&nbsp;<span style="color:blue;">is</span>&nbsp;<span style="color:#2b91af;">RoseNode</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&nbsp;other)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">false</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;Equals(value,&nbsp;other.value) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&amp;&amp;&nbsp;<span style="color:#2b91af;">Enumerable</span>.SequenceEqual(branches,&nbsp;other.branches); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">override</span>&nbsp;<span style="color:blue;">int</span>&nbsp;GetHashCode() &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;value.GetHashCode()&nbsp;^&nbsp;branches.GetHashCode(); &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> A node contains both a value (of the type <code>N</code>) and a collection of sub-trees, or <code>branches</code>. The class implements the <code>Match</code> method by unconditionally calling the <code>node</code> function argument with its constituent values. </p> <p> Again, it overrides <code>Equals</code> and <code>GetHashCode</code> for the same reasons as <code>RoseLeaf</code>. This isn't required to implement Church encoding, but makes comparison and unit testing easier. </p> <h3 id="a5c04c7e127349ed9b759e6361af5ab3"> Usage <a href="#a5c04c7e127349ed9b759e6361af5ab3" title="permalink">#</a> </h3> <p> You can use the <code>RoseLeaf</code> and <code>RoseNode</code> constructors to create new trees, but it sometimes helps to have a static helper method to create values. It turns out that there's little value in a helper method for leaves, but for nodes, it's marginally useful: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&nbsp;Node&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;(<span style="color:#2b91af;">N</span>&nbsp;value,&nbsp;<span style="color:blue;">params</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;[]&nbsp;branches) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseNode</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;(value,&nbsp;branches); }</pre> </p> <p> This enables you to create tree objects, like this: </p> <p> <pre><span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;tree&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(42),&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(1337));</pre> </p> <p> That's a single node with the label <code>"foo"</code> and two leaves with the values <code>42</code> and <code>1337</code>, respectively. You can create the tree shown in the above diagram like this: </p> <p> <pre><span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;exampleTree&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(42, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(1337, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;foo&quot;</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;bar&quot;</span>)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(2112, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(90125, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;baz&quot;</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;qux&quot;</span>), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;quux&quot;</span>)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;quuz&quot;</span>)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;corge&quot;</span>));</pre> </p> <p> You can add various extension methods to implement useful functionality. In later articles, you'll see some more compelling examples, so here, I'm only going to show a few basic examples. One of the simplest features you can add is a method that will tell you if an <code>IRoseTree&lt;N, L&gt;</code> object is a node or a leaf: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IChurchBoolean</span>&nbsp;IsLeaf&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&nbsp;source) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;source.Match&lt;<span style="color:#2b91af;">IChurchBoolean</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node:&nbsp;(_,&nbsp;__)&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ChurchFalse</span>(), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;leaf:&nbsp;_&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ChurchTrue</span>()); } <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">IChurchBoolean</span>&nbsp;IsNode&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">N</span>,&nbsp;<span style="color:#2b91af;">L</span>&gt;&nbsp;source) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ChurchNot</span>(source.IsLeaf()); }</pre> </p> <p> Since this article is part of the overall article series on Church encoding, and the purpose of that article series is also to show how basic language features can be created from Church encodings, these two methods return <a href="/2018/05/24/church-encoded-boolean-values">Church-encoded Boolean values</a> instead of the built-in <code>bool</code> type. I'm sure you can imagine how you could change the type to <code>bool</code> if you'd like. </p> <p> You can use these methods like this: </p> <p> <pre>&gt; <span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">Guid</span>,&nbsp;<span style="color:blue;">double</span>&gt;&nbsp;tree&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:#2b91af;">Guid</span>,&nbsp;<span style="color:blue;">double</span>&gt;(-3.2); &gt; tree.IsLeaf() ChurchTrue { } &gt; tree.IsNode() ChurchNot(ChurchTrue) &gt; <span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:blue;">long</span>,&nbsp;<span style="color:blue;">string</span>&gt;&nbsp;tree&nbsp;=&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node&lt;<span style="color:blue;">long</span>,&nbsp;<span style="color:blue;">string</span>&gt;(42); &gt; tree.IsLeaf() ChurchFalse { } &gt; tree.IsNode() ChurchNot(ChurchFalse)</pre> </p> <p> In a <a href="/2019/09/16/picture-archivist-in-f">future article, you'll see some more compelling examples</a>. </p> <h3 id="3be01779f059443799df57342e2510cb"> Terminology <a href="#3be01779f059443799df57342e2510cb" title="permalink">#</a> </h3> <p> It's not entirely clear what to call a tree like the one shown here. <a href="https://en.wikipedia.org/wiki/Rose_tree">The Wikipedia entry</a> doesn't state one way or the other whether internal node types ought to be distinguishable from leaf node types, but there are <a href="https://twitter.com/kbattocchi/status/1072538730911752192">indications that this could be the case</a>. At least, it seems that the <a href="https://mail.haskell.org/pipermail/haskell-cafe/2015-May/119633.html">term isn't well-defined</a>, so I took the liberty to retcon the name <em>rose tree</em> to the data structure shown here. </p> <p> In the paper that introduces the <em>rose tree</em> term, Meertens writes: <blockquote> <p> "We consider trees whose internal nodes may fork into an arbitrary (natural) number of sub-trees. (If such a node has zero descendants, we still consider it internal.) Each external node carries a data item. No further information is stored in the tree; in particular, internal nodes are unlabelled." </p> <footer><cite><em>First Steps towards the Theory of Rose Trees</em>, Lambert Meertens, 1988</cite></footer> </blockquote> While the concept is foreign in C#, you can trivially introduce a <a href="/2018/01/15/unit-isomorphisms">unit</a> data type: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">Unit</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Unit</span>&nbsp;Instance&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Unit</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;Unit()&nbsp;{&nbsp;} }</pre> </p> <p> This enables you to create a rose tree according to Meertens' definition: </p> <p> <pre><span style="color:#2b91af;">IRoseTree</span>&lt;<span style="color:#2b91af;">Unit</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;meertensTree&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(<span style="color:#2b91af;">Unit</span>.Instance, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(<span style="color:#2b91af;">Unit</span>.Instance, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(<span style="color:#2b91af;">Unit</span>.Instance, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:#2b91af;">Unit</span>,&nbsp;<span style="color:blue;">int</span>&gt;(2112)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:#2b91af;">Unit</span>,&nbsp;<span style="color:blue;">int</span>&gt;(42), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:#2b91af;">Unit</span>,&nbsp;<span style="color:blue;">int</span>&gt;(1337), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:#2b91af;">Unit</span>,&nbsp;<span style="color:blue;">int</span>&gt;(90125)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RoseTree</span>.Node(<span style="color:#2b91af;">Unit</span>.Instance, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:#2b91af;">Unit</span>,&nbsp;<span style="color:blue;">int</span>&gt;(1984)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RoseLeaf</span>&lt;<span style="color:#2b91af;">Unit</span>,&nbsp;<span style="color:blue;">int</span>&gt;(666));</pre> </p> <p> Visually, you could draw it like this: </p> <p> <img src="/content/binary/meertens-tree-example.png" alt="A Meertens rose tree example diagram, with leaves containing integers."> </p> <p> Thus, the tree structure shown here seems to be a generalisation of Meertens' original definition. </p> <p> I'm not a mathematician, so I may have misunderstood some things. If you have a better name than <em>rose tree</em> for the data structure shown here, please leave a comment. </p> <h3 id="331fa8452cdd435c86ce87b5d39d51c5"> Yeats <a href="#331fa8452cdd435c86ce87b5d39d51c5" title="permalink">#</a> </h3> <p> Now that we're on the topic of <em>rose tree</em> as a term, you may, as a bonus, enjoy a similarly-titled poem: <blockquote> <h4>THE ROSE TREE</h4> <p> "O words are lightly spoken"<br> Said Pearse to Connolly,<br> "Maybe a breath of politic words<br> Has withered our Rose Tree;<br> Or maybe but a wind that blows<br> Across the bitter sea." </p> <p> "It needs to be but watered,"<br> James Connolly replied,<br> "To make the green come out again<br> And spread on every side,<br> And shake the blossom from the bud<br> To be the garden's pride."<br> </p> <p> "But where can we draw water"<br> Said Pearse to Connolly,<br> "When all the wells are parched away?<br> O plain as plain can be<br> There's nothing but our own red blood<br> Can make a right Rose Tree." </p> <footer><cite><a href="https://en.wikipedia.org/wiki/W._B._Yeats">W. B. Yeats</a></cite></footer> </blockquote> As far as I can tell, though, Yeats' metaphor is dissimilar to Meertens'. </p> <h3 id="9906b9a8856248f38b4f03e40252b761"> Summary <a href="#9906b9a8856248f38b4f03e40252b761" title="permalink">#</a> </h3> <p> You may occasionally find use for a tree that distinguishes between internal and leaf nodes. You can model such a tree with a Church encoding, as shown in this article. </p> <p> <strong>Next: </strong> <a href="/2019/04/29/catamorphisms">Catamorphisms</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/29/church-encoded-rose-tree Chain of Responsibility as catamorphisms https://blog.ploeh.dk/2019/07/22/chain-of-responsibility-as-catamorphisms/ Mon, 22 Jul 2019 14:11:00 UTC <div id="post"> <p> <em>The Chain of Responsibility design pattern can be viewed as a list fold over the First monoid, followed by a Maybe fold.</em> </p> <p> This article is part of <a href="/2018/03/05/some-design-patterns-as-universal-abstractions">a series of articles about specific design patterns and their category theory counterparts</a>. In it, you'll see how the <a href="https://en.wikipedia.org/wiki/Chain-of-responsibility_pattern">Chain of Responsibility design pattern</a> is equivalent to a succession of <a href="/2019/04/29/catamorphisms">catamorphisms</a>. First, you apply the <a href="/2018/04/03/maybe-monoids">First Maybe monoid</a> over the <a href="/2019/05/27/list-catamorphism">list catamorphism</a>, and then you conclude the reduction with the <a href="/2019/05/20/maybe-catamorphism">Maybe catamorphism</a>. </p> <h3 id="46a6c41949db446d9387c8befbf3fdb1"> Pattern <a href="#46a6c41949db446d9387c8befbf3fdb1" title="permalink">#</a> </h3> <p> The Chain of Responsibility design pattern gives you a way to model cascading conditionals with an object structure. It's a chain (or linked list) of objects that all implement the same interface (or base class). Each object (apart from the the last) has a reference to the next object in the list. </p> <p> <img src="/content/binary/chain-of-responsibility-diagram.png" alt="General diagram of the Chain of Responsibility design pattern."> </p> <p> A client (some other code) calls a method on the first object in the list. If that object can handle the request, it does so, and the interaction ends there. If the method returns a value, the object returns the value. </p> <p> If the first object determines that it can't handle the method call, it calls the next object in the chain. It only knows the next object as the interface, so the only way it can delegate the call is by calling the same method as the first one. In the above diagram, <em>Imp1</em> can't handle the method call, so it calls the same method on <em>Imp2</em>, which also can't handle the request and delegates responsibility to <em>Imp3</em>. In the diagram, <em>Imp3</em> can handle the method call, so it does so and returns a result that propagates back up the chain. In that particular example, <em>Imp4</em> never gets involved. </p> <p> You'll see an example below. </p> <p> One of the advantages of the pattern is that you can rearrange the chain to change its behaviour. You can even do this at run time, if you'd like, since all objects implement the same interface. </p> <h3 id="08a67dafd71f4bdd9a2e2577b0e43f9a"> User icon example <a href="#08a67dafd71f4bdd9a2e2577b0e43f9a" title="permalink">#</a> </h3> <p> Consider an online system that maintains user profiles for users. A user is modelled with the <code>User</code> class: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;User(<span style="color:blue;">int</span>&nbsp;id,&nbsp;<span style="color:blue;">string</span>&nbsp;name,&nbsp;<span style="color:blue;">string</span>&nbsp;email,&nbsp;<span style="color:blue;">bool</span>&nbsp;useGravatar,&nbsp;<span style="color:blue;">bool</span>&nbsp;useIdenticon)</pre> </p> <p> While I only show the signature of the class' constructor, it should be enough to give you an idea. If you need more details, the entire example code base is <a href="https://github.com/ploeh/UserProfile">available on GitHub</a>. </p> <p> Apart from an <code>id</code>, a <code>name</code> and <code>email</code> address, a user also has two flags. One flag tracks whether the user wishes to use his or her <a href="http://www.gravatar.com">Gravatar</a>, while another flag tracks if the user would like to use an <a href="https://en.wikipedia.org/wiki/Identicon">Identicon</a>. Obviously, both flags could be <code>true</code>, in which case the current business rule states that the Gravatar should take precedence. </p> <p> If none of the flags are set, users might still have a picture associated with their profile. This could be a picture that they've uploaded to the system, and is being tracked by a database. </p> <p> If no user icon can be found or generated, ultimately the system should use a fallback, default icon: </p> <p> <img src="/content/binary/default-user-icon.png" alt="Default user icon."> </p> <p> To summarise, the current rules are: <ol> <li>Use Gravatar if flag is set.</li> <li>Use Identicon if flag is set.</li> <li>Use uploaded picture if available.</li> <li>Use default icon.</li> </ol> The order of precedence could change in the future, new images sources could be added, or some of the present sources could be removed. Modelling this set of rules as a Chain of Responsibility makes it easy for you to reorder the rules, should you need to. </p> <p> To request an icon, a client can use the <code>IIconReader</code> interface: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">interface</span>&nbsp;<span style="color:#2b91af;">IIconReader</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Icon</span>&nbsp;ReadIcon(<span style="color:#2b91af;">User</span>&nbsp;user); }</pre> </p> <p> The <code>Icon</code> class is just a <a href="https://martinfowler.com/bliki/ValueObject.html">Value Object</a> wrapper around a URL. The idea is that such a URL can be used in an <code>img</code> tag to show the icon. Again, the full source code is available on GitHub if you'd like to investigate the details. </p> <p> The various rules for icon retrieval can be implemented using this interface. </p> <h3 id="b2a4cbfb576949c392ea0e0b3d440175"> Gravatar reader <a href="#b2a4cbfb576949c392ea0e0b3d440175" title="permalink">#</a> </h3> <p> Although you don't have to implement the classes in the order in which you are going to compose them, it seems natural to do so, starting with the Gravatar implementation. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">GravatarReader</span>&nbsp;:&nbsp;<span style="color:#2b91af;">IIconReader</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">IIconReader</span>&nbsp;next; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;GravatarReader(<span style="color:#2b91af;">IIconReader</span>&nbsp;next) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.next&nbsp;=&nbsp;next; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Icon</span>&nbsp;ReadIcon(<span style="color:#2b91af;">User</span>&nbsp;user) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(user.UseGravatar) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Icon</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Gravatar</span>(user.Email).Url); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;next.ReadIcon(user); &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> The <code>GravatarReader</code> class both implements the <code>IIconReader</code> interface, but also decorates another object of the same polymorphic type. If <code>user.UseGravatar</code> is <code>true</code>, it generates the appropriate Gravatar URL based on the user's <code>Email</code> address; otherwise, it delegates the work to the <code>next</code> object in the Chain of Responsibility. </p> <p> The <code>Gravatar</code> class contains the implementation details to generate the Gravatar <code>Url</code>. Again, please refer to the GitHub repository if you're interested in the details. </p> <h3 id="222ae025b264455695f1dbbd74cad17b"> Identicon reader <a href="#222ae025b264455695f1dbbd74cad17b" title="permalink">#</a> </h3> <p> When you compose the chain, according to the above business logic, the next type of icon you should attempt to generate is an Identicon. It's natural to implement the Identicon reader next, then: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">IdenticonReader</span>&nbsp;:&nbsp;<span style="color:#2b91af;">IIconReader</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">IIconReader</span>&nbsp;next; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;IdenticonReader(<span style="color:#2b91af;">IIconReader</span>&nbsp;next) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.next&nbsp;=&nbsp;next; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Icon</span>&nbsp;ReadIcon(<span style="color:#2b91af;">User</span>&nbsp;user) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(user.UseIdenticon) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Icon</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Uri</span>(baseUrl,&nbsp;HashUser(user))); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;next.ReadIcon(user); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Implementation&nbsp;details&nbsp;go&nbsp;here...</span> }</pre> </p> <p> Again, I'm omitting implementation details in order to focus on the Chain of Responsibility design pattern. If <code>user.UseIdenticon</code> is <code>true</code>, the <code>IdenticonReader</code> generates the appropriate Identicon and returns the URL for it; otherwise, it delegates the work to the <code>next</code> object in the chain. </p> <h3 id="e9f2904333b940c1a9a90522d19a41f3"> Database icon reader <a href="#e9f2904333b940c1a9a90522d19a41f3" title="permalink">#</a> </h3> <p> The <code>DBIconReader</code> class attempts to find an icon ID in a database. If it succeeds, it creates a URL corresponding to that ID. The assumption is that that resource exists; either it's a file on disk, or it's an image resource generated on the spot based on binary data stored in the database. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">DBIconReader</span>&nbsp;:&nbsp;<span style="color:#2b91af;">IIconReader</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">IUserRepository</span>&nbsp;repository; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">IIconReader</span>&nbsp;next; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;DBIconReader(<span style="color:#2b91af;">IUserRepository</span>&nbsp;repository,&nbsp;<span style="color:#2b91af;">IIconReader</span>&nbsp;next) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.repository&nbsp;=&nbsp;repository; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.next&nbsp;=&nbsp;next; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Icon</span>&nbsp;ReadIcon(<span style="color:#2b91af;">User</span>&nbsp;user) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(!repository.TryReadIconId(user.Id,&nbsp;<span style="color:blue;">out</span>&nbsp;<span style="color:blue;">string</span>&nbsp;iconId)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;next.ReadIcon(user); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;parameters&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Dictionary</span>&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;<span style="color:#a31515;">&quot;iconId&quot;</span>,&nbsp;iconId&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Icon</span>(urlTemplate.BindByName(baseUrl,&nbsp;parameters)); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">Uri</span>&nbsp;baseUrl&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Uri</span>(<span style="color:#a31515;">&quot;https://example.com&quot;</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">UriTemplate</span>&nbsp;urlTemplate&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">UriTemplate</span>(<span style="color:#a31515;">&quot;users/{iconId}/icon&quot;</span>); }</pre> </p> <p> This class demonstrates some variations in the way you can implement the Chain of Responsibility design pattern. The above <code>GravatarReader</code> and <code>IdenticonReader</code> classes both follow the same implementation pattern of checking a condition, and then performing work if the condition is <code>true</code>. The delegation to the next object in the chain happens, in those two classes, outside of the <code>if</code> statement. </p> <p> The <code>DBIconReader</code> class, on the other hand, reverses the structure of the code. It uses a <a href="https://refactoring.com/catalog/replaceNestedConditionalWithGuardClauses.html">Guard Clause</a> to detect whether to exit early, which is done by delegating work to the <code>next</code> object in the chain. </p> <p> If <code>TryReadIconId</code> returns <code>true</code>, however, the <code>ReadIcon</code> method proceeds to create the appropriate icon URL. </p> <p> Another variation on the Chain of Responsibility design pattern demonstrated by the <code>DBIconReader</code> class is that it takes a second dependency, apart from <code>next</code>. The <code>repository</code> is the usual misapplication of the Repository design pattern that everyone think they use correctly. Here, it's used in the common sense to provide access to a database. The main point, though, is that you can add as many other dependencies to a link in the chain as you'd like. All links, apart from the last, however, must have a reference to the <code>next</code> link in the chain. </p> <h3 id="cee40120578b4732892e6fd72329d5de"> Default icon reader <a href="#cee40120578b4732892e6fd72329d5de" title="permalink">#</a> </h3> <p> Like linked lists, a Chain of Responsibility has to ultimately terminate. You can use the following <code>DefaultIconReader</code> for that. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">DefaultIconReader</span>&nbsp;:&nbsp;<span style="color:#2b91af;">IIconReader</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Icon</span>&nbsp;ReadIcon(<span style="color:#2b91af;">User</span>&nbsp;user) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:#2b91af;">Icon</span>.Default; &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> This class unconditionally returns the <code>Default</code> icon. Notice that it doesn't have any <code>next</code> object it delegates to. This terminates the chain. If no previous implementation of the <code>IIconReader</code> has returned an <code>Icon</code> for the <code>user</code>, this one does. </p> <h3 id="8eb05bed2d98488a91c09bab52b00a53"> Chain composition <a href="#8eb05bed2d98488a91c09bab52b00a53" title="permalink">#</a> </h3> <p> With four implementations of <code>IIconReader</code>, you can now compose the Chain of Responsibility: </p> <p> <pre><span style="color:#2b91af;">IIconReader</span>&nbsp;reader&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">GravatarReader</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">IdenticonReader</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DBIconReader</span>(repo, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DefaultIconReader</span>())));</pre> </p> <p> The first link in the chain is a <code>GravatarReader</code> object that contains an <code>IdenticonReader</code> object as its <code>next</code> link, and so on. Referring back to the source code of <code>GravatarReader</code>, notice that its <code>next</code> dependency is declared as an <code>IIconReader</code>. Since the <code>IdenticonReader</code> class implements that interface, you can compose the chain like this, but if you later decide to change the order of the objects, you can do so simply by changing the composition. You could remove objects altogether, or add new classes, and you could even do this at run time, if required. </p> <p> The <code>DBIconReader</code> class requires an extra <code>IUserRepository</code> dependency, here simply an existing object called <code>repo</code>. </p> <p> The <code>DefaultIconReader</code> takes no other dependencies, so this effectively terminates the chain. If you try to pass another <code>IIconReader</code> to its constructor, the code doesn't compile. </p> <h3 id="fc1551665bb940b8ba5e75be81c0629a"> Haskell proof of concept <a href="#fc1551665bb940b8ba5e75be81c0629a" title="permalink">#</a> </h3> <p> When evaluating whether a design is <a href="/2018/11/19/functional-architecture-a-definition">a functional architecture</a>, I often port the relevant parts to <a href="https://www.haskell.org">Haskell</a>. You can do the same with the above example, and put it in a form where it's clearer that the Chain of Responsibility pattern is equivalent to two well-known catamorphisms. </p> <p> Readers not comfortable with Haskell can skip the next few sections. The object-oriented example continues below. </p> <p> <code>User</code> and <code>Icon</code> types are defined by types equivalent to above. There's no explicit interface, however. Creation of Gravatars and Identicons are both pure functions with the type <code>User -&gt; Maybe Icon</code>. Here's the Gravatar function, but the Identicon function looks similar: </p> <p> <pre><span style="color:#2b91af;">gravatarUrl</span>&nbsp;::&nbsp;<span style="color:#2b91af;">String</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">String</span> gravatarUrl&nbsp;email&nbsp;= &nbsp;&nbsp;<span style="color:#a31515;">&quot;https://www.gravatar.com/avatar/&quot;</span>&nbsp;++&nbsp;<span style="color:blue;">show</span>&nbsp;(hashString&nbsp;email&nbsp;::&nbsp;MD5Digest) <span style="color:#2b91af;">getGravatar</span>&nbsp;::&nbsp;<span style="color:blue;">User</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&nbsp;<span style="color:blue;">Icon</span> getGravatar&nbsp;u&nbsp;= &nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;useGravatar&nbsp;u &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">then</span>&nbsp;Just&nbsp;$&nbsp;Icon&nbsp;$&nbsp;gravatarUrl&nbsp;&nbsp;userEmail&nbsp;u &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span>&nbsp;Nothing</pre> </p> <p> Reading an icon ID from a database, however, is an impure operation, so the function to do this has the type <code>User -&gt; IO (Maybe Icon)</code>. </p> <h3 id="11adf8bd104d41fab9e6bcaef249210c"> Lazy I/O in Haskell <a href="#11adf8bd104d41fab9e6bcaef249210c" title="permalink">#</a> </h3> <p> Notice that the database icon-querying function has the return type <code>IO (Maybe Icon)</code>. In the introduction you read that the Chain of Responsibility design pattern is a sequence of catamorphisms - the first one over a list of <code>First</code> values. While <code>First</code> is, in itself, a <code>Semigroup</code> instance, it gives rise to a <code>Monoid</code> instance when combined with <code>Maybe</code>. Thus, to showcase the abstractions being used, you could create a list of <code>Maybe (First Icon)</code> values. This forms a <code>Monoid</code>, so is easy to fold. </p> <p> The problem with that, however, is that <code>IO</code> is strict under evaluation, so while it works, <a href="https://stackoverflow.com/q/47120384/126014">it's no longer lazy</a>. You can combine <code>IO (Maybe (First Icon))</code> values, but it leads to too much I/O activity. </p> <p> You can <a href="https://stackoverflow.com/q/47120384/126014">solve this problem with a newtype wrapper</a>: </p> <p> <pre><span style="color:blue;">newtype</span>&nbsp;FirstIO&nbsp;a&nbsp;=&nbsp;FirstIO&nbsp;(MaybeT&nbsp;IO&nbsp;a)&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Functor</span>,&nbsp;<span style="color:#2b91af;">Applicative</span>,&nbsp;<span style="color:#2b91af;">Monad</span>,&nbsp;<span style="color:#2b91af;">Alternative</span>) <span style="color:#2b91af;">firstIO</span>&nbsp;::&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;(<span style="color:#2b91af;">Maybe</span>&nbsp;a)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">FirstIO</span>&nbsp;a firstIO&nbsp;=&nbsp;FirstIO&nbsp;.&nbsp;MaybeT <span style="color:#2b91af;">getFirstIO</span>&nbsp;::&nbsp;<span style="color:blue;">FirstIO</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;(<span style="color:#2b91af;">Maybe</span>&nbsp;a) getFirstIO&nbsp;(FirstIO&nbsp;(MaybeT&nbsp;x))&nbsp;=&nbsp;x <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Semigroup</span>&nbsp;(<span style="color:blue;">FirstIO</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:#2b91af;">(&lt;&gt;)</span>&nbsp;=&nbsp;<span style="color:#2b91af;">(&lt;|&gt;)</span> <span style="color:blue;">instance</span>&nbsp;<span style="color:blue;">Monoid</span>&nbsp;(<span style="color:blue;">FirstIO</span>&nbsp;a)&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;mempty&nbsp;=&nbsp;empty</pre> </p> <p> This uses the <code>GeneralizedNewtypeDeriving</code> GHC extension to automatically make <code>FirstIO</code> <code>Functor</code>, <code>Applicative</code>, <code>Monad</code>, and <code>Alternative</code>. It also uses the <code>Alternative</code> instance to implement <code>Semigroup</code> and <code>Monoid</code>. You may recall from <a href="http://hackage.haskell.org/package/base/docs/Control-Applicative.html">the documentation</a> that <code>Alternative</code> is already a "monoid on applicative functors." </p> <h3 id="995f9ea8f8344aea93b2ffd0b3aad71f"> Alignment <a href="#995f9ea8f8344aea93b2ffd0b3aad71f" title="permalink">#</a> </h3> <p> You now have three functions with different types: two pure functions with the type <code>User -&gt; Maybe Icon</code> and one impure database-bound function with the type <code>User -&gt; IO (Maybe Icon)</code>. In order to have a common abstraction, you should align them so that all types match. At first glance, <code>User -&gt; IO (Maybe (First Icon))</code> seems like a type that fits all implementations, but that causes too much I/O to take place, so instead, use <code>User -&gt; FirstIO Icon</code>. Here's how to lift the pure <code>getGravatar</code> function: </p> <p> <pre><span style="color:#2b91af;">getGravatarIO</span>&nbsp;::&nbsp;<span style="color:blue;">User</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">FirstIO</span>&nbsp;<span style="color:blue;">Icon</span> getGravatarIO&nbsp;=&nbsp;firstIO&nbsp;.&nbsp;<span style="color:blue;">return</span>&nbsp;.&nbsp;getGravatar</pre> </p> <p> You can lift the other functions in similar fashion, to produce <code>getGravatarIO</code>, <code>getIdenticonIO</code>, and <code>getDBIconIO</code>, all with the mutual type <code>User -&gt; FirstIO Icon</code>. </p> <h3 id="f601a51f3006430398232e05b6595da0"> Haskell composition <a href="#f601a51f3006430398232e05b6595da0" title="permalink">#</a> </h3> <p> The goal of the Haskell proof of concept is to compose a function that can provide an <code>Icon</code> for any <code>User</code> - just like the above C# composition that uses Chain of Responsibility. There's, however, no way around impurity, because one of the steps involve a database, so the aim is a composition with the type <code>User -&gt; IO Icon</code>. </p> <p> While a more compact composition is possible, I'll show it in a way that makes the catamorphisms explicit: </p> <p> <pre><span style="color:#2b91af;">getIcon</span>&nbsp;::&nbsp;<span style="color:blue;">User</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;<span style="color:blue;">Icon</span> getIcon&nbsp;u&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;lazyIcons&nbsp;=&nbsp;<span style="color:blue;">fmap</span>&nbsp;(\f&nbsp;-&gt;&nbsp;f&nbsp;u)&nbsp;[getGravatarIO,&nbsp;getIdenticonIO,&nbsp;getDBIconIO] &nbsp;&nbsp;m&nbsp;&lt;-&nbsp;getFirstIO&nbsp;&nbsp;fold&nbsp;lazyIcons &nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;\$&nbsp;fromMaybe&nbsp;defaultIcon&nbsp;m</pre> </p> <p> The <code>getIcon</code> function starts with a list of all three functions. For each of them, it calls the function with the <code>User</code> value <code>u</code>. This may seem inefficient and redundant, because all three function calls may not be required, but since the return values are <code>FirstIO</code> values, all three function calls are lazily evaluated - even under <code>IO</code>. The result, <code>lazyIcons</code>, is a <code>[FirstIO Icon]</code> value; i.e. a lazily evaluated list of lazily evaluated values. </p> <p> This first step is just to put the potential values in a form that's recognisable. You can now <code>fold</code> the <code>lazyIcons</code> to a single <code>FirstIO Icon</code> value, and then use <code>getFirstIO</code> to unwrap it. Due to <code>do</code> notation, <code>m</code> is a <code>Maybe Icon</code> value. </p> <p> This is the first catamorphism. Granted, the generalisation that <code>fold</code> offers is not really required, since <code>lazyIcons</code> is a list; <code>mconcat</code> would have worked just as well. I did, however, choose to use <code>fold</code> (from <code>Data.Foldable</code>) to emphasise the point. While the <code>fold</code> function itself isn't the catamorphism for lists, we know that <a href="/2019/05/27/list-catamorphism">it's derived from the list catamorphism</a>. </p> <p> The final step is to utilise the Maybe catamorphism to reduce the <code>Maybe Icon</code> value to an <code>Icon</code> value. Again, the <code>getIcon</code> function doesn't use the Maybe catamorphism directly, but rather the derived <code>fromMaybe</code> function. The <a href="/2019/05/20/maybe-catamorphism">Maybe catamorphism</a> is the <code>maybe</code> function, but you can trivially implement <code>fromMaybe</code> with <code>maybe</code>. </p> <p> For <a href="https://en.wikipedia.org/wiki/Code_golf">golfers</a>, it's certainly possible to write this function in a more compact manner. Here's a <a href="https://en.wikipedia.org/wiki/Tacit_programming">point-free</a> version: </p> <p> <pre><span style="color:#2b91af;">getIcon</span>&nbsp;::&nbsp;<span style="color:blue;">User</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;<span style="color:blue;">Icon</span> getIcon&nbsp;= &nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;(fromMaybe&nbsp;defaultIcon)&nbsp;.&nbsp;getFirstIO&nbsp;.&nbsp;fold&nbsp;[getGravatarIO,&nbsp;getIdenticonIO,&nbsp;getDBIconIO]</pre> </p> <p> This alternative version utilises that <code>a -&gt; m</code> is a <code>Monoid</code> instance when <code>m</code> is a <code>Monoid</code> instance. That's the reason that you can <code>fold</code> a list of functions. The more explicit version above doesn't do that, but the behaviour is the same in both cases. </p> <p> That's all the Haskell code we need to discern the universal abstractions involved in the Chain of Responsibility design pattern. We can now return to the C# code example. </p> <h3 id="492ff50788784d7dbf6560ed08ed6bf7"> Chains as lists <a href="#492ff50788784d7dbf6560ed08ed6bf7" title="permalink">#</a> </h3> <p> The Chain of Responsibility design pattern is often illustrated like above, in a staircase-like diagram. There's, however, no inherent requirement to do so. You could also flatten the diagram: </p> <p> <img src="/content/binary/chain-of-responsibility-as-a-linked-list.png" alt="Chain of Responsibility illustrated as a linked list."> </p> <p> This looks a lot like a linked list. </p> <p> The difference is, however, that the terminator of a linked list is usually empty. Here, however, you have two types of objects. All objects apart from the rightmost object represent a <em>potential</em>. Each object may, or may not, handle the method call and produce an outcome; if an object can't handle the method call, it'll delegate to the next object in the chain. </p> <p> The rightmost object, however, is different. This object can't delegate any further, but <em>must</em> handle the method call. In the icon reader example, this is the <code>DefaultIconReader</code> class. </p> <p> Once you start to see most of the list as a list of potential values, you may realise that you'll be able to collapse into it a single potential value. This is possible because <a href="/2018/04/03/maybe-monoids">a list of values where you pick the first non-empty value forms a monoid</a>. This is sometimes called the <em>First</em> <a href="/2017/10/06/monoids">monoid</a>. </p> <p> In other words, you can reduce, or fold, all of the list, except the rightmost value, to a single potential value: </p> <p> <img src="/content/binary/chain-of-responsibility-as-a-linked-list-single-fold.png" alt="Chain of Responsibility illustrated as a linked list, with all but the rightmost objects folded to one."> </p> <p> When you do that, however, you're left with a single potential value. The result of folding most of the list is that you get the leftmost non-empty value in the list. There's no guarantee, however, that that value is non-empty. If all the values in the list are empty, the result is also empty. This means that you somehow need to combine a potential value with a value that's guaranteed to be present: the terminator. </p> <p> You can do that wither another fold: </p> <p> <img src="/content/binary/chain-of-responsibility-as-a-linked-list-double-fold.png" alt="Chain of Responsibility illustrated as a linked list, with two consecutive folds."> </p> <p> This second fold isn't a list fold, but rather a Maybe fold. </p> <h3 id="7632b9ff458d417fa49b1c65f7b198ed"> Maybe <a href="#7632b9ff458d417fa49b1c65f7b198ed" title="permalink">#</a> </h3> <p> The <em>First</em> monoid is a monoid over <a href="/2018/03/26/the-maybe-functor">Maybe</a>, so add a <code>Maybe</code> class to the code base. In Haskell, the catamorphism for Maybe is called <code>maybe</code>, but that's not a good method name in object-oriented design. Another option is some variation of <em>fold</em>, but in C#, this functionality tends to be called <code>Aggregate</code>, at least for <code>IEnumerable&lt;T&gt;</code>, so I'll reuse that terminology: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">TResult</span>&nbsp;Aggregate&lt;<span style="color:#2b91af;">TResult</span>&gt;(<span style="color:#2b91af;">TResult</span>&nbsp;@default,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;func) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(func&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>(func)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;hasItem&nbsp;?&nbsp;func(item)&nbsp;:&nbsp;@default; }</pre> </p> <p> You can implement another, more list-like <code>Aggregate</code> overload from this one, but for this article, you don't need it. </p> <h3 id="8b60d0c605d14cffbfa5e237cf26b7b2"> From TryReadIconId to Maybe <a href="#8b60d0c605d14cffbfa5e237cf26b7b2" title="permalink">#</a> </h3> <p> In the above code examples, <code>DBIconReader</code> depends on <code>IUserRepository</code>, which defined this method: </p> <p> <pre><span style="color:blue;">bool</span>&nbsp;TryReadIconId(<span style="color:blue;">int</span>&nbsp;userId,&nbsp;<span style="color:blue;">out</span>&nbsp;<span style="color:blue;">string</span>&nbsp;iconId);</pre> </p> <p> From <a href="/2019/07/15/tester-doer-isomorphisms">Tester-Doer isomorphisms</a> we know, however, that such a design is isomorphic to returning a Maybe value, and since that's more composable, do that: </p> <p> <pre><span style="color:#2b91af;">Maybe</span>&lt;<span style="color:blue;">string</span>&gt;&nbsp;ReadIconId(<span style="color:blue;">int</span>&nbsp;userId);</pre> </p> <p> This requires you to refactor the <code>DBIconReader</code> implementation of the <code>ReadIcon</code> method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Icon</span>&nbsp;ReadIcon(<span style="color:#2b91af;">User</span>&nbsp;user) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:blue;">string</span>&gt;&nbsp;mid&nbsp;=&nbsp;repository.ReadIconId(user.Id); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;&nbsp;lazyResult&nbsp;=&nbsp;mid.Aggregate( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@default:&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;(()&nbsp;=&gt;&nbsp;next.ReadIcon(user)), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;func:&nbsp;id&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;(()&nbsp;=&gt;&nbsp;CreateIcon(id))); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;lazyResult.Value; }</pre> </p> <p> A few things are worth a mention. Notice that the above <code>Aggregate</code> method (the Maybe catamorphism) requires you to supply a <code>@default</code> value (to be used if the Maybe object is empty). In the Chain of Responsibility design pattern, however, the fallback value is produced by calling the <code>next</code> object in the chain. If you do this unconditionally, however, you perform too much work. You're only supposed to call <code>next</code> if the current object can't handle the method call. </p> <p> The solution is to aggregate the <code>mid</code> object to a <code>Lazy&lt;Icon&gt;</code> and then return its <code>Value</code>. The <code>@default</code> value is now a lazy computation that calls <code>next</code> only if its <code>Value</code> is read. When <code>mid</code> is populated, on the other hand, the lazy computation calls the private <code>CreateIcon</code> method when <code>Value</code> is accessed. The private <code>CreateIcon</code> method contains the same logic as before the refactoring. </p> <p> This change of <code>DBIconReader</code> isn't strictly necessary in order to change the overall Chain of Responsibility to a pair of catamorphisms, but serves, I think, as a nice introduction to the use of the Maybe catamorphism. </p> <h3 id="ec329c8a0b70432d81d6f69e7084c13f"> Optional icon readers <a href="#ec329c8a0b70432d81d6f69e7084c13f" title="permalink">#</a> </h3> <p> Previously, the <code>IIconReader</code> interface <em>required</em> each implementation to return an <code>Icon</code> object: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">interface</span>&nbsp;<span style="color:#2b91af;">IIconReader</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Icon</span>&nbsp;ReadIcon(<span style="color:#2b91af;">User</span>&nbsp;user); }</pre> </p> <p> When you have an object like <code>GravatarReader</code> that may or may not return an <code>Icon</code>, this requirement leads toward the Chain of Responsibility design pattern. You can, however, shift the responsibility of what to do next by changing the interface: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">interface</span>&nbsp;<span style="color:#2b91af;">IIconReader</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;&nbsp;ReadIcon(<span style="color:#2b91af;">User</span>&nbsp;user); }</pre> </p> <p> An implementation like <code>GravatarReader</code> becomes simpler: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">GravatarReader</span>&nbsp;:&nbsp;<span style="color:#2b91af;">IIconReader</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;&nbsp;ReadIcon(<span style="color:#2b91af;">User</span>&nbsp;user) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(user.UseGravatar) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Icon</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Gravatar</span>(user.Email).Url)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;(); &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> No longer do you have to pass in a <code>next</code> dependency. Instead, you just return an empty <code>Maybe&lt;Icon&gt;</code> if you can't handle the method call. The same change applies to the <code>IdenticonReader</code> class. </p> <p> Since <a href="/2018/03/26/the-maybe-functor">Maybe is a functor</a>, and the <code>DBIconReader</code> already works on a <code>Maybe&lt;string&gt;</code> value, its implementation is greatly simplified: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;&nbsp;ReadIcon(<span style="color:#2b91af;">User</span>&nbsp;user) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;repository.ReadIconId(user.Id).Select(CreateIcon); }</pre> </p> <p> Since <code>ReadIconId</code> returns a <code>Maybe&lt;string&gt;</code>, you can simply use <code>Select</code> to transform the icon ID to an <code>Icon</code> object if the Maybe is populated. </p> <h3 id="94cac3b9e52e48c2a1768fd24c72e4bd"> Coalescing Composite <a href="#94cac3b9e52e48c2a1768fd24c72e4bd" title="permalink">#</a> </h3> <p> As an intermediate step, you can compose the various readers using a <a href="/2018/04/09/coalescing-composite-as-a-monoid">Coalescing Composite</a>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">CompositeIconReader</span>&nbsp;:&nbsp;<span style="color:#2b91af;">IIconReader</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">IIconReader</span>[]&nbsp;iconReaders; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;CompositeIconReader(<span style="color:blue;">params</span>&nbsp;<span style="color:#2b91af;">IIconReader</span>[]&nbsp;iconReaders) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.iconReaders&nbsp;=&nbsp;iconReaders; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;&nbsp;ReadIcon(<span style="color:#2b91af;">User</span>&nbsp;user) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">foreach</span>&nbsp;(<span style="color:blue;">var</span>&nbsp;iconReader&nbsp;<span style="color:blue;">in</span>&nbsp;iconReaders) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;mIcon&nbsp;=&nbsp;iconReader.ReadIcon(user); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(IsPopulated(mIcon)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;mIcon; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;(); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;IsPopulated&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;m) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;m.Aggregate(<span style="color:blue;">false</span>,&nbsp;_&nbsp;=&gt;&nbsp;<span style="color:blue;">true</span>); &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> I prefer a more explicit design over this one, so this is just an intermediate step. This <code>IIconReader</code> implementation composes an array of other <code>IIconReader</code> objects and queries each in order to return the first populated Maybe value it finds. If it doesn't find any populated value, it returns an empty Maybe object. </p> <p> You can now compose your <code>IIconReader</code> objects into a <a href="https://en.wikipedia.org/wiki/Composite_pattern">Composite</a>: </p> <p> <pre><span style="color:#2b91af;">IIconReader</span>&nbsp;reader&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">CompositeIconReader</span>( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">GravatarReader</span>(), &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">IdenticonReader</span>(), &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DBIconReader</span>(repo));</pre> </p> <p> While this gives you a single object on which you can call <code>ReadIcon</code>, the return value of that method is still a <code>Maybe&lt;Icon&gt;</code> object. You still need to reduce the <code>Maybe&lt;Icon&gt;</code> object to an <code>Icon</code> object. You can do this with a Maybe helper method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">T</span>&nbsp;GetValueOrDefault(<span style="color:#2b91af;">T</span>&nbsp;@default) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;Aggregate(@default,&nbsp;x&nbsp;=&gt;&nbsp;x); }</pre> </p> <p> Given a <code>User</code> object named <code>user</code>, you can now use the composition and the <code>GetValueOrDefault</code> method to get an <code>Icon</code> object: </p> <p> <pre><span style="color:#2b91af;">Icon</span>&nbsp;icon&nbsp;=&nbsp;reader.ReadIcon(user).GetValueOrDefault(<span style="color:#2b91af;">Icon</span>.Default);</pre> </p> <p> First you use the composed <code>reader</code> to produce a <code>Maybe&lt;Icon&gt;</code> object, and then you use the <code>GetValueOrDefault</code> method to reduce the <code>Maybe&lt;Icon&gt;</code> object to an <code>Icon</code> object. </p> <p> The latter of these two steps, <code>GetValueOrDefault</code>, is already based on the Maybe catamorphism, but the first step is still too implicit to clearly show the nature of what's actually going on. The next step is to refactor the Coalescing Composite to a list of monoidal values. </p> <h3 id="c75ce57c2b4f4315a93eaa91b653a370"> First <a href="#c75ce57c2b4f4315a93eaa91b653a370" title="permalink">#</a> </h3> <p> While not strictly necessary, you can introduce a <code>First&lt;T&gt;</code> wrapper: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">sealed</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">First</span>&lt;<span style="color:#2b91af;">T</span>&gt; { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;First(<span style="color:#2b91af;">T</span>&nbsp;item) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(item&nbsp;==&nbsp;<span style="color:blue;">null</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">throw</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ArgumentNullException</span>(<span style="color:blue;">nameof</span>(item)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Item&nbsp;=&nbsp;item; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">T</span>&nbsp;Item&nbsp;{&nbsp;<span style="color:blue;">get</span>;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">override</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;Equals(<span style="color:blue;">object</span>&nbsp;obj) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(!(obj&nbsp;<span style="color:blue;">is</span>&nbsp;<span style="color:#2b91af;">First</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;other)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="color:blue;">false</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;Equals(Item,&nbsp;other.Item); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:blue;">override</span>&nbsp;<span style="color:blue;">int</span>&nbsp;GetHashCode() &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;Item.GetHashCode(); &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> In this particular example, the <code>First&lt;T&gt;</code> class adds no new capabilities, so it's technically redundant. You could add to it methods to combine two <code>First&lt;T&gt;</code> objects into one (since <em>First</em> forms a <a href="/2017/11/27/semigroups">semigroup</a>), and perhaps a method or two to <a href="/2017/12/11/semigroups-accumulate">accumulate multiple values</a>, but in this article, none of those are required. </p> <p> While the class as shown above doesn't add any behaviour, I like that it signals intent, so I'll use it in that role. </p> <h3 id="c3feb40d90fc4d389fa0b3812abaa62c"> Lazy I/O in C# <a href="#c3feb40d90fc4d389fa0b3812abaa62c" title="permalink">#</a> </h3> <p> Like in the above Haskell code, you'll need to be able to combine two <code>First&lt;T&gt;</code> objects in a lazy fashion, in such a way that if the first object is populated, the I/O associated with producing the second value never happens. In Haskell I addressed that concern with a <code>newtype</code> that, among other abstractions, is a monoid. You can do the same in C# with an extension method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">First</span>&lt;<span style="color:#2b91af;">T</span>&gt;&gt;&gt;&nbsp;FindFirst&lt;<span style="color:#2b91af;">T</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">First</span>&lt;<span style="color:#2b91af;">T</span>&gt;&gt;&gt;&nbsp;m, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">First</span>&lt;<span style="color:#2b91af;">T</span>&gt;&gt;&gt;&nbsp;other) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;(m.Value.IsPopulated()) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;m; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;other; } <span style="color:blue;">private</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">bool</span>&nbsp;IsPopulated&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;m) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;m.Aggregate(<span style="color:blue;">false</span>,&nbsp;_&nbsp;=&gt;&nbsp;<span style="color:blue;">true</span>); }</pre> </p> <p> The <code>FindFirst</code> method returns the first (leftmost) non-empty object of two options. It's a lazy version of the <em>First</em> monoid, and <a href="/2019/04/15/lazy-monoids">that's still a monoid</a>. It's truly lazy because it never accesses the <code>Value</code> property on <code>other</code>. While it has to force evaluation of the first lazy computation, <code>m</code>, it doesn't have to evaluate <code>other</code>. Thus, whenever <code>m</code> is populated, <code>other</code> can remain non-evaluated. </p> <p> Since <a href="/2017/11/20/monoids-accumulate">monoids accumulate</a>, you can also write an extension method to implement that functionality: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">First</span>&lt;<span style="color:#2b91af;">T</span>&gt;&gt;&gt;&nbsp;FindFirst&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">First</span>&lt;<span style="color:#2b91af;">T</span>&gt;&gt;&gt;&gt;&nbsp;source) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;identity&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">First</span>&lt;<span style="color:#2b91af;">T</span>&gt;&gt;&gt;(()&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">First</span>&lt;<span style="color:#2b91af;">T</span>&gt;&gt;()); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;source.Aggregate(identity,&nbsp;(acc,&nbsp;x)&nbsp;=&gt;&nbsp;acc.FindFirst(x)); }</pre> </p> <p> This overload just uses the earlier <code>FindFirst</code> extension method to fold an arbitrary number of lazy <code>First&lt;T&gt;</code> objects into one. Notice that <code>Aggregate</code> is the C# name for the list catamorphisms. </p> <p> You can now compose the desired functionality using the basic building blocks of monoids, <a href="/2018/03/22/functors">functors</a>, and catamorphisms. </p> <h3 id="0fe80a69c74c463dacb8af0f86898518"> Composition from universal abstractions <a href="#0fe80a69c74c463dacb8af0f86898518" title="permalink">#</a> </h3> <p> The goal is still a function that takes a <code>User</code> object as input and produces an <code>Icon</code> object as output. While you could compose that functionality directly in-line where you need it, I think it may be helpful to package the composition in a <a href="https://en.wikipedia.org/wiki/Facade_pattern">Facade</a> object. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">IconReaderFacade</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">IIconReader</span>&gt;&nbsp;readers; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;IconReaderFacade(<span style="color:#2b91af;">IUserRepository</span>&nbsp;repository) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;readers&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">IIconReader</span>[] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">GravatarReader</span>(), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">IdenticonReader</span>(), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">DBIconReader</span>(repository) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Icon</span>&nbsp;ReadIcon(<span style="color:#2b91af;">User</span>&nbsp;user) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">First</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;&gt;&gt;&gt;&nbsp;lazyIcons&nbsp;=&nbsp;readers &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.Select(r&nbsp;=&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">First</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;&gt;&gt;(()&nbsp;=&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r.ReadIcon(user).Select(i&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">First</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;(i)))); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Lazy</span>&lt;<span style="color:#2b91af;">Maybe</span>&lt;<span style="color:#2b91af;">First</span>&lt;<span style="color:#2b91af;">Icon</span>&gt;&gt;&gt;&nbsp;m&nbsp;=&nbsp;lazyIcons.FindFirst(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;m.Value.Aggregate(<span style="color:#2b91af;">Icon</span>.Default,&nbsp;fi&nbsp;=&gt;&nbsp;fi.Item); &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> When you initialise an <code>IconReaderFacade</code> object, it creates an array of the desired <code>readers</code>. Whenever <code>ReadIcon</code> is invoked, it first transforms all those readers to a sequence of potential icons. All the values in the sequence are lazily evaluated, so in this step, nothing actually happens, even though it looks as though all readers' <code>ReadIcon</code> method gets called. The <code>Select</code> method is a structure-preserving map, so all readers are still potential producers of <code>Icon</code> objects. </p> <p> You now have an <code>IEnumerable&lt;Lazy&lt;Maybe&lt;First&lt;Icon&gt;&gt;&gt;&gt;</code>, which must be a good candidate for the prize for the <em>most nested generic .NET type of 2019</em>. It fits, though, the input type for the above <code>FindFirst</code> overload, so you can call that. The result is a single potential value <code>m</code>. That's the list catamorphism applied. </p> <p> Finally, you force evaluation of the lazy computation and apply the Maybe catamorphism (<code>Aggregate</code>). The <code>@default</code> value is <code>Icon.Default</code>, which gets returned if <code>m</code> turns out to be empty. When <code>m</code> is populated, you pull the <code>Item</code> out of the <code>First</code> object. In either case, you now have an <code>Icon</code> object to return. </p> <p> This composition has exactly the same behaviour as the initial Chain of Responsibility implementation, but is now composed from universal abstractions. </p> <h3 id="23819ca370344b94875ddbf5bde5aef3"> Summary <a href="#23819ca370344b94875ddbf5bde5aef3" title="permalink">#</a> </h3> <p> The Chain of Responsibility design pattern describes a flexible way to implement conditional logic. Instead of relying on keywords like <code>if</code> or <code>switch</code>, you can compose the conditional logic from polymorphic objects. This gives you several advantages. One is that you get better separations of concerns, which will tend to make it easier to refactor the code. Another is that it's possible to change the behaviour at run time, by moving the objects around. </p> <p> You can achieve a similar design, with equivalent advantages, by composing polymorphically similar functions in a list, map the functions to a list of potential values, and then use the list catamorphism to reduce many potential values to one. Finally, you apply the Maybe catamorphism to produce a value, even if the potential value is empty. </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/22/chain-of-responsibility-as-catamorphisms 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