10 Working effectively with multi-argument functions

This chapter covers

• Using multi-argument functions with elevated types
• Using LINQ syntax with any monadic type
• Fundamentals of property-based testing

The main goal of this chapter is to teach you to use multi-argument functions in the world of effectful types, so the “effectively” in the title is also a pun! Remember from section 6.6.1, effectful types are types such as Option (which adds the effect of optionality), Exceptional (exception handling), IEnumerable (aggregation), and others. In part 3, you’ll see several more effects related to state, laziness, and asynchrony.

As you code more functionally, you’ll come to rely heavily on these effects. You probably already use IEnumerable a lot. If you embrace the fact that types like Option and some variation of Either add robustness to your programs, you’ll soon be dealing in elevated types in much of your code.

Although you’ve seen the power of core functions like Map and Bind, there’s an important technique you haven’t seen yet: how to integrate multi-argument functions in your workflows, given that Map and Bind both take unary functions.

It turns out that there are two possible approaches: the applicative and monadic approaches. We’ll first look at the applicative approach, which uses the Apply function (a core function you haven’t seen yet). We’ll then revisit monads, and you’ll see how you can use Bind with multi-argument functions and how LINQ syntax can be helpful in this area. We’ll then compare the two approaches and see why both can be useful in different cases. Along the way, I’ll also present some of the theory related to monads and applicatives, and I’ll introduce a technique for unit testing called property-based testing.

10.1 Function application in the elevated world

In this section, I’ll introduce the applicative approach, which relies on the definition of a new function, Apply, that performs function application in the elevated world. Apply, like Map and Bind, is one of the core functions in FP.

To warm up, start the REPL and import the LaYumba.Functional library as usual. Then, type the following:

var doubl = (int i) => i * 2;
 
Some(3).Map(doubl) // => Some(6)

So far, nothing new: you have a number wrapped in an Option, and you can apply the unary function doubl to it with Map. Now, say you have a binary function like multiplication, and you have two numbers, each wrapped in an Option. How can you apply the function to its arguments?

Here’s the key concept: currying (which was covered in chapter 9) allows you to turn any n-ary function into a unary function that, when given its argument, returns a (n–1)-ary function. This means you can use Map with any function as long as it’s curried! Let’s see this in practice as the following listing shows.

Listing 10.1 Mapping a curried function onto an Option

var multiply = (int x) => (int y) => x * y;
 
var multBy3 = Some(3).Map(multiply);
// => Some(y => 3 * y))

Remember, when you Map a function onto an Option, Map extracts the value in the Option and applies the given function to it. In the preceding listing, Map extracts the value 3 from Option and feeds it to the multiply function: 3 replaces the variable x, yielding the function y => 3 * y. Let’s look at the types:

multiply              : int → int → int
Some(3)               : Option<int>
Some(3).Map(multiply) : Option<int → int>

When you map a multi-argument function, the function is partially applied to the argument wrapped in the Option. Let’s look at this from a more general point of view. Here’s the signature of Map for a functor F:

Map : F<T> → (T → R) → F<R>

Now imagine that the type of R happens to be T1 → T2, so R is actually a function. In that case, the signature expands to

F<T> → (T → T1 → T2) → F<T1 → T2>

But look at the second argument: T → T1 → T2. That’s a binary function in curried form. This means that you can use Map with functions of any arity! In order to free the caller from having to curry functions, my functional library includes overloads of Map that accept functions of various arities and takes care of currying: for example,

public static Option<Func<T2, R>> Map<T1, T2, R>
   (this Option<T1> opt, Func<T1, T2, R> func)
   => opt.Map(func.Curry());

As a result, the code in the following listing also works.

Listing 10.2 Mapping a binary function onto an Option

var multiply = (int x, int y) => x * y;
 
var multBy3 = Some(3).Map(multiply);
multBy3 // => Some(y => 3 * y))

Now that you know you can effectively use Map with multi-argument functions, let’s look at the resulting value. This is something you’ve not seen before: an elevated function, which is a function wrapped in an elevated type, as figure 10.1 illustrates.

There’s nothing special about an elevated function. Functions are values, so it’s simply another value wrapped in one of the usual containers.

And yet, how do you deal with an elevated value that’s a function? Now that you have a unary function wrapped in an Option, how do you supply it its second argument? And what if the second argument is also wrapped in an Option? A crude approach would be to explicitly unwrap both values and then apply the function to the argument like this:

var multiply = (int x, int y) => x * y;
 
Option<int> optX = Some(3)
          , optY = Some(4);
 
var result = optX.Map(multiply).Match
(
   () => None,
   (f) => optY.Match
   (
      () => None,
      (y) => Some(f(y))
   )
);
 
result // => Some(12)

This code isn’t nice. It leaves the elevated world of Option to apply the function, only to lift the result back up into an Option. Is it possible to abstract this and integrate multi-argument functions in a workflow without leaving the elevated world? This is indeed what the Apply function does, and we’ll look at it next.

10.1.1 Understanding applicatives

Before we look at defining Apply for elevated values, let’s briefly review the Apply function we defined in chapter 9, which performs partial application in the world of regular values. We defined various overloads for Apply that take an n-ary function and an argument and return the result of applying the function to the argument. The signatures are in the form

Apply : (T → R) → T → R
Apply : (T1 → T2 → R) → T1 → (T2 → R)
Apply : (T1 → T2 → T3 → R) → T1 → (T2 → T3 → R)

These signatures say, “Give me a function and a value, and I’ll give you the result of applying the function to the value,” whether that’s the function’s return value or the partially applied function.

In the elevated world, we need to define overloads of Apply where the input and output values are wrapped in elevated types. In general, for any functor A for which Apply can be defined, the signatures of Apply will be in the form

