ploeh blog https://blog.ploeh.dk danish software design en-us Mark Seemann Sat, 21 May 2022 05:59:38 UTC Sat, 21 May 2022 05:59:38 UTC The Identity monad https://blog.ploeh.dk/2022/05/16/the-identity-monad/ Mon, 16 May 2022 05:49:00 UTC <div id="post"> <p> <em>Probably one of the least useful monads. An article for object-oriented developers.</em> </p> <p> This article is an instalment in <a href="/2022/03/28/monads">an article series about monads</a>. </p> <p> <a href="/2018/09/03/the-identity-functor">The Identity functor</a> is another example of a functor that also forms a monad. Contrary to useful monads like <a href="/2022/04/19/the-list-monad">list</a>, <a href="/2022/04/25/the-maybe-monad">Maybe</a>, and <a href="/2022/05/09/an-either-monad">Either</a>, the Identity monad isn't particularly useful. In <a href="https://www.haskell.org">Haskell</a> it serves a few niche positions, for example when it comes to monad transformers. It's possible to define abstractions at a higher level in Haskell than it is in many other languages. Some of those abstractions involve monads. The Identity monad can plug into these abstractions as a 'do-nothing' monad, a bit like the <a href="https://en.wikipedia.org/wiki/Null_object_pattern">Null Object pattern</a> can supply a 'do-nothing' implementation of an interface. </p> <p> Other languages with which I'm proficient (C#, <a href="https://fsharp.org">F#</a>) don't enable that kind of abstraction, and I've never felt the need to actually <em>use</em> the Identity monad in those languages. Still, the Identity monad exists mathematically and conceptually, and it can be useful to know of that existence. This implies, like the Null Object pattern, that some abstractions can be simplified by 'plugging in' the Identity monad. The alternative would have had to involve some hand-waving about special cases. </p> <p> The code in this article continues the implementation shown in the article about <a href="/2018/09/03/the-identity-functor">the Identity functor</a>. </p> <h3 id="db0c7e97a3ee4477a96078c22cf89330"> SelectMany <a href="#db0c7e97a3ee4477a96078c22cf89330" title="permalink">#</a> </h3> <p> A monad must define either a <em>bind</em> or <em>join</em> function. In C#, monadic bind is called <code>SelectMany</code>. For <code>Identity&lt;T&gt;</code> the implementation is trivial: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;Identity&lt;TResult&gt;&nbsp;<span style="color:#74531f;">SelectMany</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;(Func&lt;T,&nbsp;Identity&lt;TResult&gt;&gt;&nbsp;<span style="color:#1f377f;">selector</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;selector(Item); }</pre> </p> <p> This is an instance method on <code>Identity&lt;T&gt;</code>, which means that the <code>Item</code> property has the type <code>T</code>. Since the <code>selector</code> return a new <code>Identity&lt;TResult&gt;</code>, the method can simply return that value. </p> <h3 id="9e4f558b6a7542148090044ab8e19060"> Query syntax <a href="#9e4f558b6a7542148090044ab8e19060" title="permalink">#</a> </h3> <p> As usual, you can implement C# query syntax with a boilerplate overload of <code>SelectMany</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;Identity&lt;TResult&gt;&nbsp;<span style="color:#74531f;">SelectMany</span>&lt;<span style="color:#2b91af;">U</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;T,&nbsp;Identity&lt;U&gt;&gt;&nbsp;<span style="color:#1f377f;">k</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;T,&nbsp;U,&nbsp;TResult&gt;&nbsp;<span style="color:#1f377f;">s</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;SelectMany(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;k(x).Select(<span style="color:#1f377f;">y</span>&nbsp;=&gt;&nbsp;s(x,&nbsp;y))); }</pre> </p> <p> The implementation is the same as in the previous articles in this article series. If it looks a little different than, say, the implementation for <a href="/2022/04/25/the-maybe-monad">the Maybe monad</a>, it's only because this <code>SelectMany</code> overload is an instance method, whereas the Maybe implementation is an extension method. </p> <p> Query syntax enables syntactic sugar like this: </p> <p> <pre>Identity&lt;<span style="color:blue;">int</span>&gt;&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&nbsp;<span style="color:blue;">from</span>&nbsp;x&nbsp;<span style="color:blue;">in</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Identity&lt;<span style="color:blue;">int</span>&gt;(39) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">from</span>&nbsp;y&nbsp;<span style="color:blue;">in</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Identity&lt;<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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">select</span>&nbsp;x&nbsp;+&nbsp;y.Length;</pre> </p> <p> The C# compiler infers that <code>x</code> is an <code>int</code> and <code>y</code> is a <code>string</code>. </p> <h3 id="9ee27fde0adc488b82f4c5ec358bc17c"> Flatten <a href="#9ee27fde0adc488b82f4c5ec358bc17c" title="permalink">#</a> </h3> <p> As <a href="/2022/03/28/monads">the monad introduction</a> also points out, if you have monadic bind (<code>SelectMany</code>) you can always implement a function to flatten a nested <a href="/2018/03/22/functors">functor</a>. This function is sometimes called <em>join</em> and sometimes (perhaps more intuitively) <em>flatten</em>. Here I've chosen to call it <code>Flatten</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Identity&lt;T&gt;&nbsp;<span style="color:#74531f;">Flatten</span>&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:blue;">this</span>&nbsp;Identity&lt;Identity&lt;T&gt;&gt;&nbsp;<span style="color:#1f377f;">source</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;source.SelectMany(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;x); }</pre> </p> <p> Even though the other methods shown so far have been instance methods, <code>Flatten</code> has to be an extension method, since the source is a nested <code>Identity&lt;Identity&lt;T&gt;&gt;</code>. There's no class of that specific type - only <code>Identity&lt;T&gt;</code>. </p> <p> If there's one useful aspect of the Identity monad, it may be that it reveals the concept of a nested functor in all its triviality: </p> <p> <pre>Identity&lt;Identity&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">nested</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;Identity&lt;Identity&lt;<span style="color:blue;">string</span>&gt;&gt;(<span style="color:blue;">new</span>&nbsp;Identity&lt;<span style="color:blue;">string</span>&gt;(<span style="color:#a31515;">&quot;bar&quot;</span>)); Identity&lt;<span style="color:blue;">string</span>&gt;&nbsp;<span style="color:#1f377f;">flattened</span>&nbsp;=&nbsp;nested.Flatten();</pre> </p> <p> Recall: A monad is a functor you can flatten. </p> <h3 id="be7d9a35a21a48498f469ae3a3357bc0"> Return <a href="#be7d9a35a21a48498f469ae3a3357bc0" title="permalink">#</a> </h3> <p> Apart from monadic bind, a monad must also define a way to put a normal value into the monad. Conceptually, I call this function <em>return</em> (because that's the name that Haskell uses). You don't, however, have to define a static method called <code>Return</code>. What's of importance is that the capability exists. For <code>Identity&lt;T&gt;</code> in C# the idiomatic way would be to use a constructor. This constructor does double duty as monadic <em>return</em>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Identity</span>(T&nbsp;<span style="color:#1f377f;">item</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Item&nbsp;=&nbsp;item; }</pre> </p> <p> In other words, <em>return</em> just wraps a value in the <code>Identity&lt;T&gt;</code> <a href="https://bartoszmilewski.com/2014/01/14/functors-are-containers">container</a>. </p> <h3 id="6bc314d479564086a2acd46dbccf44dd"> Left identity <a href="#6bc314d479564086a2acd46dbccf44dd" title="permalink">#</a> </h3> <p> We need to identify the <em>return</em> function in order to examine <a href="/2022/04/11/monad-laws">the monad laws</a>. Let's see what they look like for the Identity monad, starting with the left identity law. </p> <p> <pre>[Property(QuietOnSuccess&nbsp;=&nbsp;<span style="color:blue;">true</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">IdentityHasLeftIdentity</span>(Func&lt;<span style="color:blue;">int</span>,&nbsp;Identity&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">h</span>,&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Identity&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">@return</span>&nbsp;=&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;Identity&lt;<span style="color:blue;">int</span>&gt;(i); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(@return(a).SelectMany(h),&nbsp;h(a)); }</pre> </p> <p> This example is a bit different compared to the previous examples, since it uses <a href="https://fscheck.github.io/FsCheck/">FsCheck</a> 2.11.0 and <a href="https://xunit.net/">xUnit.net</a> 2.4.0. FScheck can generate arbitrary functions in addition to arbitrary values, so I've simply asked it to generate some arbitrary <code>h</code> functions. </p> <h3 id="b97ac93ff7d74d0ba165dc847f604d0d"> Right identity <a href="#b97ac93ff7d74d0ba165dc847f604d0d" title="permalink">#</a> </h3> <p> In a similar manner, we can showcase the right identity law as a test. </p> <p> <pre>[Property(QuietOnSuccess&nbsp;=&nbsp;<span style="color:blue;">true</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">IdentityHasRightIdentity</span>(Func&lt;<span style="color:blue;">string</span>,&nbsp;Identity&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">f</span>,&nbsp;<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Identity&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">@return</span>&nbsp;=&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;Identity&lt;<span style="color:blue;">int</span>&gt;(i); &nbsp;&nbsp;&nbsp;&nbsp;Identity&lt;<span style="color:blue;">int</span>&gt;&nbsp;<span style="color:#1f377f;">m</span>&nbsp;=&nbsp;f(a); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(m.SelectMany(@return),&nbsp;m); }</pre> </p> <p> As always, even a property-based test constitutes no <em>proof</em> that the law holds. I show it only to illustrate what the laws look like in 'real' code. </p> <h3 id="fc12cf871df6428fb9e14906e9c65707"> Associativity <a href="#fc12cf871df6428fb9e14906e9c65707" title="permalink">#</a> </h3> <p> The last monad law is the associativity law that describes how (at least) three functions compose. </p> <p> <pre>[Property(QuietOnSuccess&nbsp;=&nbsp;<span style="color:blue;">true</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">IdentityIsAssociative</span>( &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Identity&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">f</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;Identity&lt;<span style="color:blue;">byte</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">g</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">byte</span>,&nbsp;Identity&lt;TimeSpan&gt;&gt;&nbsp;<span style="color:#1f377f;">h</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Identity&lt;<span style="color:blue;">string</span>&gt;&nbsp;<span style="color:#1f377f;">m</span>&nbsp;=&nbsp;f(a); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(m.SelectMany(g).SelectMany(h),&nbsp;m.SelectMany(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;g(x).SelectMany(h))); }</pre> </p> <p> This property once more relies on FsCheck's ability to generate arbitrary <a href="https://en.wikipedia.org/wiki/Pure_function">pure functions</a>. </p> <h3 id="33f53ea7db964a62a542244b9de58499"> F# <a href="#33f53ea7db964a62a542244b9de58499" title="permalink">#</a> </h3> <p> While the <code>Identity</code> monad is built into the Haskell standard library, there's no Identity monad in F#. While it can be occasionally useful in Haskell, Identity is as useless in F# as it is in C#. Again, that doesn't imply that you can't define it. You can: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;Identity&lt;&#39;a&gt;&nbsp;=&nbsp;Identity&nbsp;<span style="color:blue;">of</span>&nbsp;&#39;a <span style="color:blue;">module</span>&nbsp;Identity&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Identity&lt;&#39;a&gt;&nbsp;-&gt;&nbsp;&#39;a</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;get&nbsp;(Identity&nbsp;x)&nbsp;=&nbsp;x &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b)&nbsp;-&gt;&nbsp;Identity&lt;&#39;a&gt;&nbsp;-&gt;&nbsp;Identity&lt;&#39;b&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;map&nbsp;f&nbsp;(Identity&nbsp;x)&nbsp;=&nbsp;Identity&nbsp;(f&nbsp;x) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;Identity&lt;&#39;b&gt;)&nbsp;-&gt;&nbsp;Identity&lt;&#39;a&gt;&nbsp;-&gt;&nbsp;Identity&lt;&#39;b&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;bind&nbsp;f&nbsp;(Identity&nbsp;x)&nbsp;:&nbsp;Identity&lt;_&gt;&nbsp;=&nbsp;f&nbsp;x</pre> </p> <p> Here I've repeated the functor implementation from <a href="/2018/09/03/the-identity-functor">the article about the Identity functor</a>, but now also included the <code>bind</code> function. </p> <p> You can use such a module to support syntactic sugar in the form of <a href="https://docs.microsoft.com/dotnet/fsharp/language-reference/computation-expressions">computation expressions</a>: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;IdentityBuilder()&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.Bind(x,&nbsp;f)&nbsp;=&nbsp;Identity.bind&nbsp;f&nbsp;x &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.Return&nbsp;x&nbsp;=&nbsp;Identity&nbsp;x &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.ReturnFrom&nbsp;x&nbsp;=&nbsp;x <span style="color:blue;">let</span>&nbsp;identity&nbsp;=&nbsp;IdentityBuilder&nbsp;()</pre> </p> <p> This enables you to write code like this: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;i&nbsp;=&nbsp;identity&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;x&nbsp;=&nbsp;Identity&nbsp;<span style="color:#a31515;">&quot;corge&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;y&nbsp;=&nbsp;Identity&nbsp;47 &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;y&nbsp;-&nbsp;x.Length&nbsp;}</pre> </p> <p> Here, <code>i</code> is a value of the type <code>Identity&lt;int&gt;</code>. </p> <h3 id="7b30db7a0912447c8b3aa6d9da8691e9"> Conclusion <a href="#7b30db7a0912447c8b3aa6d9da8691e9" title="permalink">#</a> </h3> <p> If the Identity monad is useful in languages like C# and F#, I have yet to encounter a use case. Even so, it exists. It is also, perhaps, the most naked illustration of what a functor and monad is. As such, I think it may be helpful to study. </p> <p> <strong>Next:</strong> The Lazy monad. </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/2022/05/16/the-identity-monad An Either monad https://blog.ploeh.dk/2022/05/09/an-either-monad/ Mon, 09 May 2022 06:30:00 UTC <div id="post"> <p> <em>The Either sum type forms a monad. An article for object-oriented programmers.</em> </p> <p> This article is an instalment in <a href="/2022/03/28/monads">an article series about monads</a>. </p> <p> The Either <a href="https://en.wikipedia.org/wiki/Tagged_union">sum type</a> is a useful data type that <a href="/2019/01/14/an-either-functor">forms a functor</a>. Actually, <a href="/2019/01/07/either-bifunctor">it forms two functors</a>. Like many other useful functors, it also forms a monad. Again, more than one monad is possible. In this article I'll focus on the 'usual' monad instance where mapping takes place over the right side. If you swap left and right, however, you can also define a monad that maps over the left side. Try it; it's a good exercise. </p> <p> <em>Either</em> is also known as <em>Result</em>, in which case <em>right</em> is usually called <em>success</em> or <em>OK</em>, while <em>left</em> is called <em>error</em> or <em>failure</em>. </p> <p> In this article, I'll base the C# implementation on the code from <a href="/2018/06/11/church-encoded-either">Church-encoded Either</a>. </p> <h3 id="d098a362e231405fb5a3b65cbc59e5f4"> Join <a href="#d098a362e231405fb5a3b65cbc59e5f4" title="permalink">#</a> </h3> <p> A monad must define either a <em>bind</em> or <em>join</em> function. As outlined in <a href="/2022/03/28/monads">the introduction to monads</a>, if you have one, you can use it to implement the other. For variety's sake, in this article series I do both. I also vary the names when there's no clear <a href="/2015/08/03/idiomatic-or-idiosyncratic">idiomatic</a> naming convention. For this version of Either, I've chosen to start with a method called <code>Join</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;IEither&lt;L,&nbsp;R&gt;&nbsp;<span style="color:#74531f;">Join</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">R</span>&gt;(<span style="color:blue;">this</span>&nbsp;IEither&lt;L,&nbsp;IEither&lt;L,&nbsp;R&gt;&gt;&nbsp;<span style="color:#1f377f;">source</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;source.Match( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;onLeft:&nbsp;&nbsp;<span style="color:#1f377f;">l</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;Left&lt;L,&nbsp;R&gt;(l), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;onRight:&nbsp;<span style="color:#1f377f;">r</span>&nbsp;=&gt;&nbsp;r); }</pre> </p> <p> This method flattens a nested Either value. If the outer Either is a <em>left</em> case, the method returns a <code>new Left&lt;L, R&gt;(l)</code> value, which fits the required return type. If the outer Either is a <em>right</em> case, it contains another, nested Either value that it can return. </p> <p> As already described in the article <a href="/2018/06/11/church-encoded-either">Church-encoded Either</a>, you can use Either values instead of exceptions. While that article already gives an example, the Either in that value isn't nested. This, however, can easily happen when you try to compose calculations that may fail. Another example may involve parsing. Here are two simple parsers: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;IEither&lt;<span style="color:blue;">string</span>,&nbsp;DateTime&gt;&nbsp;<span style="color:#74531f;">TryParseDate</span>(<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">candidate</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(DateTime.TryParse(candidate,&nbsp;<span style="color:blue;">out</span>&nbsp;var&nbsp;<span style="color:#1f377f;">d</span>)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Right&lt;<span style="color:blue;">string</span>,&nbsp;DateTime&gt;(d); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">else</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Left&lt;<span style="color:blue;">string</span>,&nbsp;DateTime&gt;(candidate); } <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;IEither&lt;<span style="color:blue;">string</span>,&nbsp;TimeSpan&gt;&nbsp;<span style="color:#74531f;">TryParseDuration</span>(<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">candidate</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(TimeSpan.TryParse(candidate,&nbsp;<span style="color:blue;">out</span>&nbsp;var&nbsp;<span style="color:#1f377f;">ts</span>)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Right&lt;<span style="color:blue;">string</span>,&nbsp;TimeSpan&gt;(ts); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">else</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Left&lt;<span style="color:blue;">string</span>,&nbsp;TimeSpan&gt;(candidate); }</pre> </p> <p> These functions try to <a href="https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-validate/">parse candidate values to more structured data types</a>. If parsing fails, they return the <a href="/2020/11/30/name-by-role">candidate value</a> so that calling code may get a chance to inspect and report the string that caused a failure. What happens if you try to compose these two functions? </p> <p> <pre>IEither&lt;<span style="color:blue;">string</span>,&nbsp;DateTime&gt;&nbsp;<span style="color:#1f377f;">dt</span>&nbsp;=&nbsp;TryParseDate(<span style="color:#a31515;">&quot;2022-03-21&quot;</span>); IEither&lt;<span style="color:blue;">string</span>,&nbsp;TimeSpan&gt;&nbsp;<span style="color:#1f377f;">ts</span>&nbsp;=&nbsp;TryParseDuration(<span style="color:#a31515;">&quot;2&quot;</span>); IEither&lt;<span style="color:blue;">string</span>,&nbsp;IEither&lt;<span style="color:blue;">string</span>,&nbsp;DateTime&gt;&gt;&nbsp;<span style="color:#1f377f;">nested</span>&nbsp;=&nbsp;dt.Select(<span style="color:#1f377f;">d</span>&nbsp;=&gt;&nbsp;ts.Select(<span style="color:#1f377f;">dur</span>&nbsp;=&gt;&nbsp;d&nbsp;+&nbsp;dur));</pre> </p> <p> Composing the results of these two functions produces a nested result that you can flatten with <code>Join</code>: </p> <p> <pre>IEither&lt;<span style="color:blue;">string</span>,&nbsp;DateTime&gt;&nbsp;<span style="color:#1f377f;">flattened</span>&nbsp;=&nbsp;nested.Join();</pre> </p> <p> Using <code>Join</code> for that purpose is, however, often awkward, so a better option is to flatten as you go. </p> <h3 id="2ae2ab4c8dea429cae52de32dd5c3a2d"> SelectMany <a href="#2ae2ab4c8dea429cae52de32dd5c3a2d" title="permalink">#</a> </h3> <p> Monadic bind (in C# called <code>SelectMany</code>) enables you to flatten as you go. As also shown in <a href="/2022/03/28/monads">the monad introduction</a>, if you already have <code>Join</code> you can always implement <code>SelectMany</code> like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;IEither&lt;L,&nbsp;R1&gt;&nbsp;<span style="color:#74531f;">SelectMany</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">R</span>,&nbsp;<span style="color:#2b91af;">R1</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;IEither&lt;L,&nbsp;R&gt;&nbsp;<span style="color:#1f377f;">source</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;R,&nbsp;IEither&lt;L,&nbsp;R1&gt;&gt;&nbsp;<span style="color:#1f377f;">selector</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;source.Select(selector).Join(); }</pre> </p> <p> The <code>SelectMany</code> method makes the above composition a little easier: </p> <p> <pre>IEither&lt;<span style="color:blue;">string</span>,&nbsp;DateTime&gt;&nbsp;<span style="color:#1f377f;">result</span>&nbsp;=&nbsp;dt.SelectMany(<span style="color:#1f377f;">d</span>&nbsp;=&gt;&nbsp;ts.Select(<span style="color:#1f377f;">dur</span>&nbsp;=&gt;&nbsp;d&nbsp;+&nbsp;dur));</pre> </p> <p> Instead of having to flatten a nested result, you can flatten as you go. I think that <a href="https://www.scala-lang.org/">Scala</a>'s <code>flatMap</code> is a better name for that operation than <code>SelectMany</code>, but the behaviour is the same. If you're wondering why it's called <code>SelectMany</code>, see my attempt at an explanation in the article about the <a href="/2022/04/19/the-list-monad">list monad</a>. The name makes modest sense in that context, but in the context of Either, that meaning is lost. </p> <h3 id="cfe7b3b6f8104ec5b766407eacaaa458"> Query syntax <a href="#cfe7b3b6f8104ec5b766407eacaaa458" title="permalink">#</a> </h3> <p> Perhaps you still find the above composition awkward. After all, you have to nest a <code>Select</code> inside a <code>SelectMany</code>. Is there a simpler way? </p> <p> One option is to use query syntax, but in order to do that, you must (again as outlined in the <a href="/2022/03/28/monads">monad introduction</a>) add a special boilerplate <code>SelectMany</code> overload: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;IEither&lt;L,&nbsp;R1&gt;&nbsp;<span style="color:#74531f;">SelectMany</span>&lt;<span style="color:#2b91af;">L</span>,&nbsp;<span style="color:#2b91af;">R</span>,&nbsp;<span style="color:#2b91af;">R1</span>,&nbsp;<span style="color:#2b91af;">U</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;IEither&lt;L,&nbsp;R&gt;&nbsp;<span style="color:#1f377f;">source</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;R,&nbsp;IEither&lt;L,&nbsp;U&gt;&gt;&nbsp;<span style="color:#1f377f;">k</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;R,&nbsp;U,&nbsp;R1&gt;&nbsp;<span style="color:#1f377f;">s</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;source.SelectMany(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;k(x).Select(<span style="color:#1f377f;">y</span>&nbsp;=&gt;&nbsp;s(x,&nbsp;y))); }</pre> </p> <p> This enables you to rewrite the above composition like this: </p> <p> <pre>IEither&lt;<span style="color:blue;">string</span>,&nbsp;DateTime&gt;&nbsp;<span style="color:#1f377f;">result</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">from</span>&nbsp;d&nbsp;<span style="color:blue;">in</span>&nbsp;dt &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">from</span>&nbsp;dur&nbsp;<span style="color:blue;">in</span>&nbsp;ts &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">select</span>&nbsp;d&nbsp;+&nbsp;dur;</pre> </p> <p> It's often a question of <a href="/2020/10/12/subjectivity">subjectivity</a> whether you like one alternative over the other, but the behaviour is the same. </p> <h3 id="064ab5098d3944b1be8bc24247592fb0"> Return <a href="#064ab5098d3944b1be8bc24247592fb0" title="permalink">#</a> </h3> <p> Apart from monadic bind, a monad must also define a way to put a normal value into the monad. Conceptually, I call this function <em>return</em> (because that's the name that Haskell uses). You don't, however, have to define a static method called <code>Return</code>. What's of importance is that the capability exists. For <code>Either&lt;L, R&gt;</code> in C# the idiomatic way would be to use a constructor. This constructor does double duty as monadic <em>return</em>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Right</span>(R&nbsp;<span style="color:#1f377f;">right</span>)</pre> </p> <p> In other words, <em>return</em> wraps a value in a <em>right</em> case. </p> <p> Why not the <em>left</em> case? Because it wouldn't type-check. A <em>return</em> function should take a value of the type <code>R</code> and return an <code>IEither&lt;L, R&gt;</code>. The <code>Left</code> constructor, however, doesn't take an <code>R</code> value - it takes an <code>L</code> value. </p> <h3 id="f0fb650204c043229df4967c22c4d6ec"> Left identity <a href="#f0fb650204c043229df4967c22c4d6ec" title="permalink">#</a> </h3> <p> We need to identify the <em>return</em> function in order to examine <a href="/2022/04/11/monad-laws">the monad laws</a>. Let's see what they look like for the Either monad, starting with the left identity law. </p> <p> <pre>[Theory] [InlineData(<span style="color:#a31515;">&quot;2&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;2.3:00&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;4.5:30&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;0:33:44&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;foo&quot;</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">LeftIdentityLaw</span>(<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;IEither&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">@return</span>&nbsp;=&nbsp;<span style="color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;Right&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">string</span>&gt;(s); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;IEither&lt;<span style="color:blue;">string</span>,&nbsp;TimeSpan&gt;&gt;&nbsp;<span style="color:#1f377f;">h</span>&nbsp;=&nbsp;TryParseDuration; &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(@return(a).SelectMany(h),&nbsp;h(a)); }</pre> </p> <p> As always, even a parametrised test constitutes no <em>proof</em> that the law holds. I show the tests to illustrate what the laws look like in 'real' code. </p> <h3 id="d158a758e9dc40149c7676a83398d17d"> Right identity <a href="#d158a758e9dc40149c7676a83398d17d" title="permalink">#</a> </h3> <p> In a similar manner, we can showcase the right identity law as a test. </p> <p> <pre>[Theory] [InlineData(<span style="color:#a31515;">&quot;2022-03-22&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;2022-03-21T16:57&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;bar&quot;</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">RightIdentityLaw</span>(<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;IEither&lt;<span style="color:blue;">string</span>,&nbsp;DateTime&gt;&gt;&nbsp;<span style="color:#1f377f;">f</span>&nbsp;=&nbsp;TryParseDate; &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;DateTime,&nbsp;IEither&lt;<span style="color:blue;">string</span>,&nbsp;DateTime&gt;&gt;&nbsp;<span style="color:#1f377f;">@return</span>&nbsp;=&nbsp;<span style="color:#1f377f;">d</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;Right&lt;<span style="color:blue;">string</span>,&nbsp;DateTime&gt;(d); &nbsp;&nbsp;&nbsp;&nbsp;IEither&lt;<span style="color:blue;">string</span>,&nbsp;DateTime&gt;&nbsp;<span style="color:#1f377f;">m</span>&nbsp;=&nbsp;f(a); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(m.SelectMany(@return),&nbsp;m); }</pre> </p> <p> The parameters supplied as <code>a</code> will cause <code>m</code> to be both <code>Left</code> and <code>Right</code> values, but the test demonstrates that the law holds in both cases. </p> <h3 id="ff7794ca964b4dfdb588251f264c7c11"> Associativity <a href="#ff7794ca964b4dfdb588251f264c7c11" title="permalink">#</a> </h3> <p> The last monad law is the associativity law that describes how (at least) three functions compose. We're going to need three functions. I'm going to reuse <code>TryParseDuration</code> and add two new Either-valued functions: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;IEither&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">double</span>&gt;&nbsp;<span style="color:#74531f;">DaysForward</span>(TimeSpan&nbsp;<span style="color:#1f377f;">ts</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(ts&nbsp;&lt;&nbsp;TimeSpan.Zero) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Left&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">double</span>&gt;(<span style="color:#a31515;">$&quot;Negative&nbsp;durations&nbsp;not&nbsp;allowed:&nbsp;</span>{ts}<span style="color:#a31515;">.&quot;</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Right&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">double</span>&gt;(ts.TotalDays); } <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;IEither&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;&nbsp;<span style="color:#74531f;">Nat</span>(<span style="color:blue;">double</span>&nbsp;<span style="color:#1f377f;">d</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(d&nbsp;%&nbsp;1&nbsp;!=&nbsp;0) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Left&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(<span style="color:#a31515;">$&quot;Non-integers&nbsp;not&nbsp;allowed:&nbsp;</span>{d}<span style="color:#a31515;">.&quot;</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(d&nbsp;&lt;&nbsp;1) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Left&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;(<span style="color:#a31515;">$&quot;Non-positive&nbsp;numbers&nbsp;not&nbsp;allowed:&nbsp;</span>{d}<span style="color:#a31515;">.&quot;</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Right&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;((<span style="color:blue;">int</span>)d); }</pre> </p> <p> These silly functions are only here for purposes of demonstration. Don't try to infer any deep meaning from them. </p> <p> Designating them <code>f</code>, <code>g</code>, and <code>h</code>, we can use them to express the monad associativity law: </p> <p> <pre>[Theory] [InlineData(<span style="color:#a31515;">&quot;2&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;-2.3:00&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;4.5:30&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;0:33:44&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;0&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;foo&quot;</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">AssociativityLaw</span>(<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;IEither&lt;<span style="color:blue;">string</span>,&nbsp;TimeSpan&gt;&gt;&nbsp;<span style="color:#1f377f;">f</span>&nbsp;=&nbsp;TryParseDuration; &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;TimeSpan,&nbsp;IEither&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">double</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">g</span>&nbsp;=&nbsp;DaysForward; &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">double</span>,&nbsp;IEither&lt;<span style="color:blue;">string</span>,&nbsp;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">h</span>&nbsp;=&nbsp;Nat; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">m</span>&nbsp;=&nbsp;f(a); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(m.SelectMany(g).SelectMany(h),&nbsp;m.SelectMany(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;g(x).SelectMany(h))); }</pre> </p> <p> The test cases supplied via the <code>[InlineData]</code> attributes comprise a set of values that make their way through the composition to varying degrees. <code>"2"</code> makes it all the way through to a <code>Right</code> value, because it encodes a two-day duration. It's both a positive value, greater than zero, and an integer. The other test cases become <code>Left</code> values at various stages in the composition, being either a non-number, fractional, zero, or negative. </p> <h3 id="b409ce7af135433eb275832d2c45ffde"> Conclusion <a href="#b409ce7af135433eb275832d2c45ffde" title="permalink">#</a> </h3> <p> Either (AKA Result) is another useful data structure that forms a monad. You can use it instead of throwing exceptions. Its monadic nature enables you to compose multiple Either-valued functions in a sane and elegant way. </p> <p> <strong>Next:</strong> <a href="/2022/05/16/the-identity-monad">The Identity monad</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/2022/05/09/an-either-monad At the boundaries, applications aren't functional https://blog.ploeh.dk/2022/05/02/at-the-boundaries-applications-arent-functional/ Mon, 02 May 2022 05:29:00 UTC <div id="post"> <p> <em>Ten years later.</em> </p> <p> In 2011 I published an article titled <a href="/2011/05/31/AttheBoundaries,ApplicationsareNotObject-Oriented">At the Boundaries, Applications are Not Object-Oriented</a>. It made the observation that at the edges of systems, where software interacts with either humans or other software, interactions aren't object-oriented. The data exchanged is exactly that: data. </p> <p> A common catchphrase about object-oriented design is that <em>objects are data with behaviour</em>. In a user interface, a REST API, at the command line, etcetera, data is transmitted, but behaviour is not. </p> <p> The article was one of those unfortunately unsatisfying articles that point out a problem without offering a solution. While I don't like to leave readers hanging like that, I on the other hand think that it's important sometimes to ask open-ended questions. <em>Here's a problem. Can anyone offer a solution?</em> </p> <p> People occasionally come by that old article and ask me if I've changed my mind since then. The short answer is that I believe that the problem persists. I may, however, today have another approach to it. </p> <h3 id="a438ebbc5a964854906bf0ac0991e0ba"> Functional programming <a href="#a438ebbc5a964854906bf0ac0991e0ba" title="permalink">#</a> </h3> <p> Starting around the time of the original article, I became interested in functional programming (FP). The more I've learned about it, the better it seems to address my concerns of eleven years ago. </p> <p> I don't know if FP is a silver bullet (although <a href="/2019/07/01/yes-silver-bullet">I'd like to think so</a>), but at least I find that I have fewer impedance mismatch issues than I did with object-oriented programming (OOP). In FP, after all, data is just data. </p> <p> Except when it isn't, but more about that later. </p> <p> It's easier to reconcile the FP notion of data with what actually goes on at the boundaries of a system. </p> <p> Perhaps I should clarify what I mean by the word <em>boundary</em>. This is where a software system interacts with the rest of the world. This is where it receives HTTP requests and answers with HTTP responses. This is where it queries its database. This is where it sends emails. This is where it reads files from disk. This is where it repaints user interfaces. In short, the outermost circle in <a href="/2013/12/03/layers-onions-ports-adapters-its-all-the-same">ports and adapters architecture</a>. </p> <p> Notice that what crosses the boundary tends to be data. JSON or XML documents, tabular data streams, flat files, etcetera. In OOP, your training tells you that you should associate some <em>behaviour</em> with data, and that's what creates dissonance. We introduce <a href="https://en.wikipedia.org/wiki/Data_transfer_object">Data Transfer Objects</a> (DTO) even though a DTO </p> <blockquote> <p> "is one of those objects our mothers told us never to write." </p> <footer><cite>Marin Fowler, <a href="/ref/peaa">Patterns of Enterprise Application Architecture</a></cite></footer> </blockquote> <p> We almost have to do violence to ourselves to introduce a DTO in an object-oriented code base, yet grudgingly we accept that this is probably better than the alternative. </p> <p> In FP, on the other hand, that's just natural. </p> <p> To paraphrase the simple example from the old article, imagine that you receive data like this as input: </p> <p> <pre>{ &nbsp;&nbsp;<span style="color:#2e75b6;">&quot;firstName&quot;</span>:&nbsp;<span style="color:#a31515;">&quot;Mark&quot;</span>, &nbsp;&nbsp;<span style="color:#2e75b6;">&quot;lastName&quot;</span>:&nbsp;<span style="color:#a31515;">&quot;Seemann&quot;</span> }</pre> </p> <p> If we wanted to capture that structure as a type, in <a href="https://fsharp.org">F#</a> you'd write a type like this: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;Name&nbsp;=&nbsp;{&nbsp;FirstName&nbsp;:&nbsp;string;&nbsp;LastName&nbsp;:&nbsp;string&nbsp;}</pre> </p> <p> And while you might feel icky defining such a DTO-like type in OOP, it's perfectly natural and expected in FP. </p> <p> That type even supports JSON serialization and deserialization without further <a href="/2019/12/16/zone-of-ceremony">ceremony</a>: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;opts&nbsp;=&nbsp;JsonSerializerOptions&nbsp;(PropertyNamingPolicy&nbsp;=&nbsp;JsonNamingPolicy.CamelCase) <span style="color:blue;">let</span>&nbsp;n&nbsp;=&nbsp;JsonSerializer.Deserialize&lt;Name&gt;&nbsp;(json,&nbsp;opts)</pre> </p> <p> where <code>json</code> might contain the above JSON fragment. </p> <p> To summarise so far: <em>Data crosses the boundaries of systems - not objects</em>. Since FP tends to separate data from behaviour, that paradigm feels more natural in that context. </p> <h3 id="3f60d44d38f24e8080eb4d8123ed5530"> Not all peaches and cream <a href="#3f60d44d38f24e8080eb4d8123ed5530" title="permalink">#</a> </h3> <p> FP is, however, not a perfect fit either. Let's paraphrase the above medial summary: <em>Data crosses the boundaries of systems - not functions</em>. </p> <p> FP is more than just functions <em>and</em> data. It's also about functions as first-class concepts, including functions as values, and <a href="https://en.wikipedia.org/wiki/Higher-order_function">higher-order functions</a>. While an object is <em>data with behaviour</em>, <a href="/2018/02/12/object-isomorphisms">closures <em>are behaviour with data</em></a>. Such first-class values cross system boundaries with the same ease as objects do: Not very well. </p> <p> I was recently helping a client defining a domain-specific language (DSL). I wrote a proof of concept in <a href="https://www.haskell.org">Haskell</a> based on Abstract Syntax Trees (AST). Each AST would typically be defined with copious use of lambda expressions. There was also an existential type involved. </p> <p> At one time, the question of persistence came up. At first I thought that you could easily serialize those ASTs, since, after all, they're just immutable values. Then I realised that while that's true, most of the constituent values were <em>functions</em>. There's no clear way to serialize a function, other than in code. </p> <p> Functions don't easily cross boundaries, for the same reasons that objects don't. </p> <p> So while FP seems like a better fit when it comes to modelling data, <em>at the boundaries, applications aren't functional</em>. </p> <h3 id="7ab8590765114bcf91c0e505e6b34271"> Weak or strong typing? <a href="#7ab8590765114bcf91c0e505e6b34271" title="permalink">#</a> </h3> <p> In my original article, I attempted to look ahead. One option I considered was dynamic typing. Instead of defining a DTO that mirrors a particular shape of data (e.g. a JSON document), would it be easier to parse or create a document on the fly, without a static type? </p> <p> I occasionally find myself doing that, as you can see in my article <a href="/2022/01/03/to-id-or-not-to-id">To ID or not to ID</a>. The code base already used <a href="https://www.newtonsoft.com/json">Json.NET</a>, and I found it easier to use the <code>JToken</code> API to parse documents, rather than having to maintain a static type whose only raison d'être was to mirror a JSON document. I repeat an example here for your convenience: </p> <p> <pre><span style="color:green;">//&nbsp;JToken&nbsp;-&gt;&nbsp;UserData&lt;string&gt;</span> <span style="color:blue;">let</span>&nbsp;<span style="color:blue;">private</span>&nbsp;parseUser&nbsp;(jobj&nbsp;:&nbsp;JToken)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;uid&nbsp;=&nbsp;jobj.[<span style="color:#a31515;">&quot;id&quot;</span>]&nbsp;|&gt;&nbsp;string &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;fn&nbsp;=&nbsp;jobj.[<span style="color:#a31515;">&quot;firstName&quot;</span>]&nbsp;|&gt;&nbsp;Option.ofObj&nbsp;|&gt;&nbsp;Option.map&nbsp;string &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;ln&nbsp;=&nbsp;jobj.[<span style="color:#a31515;">&quot;lastName&quot;</span>]&nbsp;|&gt;&nbsp;Option.ofObj&nbsp;|&gt;&nbsp;Option.map&nbsp;string &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;email&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;jobj.[<span style="color:#a31515;">&quot;primaryEmail&quot;</span>] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;Option.ofObj &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;Option.map&nbsp;(string&nbsp;&gt;&gt;&nbsp;MailAddress) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Id&nbsp;=&nbsp;uid &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;FirstName&nbsp;=&nbsp;fn &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LastName&nbsp;=&nbsp;ln &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Email&nbsp;=&nbsp;email &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Identities&nbsp;=&nbsp;[] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Permissions&nbsp;=&nbsp;[] &nbsp;&nbsp;&nbsp;&nbsp;}</pre> </p> <p> Likewise, I also used <code>JObject</code> to create and serialize new JSON documents. The <em>To ID or not to ID</em> article also contains an example of that. </p> <p> F# types are typically one-liners, like that above <code>Name</code> example. If that's true, why do I shy away from defining a static type that mirrors the desired JSON document structure? </p> <p> Because <a href="/2018/09/17/typing-is-not-a-programming-bottleneck">typing (the other kind of typing) isn't a programming bottleneck</a>. The cost of another type isn't the time it takes to write the code. It's the maintenance burden it adds. </p> <p> One problem you'll commonly have when you define DTOs as static types is that the code base will contain more than one type that represents the same concept. If these types are too similar, it becomes difficult for programmers to distinguish between them. As a result, functionality may inadvertently be coupled to the wrong type. </p> <p> Still, there can be good reasons to introduce a DTO type and a domain model. As <a href="https://lexi-lambda.github.io/">Alexis King</a> writes, </p> <blockquote> <p> "Consider: what is a parser? Really, a parser is just a function that consumes less-structured input and produces more-structured output." </p> <footer><cite>Alexis King, <a href="https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-validate/">Parse, don’t validate</a></cite></footer> </blockquote> <p> This is the approach I took in <a href="/code-that-fits-in-your-head">Code That Fits in Your Head</a>. A <code>ReservationDto</code> class has almost no invariants. It's just a bag of mutable and nullable properties; it's less-structured data. </p> <p> The corresponding domain model <code>Reservation</code> is more-structured. It's an immutable <a href="https://martinfowler.com/bliki/ValueObject.html">Value Object</a> that guarantees various invariants: All required data is present, quantity is a natural number, you can't mutate the object, and it has structural equality. </p> <p> In that case, <code>ReservationDto</code> and <code>Reservation</code> are sufficiently different. I consider their separate roles in the code base clear and distinct. </p> <h3 id="f416242d15a24f41a925182f180b4c2e"> Conclusion <a href="#f416242d15a24f41a925182f180b4c2e" title="permalink">#</a> </h3> <p> In 2011 I observed that at the boundaries, applications aren't object-oriented. For years, I've thought it a natural corollary that likewise, <em>at the boundaries, applications aren't functional</em>, either. On the other hand, I don't think I've explicitly made that statement before. </p> <p> A decade after 2011, I still find object-oriented programming incongruent with how software must work in reality. Functional programming offers an alternative that, while also not perfectly aligned with all data, seems better aligned with the needs of working software. </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/2022/05/02/at-the-boundaries-applications-arent-functional The Maybe monad https://blog.ploeh.dk/2022/04/25/the-maybe-monad/ Mon, 25 Apr 2022 06:50:00 UTC <div id="post"> <p> <em>The Maybe sum type forms a monad. An article for object-oriented programmers.</em> </p> <p> This article is an instalment in <a href="/2022/03/28/monads">an article series about monads</a>. </p> <p> The Maybe <a href="https://en.wikipedia.org/wiki/Tagged_union">sum type</a> is a useful data type that <a href="/2018/03/26/the-maybe-functor">forms a functor</a>. Like many other useful functors, it also forms a monad. </p> <p> It can be useful when querying another data structure (like a list or a tree) for a value that may or may not be present. It's also useful when performing a calculation that may not be possible, such as taking the square root of of a number, or calculating the average of a collection of values. A third common use case is when parsing a value, although usually, the Either sum type is often a better option for that task. </p> <h3 id="20497728035845fd9e7be0bb1ffae94c"> Bind <a href="#20497728035845fd9e7be0bb1ffae94c" title="permalink">#</a> </h3> <p> A monad must define either a <em>bind</em> or <em>join</em> function. In C#, monadic bind is called <code>SelectMany</code>. Depending on how you've implemented <code>Maybe&lt;T&gt;</code> the details of the implementation may vary, but the observable behaviour must always be the same. In this article I'm going to continue to use the <code>Maybe&lt;T&gt;</code> class first shown in <a href="/2018/03/26/the-maybe-functor">the article about the Maybe functor</a>. (That's not really my favourite implementation, but it doesn't matter.) </p> <p> In that code base, I chose to implement <code>SelectMany</code> as an extension method. Why I didn't use an instance method I no longer remember. Again, this doesn't matter. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Maybe&lt;TResult&gt;&nbsp;<span style="color:#74531f;">SelectMany</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;Maybe&lt;T&gt;&nbsp;<span style="color:#1f377f;">source</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;T,&nbsp;Maybe&lt;TResult&gt;&gt;&nbsp;<span style="color:#1f377f;">selector</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(source.HasItem) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;selector(source.Item); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">else</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;TResult&gt;(); }</pre> </p> <p> If the <code>source</code> has an item, <code>SelectMany</code> calls <code>selector</code> with the value and returns the result. If not, the result is an empty <code>Maybe&lt;TResult&gt;</code>. </p> <p> Monadic bind becomes useful when you have more than one function that returns a monadic value. Consider, for example, this variation of <code>Average</code>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;&nbsp;<span style="color:#74531f;">Average</span>(IEnumerable&lt;<span style="color:blue;">double</span>&gt;&nbsp;<span style="color:#1f377f;">values</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(values.Any()) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;(values.Average()); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">else</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;(); }</pre> </p> <p> You can't calculate the average of an empty collection, so if <code>values</code> is empty, this function returns an empty <code>Maybe&lt;double&gt;</code>. </p> <p> If you only needed this <code>Average</code> function, then you could use Maybe's <a href="/2018/03/22/functors">functor</a> affordance to map the result. On the other hand, imagine that you'd like to pass the <code>Average</code> result to this <code>Sqrt</code> function: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;&nbsp;<span style="color:#74531f;">Sqrt</span>(<span style="color:blue;">double</span>&nbsp;<span style="color:#1f377f;">d</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">result</span>&nbsp;=&nbsp;Math.Sqrt(d); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">switch</span>&nbsp;(result) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">case</span>&nbsp;<span style="color:blue;">double</span>.NaN: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">case</span>&nbsp;<span style="color:blue;">double</span>.PositiveInfinity:&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">default</span>:&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;(result); &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> This is another calculation that may not be possible. If you try to compose <code>Average</code> and <code>Sqrt</code> with <code>Select</code> (the functor's <em>map</em> function), you'd get a <code>Maybe&lt;Maybe&lt;double&gt;&gt;</code>. Fortunately, however, monads are functors you can flatten: </p> <p> <pre>[Theory] [InlineData(<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">double</span>[0],&nbsp;-100)] [InlineData(<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">double</span>[]&nbsp;{&nbsp;5,&nbsp;3&nbsp;},&nbsp;2)] [InlineData(<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">double</span>[]&nbsp;{&nbsp;1,&nbsp;-2&nbsp;},&nbsp;-100)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">ComposeAverageAndSqrt</span>(<span style="color:blue;">double</span>[]&nbsp;<span style="color:#1f377f;">values</span>,&nbsp;<span style="color:blue;">double</span>&nbsp;<span style="color:#1f377f;">expected</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;Average(values).SelectMany(Sqrt); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(expected,&nbsp;actual.GetValueOrFallback(-100)); }</pre> </p> <p> The <code>SelectMany</code> method flattens as it goes. Viewed in this way, <a href="https://www.scala-lang.org/">Scala</a>'s <code>flatMap</code> seems like a more appropriate name. </p> <p> The above test demonstrates how <code>SelectMany</code> returns a flattened <code>Maybe&lt;double&gt;</code>. The first test case has zero elements, so the <code>Average</code> method is going to return an empty <code>Maybe&lt;double&gt;</code>. <code>SelectMany</code> handles that gracefully by returning another empty value. </p> <p> In the second test case <code>Average</code> returns a populated value that contains the number <code>4</code>. <code>SelectMany</code> passes <code>4</code> to <code>Sqrt</code>, which returns <code>2</code> wrapped in a <code>Maybe&lt;double&gt;</code>. </p> <p> In the third test case, the average is <code>-.5</code>, wrapped in a <code>Maybe&lt;double&gt;</code>. <code>SelectMany</code> passes <code>-.5</code> on to <code>Sqrt</code>, which returns an empty value. </p> <h3 id="c9bb381e6f834ba2b955e3ea13efba7d"> Query syntax <a href="#c9bb381e6f834ba2b955e3ea13efba7d" title="permalink">#</a> </h3> <p> Monads also enable query syntax in C# (just like they enable other kinds of syntactic sugar in languages like <a href="https://fsharp.org">F#</a> and <a href="https://www.haskell.org">Haskell</a>). As outlined in the <a href="/2022/03/28/monads">monad introduction</a>, however, you must add a special <code>SelectMany</code> overload: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Maybe&lt;TResult&gt;&nbsp;<span style="color:#74531f;">SelectMany</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">U</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;Maybe&lt;T&gt;&nbsp;<span style="color:#1f377f;">source</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;T,&nbsp;Maybe&lt;U&gt;&gt;&nbsp;<span style="color:#1f377f;">k</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;T,&nbsp;U,&nbsp;TResult&gt;&nbsp;<span style="color:#1f377f;">s</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;source.SelectMany(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;k(x).Select(<span style="color:#1f377f;">y</span>&nbsp;=&gt;&nbsp;s(x,&nbsp;y))); }</pre> </p> <p> As I also mentioned in the monad introduction, it seems to me that you can always implement this overload with the above expression. Once this overload is in place, you can rewrite the above composition in query syntax, if that's more to your liking: </p> <p> <pre>[Theory] [InlineData(<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">double</span>[0],&nbsp;-100)] [InlineData(<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">double</span>[]&nbsp;{&nbsp;5,&nbsp;3&nbsp;},&nbsp;2)] [InlineData(<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">double</span>[]&nbsp;{&nbsp;1,&nbsp;-2&nbsp;},&nbsp;-100)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">ComposeAverageAndSqrtWithQuerySyntax</span>(<span style="color:blue;">double</span>[]&nbsp;<span style="color:#1f377f;">values</span>,&nbsp;<span style="color:blue;">double</span>&nbsp;<span style="color:#1f377f;">expected</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">from</span>&nbsp;a&nbsp;<span style="color:blue;">in</span>&nbsp;Average(values) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">from</span>&nbsp;s&nbsp;<span style="color:blue;">in</span>&nbsp;Sqrt(a) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">select</span>&nbsp;s; &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(expected,&nbsp;actual.GetValueOrFallback(-100)); }</pre> </p> <p> In this case, query syntax is more verbose, but the behaviour is the same. It's just two different ways of writing the same expression. The C# compiler desugars the query-syntax expression to one that composes with <code>SelectMany</code>. </p> <h3 id="09cb0abf4e7d4c21bce8796a57a5df50"> Join <a href="#09cb0abf4e7d4c21bce8796a57a5df50" title="permalink">#</a> </h3> <p> In <a href="/2022/03/28/monads">the introduction</a> you learned that if you have a <code>Flatten</code> or <code>Join</code> function, you can implement <code>SelectMany</code>, and the other way around. Since we've already defined <code>SelectMany</code> for <code>Maybe&lt;T&gt;</code>, we can use that to implement <code>Join</code>. In this article I use the name <code>Join</code> rather than <code>Flatten</code>. This is an arbitrary choice that doesn't impact behaviour. Perhaps you find it confusing that I'm inconsistent, but I do it in order to demonstrate that the behaviour is the same even if the name is different. </p> <p> The concept of a monad is universal, but the names used to describe its components differ from language to language. What C# calls <code>SelectMany</code>, Scala calls <code>flatMap</code>, and what Haskell calls <code>join</code>, other languages may call <code>Flatten</code>. </p> <p> You can always implement <code>Join</code> by using <code>SelectMany</code> with the identity function. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Maybe&lt;T&gt;&nbsp;<span style="color:#74531f;">Join</span>&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:blue;">this</span>&nbsp;Maybe&lt;Maybe&lt;T&gt;&gt;&nbsp;<span style="color:#1f377f;">source</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;source.SelectMany(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;x); }</pre> </p> <p> Instead of flattening as you go with <code>SelectMany</code>, you could also use <code>Select</code> and <code>Join</code> to compose <code>Average</code> and <code>Sqrt</code>: </p> <p> <pre>[Theory] [InlineData(<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">double</span>[0],&nbsp;-100)] [InlineData(<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">double</span>[]&nbsp;{&nbsp;5,&nbsp;3&nbsp;},&nbsp;2)] [InlineData(<span style="color:blue;">new</span>&nbsp;<span style="color:blue;">double</span>[]&nbsp;{&nbsp;1,&nbsp;-2&nbsp;},&nbsp;-100)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">JoinAverageAndSqrt</span>(<span style="color:blue;">double</span>[]&nbsp;<span style="color:#1f377f;">values</span>,&nbsp;<span style="color:blue;">double</span>&nbsp;<span style="color:#1f377f;">expected</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;Average(values).Select(Sqrt).Join(); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(expected,&nbsp;actual.GetValueOrFallback(-100)); }</pre> </p> <p> You'd typically not write the composition like this, as it seems more convenient to use <code>SelectMany</code>, but you could. The behaviour is the same. </p> <h3 id="770215f4b3da49dd976dc67e2416481e"> Return <a href="#770215f4b3da49dd976dc67e2416481e" title="permalink">#</a> </h3> <p> Apart from monadic bind, a monad must also define a way to put a normal value into the monad. Conceptually, I call this function <em>return</em> (because that's the name that Haskell uses). You don't, however, have to define a static method called <code>Return</code>. What's of importance is that the capability exists. For <code>Maybe&lt;T&gt;</code> in C# the <a href="/2015/08/03/idiomatic-or-idiosyncratic">idiomatic</a> way would be to use a constructor. This constructor overload does double duty as monadic <em>return</em>: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">Maybe</span>(T&nbsp;<span style="color:#1f377f;">item</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(item&nbsp;==&nbsp;<span style="color:blue;">null</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">throw</span>&nbsp;<span style="color:blue;">new</span>&nbsp;ArgumentNullException(nameof(item)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.HasItem&nbsp;=&nbsp;<span style="color:blue;">true</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.Item&nbsp;=&nbsp;item; }</pre> </p> <p> Why is it that overload, and not the other one? Because if you try to use <code>new Maybe&lt;T&gt;()</code> as <em>return</em>, you'll find that it breaks the <a href="/2022/04/11/monad-laws">monad laws</a>. Try it. It's a good exercise. </p> <h3 id="393bd508a0b549ca908c8950589bd910"> Left identity <a href="#393bd508a0b549ca908c8950589bd910" title="permalink">#</a> </h3> <p> Now that we're on the topic of the monad laws, let's see what they look like for the Maybe monad, starting with the left identity law. </p> <p> <pre>[Theory] [InlineData(0)] [InlineData(1)] [InlineData(2)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">LeftIdentity</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Maybe&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">@return</span>&nbsp;=&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">int</span>&gt;(i); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">h</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;i&nbsp;!=&nbsp;0&nbsp;?&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;(1.0&nbsp;/&nbsp;i)&nbsp;:&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;(); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(@return(a).SelectMany(h),&nbsp;h(a)); }</pre> </p> <p> To provide some variety, <code>h</code> is another Maybe-valued function - this time one that performs a safe <a href="https://en.wikipedia.org/wiki/Multiplicative_inverse">multiplicative inverse</a>. If <code>i</code> is zero, it returns an empty <code>Maybe&lt;double&gt;</code> because you can't devide by zero; otherwise, it returns one divided by <code>i</code> (wrapped in a <code>Maybe&lt;double&gt;</code>). </p> <h3 id="fcd0a8fe00784ec1a606d867fbc52384"> Right identity <a href="#fcd0a8fe00784ec1a606d867fbc52384" title="permalink">#</a> </h3> <p> In a similar manner, we can showcase the right identity law as a test. </p> <p> <pre>[Theory] [InlineData(<span style="color:#a31515;">&quot;&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;foo&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;42&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;1337&quot;</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">RightIdentity</span>(<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Maybe&lt;<span style="color:blue;">int</span>&gt;&nbsp;<span style="color:#74531f;">f</span>(<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">s</span>) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(<span style="color:blue;">int</span>.TryParse(s,&nbsp;<span style="color:blue;">out</span>&nbsp;var&nbsp;<span style="color:#1f377f;">i</span>)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">int</span>&gt;(i); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">else</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">int</span>&gt;(); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Maybe&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">@return</span>&nbsp;=&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">int</span>&gt;(i); &nbsp;&nbsp;&nbsp;&nbsp;Maybe&lt;<span style="color:blue;">int</span>&gt;&nbsp;<span style="color:#1f377f;">m</span>&nbsp;=&nbsp;f(a); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(m.SelectMany(@return),&nbsp;m); }</pre> </p> <p> Again, for variety's sake, for <code>f</code> I've chosen a function that should probably be named <code>TryParseInt</code> if used in another context. </p> <h3 id="52f8e7ce874942d2999e647c3a354869"> Associativity <a href="#52f8e7ce874942d2999e647c3a354869" title="permalink">#</a> </h3> <p> The last monad law is the associativity law that we can demonstrate like this: </p> <p> <pre>[Theory] [InlineData(<span style="color:#a31515;">&quot;bar&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;-1&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;0&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;4&quot;</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">Associativity</span>(<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Maybe&lt;<span style="color:blue;">int</span>&gt;&nbsp;<span style="color:#74531f;">f</span>(<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">s</span>) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(<span style="color:blue;">int</span>.TryParse(s,&nbsp;<span style="color:blue;">out</span>&nbsp;var&nbsp;<span style="color:#1f377f;">i</span>)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">int</span>&gt;(i); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">else</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">int</span>&gt;(); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">g</span>&nbsp;=&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;Sqrt(i); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">double</span>,&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">h</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">d</span>&nbsp;=&gt;&nbsp;d&nbsp;==&nbsp;0&nbsp;?&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;()&nbsp;:&nbsp;<span style="color:blue;">new</span>&nbsp;Maybe&lt;<span style="color:blue;">double</span>&gt;(1&nbsp;/&nbsp;d); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">m</span>&nbsp;=&nbsp;f(a); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(m.SelectMany(g).SelectMany(h),&nbsp;m.SelectMany(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;g(x).SelectMany(h))); }</pre> </p> <p> Here, I've copy-and-pasted the <em>TryParseInt</em> function I also used in the right identity example, and combined it with the <code>Sqrt</code> function and a safe multiplicative inverse. The law, however, should hold for all <a href="https://en.wikipedia.org/wiki/Pure_function">pure functions</a> that type-check. The functions shown here are just examples. </p> <p> As usual, a parametrised test is no proof that the law holds. I provide the tests only as examples of what the laws looks like. </p> <h3 id="7a49fae4e6fc4ba3850c323cf22d62f6"> Conclusion <a href="#7a49fae4e6fc4ba3850c323cf22d62f6" title="permalink">#</a> </h3> <p> The Maybe sum type is a versatile and useful data structure that forms a monad. This enables you to compose disparate functions that each may err by failing to return a value. </p> <p> <strong>Next: </strong> <a href="/2022/05/09/an-either-monad">An Either monad</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/2022/04/25/the-maybe-monad The List monad https://blog.ploeh.dk/2022/04/19/the-list-monad/ Tue, 19 Apr 2022 05:45:00 UTC <div id="post"> <p> <em>Lists, collections, deterministic Iterators form a monad. An article for object-oriented programmers.</em> </p> <p> This article is an instalment in <a href="/2022/03/28/monads">an article series about monads</a>. </p> <p> In the article series about <a href="/2018/03/22/functors">functors</a> I never included an explicit article about collections. Instead, I wrote: </p> <blockquote> <p> "Perhaps the most well-known of all functors is List, a.k.a. Sequence. C# query syntax can handle any functor, but most people only think of it as a language feature related to <code>IEnumerable&lt;T&gt;</code>. Since the combination of <code>IEnumerable&lt;T&gt;</code> and query syntax is already well-described, I'm not going to cover it explicitly here." </p> <footer><cite><a href="/2018/03/22/functors">Functors</a>, Mark Seemann, 2018</cite></footer> </blockquote> <p> Like many other useful functors, a list also forms a monad. In this article, I call it <em>list</em>. In <a href="https://www.haskell.org">Haskell</a> the most readily available equivalent is the built-in linked list (<code>[]</code>). Likewise, in <a href="https://fsharp.org">F#</a>, the fundamental collection types are linked lists and arrays. In C#, any <code>IEnumerable&lt;T&gt;</code> forms a monad. The .NET <code>IEnumerable&lt;T&gt;</code> interface is an application of the <a href="https://en.wikipedia.org/wiki/Iterator_pattern">Iterator design pattern</a>. There are many possible names for this monad: <em>list</em>, <em>sequence</em>, <em>collection</em>, <em>iterator</em>, etcetera. I've arbitrarily chosen to mostly use <em>list</em>. </p> <h3 id="13be436e595c411baf581dcfb31ab86f"> SelectMany <a href="#13be436e595c411baf581dcfb31ab86f" title="permalink">#</a> </h3> <p> In the <a href="/2022/03/28/monads">introduction to monads</a> you learned that monads are characterised by having either a <em>join</em> (or <em>flatten</em>) function, or a <em>bind</em> function. While in Haskell, monadic bind is the <code>&gt;&gt;=</code> operator, in C# it's a method called <code>SelectMany</code>. Perhaps you wonder about the name. </p> <p> The name <code>SelectMany</code> makes most sense in the context of lists. An example would be useful around here. </p> <p> Imagine that you have to parse a <a href="https://en.wikipedia.org/wiki/Comma-separated_values">CSV</a> file. You've already read the file from disc and split the contents into lines. Now you need to split each line on commas. </p> <p> <pre>&gt; <span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">lines</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;foo,bar,baz&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;qux,quux,quuz&quot;</span>&nbsp;}; &gt; lines.Select(l =&gt; l.Split(',')).ToArray() string[2][] { string[3] { "foo", "bar", "baz" }, string[3] { "qux", "quux", "quuz" } }</pre> </p> <p> When you use <code>Select</code> the result is a nested list. You've already learned that a monad is a functor you can flatten. In C#, you can 'flatten as you go' with <code>SelectMany</code>. </p> <p> The above scenario offers a hint at why the method is named <code>SelectMany</code>. You use it instead of <code>Select</code> when the selector returns <em>many</em> values. In the above example, the <code>Split</code> method returns many values. </p> <p> So, instead of <code>Select</code>, use <code>SelectMany</code> if you need a flattened list: </p> <p> <pre>&gt; lines.SelectMany(l =&gt; l.Split(',')).ToArray() string[6] { "foo", "bar", "baz", "qux", "quux", "quuz" }</pre> </p> <p> I've never had the opportunity to ask any of the LINQ designers about that naming choice, but this explanation makes sense to me. Even if it turns out that they had something else in mind when they named the method, I think that my explanation at least serves as a mnemonic device. </p> <p> The name is still unfortunate, since it mostly makes sense for the list monad. Already when you use <code>SelectMany</code> with the Maybe monad, the name makes less sense. </p> <h3 id="4f2a54b64a744c5f855c2baa9f1c8d9a"> Flatten <a href="#4f2a54b64a744c5f855c2baa9f1c8d9a" title="permalink">#</a> </h3> <p> In <a href="/2022/03/28/monads">the introduction</a> you learned that if you have a <code>Flatten</code> or <code>Join</code> function, you can implement <code>SelectMany</code>, and the other way around. In C#, LINQ already comes with <code>SelectMany</code>, but surprisingly, <code>Flatten</code> isn't built in. </p> <p> You can always implement <code>Flatten</code> by using <code>SelectMany</code> with the identity function. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;IEnumerable&lt;T&gt;&nbsp;<span style="color:#74531f;">Flatten</span>&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:blue;">this</span>&nbsp;IEnumerable&lt;IEnumerable&lt;T&gt;&gt;&nbsp;<span style="color:#1f377f;">source</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;source.SelectMany(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;x); }</pre> </p> <p> Recall that the <code>selector</code> passed to <code>SelectMany</code> must have the type <code>Func&lt;TSource,&nbsp;IEnumerable&lt;TResult&gt;&gt;</code>. There's no rule, however, that says that <code>TSource</code> can't be <code>IEnumerable&lt;TResult&gt;</code>. If <code>x</code> in <code>x =&gt; x</code> has the type <code>IEnumerable&lt;TResult&gt;</code>, then <code>x =&gt; x</code> has the type <code>Func&lt;IEnumerable&lt;TResult&gt;,&nbsp;IEnumerable&lt;TResult&gt;&gt;</code> and it all type-checks. </p> <p> Here's a test that demonstrates how <code>Flatten</code> works: </p> <p> <pre>[Fact] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">FlattenExample</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">string</span>[][]&nbsp;<span style="color:#1f377f;">nested</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;bar&quot;</span>&nbsp;},&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;baz&quot;</span>&nbsp;}&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;IEnumerable&lt;<span style="color:blue;">string</span>&gt;&nbsp;<span style="color:#1f377f;">flattened</span>&nbsp;=&nbsp;nested.Flatten(); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(<span style="color:blue;">new</span>[]&nbsp;{&nbsp;<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;bar&quot;</span>,&nbsp;<span style="color:#a31515;">&quot;baz&quot;</span>&nbsp;},&nbsp;flattened); }</pre> </p> <p> In Haskell <code>Flatten</code> is called <code>join</code> and is implemented this way: </p> <p> <pre>join :: (Monad m) =&gt; m (m a) -&gt; m a join x = x &gt;&gt;= id</pre> </p> <p> It's the same implementation as the above C# method: monadic bind (<code>SelectMany</code> in C#; <code>&gt;&gt;=</code> in Haskell) with the identity function. The Haskell implementation works for all monads. </p> <h3 id="f54cad2a32b341e1a11420fe53c0a7e1"> Return <a href="#f54cad2a32b341e1a11420fe53c0a7e1" title="permalink">#</a> </h3> <p> Apart from monadic bind, a monad must also define a way to put a normal value into the monad. For the list monad, this implies a single value promoted to a list. Surprisingly, the .NET base class library doesn't come with such a built-in function, but you can easily implement it yourself: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;IEnumerable&lt;T&gt;&nbsp;<span style="color:#74531f;">Return</span>&lt;<span style="color:#2b91af;">T</span>&gt;(T&nbsp;<span style="color:#1f377f;">x</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">yield</span>&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;x; }</pre> </p> <p> In practice, however, you'd normally instead create a singleton array, like this: <code>new[] { 2112 }</code>. Since arrays implement <code>IEnumerable&lt;T&gt;</code>, this works just as well. </p> <p> Why is this the correct implementation of <em>return?</em> </p> <p> Wouldn't this work? </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;IEnumerable&lt;T&gt;&nbsp;<span style="color:#74531f;">ReturnZero</span>&lt;<span style="color:#2b91af;">T</span>&gt;(T&nbsp;<span style="color:#1f377f;">x</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">yield</span>&nbsp;<span style="color:#8f08c4;">break</span>; }</pre> </p> <p> Or this? </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;IEnumerable&lt;T&gt;&nbsp;<span style="color:#74531f;">ReturnTwo</span>&lt;<span style="color:#2b91af;">T</span>&gt;(T&nbsp;<span style="color:#1f377f;">x</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">yield</span>&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;x; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">yield</span>&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;x; }</pre> </p> <p> None of these are appropriate because they break the <a href="/2022/04/11/monad-laws">monad laws</a>. Try it, as an exercise! </p> <h3 id="0795515a923a47ad95417dc77a826c24"> Left identity <a href="#0795515a923a47ad95417dc77a826c24" title="permalink">#</a> </h3> <p> Now that we're on the topic of the monad laws, let's see what they look like for the list monad, starting with the left identity law. </p> <p> <pre>[Theory] [InlineData(<span style="color:#a31515;">&quot;&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;foo&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;foo,bar&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;foo,bar,baz&quot;</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">LeftIdentity</span>(<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;IEnumerable&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">@return</span>&nbsp;=&nbsp;List.Return; &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;IEnumerable&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">h</span>&nbsp;=&nbsp;<span style="color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;s.Split(<span style="color:#a31515;">&#39;,&#39;</span>); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(@return(a).SelectMany(h),&nbsp;h(a)); }</pre> </p> <p> As usual, a parametrised test is no proof that the law holds. I provide it only as an example of what the law looks like. </p> <h3 id="09b17be2537842a3994b697e723ada34"> Right identity <a href="#09b17be2537842a3994b697e723ada34" title="permalink">#</a> </h3> <p> Likewise, we can showcase the right identity law as a test: </p> <p> <pre>[Theory] [InlineData(0)] [InlineData(1)] [InlineData(9)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">RightIdentity</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;IEnumerable&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">f</span>&nbsp;=&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;Enumerable.Repeat(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;i); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;IEnumerable&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">@return</span>&nbsp;=&nbsp;List.Return; &nbsp;&nbsp;&nbsp;&nbsp;IEnumerable&lt;<span style="color:blue;">string</span>&gt;&nbsp;<span style="color:#1f377f;">m</span>&nbsp;=&nbsp;f(a); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(m.SelectMany(@return),&nbsp;m); }</pre> </p> <p> These tests all pass. </p> <h3 id="c8898fa040ce4c138c0beadbf5a045d0"> Associativity <a href="#c8898fa040ce4c138c0beadbf5a045d0" title="permalink">#</a> </h3> <p> The last monad law is the associativity law that we can demonstrate like this: </p> <p> <pre>[Theory] [InlineData(0)] [InlineData(3)] [InlineData(8)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">Associativity</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;IEnumerable&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">f</span>&nbsp;=&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;Enumerable.Repeat(<span style="color:#a31515;">&quot;foo&quot;</span>,&nbsp;i); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;IEnumerable&lt;<span style="color:blue;">char</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">g</span>&nbsp;=&nbsp;<span style="color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;s; &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">char</span>,&nbsp;IEnumerable&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">h</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">c</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>[]&nbsp;{&nbsp;c.ToString().ToUpper(),&nbsp;c.ToString().ToLower()&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;IEnumerable&lt;<span style="color:blue;">string</span>&gt;&nbsp;<span style="color:#1f377f;">m</span>&nbsp;=&nbsp;f(a); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(m.SelectMany(g).SelectMany(h),&nbsp;m.SelectMany(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;g(x).SelectMany(h))); }</pre> </p> <p> The three functions <code>f</code>, <code>g</code>, and <code>h</code> are just silly functions I chose for variety's sake. </p> <h3 id="e15e1dfc86b94747ab7f7dc66faa02d2"> Conclusion <a href="#e15e1dfc86b94747ab7f7dc66faa02d2" title="permalink">#</a> </h3> <p> Lists, arrays, collections, Iterators are various names for a common idea: that of an ordered sequence of values. In this article, I've called it <em>list</em> for simplicity's sake. It's possible to flatten nested lists in a well-behaved manner, which makes <em>list</em> a monad. </p> <p> <strong>Next:</strong> <a href="/2022/04/25/the-maybe-monad">The Maybe monad</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/2022/04/19/the-list-monad Monad laws https://blog.ploeh.dk/2022/04/11/monad-laws/ Mon, 11 Apr 2022 06:57:00 UTC <div id="post"> <p> <em>An article for object-oriented programmers.</em> </p> <p> This article is an instalment in <a href="/2022/03/28/monads">an article series about monads</a>. </p> <p> Just as <a href="/2018/03/22/functors">functors</a> must obey the functor laws, monads must follow the monad laws. When looked at from the right angle, these are intuitive and reasonable rules: <a href="https://en.wikipedia.org/wiki/Identity_element">identity</a> and <a href="https://en.wikipedia.org/wiki/Associative_property">associativity</a>. </p> <p> That sounds almost like a <a href="/2017/10/06/monoids">monoid</a>, but the rules are more relaxed. For monoids, we require a <a href="https://en.wikipedia.org/wiki/Binary_operation">binary operation</a>. That's not the case for functors and monads. Instead of binary operations, for monads we're going to use <a href="/2022/04/04/kleisli-composition">Kleisli composition</a>. </p> <p> This article draws heavily on the <a href="https://wiki.haskell.org/Monad_laws">Haskell wiki on monad laws</a>. </p> <p> In short, the monad laws comprise three rules: </p> <ul> <li>Left identity</li> <li>Right identity</li> <li>Associativity</li> </ul> <p> The article describes each in turn, starting with left identity. </p> <h3 id="2589cde8994b4e3db81ef821d8f346ba"> Left identity <a href="#2589cde8994b4e3db81ef821d8f346ba" title="permalink">#</a> </h3> <p> A left identity is an element that, when applied to the left of an operator, doesn't change the other element. When used with the <a href="/2022/04/04/kleisli-composition">fish operator</a> it looks like this: </p> <p> <pre>id &gt;=&gt; h ≡ h</pre> </p> <p> For monads, <code>id</code> turns out to be <code>return</code>, so more specifically: </p> <p> <pre>return &gt;=&gt; h ≡ h</pre> </p> <p> In C# we can illustrate the law as a parametrised test: </p> <p> <pre>[Theory] [InlineData(-1)] [InlineData(42)] [InlineData(87)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">LeftIdentityKleisli</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">@return</span>&nbsp;=&nbsp;Monad.Return; &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Monad&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">h</span>&nbsp;=&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;Monad.Return(i.ToString()); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Monad&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">composed</span>&nbsp;=&nbsp;@return.Compose(h); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(composed(a),&nbsp;h(a)); }</pre> </p> <p> Recall that we can implement the fish operators as <code>Compose</code> overloads. The above test demonstrates the notion that <code>@return</code> composed with <code>h</code> should be indistinguishable from <code>h</code>. Such a test should pass. </p> <p> Keep in mind, however, that Kleisli composition is <em>derived</em> from the definition of a monad. The direct definition of monads is that they come with a <code>return</code> and <code>bind</code> functions (or, alternatively <code>return</code> and <code>join</code>). If we <a href="https://refactoring.com/catalog/inlineFunction.html">inline</a> the implementation of <code>Compose</code>, the test instead looks like this: </p> <p> <pre>[Theory] [InlineData(-1)] [InlineData(42)] [InlineData(87)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">LeftIdentityInlined</span>(<span style="color:blue;">int</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">@return</span>&nbsp;=&nbsp;Monad.Return; &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Monad&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">h</span>&nbsp;=&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;Monad.Return(i.ToString()); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Monad&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">composed</span>&nbsp;=&nbsp;<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;@return(x).SelectMany(h); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(composed(a),&nbsp;h(a)); }</pre> </p> <p> or, more succinctly: </p> <p> <pre>Assert.Equal(@return(a).SelectMany(h),&nbsp;h(a));</pre> </p> <p> This is also the way the left identity law is usually presented in <a href="https://www.haskell.org">Haskell</a>: </p> <p> <pre>return a &gt;&gt;= h = h a</pre> </p> <p> In Haskell, <em>monadic bind</em> is represented by the <code>&gt;&gt;=</code> operator, while in C# it's the <code>SelectMany</code> method. Thus, the Haskell and the C# representations are equivalent. </p> <h3 id="b74cccb66945471d8b28e40e4e90516d"> Right identity <a href="#b74cccb66945471d8b28e40e4e90516d" title="permalink">#</a> </h3> <p> Right identity starts out similar to left identity. Using the fish operator, the Haskell wiki describes it as: </p> <p> <pre>f &gt;=&gt; return ≡ f</pre> </p> <p> Translated to a C# test, an example of that law might look like this: </p> <p> <pre>[Theory] [InlineData(<span style="color:#a31515;">&quot;foo&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;ploeh&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;lawful&quot;</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">RightIdentityKleisli</span>(<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">f</span>&nbsp;=&nbsp;<span style="color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;Monad.Return(s.Length); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">@return</span>&nbsp;=&nbsp;Monad.Return; &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">composed</span>&nbsp;=&nbsp;f.Compose(@return); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(composed(a),&nbsp;f(a)); }</pre> </p> <p> Again, if we inline <code>Compose</code>, the test instead looks like this: </p> <p> <pre>[Theory] [InlineData(<span style="color:#a31515;">&quot;foo&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;ploeh&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;lawful&quot;</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">RightIdentityInlined</span>(<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">f</span>&nbsp;=&nbsp;<span style="color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;Monad.Return(s.Length); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">@return</span>&nbsp;=&nbsp;Monad.Return; &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">composed</span>&nbsp;=&nbsp;<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;f(x).SelectMany(@return); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(composed(a),&nbsp;f(a)); }</pre> </p> <p> Now explicitly call the <code>f</code> function and assign it to a variable <code>m</code>: </p> <p> <pre>[Theory] [InlineData(<span style="color:#a31515;">&quot;foo&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;ploeh&quot;</span>)] [InlineData(<span style="color:#a31515;">&quot;lawful&quot;</span>)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">RightIdentityInlinedIntoAssertion</span>(<span style="color:blue;">string</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">f</span>&nbsp;=&nbsp;<span style="color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;Monad.Return(s.Length); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">int</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">@return</span>&nbsp;=&nbsp;Monad.Return; &nbsp;&nbsp;&nbsp;&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&nbsp;<span style="color:#1f377f;">m</span>&nbsp;=&nbsp;f(a); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(m.SelectMany(@return),&nbsp;m); }</pre> </p> <p> The assertion is now the C# version of the normal Haskell definition of the right identity law: </p> <p> <pre>m &gt;&gt;= return = m</pre> </p> <p> In other words, <code>return</code> is the identity element for monadic composition. It doesn't really 'do' anything in itself. </p> <h3 id="3d323da500cc4405ac4768b1108cfdf9"> Associativity <a href="#3d323da500cc4405ac4768b1108cfdf9" title="permalink">#</a> </h3> <p> The third monad law is the associativity law. Keep in mind that an operator like <code>+</code> is associative if it's true that </p> <p> <pre>(x + y) + z = x + (y + z)</pre> </p> <p> Instead of <code>+</code>, the operator in question is the fish operator, and since values are functions, we typically call them <code>f</code>, <code>g</code>, and <code>h</code> rather than <code>x</code>, <code>y</code>, and <code>z</code>: </p> <p> <pre>(f &gt;=&gt; g) &gt;=&gt; h ≡ f &gt;=&gt; (g &gt;=&gt; h)</pre> </p> <p> Translated to a C# test as an example, the law looks like this: </p> <p> <pre>[Theory] [InlineData(0)] [InlineData(1)] [InlineData(2)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">AssociativityKleisli</span>(<span style="color:blue;">double</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">double</span>,&nbsp;Monad&lt;<span style="color:blue;">bool</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">f</span>&nbsp;=&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;Monad.Return(i&nbsp;%&nbsp;2&nbsp;==&nbsp;0); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">bool</span>,&nbsp;Monad&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">g</span>&nbsp;=&nbsp;<span style="color:#1f377f;">b</span>&nbsp;=&gt;&nbsp;Monad.Return(b.ToString()); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">h</span>&nbsp;=&nbsp;<span style="color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;Monad.Return(s.Length); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">double</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">left</span>&nbsp;=&nbsp;(f.Compose(g)).Compose(h); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">double</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">right</span>&nbsp;=&nbsp;f.Compose(g.Compose(h)); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(left(a),&nbsp;right(a)); }</pre> </p> <p> The outer brackets around <code>(f.Compose(g))</code> are actually redundant; we should remove them. Also, inline <code>Compose</code>: </p> <p> <pre>[Theory] [InlineData(0)] [InlineData(1)] [InlineData(2)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">AssociativityInlined</span>(<span style="color:blue;">double</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">double</span>,&nbsp;Monad&lt;<span style="color:blue;">bool</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">f</span>&nbsp;=&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;Monad.Return(i&nbsp;%&nbsp;2&nbsp;==&nbsp;0); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">bool</span>,&nbsp;Monad&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">g</span>&nbsp;=&nbsp;<span style="color:#1f377f;">b</span>&nbsp;=&gt;&nbsp;Monad.Return(b.ToString()); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">h</span>&nbsp;=&nbsp;<span style="color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;Monad.Return(s.Length); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">double</span>,&nbsp;Monad&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">fg</span>&nbsp;=&nbsp;<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;f(x).SelectMany(g); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">double</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">left</span>&nbsp;=&nbsp;<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;fg(x).SelectMany(h); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">bool</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">gh</span>&nbsp;=&nbsp;<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;g(x).SelectMany(h); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">double</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">right</span>&nbsp;=&nbsp;<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;f(x).SelectMany(gh); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(left(a),&nbsp;right(a)); }</pre> </p> <p> If there's a way in C# to inline the local compositions <code>fg</code> and <code>gh</code> directly into <code>left</code> and <code>right</code>, respectively, I don't know how. In any case, the above is just an intermediate step. </p> <p> For both <code>left</code> and <code>right</code>, notice that the first step involves invoking <code>f</code> with <code>x</code>. If, instead, we call that value <code>m</code>, we can rewrite the test like this: </p> <p> <pre>[Theory] [InlineData(0)] [InlineData(1)] [InlineData(2)] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="color:#74531f;">AssociativityInlinedIntoAssertion</span>(<span style="color:blue;">double</span>&nbsp;<span style="color:#1f377f;">a</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">double</span>,&nbsp;Monad&lt;<span style="color:blue;">bool</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">f</span>&nbsp;=&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;Monad.Return(i&nbsp;%&nbsp;2&nbsp;==&nbsp;0); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">bool</span>,&nbsp;Monad&lt;<span style="color:blue;">string</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">g</span>&nbsp;=&nbsp;<span style="color:#1f377f;">b</span>&nbsp;=&gt;&nbsp;Monad.Return(b.ToString()); &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;<span style="color:blue;">string</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">h</span>&nbsp;=&nbsp;<span style="color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;Monad.Return(s.Length); &nbsp;&nbsp;&nbsp;&nbsp;Monad&lt;<span style="color:blue;">bool</span>&gt;&nbsp;<span style="color:#1f377f;">m</span>&nbsp;=&nbsp;f(a); &nbsp;&nbsp;&nbsp;&nbsp;Assert.Equal(m.SelectMany(g).SelectMany(h),&nbsp;m.SelectMany(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;g(x).SelectMany(h))); }</pre> </p> <p> The above assertion corresponds to the way the associativity law is usually represented in Haskell: </p> <p> <pre>(m &gt;&gt;= g) &gt;&gt;= h = m &gt;&gt;= (\x -&gt; g x &gt;&gt;= h)</pre> </p> <p> Once more, keep in mind that <code>&gt;&gt;=</code> in Haskell corresponds to <code>SelectMany</code> in C#. </p> <h3 id="d43cb529320e4dc2ab2003e68918ae92"> Conclusion <a href="#d43cb529320e4dc2ab2003e68918ae92" title="permalink">#</a> </h3> <p> A proper monad must satisfy the three monad laws: left identity, right identity, and associativity. Together, left identity and right identity are know as simply <em>identity</em>. What's so special about identity and associativity? </p> <p> As <a href="https://bartoszmilewski.com/2014/11/04/category-the-essence-of-composition/">Bartosz Milewski explains</a>, a <em>category</em> must satisfy associativity and identity. When it comes to monads, the category in question is the <a href="https://bartoszmilewski.com/2014/12/23/kleisli-categories/">Kleisli category</a>. Or, as the Haskell wiki puts it: </p> <blockquote> <p>Monad axioms:<br/> Kleisli composition forms<br/> a category.</p> <footer><cite><a href="https://wiki.haskell.org/Monad_laws">Haskell wiki</a></cite></footer> </blockquote> <p> Subsequent articles in this article series will now proceed to give examples of concrete monads, and what the laws look like for each of these. </p> <p> <strong>Next:</strong> <a href="/2022/04/19/the-list-monad">The List monad</a>. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="8e777ae4b3c64f5ab244b0e4d0f0d263"> <div class="comment-author"><a href="https://about.me/tysonwilliams">Tyson Williams</a></div> <div class="comment-content"> <blockquote> That sounds almost like a <a href="/2017/10/06/monoids">monoid</a>, but the rules are more relaxed. For monoids, we require a <a href="https://en.wikipedia.org/wiki/Binary_operation">binary operation</a>. That's not the case for functors and monads. Instead of binary operations, for monads we're going to use <a href="/2022/04/04/kleisli-composition">Kleisli composition</a>. </blockquote> <p> I am confused by this paragraph. A monoid requries a binary operation (that is also closed), and Kleisli composition is (closed) binary operation. </p> <p> As you said in the <a href="https://blog.ploeh.dk/2022/03/28/monads/">introductory article to this monad series</a>, there are three pieces to a monad: a generic type <code>M&lt;&gt;</code>, a function with type <code>a -&gt; M&lt;a&gt;</code> (typically called "return"), and a function with signature <code>(a -&gt; M&lt;b&gt;) -&gt; M&lt;a&gt; -&gt; M&lt;b&gt;</code> (sometimes called "bind"). Then <code>(M&lt;&gt;, return, bind)</code> is a monad if those three items satisfy the monad laws. </p> <p> I think the following is true. Let <code>M&lt;&gt;</code> be a generic type, and let <code>S</code> be the set of all functions with signature <code>a -&gt; M&lt;a&gt;</code>. Then <code>(M&lt;&gt;, return, bind)</code> is a monad if only only if <code>(S, &gt;=&gt;, return)</code> is a monoid. </p> </div> <div class="comment-date">2022-04-18 16:17 UTC</div> </div> <div class="comment" id="2bf9e517fa744a89928ae3d9f08fedd2"> <div class="comment-author"><a href="/">Mark Seemann</a></div> <div class="comment-content"> <p> Tyson, thank you for writing. To address the elephant in the room first: A monad <em>is</em> a monoid (<a href="https://bartoszmilewski.com/2016/12/27/monads-categorically/">in the category of endofunctors</a>), but as far as I can tell, you have to look more abstractly at it than allowed by the static type systems we normally employ. </p> <p> <a href="https://bartoszmilewski.com/2016/12/27/monads-categorically/">Bartosz Milewski describes</a> a <a href="/2022/03/28/monads">nested functor</a> as the tensor product of two monadic types: <code>M ⊗ M</code>. The binary operation in question is then <code>M ⊗ M -> M</code>, or <em>join/flatten</em> (from here on just <em>join</em>). In this very abstract view, monads <em>are</em> monoids. It does require an abstract view of functors as objects in a category. At that level of abstraction, so many details are lost that <em>join</em> looks like a binary operation. </p> <p> So, to be clear, if you want to look at a monad as a monoid, it's not the monadic <em>bind</em> function that's the binary operation; it's <em>join</em>. (That's another reason I prefer explaining monads in terms of <em>join</em> rather than leading with <em>bind</em>.) </p> <p> When you zoom in on the details, however, <a href="https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:join">join</a> doesn't look like a regular binary operation: <code>m (m a) -&gt; m a</code>. A binary operation, on the other hand, should look like this: <code>m a -&gt; m a -&gt; m a</code>. </p> <p> The Kleisli composition operator unfortunately doesn't fix this. Let's look at the C# method signature, since it may offer a way out: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Func&lt;T,&nbsp;Monad&lt;T2&gt;&gt;&nbsp;<span style="color:#74531f;">Compose</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">T2</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;T,&nbsp;Monad&lt;T1&gt;&gt;&nbsp;<span style="color:#1f377f;">action1</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;T1,&nbsp;Monad&lt;T2&gt;&gt;&nbsp;<span style="color:#1f377f;">action2</span>) </pre> </p> <p> Notice that the types don't match: <code>action1</code> has a type different from <code>action2</code>, which is again different from the return type. Thus, it's not a binary operation, because the elements don't belong to the same <a href="/2021/11/15/types-as-sets">set</a>. </p> <p> As Bartosz Milewski wrote, though, if we squint a little, we may make it work. C# allows us to 'squint' because of its object hierarchy: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Func&lt;object,&nbsp;Monad&lt;object&gt;&gt;&nbsp;<span style="color:#74531f;">Compose</span>( &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;object,&nbsp;Monad&lt;object&gt;&gt;&nbsp;<span style="color:#1f377f;">action1</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;object,&nbsp;Monad&lt;object&gt;&gt;&nbsp;<span style="color:#1f377f;">action2</span>) </pre> </p> <p> I'm not sure how helpful that is, though, so I didn't want to get into these weeds in the above article itself. It's fine here in the comments, because I expect only very dedicated readers to consult them. This, thus, serves more like a footnote or appendix. </p> </div> <div class="comment-date">2022-04-23 11:29 UTC</div> </div> <div class="comment" id="2b7a3b85cfec410c8213adbfa3b7d33f"> <div class="comment-author"><a href="https://about.me/tysonwilliams">Tyson Williams</a></div> <div class="comment-content"> <p> Thanks very much for you reply. It helped me to see where I was wrong. <code>(S, &gt;=&gt;, return)</code> is not a monoid because <code>&gt;=&gt;</code> is not total over <code>S</code>, which is another condition the binary operation must satisfy, but I overlooked that. Furthremore, I meant to define <code>S</code> as the set of all functions with signature <code>a -&gt; M&lt;b&gt;</code>. The same problem still exists though. The second code block in your comment has this same problem. There is not a natural choice for the implementation unless the types of the objects satisfy the constraints implied by the use of type parameters in the first code block in your comment. I will keep thinking about this. </p> <p> In the meantime, keep up the great work. I am loving your monad content. </p> </div> <div class="comment-date">2022-04-23 19:47 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/2022/04/11/monad-laws Kleisli composition https://blog.ploeh.dk/2022/04/04/kleisli-composition/ Mon, 04 Apr 2022 06:08:00 UTC <div id="post"> <p> <em>A way to compose two monadic functions. An article for object-oriented programmers.</em> </p> <p> This article is an instalment in <a href="/2022/03/28/monads">an article series about monads</a>. </p> <p> There's a bit of groundwork which will be useful before we get to the <a href="/2022/04/11/monad-laws">monad laws</a>. There are two ways to present the monad laws. One is quite unintuitive, but uses only the concepts already discussed in the <a href="/2022/03/28/monads">introductory article</a>. The other way to present the laws is much more intuitive, but builds on a derived concept: Kleisli composition. </p> <p> I find it preferable to take the intuitive route, even if it requires this little detour around the <a href="https://bartoszmilewski.com/2014/12/23/kleisli-categories/">Kleisli category</a>. </p> <h3 id="751e600750344be6bce3b19a3353ac9b"> Monadic functions <a href="#751e600750344be6bce3b19a3353ac9b" title="permalink">#</a> </h3> <p> Imagine some monad - any monad. It could be <em>Maybe</em> (AKA <em>Option</em>), <em>Either</em> (AKA <em>Result</em>), <em>Task</em>, <em>State</em>, etcetera. In <a href="https://www.haskell.org">Haskell</a> notation we denote it <code>m</code>. (Don't worry if you don't know Haskell. The type notation is fairly intuitive, and I'll explain enough of it along the way.) </p> <p> You may have a function that takes some input and returns a monadic value. Perhaps it's a parser that takes a string as input and returns a <em>Maybe</em> or <em>Either</em> as output: </p> <p> <pre>String -&gt; Maybe Int</pre> </p> <p> Perhaps it's a database query that takes an ID as input and returns a <em>Task</em> or <em>IO</em> value: </p> <p> <pre>UUID -&gt; IO Reservation</pre> </p> <p> Notice that in Haskell, you write the input to the left of the output. (This is also the case in <a href="https://fsharp.org/">F#</a>.) Functions looks like arrows that point from the input to the output, which is a common depiction that <a href="/2021/11/22/functions-as-pipes">I've also used before</a>. </p> <p> If we generalise this notation, we would write a monadic function like this: </p> <p> <pre>a -&gt; m b</pre> </p> <p> <code>a</code> is a generic type that denotes input. It could be <code>String</code> or <code>UUID</code> as shown above, or anything else. Likewise, <code>b</code> is another generic type that could be <code>Int</code>, <code>Reservation</code>, or anything else. And <code>m</code>, as already explained, may be any monad. The corresponding C# method signature would be: </p> <p> <pre>Func&lt;T,&nbsp;Monad&lt;T1&gt;&gt;</pre> </p> <p> In C#, it's <a href="/2015/08/03/idiomatic-or-idiosyncratic">idiomatic</a> to name generic type arguments <code>T</code> and <code>T1</code> rather than <code>a</code> and <code>b</code>, but the idea is the same. </p> <p> The previous article used <code>Functor&lt;T&gt;</code> as a stand-in for any functor. Likewise, now that you know what a monad is, the type <code>Monad&lt;T&gt;</code> is a similar pretend type. It symbolises 'any monad'. </p> <h3 id="9581579bd43f47cf9973222d0bbec20c"> Kleisli composition <a href="#9581579bd43f47cf9973222d0bbec20c" title="permalink">#</a> </h3> <p> In <a href="/2021/11/22/functions-as-pipes">Functions as pipes</a> you got a visual illustration of how functions compose. If you have a function that returns a Boolean value, you can use that Boolean value as input to a function that accepts Boolean values as input. Generalised, if one function returns <code>a</code> and another function accepts <code>a</code> as input, you can compose these two functions: </p> <p> <pre>(a -&gt; b) -&gt; (b -&gt; c) -&gt; (a -&gt; c)</pre> </p> <p> A combinator of this type takes two functions as input: <code>a -&gt; b</code> (a function from <code>a</code> to <code>b</code>) and <code>(b -&gt; c)</code>, and returns a new function that 'hides' the middle step: <code>a -&gt; c</code>. </p> <p> If this is possible, it seems intuitive that you can also compose monadic functions: </p> <p> <pre>(&gt;=&gt;) :: Monad m =&gt; (a -&gt; m b) -&gt; (b -&gt; m c) -&gt; a -&gt; m c</pre> </p> <p> The <a href="https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:-62--61--62-">&gt;=&gt;</a> operator is known as the <em>fish</em> operator - or more precisely the <em>right fish</em> operator, since there's also a <em>left fish</em> operator <a href="https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:-60--61--60-">&lt;=&lt;</a>. </p> <p> This is known as <em>Kleisli composition</em>. In C# you could write it like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Func&lt;T,&nbsp;Monad&lt;T2&gt;&gt;&nbsp;<span style="color:#74531f;">Compose</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">T1</span>,&nbsp;<span style="color:#2b91af;">T2</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;Func&lt;T,&nbsp;Monad&lt;T1&gt;&gt;&nbsp;<span style="color:#1f377f;">action1</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;T1,&nbsp;Monad&lt;T2&gt;&gt;&nbsp;<span style="color:#1f377f;">action2</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;action1(x).SelectMany(action2); }</pre> </p> <p> Notice that Kleisli composition works for any monad. You don't need any new abilities in order to compose a monad in this way. The composition exclusively relies on <code>SelectMany</code> (monadic <em>bind</em>). </p> <p> Here's a usage example: </p> <p> <pre>Func&lt;<span style="color:blue;">string</span>,&nbsp;Monad&lt;<span style="color:blue;">int</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">f</span>&nbsp;=&nbsp;<span style="color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;Monad.Return(s.Length); Func&lt;<span style="color:blue;">int</span>,&nbsp;Monad&lt;<span style="color:blue;">bool</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">g</span>&nbsp;=&nbsp;<span style="color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;Monad.Return(i&nbsp;%&nbsp;2&nbsp;==&nbsp;0); Func&lt;<span style="color:blue;">string</span>,&nbsp;Monad&lt;<span style="color:blue;">bool</span>&gt;&gt;&nbsp;<span style="color:#1f377f;">composed</span>&nbsp;=&nbsp;f.Compose(g);</pre> </p> <p> The <code>Compose</code> method corresponds to the right fish operator, but obviously you could define an overload that flips the arguments. That would correspond to the left fish operator. </p> <h3 id="6c831b646c374287a07c3918097818e2"> Universality <a href="#6c831b646c374287a07c3918097818e2" title="permalink">#</a> </h3> <p> Kleisli composition seems compelling, but in reality I find that I rarely use it. If it isn't that useful, then why dedicate an entire article to it? </p> <p> As I wrote in the introduction, it's mostly because it gives us an intuitive way to describe the monad laws. </p> <p> Kleisli arrows form a <a href="https://en.wikipedia.org/wiki/Category_theory">category</a>. As such, it's a universal abstraction. I admit that <a href="/2017/10/04/from-design-patterns-to-category-theory">this article series</a> has strayed away from its initial vision of discussing category theory, but I still find it assuring when I encounter some bedrock of theory behind a programming concept. </p> <h3 id="afc020e8bbe7436b891782b8d469c111"> Conclusion <a href="#afc020e8bbe7436b891782b8d469c111" title="permalink">#</a> </h3> <p> Kleisli composition lets you compose two (or more) compatible monadic functions into a single monadic function. </p> <p> <strong>Next:</strong> <a href="/2022/04/11/monad-laws">Monad laws</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/2022/04/04/kleisli-composition Monads https://blog.ploeh.dk/2022/03/28/monads/ Mon, 28 Mar 2022 06:12:00 UTC <div id="post"> <p> <em>A monad is a common abstraction. While typically associated with Haskell, monads also exist in C# and other languages.</em> </p> <p> This article series is part of <a href="/2018/03/19/functors-applicatives-and-friends">a larger series of articles about functors, applicatives, and other mappable containers</a>. </p> <p> If you understand what a <a href="/2018/03/22/functors">functor</a> is, it should be easy to grasp the idea of a monad. <em>It's a functor you can flatten.</em> </p> <p> There's a little more to it than that, and you also need to learn what I mean by <em>flatten</em>, but that's the essence of it. </p> <p> In this article-series-within-an-article series, I'll explain this disproportionally dreaded concept, giving you plenty of examples as well as a more formal definition. Examples will be in both C#, <a href="https://fsharp.org">F#</a>, and <a href="https://www.haskell.org">Haskell</a>, although I plan to emphasise C#. I expect that there's little need of explaining monads to people already familiar with Haskell. I'll show examples as separate articles in this series. These articles are mostly aimed at object-oriented programmers curious about monads. </p> <ul> <li><a href="/2022/04/04/kleisli-composition">Kleisli composition</a></li> <li><a href="/2022/04/11/monad-laws">Monad laws</a></li> <li><a href="/2022/04/19/the-list-monad">The List monad</a></li> <li><a href="/2022/04/25/the-maybe-monad">The Maybe monad</a></li> <li><a href="/2022/05/09/an-either-monad">An Either monad</a></li> <li><a href="/2022/05/16/the-identity-monad">The Identity monad</a></li> <li>The Lazy monad</li> <li>Asynchronous monads</li> <li>The State monad</li> <li>The Reader monad</li> <li>The IO monad</li> </ul> <p> This list is far from exhaustive; more monads exist. </p> <p> <img src="/content/binary/functors-applicatives-monads.png" alt="Set diagram with monads shown as a subset of applicatives, which is shown as a subset of functors, again a subset of generic types."> </p> <p> All monads are <a href="/2018/10/01/applicative-functors">applicative functors</a>, but not all applicative functors are monads. As the set diagram reiterates, applicative functors are functors, but again: not necessarily the other way around. </p> <h3 id="a342785804ef4d5ebb6e88cef8140432"> Flattening <a href="#a342785804ef4d5ebb6e88cef8140432" title="permalink">#</a> </h3> <p> A monad is a functor you can flatten. What do I mean by <em>flatten?</em> </p> <p> As in <a href="/2018/03/22/functors">the article that introduces functors</a>, imagine that you have some <code>Functor&lt;T&gt;</code> <a href="https://bartoszmilewski.com/2014/01/14/functors-are-containers">container</a>. More concretely, this could be <code>IEnumerable&lt;T&gt;</code>, <code>Maybe&lt;T&gt;</code>, <code>Task&lt;T&gt;</code>, etcetera. </p> <p> When working with functors, you sometimes run into situations where the containers nest inside each other. Instead of a <code>Functor&lt;decimal&gt;</code>, you may find yourself with a <code>Functor&lt;Functor&lt;decimal&gt;&gt;</code>, or maybe even an object that's thrice or quadruply nested. </p> <p> If you can flatten such nested functor objects to just <code>Functor&lt;T&gt;</code>, then that functor also forms a monad. </p> <p> In C#, you need a method with this kind of signature: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Functor&lt;T&gt;&nbsp;<span style="color:#74531f;">Flatten</span>&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:blue;">this</span>&nbsp;Functor&lt;Functor&lt;T&gt;&gt;&nbsp;<span style="color:#1f377f;">source</span>)</pre> </p> <p> Notice that this method takes a <code>Functor&lt;Functor&lt;T&gt;&gt;</code> as input and returns a <code>Functor&lt;T&gt;</code> as output. I'm not showing the actual implementation, since <code>Functor&lt;T&gt;</code> is really just a 'pretend' functor (and monad). In the example articles that follow, you'll see actual implementation code. </p> <p> With <code>Flatten</code> you can write code like this: </p> <p> <pre>Functor&lt;<span style="color:blue;">decimal</span>&gt;&nbsp;<span style="color:#1f377f;">dest</span>&nbsp;=&nbsp;source.Flatten();</pre> </p> <p> Here, <code>source</code> is a <code>Functor&lt;Functor&lt;<span style="color:blue;">decimal</span>&gt;&gt;</code>. </p> <p> This function also exists in Haskell, although there, it's called <a href="https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:join">join</a>: </p> <p> <pre>join :: Monad m =&gt; m (m a) -&gt; m a</pre> </p> <p> For any <code>Monad m</code> you can flatten or join a nested monad <code>m (m a)</code> to a 'normal' monad <code>m a</code>. </p> <p> This is the same function as <code>Flatten</code>, so in C# we could define an alias like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Functor&lt;T&gt;&nbsp;<span style="color:#74531f;">Join</span>&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:blue;">this</span>&nbsp;Functor&lt;Functor&lt;T&gt;&gt;&nbsp;<span style="color:#1f377f;">source</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;source.Flatten(); }</pre> </p> <p> Usually, however, you don't see monads introduced via <code>join</code> or <code>Flatten</code>. It's a shame, really, because it's the most straightforward description. </p> <h3 id="948d267819284e61af68d575c9d294e6"> Bind <a href="#948d267819284e61af68d575c9d294e6" title="permalink">#</a> </h3> <p> Most languages that come with a notion of monads define them via a function colloquially referred to as <em>monadic bind</em> or just <em>bind</em>. In C# it's called <code>SelectMany</code>, <a href="https://docs.microsoft.com/dotnet/fsharp/language-reference/computation-expressions">F# computation expressions</a> call it <code>Bind</code>, and Scala calls it <code>flatMap</code> (with a vestige of the concept of flattening). Haskell just defines it as an operator: </p> <p> <pre>(&gt;&gt;=) :: Monad m =&gt; m a -&gt; (a -&gt; m b) -&gt; m b</pre> </p> <p> When talking about it, I tend to call the <code>&gt;&gt;=</code> operator <em>bind</em>. </p> <p> Translated to C# it has this kind of signature: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Functor&lt;TResult&gt;&nbsp;<span style="color:#74531f;">SelectMany</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;Functor&lt;T&gt;&nbsp;<span style="color:#1f377f;">source</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;T,&nbsp;Functor&lt;TResult&gt;&gt;&nbsp;<span style="color:#1f377f;">selector</span>)</pre> </p> <p> It looks almost like a functor's <code>Select</code> method (AKA <code>map</code> or <code>fmap</code> function). The difference is that this <code>selector</code> returns a functor value (<code>Functor&lt;TResult&gt;</code>) rather than a 'naked' <code>TResult</code> value. </p> <p> When a <code>Flatten</code> (or <code>Join</code>) method already exists, you can always implement <code>SelectMany</code> like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Functor&lt;TResult&gt;&nbsp;<span style="color:#74531f;">SelectMany</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;Functor&lt;T&gt;&nbsp;<span style="color:#1f377f;">source</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;T,&nbsp;Functor&lt;TResult&gt;&gt;&nbsp;<span style="color:#1f377f;">selector</span>) { &nbsp;&nbsp;&nbsp;&nbsp;Functor&lt;Functor&lt;TResult&gt;&gt;&nbsp;<span style="color:#1f377f;">nest</span>&nbsp;=&nbsp;source.Select(selector); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;nest.Flatten(); }</pre> </p> <p> I've split the implementation over two lines of code to make it clearer what's going on. That's also the reason I've used an explicit type declaration rather than <code>var</code>. </p> <p> The <code>Select</code> method exists because the type is already a functor. When you call <code>Select</code> with <code>selector</code> you get a <code>Functor&lt;Functor&lt;TResult&gt;&gt;</code> because <code>selector</code> itself returns a <code>Functor&lt;TResult&gt;</code>. That's a nested functor, which you can <code>Flatten</code>. </p> <p> You can use <code>SelectMany</code> like this: </p> <p> <pre>Functor&lt;TimeSpan&gt;&nbsp;<span style="color:#1f377f;">source</span>&nbsp;=&nbsp;Functor.Return(TimeSpan.FromMinutes(32)); Functor&lt;<span style="color:blue;">double</span>&gt;&nbsp;<span style="color:#1f377f;">dest</span>&nbsp;=&nbsp;source.SelectMany(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;Functor.Return(x.TotalSeconds&nbsp;+&nbsp;192));</pre> </p> <p> The lambda expression returns a <code>Functor&lt;double&gt;</code>. Had you called <code>Select</code> with this lambda expression, the result would have been a nested functor. <code>SelectMany</code>, however, flattens while it maps (it <em>flatMaps</em>). (This example is rather inane, since it would be simpler to use <code>Select</code> and omit wrapping the output of the lambda in the functor. The later articles in this series will show some more compelling examples.) </p> <p> If you already have <code>Flatten</code> (or <code>Join</code>) you can always implement <code>SelectMany</code> like this. Usually, however, languages use monadic bind (e.g. <code>SelectMany</code>) as the foundation. Both C#, Haskell, and F# do that. In that case, it's also possible to go the other way and implement <code>Flatten</code> with <code>SelectMany</code>. You'll see examples of that in the subsequent articles. </p> <h3 id="ed8ec161f2f3424089c5c0cee07d5fbd"> Syntactic sugar <a href="#ed8ec161f2f3424089c5c0cee07d5fbd" title="permalink">#</a> </h3> <p> Several languages understand monads well enough to provide some degree of syntactic sugar. While you can always use <code>SelectMany</code> in C# by simply calling the method, there are situations where that becomes awkward. The same is true with <code>bind</code> functions in F# and <code>&gt;&gt;=</code> in Haskell. </p> <p> In C# you can use <em>query syntax</em>: </p> <p> <pre>Functor&lt;DateTime&gt;&nbsp;<span style="color:#1f377f;">fdt</span>&nbsp;=&nbsp;Functor.Return(<span style="color:blue;">new</span>&nbsp;DateTime(2001,&nbsp;8,&nbsp;3)); Functor&lt;TimeSpan&gt;&nbsp;<span style="color:#1f377f;">fts</span>&nbsp;=&nbsp;Functor.Return(TimeSpan.FromDays(4)); Functor&lt;DateTime&gt;&nbsp;<span style="color:#1f377f;">dest</span>&nbsp;=&nbsp;<span style="color:blue;">from</span>&nbsp;dt&nbsp;<span style="color:blue;">in</span>&nbsp;fdt &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;">from</span>&nbsp;ts&nbsp;<span style="color:blue;">in</span>&nbsp;fts &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;">select</span>&nbsp;dt&nbsp;-&nbsp;ts;</pre> </p> <p> In order to support more than a single <code>from</code> expression, however, you must supply a special <code>SelectMany</code> overload, or the code doesn't compile: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Functor&lt;TResult&gt;&nbsp;<span style="color:#74531f;">SelectMany</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">U</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;Functor&lt;T&gt;&nbsp;<span style="color:#1f377f;">source</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;T,&nbsp;Functor&lt;U&gt;&gt;&nbsp;<span style="color:#1f377f;">k</span>, &nbsp;&nbsp;&nbsp;&nbsp;Func&lt;T,&nbsp;U,&nbsp;TResult&gt;&nbsp;<span style="color:#1f377f;">s</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;source.SelectMany(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;k(x).Select(<span style="color:#1f377f;">y</span>&nbsp;=&gt;&nbsp;s(x,&nbsp;y))); }</pre> </p> <p> This is an odd quirk of C# that I've yet to encounter in other languages, and I consider it <a href="/2019/12/16/zone-of-ceremony">ceremony</a> that I have to perform to satiate the C# compiler. It's not part of the concept of what a monad is. As far as I can tell, you can always implement it like shown here. </p> <p> Haskell's syntactic sugar is called <em>do notation</em> and works for all monads: </p> <p> <pre><span style="color:#2b91af;">example</span>&nbsp;::&nbsp;(<span style="color:blue;">Monad</span>&nbsp;m,&nbsp;<span style="color:blue;">Num</span>&nbsp;a)&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;m&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;m&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;m&nbsp;a example&nbsp;fdt&nbsp;fts&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;dt&nbsp;&lt;-&nbsp;fdt &nbsp;&nbsp;ts&nbsp;&lt;-&nbsp;fts &nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;dt&nbsp;-&nbsp;ts</pre> </p> <p> In F#, <a href="https://docs.microsoft.com/dotnet/fsharp/language-reference/computation-expressions">computation expressions</a> drive syntactic sugar, but still based (among other things) on the concept of a monad: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;example&nbsp;(fdt&nbsp;:&nbsp;Monad&lt;DateTime&gt;)&nbsp;(fts&nbsp;:&nbsp;Monad&lt;TimeSpan&gt;)&nbsp;=&nbsp;monad&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;dt&nbsp;=&nbsp;fdt &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;ts&nbsp;=&nbsp;fts &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;dt&nbsp;-&nbsp;ts&nbsp;}</pre> </p> <p> Here, we again have to pretend that a <code>Monad&lt;'a&gt;</code> type exists, with a companion <code>monad</code> computation expression. </p> <h3 id="440abd098e1144c78229eb0ee2d0ad4f"> Return <a href="#440abd098e1144c78229eb0ee2d0ad4f" title="permalink">#</a> </h3> <p> The ability to flatten nested functors is the essence of what a monad is. There are, however, also some formal requirements. As is the case with functors, there are laws that a monad should obey. I'll dedicate <a href="/2022/04/11/monad-laws">a separate article</a> for those, so we'll skip them for now. </p> <p> Another requirement is that in addition to <code>SelectMany</code>/<code>bind</code>/<code>flatMap</code>/<code>&gt;&gt;=</code> a monad must also provide a method to 'elevate' a value to the monad. This function is usually called <em>return</em>. It should have a type like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;Functor&lt;T&gt;&nbsp;<span style="color:#74531f;">Return</span>&lt;<span style="color:#2b91af;">T</span>&gt;(T&nbsp;<span style="color:#1f377f;">x</span>)</pre> </p> <p> You can see it in use in the above code snippet, and with the relevant parts repeated here: </p> <p> <pre>Functor&lt;DateTime&gt;&nbsp;<span style="color:#1f377f;">fdt</span>&nbsp;=&nbsp;Functor.Return(<span style="color:blue;">new</span>&nbsp;DateTime(2001,&nbsp;8,&nbsp;3)); Functor&lt;TimeSpan&gt;&nbsp;<span style="color:#1f377f;">fts</span>&nbsp;=&nbsp;Functor.Return(TimeSpan.FromDays(4));</pre> </p> <p> This code example lifts the value <code>DateTime(2001,&nbsp;8,&nbsp;3)</code> to a <code>Functor&lt;DateTime&gt;</code> value, and the value <code>TimeSpan.FromDays(4)</code> to a <code>Functor&lt;TimeSpan&gt;</code> value. </p> <p> Usually, in a language like C# a concrete monad type may either afford a constructor or factory method for this purpose. You'll see examples in the articles that give specific monad examples. </p> <h3 id="558c849b4c644f9fb28c788aa43cb263"> Conclusion <a href="#558c849b4c644f9fb28c788aa43cb263" title="permalink">#</a> </h3> <p> A monad is a functor you can flatten. That's the simplest way I can put it. </p> <p> In this article you learned what <em>flattening</em> means. You also learned that a monad must obey some laws and have a <em>return</em> function. The essence, however, is flattening. The laws just ensure that the flattening is well-behaved. </p> <p> It may not yet be clear to you why some functors would need flattening in the first place, but subsequent articles will show examples. </p> <p> The word <em>monad</em> has its own mystique in software development culture. If you've ever encountered some <a href="/2021/06/07/abstruse-nomenclature">abstruse nomenclature</a> about monads, then try to forget about it. The concept is really not hard to grasp, and it usually clicks once you've seen enough examples, and perhaps done some exercises. </p> <p> <strong>Next:</strong> <a href="/2022/04/04/kleisli-composition">Kleisli composition</a>. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="86bf8188e50f4dee891bde7f2b7a8225"> <div class="comment-author"><a href="https://about.me/tysonwilliams">Tyson Williams</a></div> <div class="comment-content"> <p>Quoting image in words:</p> <blockquote> <ul> <li>Every Monad is an applicative functor</li> <li>Every applicative functor is a functor</li> <li>Every functor is a generic type</li> </ul> </blockquote> <p> As your aricle about <a href="https://blog.ploeh.dk/2020/10/19/monomorphic-functors/">Monomorphic functors</a> shows, not every functor is a generic type. However, it is true that every applicative functor is a generic (or polymorphic) functor. </p> </div> <div class="comment-date">2022-04-18 15:28 UTC</div> </div> <div class="comment" id="2971857cfe8d4766bb48b37ce92eef4b"> <div class="comment-author"><a href="/">Mark Seemann</a></div> <div class="comment-content"> <p> True, the illustration is a simplification. </p> </div> <div class="comment-date">2022-04-18 20:38 UTC</div> </div> <div class="comment" id="adddc3fdc50ac979899dfbe272794544"> <div class="comment-author"><a href="https://github.com/mormegil-cz">Petr Kadlec</a></div> <div class="comment-content"> <p> I guess you might know that already but the reason for the strange <code>SelectMany</code> ceremonial version is compiler performance. The complicated form is needed so that the overload resolution does not take exponential amount of time. See <a href="https://ericlippert.com/2013/04/02/monads-part-twelve/">a 2013 article by Eric Lippert covering this</a>. </p> </div> <div class="comment-date">2022-05-02 11:50 UTC</div> </div> <div class="comment" id="f7409894f143485683c9862221f3a903"> <div class="comment-author"><a href="/">Mark Seemann</a></div> <div class="comment-content"> <p> Petr, thank you for writing. I remember reading about it before, but it's good to have a proper source. </p> <p> If I understand the article correctly, the problem seems to originate from overload resolution. This would, at least, explain why neither F# nor Haskell needs that extra overload. I wonder if a language like Java would have a similar problem, but I don't think that Java has syntactic sugar for monads. </p> <p> It still seems a little strange that the C# compiler <em>requires</em> the presence of that overload. Eric Lippert seems to strongly imply that it's always possible to derive that extra overload from any monad's fundamental functions (as is also my conjecture). If this is so, the C# compiler should be able to do that work by itself. Monads that wish to supply a more efficient implement (e.g. <code>IEnumerable&lt;T&gt;</code>) could still do so: The C# compiler could look for the overload and use it if it finds it, and still fall back to the default implementation if none is available. </p> <p> But I suppose that since the query syntax feature only really exists to support <code>IEnumerable&lt;T&gt;</code> this degree of sophistication wasn't warranted. </p> </div> <div class="comment-date">2022-05-03 6:12 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/2022/03/28/monads Contravariant Dependency Injection https://blog.ploeh.dk/2022/03/21/contravariant-dependency-injection/ Mon, 21 Mar 2022 06:46:00 UTC <div id="post"> <p> <em>How to use a DI Container in FP... or not.</em> </p> <p> This article is an instalment in <a href="/2021/09/02/contravariant-functors">an article series about contravariant functors</a>. It assumes that you've read the introduction, and a few of the examples. </p> <p> People sometimes ask me how to do Dependency Injection (DI) in Functional Programming (FP). The short answer is that <a href="/2017/01/27/from-dependency-injection-to-dependency-rejection">you don't, because dependencies make functions impure</a>. If you're having the discussion on Twitter, you may get some drive-by comments to the effect that <em>DI is just a contravariant functor</em>. (I've seen such interactions take place, but currently can't find the specific examples.) </p> <p> What might people mean by that? </p> <p> In this article, I'll explain. You'll also see how this doesn't address the underlying problem that DI makes everything impure. Ultimately, then, it doesn't really matter. It's still not functional. </p> <h3 id="43f01ded1bbd42e28a90f398152518ff"> Partial application as Dependency Injection <a href="#43f01ded1bbd42e28a90f398152518ff" title="permalink">#</a> </h3> <p> As example code, let's revisit the code from the article <a href="/2017/01/30/partial-application-is-dependency-injection">Partial application is dependency injection</a>. You may have an impure action like this: </p> <p> <pre><span style="color:green;">//&nbsp;int&nbsp;-&gt;&nbsp;(DateTimeOffset&nbsp;-&gt;&nbsp;Reservation&nbsp;list)&nbsp;-&gt;&nbsp;(Reservation&nbsp;-&gt;&nbsp;int)&nbsp;-&gt;&nbsp;Reservation</span> <span style="color:green;">//&nbsp;-&gt;&nbsp;int&nbsp;option</span> <span style="color:blue;">let</span>&nbsp;tryAccept&nbsp;capacity&nbsp;readReservations&nbsp;createReservation&nbsp;reservation&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;reservedSeats&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;readReservations&nbsp;reservation.Date&nbsp;|&gt;&nbsp;List.sumBy&nbsp;(<span style="color:blue;">fun</span>&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;x.Quantity) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;reservedSeats&nbsp;+&nbsp;reservation.Quantity&nbsp;&lt;=&nbsp;capacity &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">then</span>&nbsp;createReservation&nbsp;{&nbsp;reservation&nbsp;<span style="color:blue;">with</span>&nbsp;IsAccepted&nbsp;=&nbsp;<span style="color:blue;">true</span>&nbsp;}&nbsp;|&gt;&nbsp;Some &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span>&nbsp;None</pre> </p> <p> The <code>readReservations</code> and <code>createReservation</code> 'functions' will in reality be impure actions that read from and write to a database. Since they are impure, the entire <code>tryAccept</code> action is impure. That's the result from that article. </p> <p> In this example the 'dependencies' are pushed to the left. This enables you to partially apply the 'function' with the dependencies: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;sut&nbsp;=&nbsp;tryAccept&nbsp;capacity&nbsp;readReservations&nbsp;createReservation</pre> </p> <p> This code example is from a unit test, which is the reason that I've <a href="https://docs.microsoft.com/en-us/archive/blogs/ploeh/naming-sut-test-variables">named the partially applied 'function' <code>sut</code></a>. It has the type <code>Reservation -&gt; int option</code>. Keep in mind that while it looks like a regular function, in practice it'll be an impure action. </p> <p> You can invoke <code>sut</code> like another other function: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;sut&nbsp;reservation</pre> </p> <p> When you do this, <code>tryAccept</code> will execute, interact with the partially applied dependencies, and return a result. </p> <p> Partial application is a standard practice in FP, and in itself it's useful. Using it for Dependency Injection, however, doesn't magically make DI functional. DI remains impure, which also means that the entire <code>sut</code> composition is impure. </p> <h3 id="88c2633d1dd34a979aaca1a223ff665b"> Moving dependencies to the right <a href="#88c2633d1dd34a979aaca1a223ff665b" title="permalink">#</a> </h3> <p> Pushing dependencies to the left enables partial application. Dependencies are typically more long-lived than run-time values like <code>reservation</code>. Thus, partially applying the dependencies as shown above makes sense. If all dependencies are thread-safe, you can let an action like <code>sut</code>, above, have Singleton lifetime. In other words, just keep a single, stateless <code>Reservation -&gt; int option</code> action around for the lifetime of the application, and pass it <code>Reservation</code> values as they arrive. </p> <p> Moving dependencies to the right seems, then, counterproductive. </p> <p> <pre><span style="color:green;">//&nbsp;Reservation&nbsp;-&gt;&nbsp;int&nbsp;-&gt;&nbsp;(DateTimeOffset&nbsp;-&gt;&nbsp;Reservation&nbsp;list)&nbsp;-&gt;&nbsp;(Reservation&nbsp;-&gt;&nbsp;int)</span> <span style="color:green;">//&nbsp;-&gt;&nbsp;int&nbsp;option</span> <span style="color:blue;">let</span>&nbsp;tryAccept&nbsp;reservation&nbsp;capacity&nbsp;readReservations&nbsp;createReservation&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;reservedSeats&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;readReservations&nbsp;reservation.Date&nbsp;|&gt;&nbsp;List.sumBy&nbsp;(<span style="color:blue;">fun</span>&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;x.Quantity) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;reservedSeats&nbsp;+&nbsp;reservation.Quantity&nbsp;&lt;=&nbsp;capacity &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">then</span>&nbsp;createReservation&nbsp;{&nbsp;reservation&nbsp;<span style="color:blue;">with</span>&nbsp;IsAccepted&nbsp;=&nbsp;<span style="color:blue;">true</span>&nbsp;}&nbsp;|&gt;&nbsp;Some &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span>&nbsp;None</pre> </p> <p> If you move the dependencies to the right, you can no longer partially apply them, so what would be the point of that? </p> <p> As given above, it seems that you'll have to supply all arguments in one go: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;tryAccept&nbsp;reservation&nbsp;capacity&nbsp;readReservations&nbsp;createReservation</pre> </p> <p> If, on the other hand, you turn all the dependencies into a tuple, some new options arise: </p> <p> <pre><span style="color:green;">//&nbsp;Reservation&nbsp;-&gt;&nbsp;(int&nbsp;*&nbsp;(DateTimeOffset&nbsp;-&gt;&nbsp;Reservation&nbsp;list)&nbsp;*&nbsp;(Reservation&nbsp;-&gt;&nbsp;int))</span> <span style="color:green;">//&nbsp;-&gt;&nbsp;int&nbsp;option</span> <span style="color:blue;">let</span>&nbsp;tryAccept&nbsp;reservation&nbsp;(capacity,&nbsp;readReservations,&nbsp;createReservation)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;reservedSeats&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;readReservations&nbsp;reservation.Date&nbsp;|&gt;&nbsp;List.sumBy&nbsp;(<span style="color:blue;">fun</span>&nbsp;x&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;x.Quantity) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;reservedSeats&nbsp;+&nbsp;reservation.Quantity&nbsp;&lt;=&nbsp;capacity &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">then</span>&nbsp;createReservation&nbsp;{&nbsp;reservation&nbsp;<span style="color:blue;">with</span>&nbsp;IsAccepted&nbsp;=&nbsp;<span style="color:blue;">true</span>&nbsp;}&nbsp;|&gt;&nbsp;Some &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span>&nbsp;None</pre> </p> <p> I decided to count <code>capacity</code> as a dependency, since this is most likely a value that originates from a configuration setting somewhere. Thus, it'd tend to have a singleton lifetime equivalent to <code>readReservations</code> and <code>createReservation</code>. </p> <p> It still seems that you have to supply all the arguments, though: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;tryAccept&nbsp;reservation&nbsp;(capacity,&nbsp;readReservations,&nbsp;createReservation)</pre> </p> <p> What's the point, then? </p> <h3 id="8bf311e8b5184d1396e7f49b5b9d9b48"> Reader <a href="#8bf311e8b5184d1396e7f49b5b9d9b48" title="permalink">#</a> </h3> <p> You can view all functions as values of the <a href="/2021/11/08/reader-as-a-profunctor">Reader profunctor</a>. This, then, is also true for <code>tryAccept</code>. It's an (impure) function that takes a <code>Reservation</code> as input, and returns a Reader value as output. The 'Reader environment' is a tuple of dependencies, and the output is <code>int option</code>. </p> <p> First, add an explicit <code>Reader</code> module: </p> <p> <pre><span style="color:green;">//&nbsp;&#39;a&nbsp;-&gt;&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b)&nbsp;-&gt;&nbsp;&#39;b</span> <span style="color:blue;">let</span>&nbsp;run&nbsp;env&nbsp;rdr&nbsp;=&nbsp;rdr&nbsp;env <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;(&#39;b&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;&#39;a&nbsp;-&gt;&nbsp;&#39;d</span> <span style="color:blue;">let</span>&nbsp;dimap&nbsp;f&nbsp;g&nbsp;rdr&nbsp;=&nbsp;<span style="color:blue;">fun</span>&nbsp;env&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;g&nbsp;(rdr&nbsp;(f&nbsp;env)) <span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b)&nbsp;-&gt;&nbsp;(&#39;c&nbsp;-&gt;&nbsp;&#39;a)&nbsp;-&gt;&nbsp;&#39;c&nbsp;-&gt;&nbsp;&#39;b</span> <span style="color:blue;">let</span>&nbsp;map&nbsp;g&nbsp;=&nbsp;dimap&nbsp;id&nbsp;g <span style="color:green;">//&nbsp;(&#39;a&nbsp;-&gt;&nbsp;&#39;b)&nbsp;-&gt;&nbsp;(&#39;b&nbsp;-&gt;&nbsp;&#39;c)&nbsp;-&gt;&nbsp;&#39;a&nbsp;-&gt;&nbsp;&#39;c</span> <span style="color:blue;">let</span>&nbsp;contraMap&nbsp;f&nbsp;=&nbsp;dimap&nbsp;f&nbsp;id</pre> </p> <p> The <code>run</code> function is mostly there to make the Reader concept more explicit. The <code>dimap</code> implementation is what makes Reader a <a href="/2021/11/01/profunctors">profunctor</a>. You can use <code>dimap</code> to implement <code>map</code> and <code>contraMap</code>. In the following, we're not going to need <code>map</code>, but I still included it for good measure. </p> <p> You can partially apply the last version of <code>tryAccept</code> with a <code>reservation</code>: </p> <p> <pre><span style="color:green;">//&nbsp;sut&nbsp;:&nbsp;(int&nbsp;*&nbsp;(DateTimeOffset&nbsp;-&gt;&nbsp;Reservation&nbsp;list)&nbsp;*&nbsp;(Reservation&nbsp;-&gt;&nbsp;int))&nbsp;-&gt;&nbsp;int&nbsp;option</span> <span style="color:blue;">let</span>&nbsp;sut&nbsp;=&nbsp;tryAccept&nbsp;reservation</pre> </p> <p> You can view the <code>sut</code> value as a Reader. The 'environment' is the tuple of dependencies, and the output is still <code>int option</code>. Since we can <a href="/2022/03/07/a-type-safe-di-container-as-a-tuple">view a tuple as a type-safe DI Container</a>, we've now introduced a DI Container to the 'function'. We can say that the action is a Reader of the DI Container. </p> <p> You can <code>run</code> the action by supplying a <code>container</code>: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;container&nbsp;=&nbsp;(capacity,&nbsp;readReservations,&nbsp;createReservation) <span style="color:blue;">let</span>&nbsp;sut&nbsp;=&nbsp;tryAccept&nbsp;reservation <span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;sut&nbsp;|&gt;&nbsp;Reader.run&nbsp;container</pre> </p> <p> This <code>container</code>, however, is specialised to fit <code>tryAccept</code>. What if other actions require other dependencies? </p> <h3 id="ada91148e72f45e3b274d89e19644f50"> Contravariant mapping <a href="#ada91148e72f45e3b274d89e19644f50" title="permalink">#</a> </h3> <p> In a larger system, you're likely to have more than the three dependencies shown above. Other actions require other dependencies, and may not need <code>capacity</code>, <code>readReservations</code>, or <code>createReservation</code>. </p> <p> To make the point, perhaps the <code>container</code> looks like this: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;container&nbsp;=&nbsp;(capacity,&nbsp;readReservations,&nbsp;createReservation,&nbsp;someOtherService,&nbsp;yetAnotherService)</pre> </p> <p> If you try to <code>run</code> a partially applied Reader like <code>sut</code> with this action, your code doesn't compile. <code>sut</code> needs a triple of a specific type, but <code>container</code> is now a pentuple. Should you change <code>tryAccept</code> so that it takes the bigger pentuple as a parameter? </p> <p> That would compile, but would be a leaky abstraction. It would also violate the <a href="https://en.wikipedia.org/wiki/Dependency_inversion_principle">Dependency Inversion Principle</a> and the <a href="https://en.wikipedia.org/wiki/Interface_segregation_principle">Interface Segregation Principle</a> because <code>tryAccept</code> would require callers to supply a bigger argument than is needed. </p> <p> Instead, you can <code>contraMap</code> the pentuple: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;container&nbsp;=&nbsp;(capacity,&nbsp;readReservations,&nbsp;createReservation,&nbsp;someOtherService,&nbsp;yetAnotherService) <span style="color:blue;">let</span>&nbsp;sut&nbsp;=&nbsp;tryAccept&nbsp;reservation&nbsp;|&gt;&nbsp;Reader.contraMap&nbsp;(<span style="color:blue;">fun</span>&nbsp;(c,&nbsp;rr,&nbsp;cr,&nbsp;_,&nbsp;_)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(c,&nbsp;rr,&nbsp;cr)) <span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;sut&nbsp;|&gt;&nbsp;Reader.run&nbsp;container</pre> </p> <p> This turns <code>sut</code> into a Reader of the pentuple, instead of a Reader of the triple. You can now <code>run</code> it with the pentuple <code>container</code>. <code>tryAccept</code> remains a Reader of the triple. </p> <h3 id="e8cb20a7be2342f7802f6522fa5edd5a"> Conclusion <a href="#e8cb20a7be2342f7802f6522fa5edd5a" title="permalink">#</a> </h3> <p> Keep in mind that <code>tryAccept</code> remains impure. While this may look impressively functional, it really isn't. It doesn't address the original problem that <a href="/2021/07/28/referential-transparency-fits-in-your-head">composition of impure actions creates larger impure actions that don't fit in your head</a>. </p> <p> Why, then, make things more complicated than they have to be? </p> <p> In FP, I'd look long and hard for a better alternative - one that obeys <a href="/2018/11/19/functional-architecture-a-definition">the functional architecture law</a>. If, for various reasons, I was unable to produce a purely functional design, I'd prefer composing impure actions with partial application. It's simpler. </p> <p> This article isn't an endorsement of using contravariant DI in FP. It's only meant as an explanation of a phrase like <em>DI is just a contravariant functor</em>. </p> <p> <strong>Next:</strong> <a href="/2021/11/01/profunctors">Profunctors</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/2022/03/21/contravariant-dependency-injection Type-safe DI Containers are redundant https://blog.ploeh.dk/2022/03/14/type-safe-di-containers-are-redundant/ Mon, 14 Mar 2022 05:27:00 UTC <div id="post"> <p> <em>Just use Pure DI.</em> </p> <p> This article is part of a series called <a href="/2022/01/10/type-safe-di-composition">Type-safe DI composition</a>. In the previous article, you saw <a href="/2022/03/07/a-type-safe-di-container-as-a-tuple">how tuples are adequate DI Containers</a>. In case it's not clear from the article that introduces the series, there's really no point to any of this. My motivation for writing the article is that readers sometimes ask me about topics such as DI Containers versus type safety, or DI Containers in functional programming. The goal of these articles is to make it painfully clear why I find such ideas moot. </p> <h3 id="5cc2827dd110479c980af791313d03da"> Tuples as DI Containers <a href="#5cc2827dd110479c980af791313d03da" title="permalink">#</a> </h3> <p> In the <a href="/2022/03/07/a-type-safe-di-container-as-a-tuple">previous article</a> you saw how tuples make adequate DI Containers. Consider, however, this constructor: </p> <p> <pre><span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;(IRestaurantDatabase&nbsp;rdb,&nbsp;IClock&nbsp;clock,&nbsp;IReservationsRepository&nbsp;repo)&nbsp;container; <span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">CompositionRoot</span>( &nbsp;&nbsp;&nbsp;&nbsp;(IRestaurantDatabase&nbsp;rdb,&nbsp;IClock&nbsp;clock,&nbsp;IReservationsRepository&nbsp;repo)&nbsp;<span style="color:#1f377f;">container</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.container&nbsp;=&nbsp;container; }</pre> </p> <p> One question, though: Why pass a tuple of three objects as a single argument? Wouldn't it be more <a href="/2015/08/03/idiomatic-or-idiosyncratic">idiomatic</a> to use a normal argument list? </p> <h3 id="1612596b46e045bbae911e2868a4bbfe"> Argument list <a href="#1612596b46e045bbae911e2868a4bbfe" title="permalink">#</a> </h3> <p> Just remove the brackets around the tuple argument and dissolve the elements into separate class fields: </p> <p> <pre><span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;IRestaurantDatabase&nbsp;rdb; <span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;IClock&nbsp;clock; <span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;IReservationsRepository&nbsp;repo; <span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">CompositionRoot</span>(IRestaurantDatabase&nbsp;<span style="color:#1f377f;">rdb</span>,&nbsp;IClock&nbsp;<span style="color:#1f377f;">clock</span>,&nbsp;IReservationsRepository&nbsp;<span style="color:#1f377f;">repo</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.rdb&nbsp;=&nbsp;rdb; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.clock&nbsp;=&nbsp;clock; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.repo&nbsp;=&nbsp;repo; }</pre> </p> <p> You no longer need to <a href="/2010/09/29/TheRegisterResolveReleasepattern">resolve</a> services from a DI Container. You can simply use the class fields directly: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">object</span>&nbsp;<span style="color:#74531f;">Create</span>(ControllerContext&nbsp;<span style="color:#1f377f;">context</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(context&nbsp;<span style="color:blue;">is</span>&nbsp;<span style="color:blue;">null</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">throw</span>&nbsp;<span style="color:blue;">new</span>&nbsp;ArgumentNullException(nameof(context)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">t</span>&nbsp;=&nbsp;context.ActionDescriptor.ControllerTypeInfo; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(t&nbsp;==&nbsp;<span style="color:blue;">typeof</span>(CalendarController)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;CalendarController(rdb,&nbsp;repo); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">else</span>&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(t&nbsp;==&nbsp;<span style="color:blue;">typeof</span>(HomeController)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;HomeController(rdb); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">else</span>&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(t&nbsp;==&nbsp;<span style="color:blue;">typeof</span>(ReservationsController)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;ReservationsController(clock,&nbsp;rdb,&nbsp;repo); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">else</span>&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(t&nbsp;==&nbsp;<span style="color:blue;">typeof</span>(RestaurantsController)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;RestaurantsController(rdb); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">else</span>&nbsp;<span style="color:#8f08c4;">if</span>&nbsp;(t&nbsp;==&nbsp;<span style="color:blue;">typeof</span>(ScheduleController)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;<span style="color:blue;">new</span>&nbsp;ScheduleController( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;rdb, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;repo, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AccessControlList.FromUser(context.HttpContext.User)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">else</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">throw</span>&nbsp;<span style="color:blue;">new</span>&nbsp;ArgumentException( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#a31515;">$&quot;Unexpected&nbsp;controller&nbsp;type:&nbsp;</span>{t}<span style="color:#a31515;">.&quot;</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nameof(context)); }</pre> </p> <p> Instead of <code>container.rdb</code>, <code>container.repo</code>, and <code>container.clock</code>, you can simply access <code>rdb</code>, <code>repo</code>, and <code>clock</code>. </p> <p> The <a href="/2010/09/29/TheRegisterResolveReleasepattern">registration phase</a> (such as it now remains) also becomes simpler: </p> <p> <pre><span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">rdb</span>&nbsp;=&nbsp;CompositionRoot.CreateRestaurantDatabase(Configuration); <span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">po</span>&nbsp;=&nbsp;CompositionRoot.CreatePostOffice(Configuration,&nbsp;rdb); <span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">clock</span>&nbsp;=&nbsp;CompositionRoot.CreateClock(); <span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">repo</span>&nbsp;=&nbsp;CompositionRoot.CreateRepository(Configuration,&nbsp;po); <span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">compositionRoot</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;CompositionRoot(rdb,&nbsp;clock,&nbsp;repo); services.AddSingleton&lt;IControllerActivator&gt;(compositionRoot);</pre> </p> <p> There's no longer any remnant of a DI Container. This is <a href="/2014/06/10/pure-di">Pure DI</a>. </p> <h3 id="b7d5b475bb88437ca9a39c6d2fbda35a"> Conclusion <a href="#b7d5b475bb88437ca9a39c6d2fbda35a" title="permalink">#</a> </h3> <p> Type-safe DI Containers are redundant. The simplest way to compose dependencies in a type-safe fashion is to write normal code, i.e. Pure DI. </p> <p> What about 'normal' DI Containers, though? These aren't type-safe, but <a href="/2012/11/06/WhentouseaDIContainer">may have their uses</a>. They represent a trade-off. For sufficiently complicated code bases, they may offer some benefits. </p> <p> I typically don't consider the trade-off worthwhile. The keywords in the above paragraph are 'sufficiently complicated'. Instead of writing complicated code, I favour simplicity: <a href="/code-that-fits-in-your-head">code that fits in my head</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/2022/03/14/type-safe-di-containers-are-redundant