Apply : A<T → R> → A<T> → A<R>
Apply : A<T1 → T2 → R> → A<T1> → A<T2 → R>
Apply : A<T1 → T2 → T3 → R> → A<T1> → A<T2 → T3 → R>

It’s just like the regular Apply, but in the elevated world, it says, “Give me a function wrapped in an A and a value wrapped in an A, and I’ll give you the result of applying the function to the value also wrapped in an A, of course.” This is illustrated in fig- ure 10.2.

An implementation of Apply must unwrap the function, unwrap the value, apply the function to the value, and wrap the result back up. When we define a suitable implementation of Apply for a functor A, this is called an applicative functor (or simply an applicative). The following listing shows how Apply is defined for Option, thus making Option an applicative.

Listing 10.3 Implementation of Apply for Option

public static Option<R> Apply<T, R>
(
   this Option<Func<T, R>> optF,
   Option<T> optT
)
=> optF.Match
(
   () => None,
   (f) => optT.Match
   (
      () => None,
      (t) => Some(f(t))                ❶
   )
);
 
public static Option<Func<T2, R>> Apply<T1, T2, R>
(
   this Option<Func<T1, T2, R>> optF,
   Option<T1> optT
)
=> Apply(optF.Map(F.Curry), optT);     ❷

❶ Only applies the wrapped function to the wrapped value if both Options are Some

❷ Curries the wrapped function and calls the overload that takes an Option wrapping a unary function

The first overload is the important one. It takes a unary function wrapped in an Option and an argument to that function, also wrapped in an Option. The implementation returns Some only if both inputs are Some and None in all other cases.

As usual, overloads are required for the various arities of the wrapped functions. We can define those in terms of the unary version as the second overload demonstrates.

Now that the low-level details of wrapping and unwrapping are taken care of, let’s see how you can use Apply with a binary function:

var multiply = (int x, int y) => x * y;
 
Some(3).Map(multiply).Apply(Some(4));
// => Some(12)
 
Some(3).Map(multiply).Apply(None);
// => None

In short, if you have a function wrapped in a container, Apply allows you to supply arguments to it. Let’s take this idea one step further.

10.1.2 Lifting functions

In the examples so far, you’ve seen functions lifted into a container by mapping a multi-argument function onto an elevated value like this:

Some(3).Map(multiply)

Alternatively, you could lift a function into a container by simply using the container’s Return function as with any other value. After all, the wrapped function doesn’t care how it gets there, so you can write this:

Some(multiply)       ❶
   .Apply(Some(3))   ❷
   .Apply(Some(4))   ❷
 
// => Some(12)

❶ Lifts the function into an Option

❷ Supplies arguments with Apply

This can be generalized to functions of any arity. And, as usual, you get the safety of Option so that if any value along the way is None, the final result is also None:

Some(multiply)
   .Apply(None)
   .Apply(Some(4))
// => None

As you can see, there are two distinct but equivalent ways of evaluating a binary function in the elevated world. You can see these side by side in table 10.1.

Table 10.1 Two equivalent ways to achieve function application in the elevated world

Some(3)
   .Map(multiply)
   .Apply(Some(4))

Some(multiply)
   .Apply(Some(3))
   .Apply(Some(4))

The second way (first lifting the function with Return and then applying arguments) is more readable and more intuitive because it’s similar to partial application in the world of regular values, as table 10.2 shows.

Table 10.2 Partial application in the worlds of regular and elevated values

multiply
   .Apply(3)
   .Apply(4)
 
   // => 12

Some(multiply)
   .Apply(Some(3))
   .Apply(Some(4))
 
   // => Some(12)

Whether you obtain the function by using Map or lifting it with Return doesn’t matter in terms of the resulting functor. This is a requirement, and it will hold if the applicative is correctly implemented. It’s sometimes called the applicative law.¹

10.1.3 An introduction to property-based testing

Can we write some unit tests to prove that the functions we’ve been using to work with Option satisfy the applicative law? There’s a specific technique for this sort of testing (testing that an implementation satisfies certain laws or properties). It’s called property-based testing, and a supporting framework called FsCheck is available for doing property-based testing in .NET.²

Property-based tests are parameterized unit tests whose assertions should hold for any possible value of the parameters. You write a parameterized test and then let a framework, such as FsCheck, repeatedly run the test with a large set of randomly generated parameter values.

It’s easiest to understand this with an example. The following listing shows what a property test for the applicative law could look like.

Listing 10.4 A property-based test illustrating the applicative law

using FsCheck.Xunit;
using Xunit;
 
Func<int, int, int> multiply = (i, j) => i * j;
 
[Property]                                 ❶
void ApplicativeLawHolds(int a, int b)     ❷
{
   var first = Some(multiply)
       .Apply(Some(a))
       .Apply(Some(b));
   var second = Some(a)
       .Map(multiply)
       .Apply(Some(b));
 
   Assert.Equal(first, second);
}

❶ Marks a property-based test

❷ FsCheck randomly generates a large set of input values to run the test with.

If you look at the signature of the test method, you’ll see that it’s parameterized with two int values. But unlike the parameterized tests discussed in the sidebar on “Parameterized unit tests” in chapter 3, here we’re not providing any values for the parameters. Instead, we’re just decorating the test method with the Property attribute defined in FsCheck.Xunit.³ When you run your tests, FsCheck randomly generates a large number of input values and runs the test with these values.⁴ This frees you from having to come up with sample inputs and gives you much better confidence that edge cases are covered.

This test passes, but we’re taking ints as parameters and lifting them into Options, so it only illustrates the behavior with Options in the Some state. We should also test what happens with None. The signature of our test method should really be

void ApplicativeLawHolds(Option<int> a, Option<int> b)

We’d also ideally like FsCheck to randomly generate Options in the Some or None state and feed them to the test.

If we try to run this, FsCheck will complain that it doesn’t know how to randomly generate an Option<int>. Fortunately, we can teach FsCheck how to do this as the following listing demonstrates.

Listing 10.5 Teaching FsCheck to create an arbitrary Option

static class ArbitraryOption
{
   public static Arbitrary<Option<T>> Option<T>()
   {
      var gen = from isSome in Arb.Generate<bool>()
                from val in Arb.Generate<T>()
                select isSome && val != null ? Some(val) : None;
      return gen.ToArbitrary();
   }
}

FsCheck knows how to generate primitive types such as bool and int, so generating an Option<int> should be easy: generate a random bool and then a random int; if the bool is false, return None; otherwise, wrap the generated int into a Some. This is the essential meaning of the preceding code—don’t worry about the exact details at this point.

Now we just need to instruct FsCheck to look into the ArbitraryOption class when a random Option<T>, is required. The following listing shows how to do this.

Listing 10.6 The property-based test parameterized with arbitrary Options

[Property(Arbitrary = new[] { typeof(ArbitraryOption) })]
void ApplicativeLawHolds(Option<int> a, Option<int> b)
   => Assert.Equal
   (
      Some(multiply).Apply(a).Apply(b),
      a.Map(multiply).Apply(b)
   );

Sure enough, FsCheck is now able to randomly generate the inputs to this test, which passes and beautifully illustrates the applicative law. Does it prove that our implementation always satisfies the applicative law? Not entirely, because it only tests that the property holds for the multiply function, whereas the law should hold for any function. Unfortunately, unlike with numbers and other values, it’s impossible to randomly generate a meaningful set of functions. But this sort of property-based test still gives us good confidence—certainly better than a unit test, even a parameterized one.

Now that we’ve covered the mechanics of the Apply function, let’s compare applicatives with the other patterns we’ve previously discussed. Once that’s done, we’ll look at applicatives in action with a more concrete example and at how they compare, especially to monads.

10.2 Functors, applicatives, and monads

Let’s recap three important patterns you’ve seen so far: functors, applicatives, and monads.⁵ Remember that functors are defined by an implementation of Map, monads by an implementation of Bind and Return, and applicatives by an implementation of Apply and Return as table 10.3 shows.

Table 10.3 Summary of the core functions for functors, applicatives, and monads

First, why is Return a requirement for monads and applicatives but not for functors? You need a way to somehow put a value T into a functor F<T>; otherwise, you couldn’t create anything on which to Map a function. The point, really, is that the functor laws (the properties that Map should observe) don’t rely on a definition of Return, whereas the monad and applicative laws do. This is then mostly a technicality.

More interestingly, you may be wondering what the relationship is between these three patterns. In chapter 7, you saw that monads are more powerful than functors. Applicatives are also more powerful than functors because you can define Map in terms of Return and Apply. Map takes an elevated value and a regular function, so you can lift the function using Return and then apply it to the elevated value using Apply. For Option, that looks like this:

public static Option<R> Map<T, R>
   (this Option<T> opt, Func<T, R> f)
   => Some(f).Apply(opt);

The implementation for any other applicative would be the same, using the relevant Return function instead of Some.

Finally, monads are more powerful than applicatives because you can define Apply in terms of Bind and Return like so:

public static Option<R> Apply<T, R>
(
   this Option<Func<T, R>> optF,
   Option<T> optT
)
=> optT.Bind(t => optF.Bind(f => Some(f(t))));

This enables us to establish a hierarchy in which functor is the most general pattern and applicative sits between functor and monad. Figure 10.3 shows these relationships.

You can read this as a class diagram: if functor were an interface, applicative would extend it. Furthermore, in chapter 9, I discussed the fold function, or Aggregate as it’s called in LINQ, which is the most powerful of them all because you can define Bind in terms of it. Foldables (things for which fold can be defined) are more powerful than monads.

Applicatives aren’t as commonly used as functors and monads, so why even bother? It turns out that although Apply can be defined in terms of Bind, it generally receives its own implementation, both for efficiency and because Apply can include interesting behavior that’s lost when you define Apply in terms of Bind. In this book, I’ll show two monads for which the implementation of Apply has such interesting behavior: Validation (later in this chapter) and Task (in chapter 16).

Next, let’s go back to the topic of monads to see how you can use Bind with multi-argument functions.

10.3 The monad laws

I’ll now discuss the monad laws as promised in chapter 6, where I first introduced the term monad. If you’re not interested in the theory, skip to section 10.3.4.

Remember, a monad is a type M for which the following functions are defined:

• Return—Takes a regular value of type T and lifts it into a monadic value of type M<T>

• Bind—Takes a monadic value m and a world-crossing function f; extracts from m its inner value(s) t and applies f to it

Return and Bind should have the following three properties:

1. Right identity

2. Left identity

3. Associativity

For the present discussion, we’re mostly interested in the third law, associativity, but the first two are simple enough that we can cover them too.

10.3.1 Right identity

The property of right identity states that if you Bind the Return function onto a monadic value m, you end up with m. In other words, the following should hold:

m == m.Bind(Return)

If you look at the preceding equation, on the right side, Bind unwraps the value inside m and applies Return, which lifts it back up. It’s not surprising that the net effect should be nought. The next listing shows a test that proves that right identity holds for the Option type.

Listing 10.7 A property-based test for right identity

[Property(Arbitrary = new[] { typeof(ArbitraryOption) })]
void RightIdentityHolds(Option<object> m)
   => Assert.Equal
   (
      m,
      m.Bind(Some)
   );

10.3.2 Left identity

The property of left identity states that if you first use Return to lift a t and then Bind a function f over the result, that should be equivalent to applying f to t:

Return(t).Bind(f) == f(t)

If you look at this equation, on the left side you’re lifting t with Return and then Bind extracts it before feeding it to f. This law states that this lifting and extracting should have no side effects, and it should also not affect t in any way. The next listing shows a test that proves that left identity holds for IEnumerable.

Listing 10.8 A property-based test for left identity

Func<int, IEnumerable<int>> f = i => Range(0, i);
 
[Property] void LeftIdentityHolds(int t)
   => Assert.Equal
   (
      f(t),
      List(t).Bind(f)
   );

Taken together, left and right identity ensure that the lifting operation performed in Return and the unwrapping that occurs as part of Bind are neutral operations that have no side effects and don’t distort the value of t or the behavior of f, regardless of whether this wrapping and unwrapping happens before (left) or after (right) a value is lifted into the monad. We could write a monad that, say, internally keeps a count of how many times Bind is called, or includes some other side effect. That would violate this property.

In simpler words, Return should be as dumb as possible: no side effects, no conditional logic, no acting upon the given t; only the minimal work required to satisfy the signature T → C<T>.

Let’s look at a counterexample. The following property-based test supposedly illustrates left identity for Option:

Func<string, Option<string>> f = s => Some($"Hello {s}");
 
[Property] void LeftIdentityHolds(string t)
   => Assert.Equal
   (
      f(t),
      Some(t).Bind(f)
   );

It turns out that the preceding property fails when the value of t is null. This is because our implementation of Some is too smart and throws an exception if given null, whereas this particular function, f, is null-tolerant and yields Some("Hello ").

If you wanted left identity to hold for any value including null, you’d need to change the implementation of Some to lift null into a Some. But this would not be a good idea because then Some would indicate the presence of data when, in fact, there is none. This is a case in which practicality trumps theory.⁶

10.3.3 Associativity

Let’s now move on to the third law, which is the most meaningful for our present discussion. I’ll start with a reminder of what associativity means for addition: if you need to add more than two numbers, it doesn’t matter how you group them. That is, for any numbers a, b, and c, the following is true:

(a + b) + c  ==  a + (b + c)

Bind can also be thought of as a binary operator and can be indicated with the symbol >>= so that instead of m.Bind(f), you can symbolically write m >>= f, where m indicates a monadic value and f a world-crossing function. The symbol >>= is a fairly standard notation for Bind, and it’s supposed to graphically reflect what Bind does: extract the inner value of the left operand and feed it to the function that’s the right operand.

It turns out that Bind is also associative in some sense. You should be able to write the following equation:

(m >>= f) >>= g == m >>= (f >>= g)

Let’s look at the left side. Here you compute the first Bind operation and then you use the resulting monadic value as input to the next Bind operation. This would expand to m.Bind(f).Bind(g), which is how we normally use Bind.

Let’s now look at the right side. As it’s written, it’s syntactically wrong: (f >>= g) doesn’t work because >>= expects the left operand to be a monadic value, whereas f is a function. But note that f can be expanded to its lambda form, x ⇒ f(x), so you can rewrite the right side as follows:

m >>= (x => f(x) >>= g)

The associativity of Bind can be then summarized with this equation:

(m >>= f) >>= g  ==  m >>= (x => f(x) >>= g)

Or, if you prefer, the following:

m.Bind(f).Bind(g)  ==  m.Bind(x => f(x).Bind(g))

The following listing shows how you could translate this into code. It shows a property-based test illustrating that the associative property holds for my implementation of Option.

Listing 10.9 A property-based test showing Bind associativity for Option

using Double = LaYumba.Functional.Double;      ❶
 
Func<double, Option<double>> safeSqrt = d
   => d < 0 ? None : Some(Math.Sqrt(d));
 
[Property(Arbitrary = new[] { typeof(ArbitraryOption) })]
void AssociativityHolds(Option<string> m)
   => Assert.Equal
   (
      m.Bind(Double.Parse).Bind(safeSqrt),
      m.Bind(x => Double.Parse(x).Bind(safeSqrt))
   );

❶ Exposes an Option-returning Parse function

When we associate to the left as in m.Bind(f).Bind(g), that gives the more readable syntax (the one we’ve used so far). But if we associate to the right and expand g to its lambda form, we get this:

m.Bind(x => f(x).Bind(y => g(y)))

The interesting thing is that here g has visibility not only of y but also of x. This is what enables you to integrate multi-argument functions in a monadic flow (by which I mean a workflow chaining several operations with Bind). We’ll look at this next.

10.3.4 Using Bind with multi-argument functions

Let’s look at how calling Bind inside a previous call to Bind allows you to integrate multi-argument functions. For instance, imagine multiplication where both arguments are wrapped in an Option because they must be parsed from strings. In this example, Int.Parse takes a string and returns an Option<int>:

static Option<int> MultiplicationWithBind(string strX, string strY)
   => Int.Parse(strX)
      .Bind(x => Int.Parse(strY)
         .Bind<int, int>(y => multiply(x, y)));

That works, but it’s not at all readable. Imagine if you had a function taking three or more arguments! The nested calls to Bind make the code difficult to read, so you certainly wouldn’t want to write or maintain code like this. The applicative syntax you saw in section 10.1.2 was much clearer. It turns out that there’s a much better syntax for writing nested applications of Bind. That syntax is called LINQ.

10.4 Improving readability by using LINQ with any monad

Depending on the context, the name LINQ is used to indicate different things:

• It can simply refer to the System.Linq library.

• It can indicate a special SQL-like syntax that can be used to express queries on various kinds of data. In fact, LINQ stands for Language-Integrated Query.

Naturally, these two are linked, and they were both introduced in tandem in C# 3. So far, all usages of the LINQ library you’ve seen in this book have used normal method invocation, but sometimes using the LINQ syntax can result in more readable queries. For example, type the two expressions in table 10.4 into the REPL to see that they’re equivalent.

Table 10.4 LINQ is a dedicated syntax for expressing queries.

Enumerable.Range(1, 100).
   Where(i => i % 20 == 0).
   OrderBy(i => -i).
   Select(i => $"{i}%")

from i in Enumerable.Range(1, 100)
where i % 20 == 0
orderby -i
select $"{i}%"

These two expressions aren’t just equivalent in the sense that they produce the same result; they actually compile to the same code. When the C# compiler finds a LINQ expression, it translates its clauses to method calls in a pattern-based way—you’ll see what this means in more detail in a moment.

This means that it’s possible for you to implement the query pattern for your own types and work with them using LINQ syntax, which can significantly improve readability. Next, we’ll look at implementing the query pattern for Option.

10.4.1 Using LINQ with arbitrary functors

The simplest LINQ queries have single from and select clauses, and they resolve to the Select method. For example, here’s a simple query using a range as a data source:

using System.Linq;
using static System.Linq.Enumerable;
 
from x in Range(1, 4)
select x * 2;
// => [2, 4, 6, 8]

Range(1, 4) yields a sequence with the values [1, 2, 3, 4], and this is the data source for the LINQ expression. We then create a projection by mapping each item x in the data source to x * 2 to produce the result. What happens under the hood?

Given a LINQ expression like the preceding one, the compiler looks at the type of the data source (in this case, Range(1, 4) has type RangeIterator) and then looks for an instance or extension method called Select. The compiler uses its normal strategy for method resolution, prioritizing the most specific match in scope, which in this case is Enumerable.Select, defined as an extension method on IEnumerable.

In table 10.5, you can see the LINQ expression and its translation side by side. Notice how the lambda given to Select combines the identifier x in the from clause and the selector expression x * 2 in the select clause.

Table 10.5 A LINQ expression with a single from clause and its interpretation

from x in Range(1, 4)
select x * 2

Range(1, 4).
   Select(x => x * 2)

Remember from chapter 6 that Select is the LINQ equivalent for the operation more commonly known in FP as Map. LINQ’s pattern-based approach means that you can define Select for any type you please, and the compiler will use it whenever it finds that type as the data source of a LINQ query. Let’s do that for Option:

public static Option<R> Select<T, R>
   (this Option<T> opt, Func<T, R> f)
   => opt.Map(f);

The preceding code effectively just aliases Map with Select, which is the name that the compiler looks for. That’s all you need to be able to use an Option inside a simple LINQ expression! Here are some examples:

from x in Some(12)
select x * 2
// => Some(24)
 
from x in (Option<int>)None
select x * 2
// => None
 
(from x in Some(1) select x * 2) == Some(1).Map(x => x * 2)
// => true

In summary, you can use LINQ queries with a single from clause with any functor by providing a suitable Select method. Of course, for such simple queries, the LINQ notation isn’t really beneficial; standard method invocation even saves you a couple of keystrokes. Let’s see what happens with more complex queries.

10.4.2 Using LINQ with arbitrary monads

Let’s look at queries with multiple from clauses—queries that combine data from multiple data sources. Here’s an example:

var chars = new[] { 'a', 'b', 'c' };
var ints = new [] { 2, 3 };
 
from c in chars
from i in ints
select (c, i)
// => [(a, 2), (a, 3), (b, 2), (b, 3), (c, 2), (c, 3)]

As you can see, this is somewhat analogous to a nested loop over the two data sources, which we discussed in section 6.3.2 when looking at Bind for IEnumerable. Indeed, you could write an equivalent expression using Map and Bind as follows:

chars
   .Bind(c => ints
      .Map(i => (c, i)));

Or, equivalently, using the standard LINQ method names (Select instead of Map and SelectMany instead of Bind):

chars
   .SelectMany(c => ints
      .Select(i => (c, i)));

Notice that you can construct a result that includes data from both sources because you close over the variable c.

You might guess that when multiple from clauses are present in a query, they’re interpreted with the corresponding calls to SelectMany. Your guess would be correct, but there’s a twist. For performance reasons, the compiler doesn’t perform the preceding translation, translating instead to an overload of SelectMany with a different signature:

public static IEnumerable<RR> 
SelectMany<T, R, RR>
(
   this IEnumerable<T> source,
   Func<T, IEnumerable<R>> bind,
   Func<T, R, RR> project
)
{
   foreach (T t in source)
      foreach (R r in bind(t))
         yield return project(t, r);
}

That means this LINQ query

from c in chars
from i in ints
select (c, i)

will actually be translated as

chars.SelectMany(c => ints, (c, i) => (c, i))

The following listing shows both the plain vanilla implementation of SelectMany (which has the same signature as Bind) and the extended overload (which will be used when a query with two from clauses is translated into method calls).

Listing 10.10 The two overloads of SelectMany required by LINQ

public static IEnumerable<R> SelectMany<T, R>          ❶
(
   this IEnumerable<T> source,
   Func<T, IEnumerable<R>> func
)
{
   foreach (T t in source)
      foreach (R r in func(t))
         yield return r;
}
 
public static IEnumerable<RR> SelectMany<T, R, RR>     ❷
(
   this IEnumerable<T> source,
   Func<T, IEnumerable<R>> bind,
   Func<T, R, RR> project
)
{
   foreach (T t in source)
      foreach (R r in bind(t))
         yield return project(t, r);
}

❶ Plain vanilla SelectMany, equivalent to Bind.

❷ Extended overload of SelectMany (used when translating a query with two from clauses)

Compare the signatures. You’ll see that the second overload is obtained by “squashing” the plain vanilla SelectMany with a call to a selector function; not the usual selector in the form T → R, but a selector that takes two input arguments (one for each data source).

The advantage is that with this more elaborate overload of SelectMany, there’s no longer any need to nest one lambda inside another, improving performance.⁷

The extended SelectMany is more complex than the plain vanilla version we identified with the monadic Bind, but it’s still functionally equivalent to a combination of Bind and Select. This means we can define a reasonable implementation of the LINQ-flavored SelectMany for any monad. Let’s see it for Option:

public static Option<RR> SelectMany<T, R, RR>
(
   this Option<T> opt,
   Func<T, Option<R>> bind,
   Func<T, R, RR> project
)
=> opt.Match
(
   () => None,
   (t) => bind(t).Match
   (
      () => None,
      (r) => Some(project(t, r))
   )
);

If you write an expression with three or more from clauses, the compiler also requires the plain vanilla version of SelectMany—the one with the same signature as Bind. Therefore, both overloads of SelectMany need to be defined to satisfy the LINQ query pattern.

You can now write LINQ queries on Options with multiple from clauses. For example, here’s a simple program that prompts the user for two integers and computes their sum, using the Option-returning function Int.Parse to validate that the inputs are valid integers:

WriteLine("Enter first addend:");
var s1 = ReadLine();
 
WriteLine("Enter second addend:");
var s2 = ReadLine();
 
var result = from a in Int.Parse(s1)
             from b in Int.Parse(s2)
             select a + b;
 
WriteLine(result.Match
(
   None: () => "Please enter 2 valid integers",
   Some: (r) => $"{s1} + {s2} = {r}"
));

The following listing shows how the LINQ query from the preceding example compares with alternative ways to write the same expression.

Listing 10.11 Different ways to add two optional integers

// 1. using LINQ query
from a in Int.Parse(s1)
from b in Int.Parse(s2)
select a + b
 
// 2. normal method invocation
Int.Parse(s1)
   .Bind(a => Int.Parse(s2)
      .Map(b => a + b))
 
// 3. the method invocation that the LINQ query will be converted to
Int.Parse(s1)
   .SelectMany(a => Int.Parse(s2)
      , (a, b) => a + b)
 
// 4. using Apply
Some(new Func<int, int, int>((a, b) => a + b))
   .Apply(Int.Parse(s1)
   .Apply(Int.Parse(s2))

There’s little doubt that LINQ provides the most readable syntax in this scenario. Apply compares particularly poorly because you must specify that you want your projection function to be used as a Func.⁸ You may find it unfamiliar to use the SQL-ish LINQ syntax to do something that has nothing to do with querying a data source, but this use is perfectly legitimate. LINQ expressions simply provide a convenient syntax for working with monads, and they were modeled after equivalent constructs in functional languages.⁹

10.4.3 The LINQ clauses let, where, and others

In addition to the from and select clauses you’ve seen so far, LINQ provides a few other clauses. The let clause is useful for storing the results of intermediate computations. For example, let’s look at the program in the following listing, which calculates the hypotenuse of a right triangle, having prompted the user for the lengths of the legs.

Listing 10.12 Using the let clause with Option

using Double = LaYumba.Functional.Double;    ❶
 
string s1 = Prompt("First leg:")             ❷
     , s2 = Prompt("Second leg:");
 
var result = from a in Double.Parse(s1)
             let aa = a * a                  ❸
             from b in Double.Parse(s2)
             let bb = b * b                  ❸
             select Math.Sqrt(aa + bb);
 
WriteLine(result.Match
(
   () => "Please enter two valid numbers",
   (h) => $"The hypotenuse is {h}"
));

❶ Exposes an Option-returning Parse function

❷ Assume Prompt is a convenience function that reads user input from the console

❸ A let clause allows you to store intermediate results.

The let clause allows you to put a new variable, like aa in this example, within the scope of the LINQ expression. To do so, it relies on Select, so no extra work is needed to enable the use of let.¹⁰

One more clause you can use with Option is the where clause. This resolves to the Where method we’ve already defined, so no extra work is necessary in this case. For example, for the calculation of the hypotenuse, you should check not only that the user’s inputs are valid numbers but also that they are positive. The following listing shows how to do this.

Listing 10.13 Using the where clause with Option

string s1 = Prompt("First leg:")
     , s2 = Prompt("Second leg:");
 
var result = from a in Double.Parse(s1)
             where a >= 0
             let aa = a * a
 
             from b in Double.Parse(s2)
             where b >= 0
             let bb = b * b
             select Math.Sqrt(aa + bb);
 
WriteLine(result.Match
(
   () => "Please enter two valid, positive numbers",
   (h) => $"The hypotenuse is {h}"
));

As these examples show, the LINQ syntax allows you to concisely write queries that would be cumbersome to write as combinations of calls to the corresponding Map, Bind, and Where functions. LINQ also contains various other clauses such as orderby, which you’ve seen in a previous example. These clauses make sense for collections but have no counterpart in structures like Option and Either.

In summary, for any monad you can implement the LINQ query pattern by providing implementations for Select (Map), SelectMany (Bind), and the ternary overload to SelectMany you’ve seen. Some structures may have other operations that can be included in the query pattern, such as Where in the case of Option.

Now that you’ve seen how LINQ provides a lightweight syntax for using Bind with multi-argument functions, let’s go back to comparing Bind and Apply, not just based on readability, but on actual functionality.

10.5 When to use Bind vs. Apply

LINQ provides a good syntax for using Bind, even with multi-argument functions—even better than using Apply with normal method invocation. Should we still care about Apply? It turns out that in some cases, Apply can have interesting behavior. One such case is validation; let’s see why.

10.5.1 Validation with smart constructors

Consider the following implementation of a PhoneNumber class. Can you see anything wrong with it?

public record PhoneNumber
(
   string Type,
   string Country,
   long Nr
);

The answer should be staring you in the face: the types are wrong! This class allows you to create a PhoneNumber with, say, Type equal to “green,” Country equal to “fantasyland,” and Nr equal to “•10.”

You saw in chapter 4 how defining custom types enables you to ensure that invalid data can’t creep into your system. Here’s a definition of a PhoneNumber class that follows this philosophy:

public record PhoneNumber
{
   public NumberType Type { get; }
   public CountryCode Country { get; }
   public Number Nr { get; }
 
   public enum NumberType { Mobile, Home, Office }
   public struct Number { /* ... */ }
}
 
public class CountryCode { /* ... */ }

Now the three fields of a PhoneNumber all have specific types, which should ensure that only valid values can be represented. CountryCode may be used elsewhere in the application, but the remaining two types are specific to phone numbers, so they’re defined inside the PhoneNumber class.

We still need to provide a way to construct a PhoneNumber. For that, we can define a private constructor and a public factory function, Create:

public record PhoneNumber
{
   public static Func<NumberType, CountryCode, Number, PhoneNumber>
   Create = (type, country, number)
      => new(type, country, number);
 
   PhoneNumber(NumberType type, CountryCode country, Number number)
   {
      Type = type;
      Country = country;
      Nr = number;
   }
}

Note that I’ve defined Create as a Func rather than using a constructor or a method to help out with type inference. This was discussed in section 9.2.

Now imagine we’re given three strings as raw input, and based on them, we need to create a PhoneNumber. Each property can be validated independently, so we can define three smart constructors with the following signatures:

validCountryCode : string → Validation<CountryCode>
validNumberType  : string → Validation<PhoneNumber.NumberType>
validNumber      : string → Validation<PhoneNumber.Number>

The implementation details of these functions aren’t important (see the code samples if you want to know more). The gist is that validCountryCode takes a string and returns a Validation in the Valid state only if the given string represents a valid CountryCode. The other two functions are similar.

10.5.2 Harvesting errors with the applicative flow

Given the three input strings, we can combine these three functions in the process of creating a PhoneNumber as the following listing shows. With the applicative flow, we can lift the PhoneNumber's factory function into a Valid and apply its three arguments.

Listing 10.14 Validation using an applicative flow

Validation<PhoneNumber> CreatePhoneNumber
   (string type, string countryCode, string number)
   => Valid(PhoneNumber.Create)                        ❶
      .Apply(validNumberType(type))                    ❷
      .Apply(validCountryCode(countryCode))            ❷
      .Apply(validNumber(number));                     ❷

❶ Lifts the factory function into a Validation

❷ Supplies arguments, each of which is also wrapped in a Validation

This function yields Invalid if any of the functions we use to validate the individual fields yields Invalid. Let’s see its behavior, given a variety of different inputs:

CreatePhoneNumber("Mobile", "ch", "123456")
// => Valid(Mobile: (ch) 123456)
 
CreatePhoneNumber("Mobile", "xx", "123456")
// => Invalid([xx is not a valid country code])
 
CreatePhoneNumber("Mobile", "xx", "1")
// => Invalid([xx is not a valid country code, 1 is not a valid number])

The first expression shows the successful creation of a PhoneNumber. In the second, we pass an invalid country code and get a failure as expected. In the third case, both the country and number are invalid, and we get a validation with two errors (remember, the Invalid case of a Validation holds an IEnumerable<Error> precisely to capture multiple errors).

But how are the two errors, which are returned by different functions, harvested in the final result? This is due to the implementation of Apply for Validation. Check out the following listing.

Listing 10.15 Implementation of Apply for Validation

public static Validation<R> Apply<T, R>
(
   this Validation<Func<T, R>> valF,
   Validation<T> valT
)
=> valF.Match
(
   Valid: (f) => valT.Match
   (
      Valid: (t) => Valid(f(t)),                      ❶
      Invalid: (err) => Invalid(err)
   ),
   Invalid: (errF) => valT.Match
   (
      Valid: (_) => Invalid(errF),
      Invalid: (errT) => Invalid(errF.Concat(errT))   ❷
   )
);

❶ If both inputs are valid, the wrapped function is applied to the wrapped argument, and the result is lifted into a Validation in the Valid state.

❷ If both inputs have errors, a Validation in the Invalid state is returned that collects the errors from both valF and valT.

As we’d expect, Apply applies the wrapped function to the wrapped argument only if both are valid. But, interestingly, if both are invalid, it returns an Invalid that combines errors from both arguments.

10.5.3 Failing fast with the monadic flow

The following listing demonstrates how to create a PhoneNumber using LINQ.

Listing 10.16 Validation using a monadic flow

Validation<PhoneNumber> CreatePhoneNumberM
   (string typeStr, string countryStr, string numberStr)
   => from type    in validNumberType(typeStr)
      from country in validCountryCode(countryStr)
      from number  in validNumber(numberStr)
      select PhoneNumber.Create(type, country, number);

Let’s run this new version with the same test values as before:

CreatePhoneNumberM("Mobile", "ch", "123456")
// => Valid(Mobile: (ch) 123456)
 
CreatePhoneNumberM("Mobile", "xx", "123456")
// => Invalid([xx is not a valid country code])
 
CreatePhoneNumberM("Mobile", "xx", "1")
// => Invalid([xx is not a valid country code])

The first two cases work as before, but the third case is different: only the first validation error appears. To see why, let’s look at how Bind is defined in the next listing (the LINQ query actually calls SelectMany, but this is implemented in terms of Bind).

Listing 10.17 Implementation of Bind for Validation

public static Validation<R> Bind<T, R>
(
   this Validation<T> val,
   Func<T, Validation<R>> f
)
=> val.Match
(
   Invalid: (err) => Invalid(err),
   Valid: (t) => f(t)
);

If the given monadic value is Invalid, the given function isn’t evaluated. In this listing, validCountryCode returns Invalid, so validNumber is never called. Therefore, in the monadic version, we never get a chance to accumulate errors because any error along the way causes the subsequent functions to be bypassed. You can probably grasp the difference more clearly if we compare the signatures of Apply and Bind:

Apply : Validation<(T  → R)>  → Validation<T>  → Validation<R>
Bind  : Validation<T>  → (T  → Validation<R>)  → Validation<R>

With Apply, both arguments are of type Validation; the Validations and any possible errors they contain have already been evaluated independently prior to the call to Apply. Because errors from both arguments are present, it makes sense to collect them in the resulting value.

With Bind, only the first argument has type Validation. The second argument is a function that yields a Validation, but this hasn’t been evaluated yet, so the implementation of Bind can avoid calling the function altogether if the first argument is Invalid.¹¹

Hence, Apply is about combining two elevated values that are computed independently, whereas Bind is about sequencing computations that yield an elevated value. For this reason, the monadic flow allows short-circuiting: if an operation fails along the way, the following operations will be skipped.

I think what the case of Validation shows is that despite the apparent rigor of functional patterns and their laws, there’s still room for designing elevated types in a way that suits the particular needs of a particular application. Given my implementation of Validation and the current scenario of creating a valid PhoneNumber, you’d use the monadic flow to fail fast but the applicative flow to harvest errors.

In summary, you’ve seen three ways to use multi-argument functions in the elevated world: the good, the bad, and the ugly. Nested calls to Bind are certainly the ugly and are best avoided. Which of the other two is good or bad depends on your requirements. If you have an implementation of Apply with some desirable behavior as you saw with Validation, use the applicative flow; otherwise, use the monadic flow with LINQ.

Exercises

1. Implement Apply for Either and Exceptional.

2. Implement the query pattern for Either and Exceptional. Try to write down the signatures for Select and SelectMany without looking at any examples. For the implementation, just follow the types—if it type checks, it’s probably right!

3. Come up with a scenario in which various Either-returning operations are chained with Bind. (If you’re short of ideas, you can use the “favorite dish” example from chapter 8.) Rewrite the code using a LINQ expression.

Summary

• You can use the Apply function to perform function application in an elevated world, such as the world of Option.

• Multi-argument functions can be lifted into an elevated world with Return; then you can supply arguments with Apply.

• Types for which Apply can be defined are called applicatives. Applicatives are more powerful than functors but less powerful than monads.

• Because monads are more powerful, you can also use nested calls to Bind; to perform function application in an elevated world.

• LINQ provides a lightweight syntax for working with monads that reads better than nesting calls to Bind.

• To use LINQ with a custom type, you must implement the LINQ query pattern, particularly providing implementations of Select and SelectMany with appropriate signatures.

• For several monads, Bind has short-circuiting behavior (the given function won’t be applied in some cases), but Apply doesn’t (it’s not given a function but rather an elevated value). For this reason, you can sometimes embed desirable behavior into applicatives, such as collecting validation errors in the case of Validation.

• FsCheck is a framework for property-based testing. It allows you to run a test with a large number of randomly generated inputs, giving high confidence that the test’s assertions hold for any input.

¹ In reality, there are four laws that correct implementations of Apply and Return must satisfy; these essentially hold that the identity function, function composition, and function application work in the applicative world as they do in the normal world. The applicative law I refer to in the text holds as a consequence of these, and it’s more important than the underlying four laws in terms of refactoring and practical use. I won’t discuss the four laws in detail here, but if you want to learn more, you can see the documentation for the applicative module in Haskell at http://mng.bz/AOBx. In addition, you can view property-based tests illustrating the applicative laws in the code samples, LaYumba.Functional.Tests/Option/ApplicativeLaws.cs.

² FsCheck is written in F# and is available freely (https://github.com/fscheck/FsCheck). Like many similar frameworks written for other languages, it’s a port from Haskell’s QuickCheck.

³ This also has the effect of integrating the property-based tests with your testing framework: when you run your tests with dotnet test, all property-based tests are run, as well as the regular unit tests. An FsCheck.NUnit package also exists, exposing the Property attribute for NUnit.

⁴ By default, FsCheck generates 100 values, but you can customize the number and range of input values. If you start using property-based testing seriously, being able to fine-tune the parameters with which the values are generated becomes quite important.

⁵ As pointed out in chapter 6, in the “Why is functor not an interface?” sidebar, some languages like Haskell allow you to capture these patterns with type classes, which are akin to interfaces but more powerful. The C# type system doesn’t support these generic abstractions, so you can’t idiomatically capture Map or Bind in an interface.

⁶ Of course, in a functional language, you wouldn’t have null in the first place, so you wouldn’t be in this conundrum.

⁷ The designers of LINQ noticed that performance deteriorated rapidly as several from clauses were used in a query.

⁸ This is because lambda expressions can be used to represent Expressions as well as Funcs.

⁹ For instance, do blocks in Haskell or for comprehensions in Scala.

¹⁰ let stores the newly computed result in a tuple along with the previous result.

¹¹ Of course, you could provide an implementation of Bind that doesn’t perform any such short-circuiting but always executes the bound function and collects any errors. This is possible, but it’s counterintuitive because it breaks the behavior that we’ve come to expect from similar types like Option and Either.