## Boolean catamorphism

Monday, 06 May 2019 12:30:00 UTC

The catamorphism for Boolean values is just the common ternary operator.

This article presents the catamorphism for Boolean values, as well as how you identify it. The beginning of this article presents the catamorphism in C#, with a simple example. The rest of the article describes how I deduced the catamorphism. That part of the article presents my work in Haskell. Readers not comfortable with Haskell can just read the first part, and consider the rest of the article as an optional appendix.

### C# catamorphism #

The catamorphism for Boolean values is the familiar ternary conditional operator:

```> DateTime.Now.Day % 2 == 0 ? "Even date" : "Odd date"
"Odd date"```

Given a Boolean expression, you basically provide two values: one to use in case the Boolean expression is true, and one to use in case it's false.

For Church-encoded Boolean values, the catamorphism looks like this:

`T Match<T>(T trueCase, T falseCase);`

This is an instance method where you must, again, supply two alternatives. When the instance represents true, you'll get the left-most value `trueCase`; otherwise, when the instance represents false, you'll get the right-most value `falseCase`.

The catamorphism turns out to be the same as the Church encoding. This seems to be a recurring pattern.

### Alternatives #

To be accurate, there's more than one catamorphism for Boolean values. It's only by convention that the value corresponding to true goes on the left, and the false value goes to the right. You could flip the arguments, and it would still be a catamorphism. This is, in fact, what Haskell's `Data.Bool` module does:

```Prelude Data.Bool> bool "Odd date" "Even date" \$ even date
"Odd date"```

The module documentation calls this the "Case analysis for the `Bool` type", instead of a catamorphism, but the two representations are isomorphic:

"This is equivalent to `if p then y else x`; that is, one can think of it as an if-then-else construct with its arguments reordered."
This is another recurring result. There's typically more than one catamorphism, but the alternatives are isomorphic. In this article series, I'll mostly present the alternative that strikes me as the one you'll encounter most frequently.

### Fix #

In this and future articles, I'll derive the catamorphism from an F-Algebra. For an introduction to F-Algebras and fixed points, I'll refer you to Bartosz Milewski's excellent article on the topic. In it, he presents a generic data type for a fixed point, as well as polymorphic functions for catamorphisms and anamorphisms. While they're available in his article, I'll repeat them here for good measure:

```newtype Fix f = Fix { unFix :: f (Fix f) }

cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unFix

ana :: Functor f => (a -> f a) -> a -> Fix f
ana coalg = Fix . fmap (ana coalg) . coalg```

This should be recognisable from Bartosz Milewski's article. With one small exception, this is just a copy of the code shown there.

### Boolean F-Algebra #

While F-Algebras and fixed points are mostly used for recursive data structures, you can also define an F-Algebra for a non-recursive data structure. As data types go, they don't get much simpler than Boolean values, which are just two mutually exclusive cases. In order to make a `Functor` out of the definition, though, you can equip it with a carrier type:

```data BoolF a = TrueF | FalseF deriving (Show, Eq, Read)

instance Functor BoolF where
fmap _  TrueF =  TrueF
fmap _ FalseF = FalseF```

The `Functor` instance simply ignores the carrier type and just returns `TrueF` and `FalseF`, respectively. It'd seem that nothing happens, but at the type level, this is still a translation from `BoolF a` to `BoolF b`. Not much of a function, perhaps, but definitely an endofunctor.

Another note that may be in order here, as well as for all future articles in this series, is that you'll notice that most types and custom functions come with the `F` suffix. This is simply a suffix I've added to avoid conflicts with built-in types, values, and functions, such as `Bool`, `True`, `and`, and so on. The `F` is for F-Algebra.

You can lift these values into `Fix` in order to make it fit with the `cata` function:

```trueF, falseF :: Fix BoolF
trueF  = Fix  TrueF
falseF = Fix FalseF```

That's all you need to identify the catamorphism.

At this point, you have two out of three elements of an F-Algebra. You have an endofunctor (`BoolF`), and an object `a`, but you still need to find a morphism `BoolF a -> a`. At first glance, this seems impossible, because neither `TrueF` nor `FalseF` actually contain a value of the type `a`. How, then, can you conjure an `a` value out of thin air?

The `cata` function has the answer.

What you can do is to start writing the function that will become the catamorphism, basing it on `cata`:

```boolF = cata alg
where alg  TrueF = undefined
alg FalseF = undefined```

While this compiles, with its `undefined` implementations, it obviously doesn't do anything useful. I find, however, that it helps me think. How can you return a value of the type `a` from the `TrueF` case? You could pass an argument to the `boolF` function:

```boolF x = cata alg
where alg  TrueF = x
alg FalseF = undefined```

That seems promising, so do that for the `FalseF` case as well:

```boolF :: a -> a -> Fix BoolF -> a
boolF x y = cata alg
where alg  TrueF = x
alg FalseF = y```

This works. Since `cata` has the type `Functor f => (f a -> a) -> Fix f -> a`, that means that `alg` has the type `f a -> a`. In the case of `BoolF`, the compiler infers that the `alg` function has the type `BoolF a -> a`, which is just what you need!

The `boolF` function identifies the Boolean catamorphism, which is equivalent to representations in the beginning of the article. I called the function `boolF`, because there's a tendency in Haskell to name the 'case analysis' or catamorphism after the type, just with a lower-case initial letter.

You can use the `boolF` function just like the above ternary operator:

```Prelude Boolean Nat> boolF "Even date" "Odd date" \$ evenF dateF
"Odd date"```

Here, I've also used `evenF` from the `Nat` module shown in the next article in the series.

From the above definition of `boolF`, it should also be clear that you can arrive at the alternative catamorphism defined by `Data.Bool.bool` by simply flipping `x` and `y`.

### Basis #

A catamorphism can be used to implement most (if not all) other useful functionality. For Boolean values, that would be the standard Boolean operations and, or, and not:

```andF :: Fix BoolF -> Fix BoolF -> Fix BoolF
andF x y = boolF y falseF x

orF :: Fix BoolF -> Fix BoolF -> Fix BoolF
orF x y = boolF trueF y x

notF :: Fix BoolF -> Fix BoolF
notF = boolF falseF trueF```

They work as you'd expect them to work:

```Prelude Boolean> andF trueF falseF
Fix FalseF
Prelude Boolean> orF trueF falseF
Fix TrueF
Prelude Boolean> orF (notF trueF) falseF
Fix FalseF```

You can also implement conversion to and from the built-in `Bool` type:

```toBool :: Fix BoolF -> Bool
toBool = boolF True False

fromBool :: Bool -> Fix BoolF
fromBool = ana coalg
where coalg  True = TrueF
coalg False = FalseF```

This demonstrates that `Fix BoolF` is isomorphic to `Bool`.

### Summary #

The catamorphism for Boolean values is a function, method, or operator akin to the familiar ternary conditional operator. The most common descriptions of catamorphisms that I've found emphasise how a catamorphism is like a fold; an operation you can use to reduce a data structure like a list or a tree to a single value. In that light, it may be surprising that something as simple as Boolean values have an associated catamorphism.

Since `Fix BoolF` is isomorphic to `Bool`, you may wonder what the point is. Why define this data type, and implement functions like `andF`, `orF`, and `notF`?

The code presented here is nothing but an analysis tool. It's a way to identify the catamorphism for Boolean values.

Next: Peano catamorphism.

## Catamorphisms

Monday, 29 April 2019 18:31:00 UTC

A catamorphism is a general abstraction that enables you to handle multiple values, for example in order to reduce them to a single value.

This article series is part of an even larger series of articles about the relationship between design patterns and category theory. In another article series in this big series of articles, you learned about functors, applicatives, and other types of data containers.

You may have heard about map-reduce architectures. Much software can be designed around two general types of operations: those that map data, and those that reduce data. A functor is a container of data that supports structure-preserving maps. Thus, you can think of functors as the general abstraction for map operations (also sometimes called projections). Does a similar universal abstraction exist for operations that reduce data?

Yes, that abstraction is called a catamorphism.

### Aggregation #

Catamorphism is an intimidating word, so let's start with an example. You often have a collection of values that you'd like to reduce to a single value. Such a collection can contain arbitrarily complex objects, but I'll keep it simple and start with a collection of numbers:

`new[] { 42, 1337, 2112, 90125, 5040, 7, 1984 };`

This particular list of numbers is an array, but that's not important. What comes next works for any `IEnumerable<T>`, including arrays. I only chose an array because the C# syntax for array creation is more compact than for other collection types.

How do you reduce those seven numbers to a single number? That depends on what you want that number to tell you. One option is to add the numbers together. There's a specific, built-in function for that:

```> new[] { 42, 1337, 2112, 90125, 5040, 7, 1984 }.Sum();
100647```

The Sum extension method is a one of many built-in functions that enable you to reduce a list of numbers to a single number: Average, Max, Count, and so on.

What do you do, though, if you need to reduce many values to one, and there's no existing function for that? What if, for example, you need to add all the numbers using modulo 360 addition?

In that case, you use Aggregate:

```> new[] { 42, 1337, 2112, 90125, 5040, 7, 1984 }.Aggregate((x, y) => (x + y) % 360)
207```

The way to interpret this result is that the initial array represents a sequence of rotations (measured in degrees), and the result is the final angle after all the rotations have completed.

In other (functional) languages, such a 'reduce' operation is called a fold. The metaphor, I suppose, is that you fold multiple values together, two by two.

A fold is a catamorphism, but a catamorphism is a more general abstraction. For some data structures, the catamorphism is more powerful than the fold, but for collections, there's no difference.

There's one edge case we need to be aware of, though. What if the collection is empty?

### Aggregation of empty containers #

What happens if you attempt to aggregate an empty collection?

```> new int[0].Aggregate((x, y) => (x + y) % 360)
Sequence contains no elements
+ System.Linq.Enumerable.Aggregate<TSource>(IEnumerable<TSource>, Func<TSource, TSource, TSource>)```

The `Aggregate` method throws an exception because it doesn't know how to deal with empty collections. The lambda expression you supply tells the `Aggregate` method how to combine two values into one. This is, for instance, how semigroups accumulate.

The lambda expression handles all cases where you have two or more values. If you have only a single value, then that's no problem either:

```> new[] { 1337 }.Aggregate((x, y) => (x + y) % 360)
1337```

In that case, the lambda expression isn't involved at all, because the single value is simply returned without modification. In this example, this could even be interpreted as being incorrect, since you'd expect the result to be 257 (`1337 % 360`).

It's safer to use the `Aggregate` overload that takes a seed value:

```> new int[0].Aggregate(0, (x, y) => (x + y) % 360)
0```

Not only does that gracefully handle empty collections, it also gives you a 'better' result for a single value:

```> new[] { 1337 }.Aggregate(0, (x, y) => (x + y) % 360)
257```

This works better because the method always starts with the seed value, which means that even if there's only a single value (`1337`), the lambda expression still runs (`(0 + 1337) % 360`).

This overload of `Aggregate` has a different type, though:

```public static TAccumulate Aggregate<TSource, TAccumulate>(
this IEnumerable<TSource> source,
TAccumulate seed,
Func<TAccumulate, TSource, TAccumulate> func);```

Notice that the `func` doesn't require the accumulator to have the same type as elements from the `source` collection. This enables you to translate on the fly, so to speak. You can still use binary operations like the above modulo 360 addition, because that just implies that both `TSource` and `TAccumulate` are `int`.

With this overload, you could, for example, use the Angle class to perform the work:

```> new[] { 42, 1337, 2112, 90125, 5040, 7, 1984 }
. .Aggregate(Angle.Identity, (a, i) => a.Add(Angle.FromDegrees(i)))
[{ Angle = 207° }]```

Now the `seed` argument is `Angle.Identity`, which implies that `TAccumulate` is `Angle`. The `source` is still a collection of numbers, so `TSource` is `int`. Hence, I called the angle `a` and the integer `i` in the lambda expression. The output is an `Angle` object that represents 207°.

That `Aggregate` overload is the catamorphism for collections. It reduces a collection to an object.

### Catamorphisms and folds #

Is catamorphism just an intimidating word for aggregate, accumulate, fold, or reduce?

It took me a long time to be able to tell the difference, because in many cases, it seems that there's no difference. The purpose of this article series is to make the distinction clearer. In short, a catamorphism is a more general concept.

For some data structures, such as Boolean values, or Peano numbers, the catamorphism is all there is; no fold exists. For other data structures, such as Maybe or collections, the catamorphism and the fold coincide. Still other data structures, such as Either and trees, support folding, but the fold is based on the catamorphism. For those types, there are operations you can do with the catamorphism that are impossible to implement with the fold function. One example is that a tree's catamorphism enables you to count its leaves; you can't do that with its fold function.

Each of these articles will contain a fair amount of Haskell code, but even if you're an object-oriented programmer who doesn't read Haskell, you should still scan them, as I'll start each with some C# examples. The Haskell code, by the way, is available on GitHub.

### Greek #

When encountering a word like catamorphism, your reaction might be:

"Catamorphism?! What does that even mean? It's all Greek to me."
Indeed, it's Greek, as is so much of mathematical terminology. The cata prefix means 'down'; lots of words start with cata, like catastrophe, catalogue, catatonia, catacomb, etc.

The morph suffix generally means 'shape'. While the cata prefix appears in common words like catastrophe, the morph suffix mostly appears in more academic contexts. Programmers will probably have encountered polymorphism and skeuomorphism, not to mention isomorphism. While morphism is heavily used in mathematics, other sciences use the suffix too, like dimorphism in biology.

In category theory, a morphism is basically just an arrow that points from one object to another. Think of it as a function.

If a morphism is just a function, why don't we just call it that, then? Is it really necessary with this intimidating terminology? Yes and no.

If someone had originally figured all of this out in the context of mainstream programming, he or she would probably have used friendlier names, like condense, reduce, fold, and so on. This would have been more encouraging, although I'm not sure it would have been better.

In software architecture we use many overloaded terms. For example, what's a service, or a client? What does tier mean? Is it the same as a layer, or is it something different? What's the difference between a library and a framework?

At least a word like catamorphism is concise. It's not in common use, so isn't overloaded and vague.

Another, more pragmatic, concern is that whether you like it or not, the terminology is already established. Mathematicians decided to name the concept catamorphism. While the name may seem intimidating, I prefer to teach concepts like these using established terminology. This means that if my articles are unclear, you can do further research with other resources. That's the benefit of established terminology, whether you like the specific words or not.

### Summary #

You can compose entire applications based on the abstractions of map and reduce. You can see one example of such a system in my A Functional Architecture with F# Pluralsight course.

The terms map and reduce may, however, not be helpful, because it may not be clear exactly what types of data you can map, and what types you can reduce. One of the most important goals of this overall article series about universal abstractions is to help you identify when such software architectures apply. This is more often that you think.

What sort of data can you map? You can map functors. While hardly finite, there's a catalogue of well-known functors, of which I've covered some, but not all. That catalogue contains data containers like Maybe, Tree, lazy computations, tasks, and perhaps a score more. The catalogue of (actually useful) functors has, in my experience, a manageable size.

Likewise you could ask: What sort of data can you reduce? How do you implement that reduction? Again, there's a compact set of well-known catamorphisms. How do you reduce a collection? You use its catamorphism (which is equal to a fold). How do you reduce a tree? You use its catamorphism. How do you reduce an Either object? You use its catamorphism.

When we learn new programming languages, new libraries, new frameworks, we gladly invest time in learning hundreds, if not thousands, of keywords, APIs, extensibility points, and so on. May I offer, for your consideration, that your mental resources are better spent learning only a handful of universal abstractions?

Next: Boolean catamorphism.

In other (functional) languages, such a 'reduce' operation is called a fold. The metaphor, I suppose, is that you fold multiple values together, two by two.
...the `Aggregate` overload that takes a seed value...

My impression is that part of the functional programming style is to avoid function overloading. Consistent with that is the naming used by Language Ext for these concepts. In Language Ext, the function with type (in F# notation) `seq<'a> -> ('a -> 'a -> 'a) -> 'a` is called Reduce and the function with type (in F# notation) `seq<'a> -> 'b -> ('b -> 'a -> 'b) -> 'b` is called Fold.

I don't know the origin of these two names, but I remember the difference by thinking about preparing food. In cooking, reduction increases the concentration of a liquid by boiling away some of its water. I think of the returned `'a` as being a highly concentrated form of the input sequence since every sequence element (and only those elements) was used to create that return value. In baking, folding is a technique that carefully combines two mixtures into one. This reminds me of how the seed value `'b` and the sequence of `'a` are (typically) two different types and are combined by the given function. They are not perfect analogies, but they work for me.

On a related note, I dislike that Reduce returns `'a` instead of `Option<'a>`.

2019-07-12 12:20 UTC

Tyson, thank you for writing. As you may know, my book liberally employs cooking analogies, but I admit that I've never thought about reduction and fold in that light before. Good analogies, although perhaps a bit strained (pun intended).

They do work well, though, for the reasons you give.

As far as I can tell, this has more to do with the combination of Hindley–Milner type inference and currying you encounter in Haskell and ML-derived languages than it has to do with functional programming in itself. If I recall correctly, Clojure makes copious use of overloading.

The problem with overloading in a language like F# is that if you imagine that the function you refer to as `fold` was also called `reduce`, a partially applied expression like this would be ambiguous:

`let foo = reduce xs bar`

What is `bar`, here? If `reduce` is overloaded, is it a function, or is it a 'seed value'?

As far as I can tell, the compiler can't infer that, so instead of compromising on type inference, the languages in question disallow function overloading.

Notice, additionally, that F# does allow method overloading, for the part of the language that enables interoperability with the rest of .NET. In that part of the language, type inference rarely works anyway. I'm not an expert in how the F# compiler works, but I've always understood this to indicate that the interop part of F# isn't based on Hindley-Milner. I don't see how it could be, since the .NET/IL type system isn't a Hindley-Milner type system.

The `reduce` function you refer to is, by the way, based on a semigroup instance. More specifically, it's simply how semigroups accumulate. I agree that `reduce` is partial, and therefore not as pretty as one could wish, but I think a more appropriate solution is to define it on `NotEmptyCollection<T>`, instead of on `IEnumerable<T>`, as shown in that article.

In other words, I don't think `reduce` belongs on `IEnumerable<T>` at all. I know it's in both F# and Haskell, but my personal opinion is that it shouldn't be, just like Haskell's `head` function ought not to exist either...

2019-07-14 16:29 UTC

## Applicative monoids

Monday, 22 April 2019 05:36:00 UTC

An applicative functor containing monoidal values itself forms a monoid.

This article is an instalment in an article series about applicative functors. An applicative functor is a data container that supports combinations. If an applicative functor contains values of a type that gives rise to a monoid, then the functor itself forms a monoid.

In a previous article you learned that lazy computations of monoids remain monoids. Furthermore, a lazy computation is an applicative functor, and it turns out that the result generalises. The result regarding lazy computation is just a special case.

### Monap #

Since version 4.11 of Haskell's base library, `Monoid` is a subset of `Semigroup`, so in order to create a `Monoid` instance, you must first define a `Semigroup` instance.

In order to escape the need for flexible contexts, you'll have to define a wrapper `newtype` that'll be the instance. What should you call it? It's going to be an applicative functor of monoids, so perhaps something like ApplicativeMonoid? Nah, that's too long. AppMon, then? Sure, but how about flipping the terms: MonApp? That's better. Let's drop the last p and dispense with the Pascal case: Monap.

Monap almost looks like Monad, only with the last letter rotated half a revolution. This should allow for maximum confusion.

To be clear, I normally don't advocate for droll word play when writing production code, but I occasionally do it in articles and presentations. The Monap in this article exists only to illustrate a point. It's not intended to be used. Furthermore, this article doesn't discuss monads at all, so the risk of confusion should, hopefully, be minimised. I may, however, regret this decision...

### Applicative semigroup #

First, introduce the wrapper `newtype`:

`newtype Monap f a = Monap { runMonap :: f a } deriving (Show, Eq)`

This only states that there's a type called `Monap` that wraps some higher-kinded type `f a`; that is, a container `f` of values of the type `a`. The intent is that `f` is an applicative functor, hence the use of the letter f, but the type itself doesn't constrain `f` to any type class.

The `Semigroup` instance does, though:

```instance (Applicative f, Semigroup a) => Semigroup (Monap f a) where
(Monap x) <> (Monap y) = Monap \$ liftA2 (<>) x y
```

This states that when `f` is a `Applicative` instance, and `a` is a `Semigroup` instance, then `Monap f a` is also a `Semigroup` instance.

Here's an example of combining two applicative semigroups:

```λ> Monap (Just (Max 42)) <> Monap (Just (Max 1337))
Monap {runMonap = Just (Max {getMax = 1337})}```

This example uses the `Max` semigroup container, and `Maybe` as the applicative functor. For `Max`, the `<>` operator returns the value that contains the highest value, which in this case is 1337.

It even works when the applicative functor in question is `IO`:

```λ> runMonap \$ Monap (Sum <\$> randomIO @Word8) <> Monap (Sum <\$> randomIO @Word8)
Sum {getSum = 165}```

This example uses `randomIO` to generate two random values. It uses the `TypeApplications` GHC extension to make `randomIO` generate `Word8` values. Each random number is projected into the `Sum` container, which means that `<>` will add the numbers together. In the above example, the result is 165, but if you evaluate the expression a second time, you'll most likely get another result:

```λ> runMonap \$ Monap (Sum <\$> randomIO @Word8) <> Monap (Sum <\$> randomIO @Word8)
Sum {getSum = 246}```

You can also use linked list (`[]`) as the applicative functor. In this case, the result may be surprising (depending on what you expect):

```λ> Monap [Product 2, Product 3] <> Monap [Product 4, Product 5, Product 6]
Monap {runMonap = [Product {getProduct = 8},Product {getProduct = 10},Product {getProduct = 12},
Product {getProduct = 12},Product {getProduct = 15},Product {getProduct = 18}]}```

Notice that we get all the combinations of products: 2 multiplied with each element in the second list, followed by 3 multiplied by each of the elements in the second list. This shouldn't be that startling, though, since you've already, previously in this article series, seen several examples of how an applicative functor implies combinations.

### Applicative monoid #

With the `Semigroup` instance in place, you can now add the `Monoid` instance:

```instance (Applicative f, Monoid a) => Monoid (Monap f a) where
mempty = Monap \$ pure \$ mempty
```

This is straightforward: you take the identity (`mempty`) of the monoid `a`, promote it to the applicative functor `f` with `pure`, and finally put that value into the `Monap` wrapper.

This works fine as well:

```λ> mempty :: Monap Maybe (Sum Integer)
Monap {runMonap = Just (Sum {getSum = 0})}

λ> mempty :: Monap [] (Product Word8)
Monap {runMonap = [Product {getProduct = 1}]}```

The identity laws also seem to hold:

```λ> Monap (Right mempty) <> Monap (Right (Sum 2112))
Monap {runMonap = Right (Sum {getSum = 2112})}

λ> Monap ("foo", All False) <> Monap mempty
Monap {runMonap = ("foo",All {getAll = False})}```

The last, right-identity example is interesting, because the applicative functor in question is a tuple. Tuples are `Applicative` instances when the first, or left, element is a `Monoid` instance. In other words, `f` is, in this case, `(,) String`. The `Monoid` instance that `Monap` sees as `a`, on the other hand, is `All`.

Since tuples of monoids are themselves monoids, however, I can get away with writing `Monap mempty` on the right-hand side, instead of the more elaborate template the other examples use:

```λ> Monap ("foo", All False) <> Monap ("", mempty)
Monap {runMonap = ("foo",All {getAll = False})}```

or perhaps even:

```λ> Monap ("foo", All False) <> Monap (mempty, mempty)
Monap {runMonap = ("foo",All {getAll = False})}```

Ultimately, all three alternatives mean the same.

### Associativity #

As usual, I'm not going to do the work of formally proving that the monoid laws hold for the `Monap` instances, but I'd like to share some QuickCheck properties that indicate that they do, starting with a property that verifies associativity:

```assocLaw :: (Eq a, Show a, Semigroup a) => a -> a -> a -> Property
assocLaw x y z = (x <> y) <> z === x <> (y <> z)```

This property is entirely generic. It'll verify associativity for any `Semigroup a`, not only for `Monap`. You can, however, run it for various `Monap` types, as well. You'll see how this is done a little later.

### Identity #

Likewise, you can write two properties that check left and right identity, respectively.

```leftIdLaw :: (Eq a, Show a, Monoid a) => a -> Property
leftIdLaw x = x === mempty <> x

rightIdLaw :: (Eq a, Show a, Monoid a) => a -> Property
rightIdLaw x = x === x <> mempty
```

Again, this is entirely generic. These properties can be used to test the identity laws for any monoid, including `Monap`.

### Properties #

You can run each of these properties multiple time, for various different functors and monoids. As `Applicative` instances, I've used `Maybe`, `[]`, `(,) Any`, and `Identity`. As `Monoid` instances, I've used `String`, `Sum Integer`, `Max Int16`, and `[Float]`. Notice that a list (`[]`) is both an applicative functor as well as a monoid. In this test set, I've used it in both roles.

```tests =
[
testGroup "Properties" [
testProperty "Associativity law, Maybe String" (assocLaw @(Monap Maybe String)),
testProperty "Left identity law, Maybe String" (leftIdLaw @(Monap Maybe String)),
testProperty "Right identity law, Maybe String" (rightIdLaw @(Monap Maybe String)),
testProperty "Associativity law, [Sum Integer]" (assocLaw @(Monap [] (Sum Integer))),
testProperty "Left identity law, [Sum Integer]" (leftIdLaw @(Monap [] (Sum Integer))),
testProperty "Right identity law, [Sum Integer]" (rightIdLaw @(Monap [] (Sum Integer))),
testProperty "Associativity law, (Any, Max Int8)" (assocLaw @(Monap ((,) Any) (Max Int8))),
testProperty "Left identity law, (Any, Max Int8)" (leftIdLaw @(Monap ((,) Any) (Max Int8))),
testProperty "Right identity law, (Any, Max Int8)" (rightIdLaw @(Monap ((,) Any) (Max Int8))),
testProperty "Associativity law, Identity [Float]" (assocLaw @(Monap Identity [Float])),
testProperty "Left identity law, Identity [Float]" (leftIdLaw @(Monap Identity [Float])),
testProperty "Right identity law, Identity [Float]" (rightIdLaw @(Monap Identity [Float]))
]
]
```

All of these properties pass.

### Summary #

It seems that any applicative functor that contains monoidal values itself forms a monoid. The `Monap` type presented in this article only exists to demonstrate this conjecture; it's not intended to be used.

If it holds, I think it's an interesting result, because it further enables you to reason about the properties of complex systems, based on the properties of simpler systems.

Next: Bifunctors.

It seems that any applicative functor that contains monoidal values itself forms a monoid.

Is it necessary for the functor to be applicative? Do you know of a functor that contains monoidal values for which itself does not form a monoid?

2019-05-13 11:28 UTC

Tyson, thank you for writing. Yes, it's necessary for the functor to be applicative, because you need the applicative combination operator `<*>` in order to implement the combination. In C#, you'd need an `Apply` method as shown here.

Technically, the monoidal `<>` operator for `Monap` is, as you can see, implemented with a call to `liftA2`. In Haskell, you can implement an instance of `Applicative` by implementing either `liftA2` or `<*>`, as well as `pure`. You usually see `Applicative` described by `<*>`, which is what I've done in my article series on applicative functors. If you do that, you can define `liftA2` by a combination of `<*>` and `fmap` (the `Select` method that defines functors).

If you want to put this in C# terms, you need both `Select` and `Apply` in order to be able to lift a monoid into a functor.

Is there a functor that contains monoidal values that itself doesn't form a monoid?

Yes, indeed. In order to answer that question, we 'just' need to identify a functor that's not an applicative functor. Tuples are good examples.

A tuple forms a functor, but in general nothing more than that. Consider a tuple where the first element is a `Guid`. It's a functor, but can you implement the following function?

```public static Tuple<Guid, TResult> Apply<TResult, T>(
this Tuple<Guid, Func<T, TResult>> selector,
Tuple<Guid, T> source)
{
throw new NotImplementedException("What would you write here?");
}```

You can pull the `T` value out of `source` and project it to a `TResult` value with `selector`, but you'll need to put it back in a `Tuple<Guid, TResult>`. Which `Guid` value are you going to use for that tuple?

There's no clear answer to that question.

More specifically, consider `Tuple<Guid, int>`. This is a functor that contains monoidal values. Let's say that we want to use the addition monoid over integers. How would you implement the following method?

```public static Tuple<Guid, int> Add(this Tuple<Guid, int> x, Tuple<Guid, int> y)
{
throw new NotImplementedException("What would you write here?");
}```

Again, you run into the issue that while you can pull the integers out of the tuples and add them together, there's no clear way to figure out which `Guid` value to put into the tuple that contains the sum.

The issue particularly with tuples is that there's no general way to combine the leftmost values of the tuples. If there is - that is, if leftmost values form a monoid - then the tuple is also an applicative functor. For example, `Tuple<string, int>` is applicative and forms a monoid over addition:

```public static Tuple<string, TResult> Apply<TResult, T>(
this Tuple<string, Func<T, TResult>> selector,
Tuple<string, T> source)
{
return Tuple.Create(
selector.Item1 + source.Item1,
selector.Item2(source.Item2));
}

public static Tuple<string, int> Add(this Tuple<string, int> x, Tuple<string, int> y)
{
return Tuple.Create(x.Item1 + y.Item1, x.Item2 + y.Item2);
}```

You can also implement `Add` with `Apply`, but you're going to need two `Apply` overloads to make it work.

Incidentally, unbeknownst to me, the `Ap` wrapper was added to Haskell's `Data.Monoid` module 12 days before I wrote this article. In all but name, it's equivalent to the `Monap` wrapper presented here.

2019-05-14 20:44 UTC

...if leftmost values form a monoid - then the tuple is also an applicative functor. For example, `Tuple<string, int>` is applicative...

I want to add some prepositional phrases to our statements like I commented here to help claify things. I don't think that `Tuple<string, int>` can be applicative because there are no type parameters in which it could be applicative. Were you trying to say that `Tuple<string, B>` is applicative in `B`? This seems to match your `Apply` function, which doesn't depend on `int`.

2019-05-30 05:02 UTC

Tyson, you're quite right; good catch. My wording was incorrect (I was probably either tired or in a hurry when I wrote that), but fortunately, the code looks like it's correct.

That you for pointing out my error.

2019-05-30 13:00 UTC

...`Tuple<string, int>` is applicative and forms a monoid over addition...

I do agree with the monoid part, where "addition" means string concatenation for the first item and integer addition for the second item.

`Tuple<string, B>` is applicative in `B`

Now I am trying to improve my understanding of this statement. In Haskell, my understanding the definition of the Applicative type class applied to `Tuple<string, B>` requires a function `pure` from `B` to `Tuple<string, B>`. What it the definition of this funciton? Does it use the empty string in order to make an instance of `Tuple<string, B>`? If so, what is the justification for this? Or maybe my reasoning here is mistaken.

2019-05-31 12:52 UTC

Tyson, thank you for writing. In Haskell, it's true that applicative functors must also define `pure`. In this article series, I've glosssed over that constraint, since I'm not aware of any data containers that can lawfully implement `<*>` or `liftA2`, but can't define `pure`.

The applicative instance for tuples is, however, constrained:

`Monoid a => Applicative ((,) a)`

The construct `((,) a)` means any tuple where the first element has the generic type `a`. The entire expression means that tuples are applicative functors when the first element forms a monoid; that's the restriction on `a`. The definition of `pure`, then, is:

`pure x = (mempty, x)`

That is, use the monoidal identity (`mempty`) for the first element, and use `x` as the second element. For strings, since the identity for string concatenation is the empty string, yes, it does exactly mean that `pure` for `Tuple<string, B>` would return a tuple with the empty string, and the input argument as the second element:

```public static Tuple<string, T> Pure<T>(this T x)
{
return Tuple.Create("", x);
}```

That's the behaviour you get from Haskell as well:

```Prelude Data.Monoid> pure 42 :: (String, Int)
("",42)```

2019-05-31 14:59 UTC

## Lazy monoids

Monday, 15 April 2019 13:54:00 UTC

Lazy monoids are monoids. An article for object-oriented programmers.

This article is part of a series about monoids. In short, a monoid is an associative binary operation with a neutral element (also known as identity). Previous articles have shown how more complex monoids arise from simpler monoids, such as tuple monoids, function monoids, and Maybe monoids. This article shows another such result: how lazy computations of monoids itself form monoids.

You'll see how simple this is through a series of examples. Specifically, you'll revisit several of the examples you've already seen in this article series.

Perhaps the most intuitive monoid is addition. Lazy addition forms a monoid as well. In C#, you can implement this with a simple extension method:

```public static Lazy<int> Add(this Lazy<int> x, Lazy<int> y)
{
return new Lazy<int>(() => x.Value + y.Value);
}```

This `Add` method simply adds two lazy integers together in a lazy computation. You use it like any other extension method:

```Lazy<int> x = // ...
Lazy<int> y = // ...

I'll spare you the tedious listing of FsCheck-based properties that demonstrate that the monoid laws hold. We'll look at an example of such a set of properties later in this article, for one of the other monoids.

### Lazy multiplication #

Not surprisingly, I hope, you can implement multiplication over lazy numbers in the same way:

```public static Lazy<int> Multiply(this Lazy<int> x, Lazy<int> y)
{
return new Lazy<int>(() => x.Value * y.Value);
}```

Usage is similar to lazy addition:

```Lazy<int> x = // ...
Lazy<int> y = // ...
Lazy<int> product = x.Multiply(y);```

As is the case with lazy addition, this `Multiply` method currently only works with lazy `int` values. If you also want it to work with `long`, `short`, or other types of numbers, you'll have to add method overloads.

### Lazy Boolean monoids #

There are four monoids over Boolean values, although I've customarily only shown two of them: and and or. These also, trivially, work with lazy Boolean values:

```public static Lazy<bool> And(this Lazy<bool> x, Lazy<bool> y)
{
return new Lazy<bool>(() => x.Value && y.Value);
}

public static Lazy<bool> Or(this Lazy<bool> x, Lazy<bool> y)
{
return new Lazy<bool>(() => x.Value || y.Value);
}```

Given the previous examples, you'll hardly be surprised to see how you can use one of these extension methods:

```Lazy<bool> x = // ...
Lazy<bool> y = // ...
Lazy<bool> b = x.And(y);```

Have you noticed a pattern in how the lazy binary operations `Add`, `Multiply`, `And`, and `Or` are implemented? Could this be generalised?

In a previous article you saw how angular addition forms a monoid. Lazy angular addition forms a monoid as well, which you can implement with another extension method:

```public static Lazy<Angle> Add(this Lazy<Angle> x, Lazy<Angle> y)
{
}```

Until now, you may have noticed that all the extension methods seemed to follow a common pattern that looks like this:

`return new Lazy<Foo>(() => x.Value ⋄ y.Value);`

I've here used the diamond operator `⋄` as a place-holder for any sort of binary operation. My choice of that particular character is strongly influenced by Haskell, where semigroups and monoids polymorphically are modelled with (among other options) the `<>` operator.

The lazy angular addition implementation looks a bit different, though. This is because the original example uses an instance method to model the binary operation, instead of an infix operator such as `+`, `&&`, and so on. Given that the implementation of a lazy binary operation can also look like this, can you still imagine a generalisation?

### Lazy string concatenation #

If we follow the rough ordering of examples introduced in this article series about monoids, we've now reached concatenation as a monoid. While various lists, arrays, and other sorts of collections also form a monoid over concatenation, in .NET, `IEnumerable<T>` already enables lazy evaluation, so I think it's more interesting to consider lazy string concatenation.

The implementation, however, holds few surprises:

```public static Lazy<string> Concat(this Lazy<string> x, Lazy<string> y)
{
return new Lazy<string>(() => x.Value + y.Value);
}```

The overall result, so far, seems encouraging. All the basic monoids we've covered are also monoids when lazily computed.

The portfolio example from Kent Beck's book Test-Driven Development By Example also forms a monoid. You can, again, implement an extension method that enables you to add lazy expressions together:

```public static Lazy<IExpression> Plus(
this Lazy<IExpression> source,
{
}```

So far, you've seen several examples of implementations, but are they really monoids? All are clearly binary operations, but are they associative? Do identities exist? In other words, do the lazy binary operations obey the monoid laws?

As usual, I'm not going to prove that they do, but I do want to share a set of FsCheck properties that demonstrate that the monoid laws hold. As an example, I'll share the properties for this lazy `Plus` method, but you can write similar properties for all of the above methods as well.

You can verify the associativity law like this:

```public void LazyPlusIsAssociative(
Lazy<IExpression> x,
Lazy<IExpression> y,
Lazy<IExpression> z)
{
Assert.Equal(
x.Plus(y).Plus(z),
x.Plus(y.Plus(z)),
Compare.UsingBank);
}```

Here, `Compare.UsingBank` is just a test utility API to make the code more readable:

```public static class Compare
{
public static ExpressionEqualityComparer UsingBank =
new ExpressionEqualityComparer();
}```

This takes advantage of the overloads for xUnit.net's `Assert` methods that take custom equality comparers as an extra, optional argument. `ExpressionEqualityComparer` is implemented in the test code base:

```public class ExpressionEqualityComparer :
IEqualityComparer<IExpression>, IEqualityComparer<Lazy<IExpression>>
{

public ExpressionEqualityComparer()
{
bank = new Bank();
}

public bool Equals(IExpression x, IExpression y)
{
var xm = bank.Reduce(x, "USD");
var ym = bank.Reduce(y, "USD");
return object.Equals(xm, ym);
}

public int GetHashCode(IExpression obj)
{
return bank.Reduce(obj, "USD").GetHashCode();
}

public bool Equals(Lazy<IExpression> x, Lazy<IExpression> y)
{
return Equals(x.Value, y.Value);
}

public int GetHashCode(Lazy<IExpression> obj)
{
return GetHashCode(obj.Value);
}
}```

If you think that the exchange rate between Dollars and Swiss Francs looks ridiculous, it's because I'm using the rate that Kent Beck used in his book, which is from 2002 (but otherwise timeless).

The above property passes for hundreds of randomly generated input values, as is the case for this property, which verifies the left and right identity:

```public void LazyPlusHasIdentity(Lazy<IExpression> x)
{
Assert.Equal(x, x.Plus(Plus.Identity.ToLazy()), Compare.UsingBank);
Assert.Equal(x, Plus.Identity.ToLazy().Plus(x), Compare.UsingBank);
}```

These properties are just examples, not proofs. Still, they give confidence that lazy computations of monoids are themselves monoids.

### Lazy Roster combinations #

The last example you'll get in this article is the `Roster` example from the article on tuple monoids. Here's yet another extension method that enables you to combine two lazy rosters:

```public static Lazy<Roster> Combine(this Lazy<Roster> x, Lazy<Roster> y)
{
return new Lazy<Roster>(() => x.Value.Combine(y.Value));
}```

At this point it should be clear that there's essentially two variations in how the above extension methods are implemented. One variation is when the binary operation is implemented with an infix operator (like `+`, `||`, and so on), and another variation is when it's modelled as an instance method. How do these implementations generalise?

I'm sure you could come up with an ad-hoc higher-order function, abstract base class, or interface to model such a generalisation, but I'm not motivated by saving keystrokes. What I'm trying to uncover with this overall article series is how universal abstractions apply to programming.

Which universal abstraction is in play here?

### Lazy monoids as applicative operations #

Lazy<T> forms an applicative functor. Using appropriate `Apply` overloads, you can rewrite all the above implementations in applicative style. Here's lazy addition:

```public static Lazy<int> Add(this Lazy<int> x, Lazy<int> y)
{
Func<int, int, int> f = (i, j) => i + j;
return f.Apply(x).Apply(y);
}```

This first declares a `Func` value `f` that invokes the non-lazy binary operation, in this case `+`. Next, you can leverage the applicative nature of `Lazy<T>` to apply `f` to the two lazy values `x` and `y`.

Multiplication, as well as the Boolean operations, follow the exact same template:

```public static Lazy<int> Multiply(this Lazy<int> x, Lazy<int> y)
{
Func<int, int, int> f = (i, j) => i * j;
return f.Apply(x).Apply(y);
}

public static Lazy<bool> And(this Lazy<bool> x, Lazy<bool> y)
{
Func<bool, bool, bool> f = (b1, b2) => b1 && b2;
return f.Apply(x).Apply(y);
}

public static Lazy<bool> Or(this Lazy<bool> x, Lazy<bool> y)
{
Func<bool, bool, bool> f = (b1, b2) => b1 || b2;
return f.Apply(x).Apply(y);
}```

Notice that in all four implementations, the second line of code is verbatim the same: `return f.Apply(x).Apply(y);`

Does this generalisation also hold when the underlying, non-lazy binary operation is modelled as an instance method, as is the case of e.g. angular addition? Yes, indeed:

```public static Lazy<Angle> Add(this Lazy<Angle> x, Lazy<Angle> y)
{
Func<Angle, Angle, Angle> f = (i, j) => i.Add(j);
return f.Apply(x).Apply(y);
}```

You can implement the `Combine` method for lazy `Roster` objects in the same way, as well as `Plus` for lazy monetary expressions. The latter is worth revisiting.

### Using the Lazy functor over portfolio expressions #

The lazy `Plus` implementation looks like all of the above `Apply`-based implementations:

```public static Lazy<IExpression> Plus(
{
Func<IExpression, IExpression, IExpression> f = (x, y) => x.Plus(y);
}```

In my article, however, you saw how, when `Plus` is a monoid, you can implement `Times` as an extension method. Can you implement a lazy version of `Times` as well? Must it be another extension method?

Yes, but instead of an ad-hoc implementation, you can take advantage of the functor nature of Lazy:

```public static Lazy<IExpression> Times(this Lazy<IExpression> exp, int multiplier)
{
return exp.Select(x => x.Times(multiplier));
}```

Notice that instead of explicitly reaching into the lazy `Value`, you can simply call `Select` on `exp`. This lazily projects the `Times` operation, while preserving the invariants of `Lazy<T>` (i.e. that the computation is deferred until you ultimately access the `Value` property).

You can implement a lazy version of `Reduce` in the same way:

```public static Lazy<Money> Reduce(this Lazy<IExpression> exp, Bank bank, string to)
{
return exp.Select(x => x.Reduce(bank, to));
}```

The question is, however, is it even worthwhile? Do you need to create all these overloads, or could you just leverage `Select` when you have a lazy value?

For example, if the above `Reduce` overload didn't exist, you'd still be able to work with the portfolio API like this:

```Lazy<IExpression> portfolio = // ...
Lazy<Money> result = portfolio.Select(x => x.Reduce(bank, "USD"));```

If you only occasionally use `Reduce`, then perhaps this is good enough. If you frequently call `Reduce`, however, it might be worth to add the above overload, in which case you could then instead write:

```Lazy<IExpression> portfolio = // ...
Lazy<Money> result = portfolio.Reduce(bank, "USD");```

In both cases, however, I think that you'd be putting the concept of an applicative functor to good use.

### Towards generalisation #

Is the applicative style better than the initial ad-hoc implementations? That depends on how you evaluate 'better'. If you count lines of code, then the applicative style is twice as verbose as the ad-hoc implementations. In other words, this:

`return new Lazy<int>(() => x.Value + y.Value);`

seems simpler than this:

```Func<int, int, int> f = (i, j) => i + j;
return f.Apply(x).Apply(y);```

This is, however, mostly because C# is too weak to express such abstractions in an elegant way. In F#, using the custom `<*>` operator from the article on the Lazy applicative functor, you could express the lazy addition as simply as:

`lazy (+) <*> x <*> y`

In Haskell (if we, once more, pretend that `Identity` is equivalent to `Lazy`), you can simplify even further to:

`(+) <\$> x <*> y`

Or rather, if you want it in point-free style, `liftA2 (+)`.

### Summary #

The point of this article series isn't to save keystrokes, but to identify universal laws of computing, even as they relate to object-oriented programming. The pattern seems clear enough that I dare propose the following:

All monoids remain monoids under lazy computation.

In a future article I'll offer further support for that proposition.

Next: Monoids accumulate.

## A pure Test Spy

Monday, 08 April 2019 06:02:00 UTC

In a previous article on state-based testing in Haskell, I made the following throw-away statement:

"you could write an ad-hoc Mock using, for example, the Writer monad"
In that article, I didn't pursue that thought, since the theme was another. Instead, I'll expand on it here.

### Test Double continuum #

More than a decade ago, I wrote an MSDN Magazine article called Exploring The Continuum Of Test Doubles. It was in the September 2007 issue, and you can also download the entire issue as a single file and read the article offline, should you want to.

In the article, I made the argument that the classification of Test Doubles presented in the excellent xUnit Test Patterns should be thought of more as a continuum with vague and fuzzy transitions, rather than discrete categories.

This figure appeared in the original article. Given that the entire MSDN Magazine issue is available for free, and that I'm the original author of the article, I consider it fair use to repeat it here.

The point is that it's not always clear whether a Test Double is, say, a Mock, or a Spy. What I'll show you in this article is closer to a Test Spy than to a Mock, but since the distinction is blurred anyway, I think that I can get away with it.

### Test Spy #

xUnit Test Patterns defines a Test Spy as a Test Double that captures "the indirect output calls made to another component by the SUT [System Under Test] for later verification by the test." When, as shown in a previous article, you use `Mock<T>.Verify` to assert than an interaction took place, you're using the Test Double more as a Spy than a Mock:

`repoTD.Verify(r => r.Update(user));`

Strictly speaking, a Mock is a Test Double that immediately fails the test if any unexpected interaction takes place. People often call those Strict Mocks, but according to the book, that's a Mock. If the Test Double only records what happens, so that you can later query it to verify whether some interaction took place, it's closer to being a Test Spy.

Whether you call it a Mock or a Spy, you can implement verification similar to the above `Verify` method in functional programming using the Writer monad.

### Writer-based Spy #

I'll show you a single example in Haskell. In a previous article, you saw a simplified function to implement a restaurant reservation feature, repeated here for your convenience:

```tryAccept :: Int -> Reservation -> MaybeT ReservationsProgram Int
tryAccept capacity reservation = do
guard =<< isReservationInFuture reservation

reservations <- readReservations \$ reservationDate reservation
let reservedSeats = sum \$ reservationQuantity <\$> reservations
guard \$ reservedSeats + reservationQuantity reservation <= capacity

create \$ reservation { reservationIsAccepted = True }
```

This function runs in the `MaybeT` monad, so the two `guard` functions could easily prevent if from running 'to completion'. In the happy path, though, execution should reach 'the end' of the function and call the `create` function.

In order to test this happy path, you'll need to not only run a test-specific interpreter over the `ReservationsProgram` free monad, you should also verify that `reservationIsAccepted` is `True`.

You can do this using the `Writer` monad to implement a Test Spy:

```testProperty "tryAccept, happy path" \$ \
(NonNegative i)
(fmap getReservation -> reservations)
(ArbReservation reservation)
expected
->
let spy (IsReservationInFuture _ next) = return \$ next True
spy (ReadReservations _ next) = return \$ next reservations
spy (Create r next) = tell [r] >> return (next expected)
reservedSeats = sum \$ reservationQuantity <\$> reservations
capacity = reservedSeats + reservationQuantity reservation + i

(actual, observedReservations) =
runWriter \$ foldFreeT spy \$ runMaybeT \$ tryAccept capacity reservation

in  Just expected == actual &&
[True] == (reservationIsAccepted <\$> observedReservations)```

This test is an inlined QuickCheck-based property. The entire source code is available on GitHub.

Notice the `spy` function. As the name implies, it's the Test Spy for the test. Its full type is:

`spy :: Monad m => ReservationsInstruction a -> WriterT [Reservation] m a`

This is a function that, for a given `ReservationsInstruction` value returns a `WriterT` value where the type of data being written is `[Reservation]`. The function only writes to the writer context in one of the three cases: the `Create` case. The `Create` case carries with it a `Reservation` value here named `r`. Before returning the `next` step in interpreting the free monad, the `spy` function calls `tell`, thereby writing a singleton list of `[r]` to the writer context.

In the Act phase of the test, it calls the `tryAccept` function and proceeds to interpret the result, which is a `MaybeT ReservationsProgram Int` value. Calling `runMaybeT` produces a `ReservationsProgram (Maybe Int)`, which you can then interpret with `foldFreeT spy`. This returns a `Writer [Reservation] (Maybe Int)`, which you can finally run with `runWriter` to get a `(Maybe Int, [Reservation])` tuple. Thus, `actual` is a `Maybe Int` value, and `observedReservations` is a `[Reservation]` value - the reservation that was written by `spy` using `tell`.

The Assert phase of the test is a Boolean expression that checks that `actual` is as expected, and that `reservationIsAccepted` of the observed reservation is `True`.

It takes a little while to make the pieces of the puzzle fit, but it's basically just standard Haskell library functions clicked together.

### Summary #

People sometimes ask me: How do Mocks and Stubs work in functional programming?

In general, my answer is that you don't need Mocks and Stubs because when functions are pure, you don't need to to test interactions. Sooner or later, though, you may run into higher-level interactions, even if they're pure interactions, and you'll likely want to unit test those.

In a previous article you saw how to apply state-based testing in Haskell, using the State monad. In this article you've seen how you can create ad-hoc Mocks or Spies with the Writer monad. No auto-magical test-specific 'isolation frameworks' are required.

## An example of state-based testing in C#

Monday, 01 April 2019 05:50:00 UTC

An example of avoiding Mocks and Stubs in C# unit testing.

This article is an instalment in an article series about how to move from interaction-based testing to state-based testing. In the previous article, you saw an example of a pragmatic state-based test in F#. You can now take your new-found knowledge and apply it to the original C# example.

In the spirit of xUnit Test Patterns, in this article you'll see how to refactor the tests while keeping the implementation code constant.

### Connect two users #

The previous article provides more details on the System Under Test (SUT), but here it is, repeated, for your convenience:

```public class ConnectionsController : ApiController
{
public ConnectionsController(
IUserRepository userRepository)
{
UserRepository = userRepository;
}

public IUserRepository UserRepository { get; }

public IHttpActionResult Post(string userId, string otherUserId)
{
error => error.Accept(UserLookupError.Switch(
onInvalidId: "Invalid user ID.",
onNotFound:  "User not found.")));
error => error.Accept(UserLookupError.Switch(
onInvalidId: "Invalid ID for other user.",
onNotFound:  "Other user not found.")));

var connect =
from user in userRes
from otherUser in otherUserRes
select Connect(user, otherUser);

}

private User Connect(User user, User otherUser)
{
user.Connect(otherUser);
UserRepository.Update(user);

return otherUser;
}
}```

This implementation code is a simplification of the code example that serves as an example running through my two Clean Coders videos, Church Visitor and Preserved in translation.

### A Fake database #

As in the previous article, you can define a test-specific Fake database:

```public class FakeDB : Collection<User>, IUserReader, IUserRepository
{
public IResult<User, IUserLookupError> Lookup(string id)
{
if (!(int.TryParse(id, out int i)))
return Result.Error<User, IUserLookupError>(UserLookupError.InvalidId);

var user = this.FirstOrDefault(u => u.Id == i);
if (user == null)
return Result.Error<User, IUserLookupError>(UserLookupError.NotFound);

return Result.Success<User, IUserLookupError>(user);
}

public bool IsDirty { get; set; }

public void Update(User user)
{
IsDirty = true;
if (!Contains(user))
}
}```

This is one of the few cases where I find inheritance more convenient than composition. By deriving from `Collection<User>`, you don't have to explicitly write code to expose a Retrieval Interface. The entirety of a standard collection API is already available via the base class. Had this class been part of a public API, I'd be concerned that inheritance could introduce future breaking changes, but as part of a suite of unit tests, I hope that I've made the right decision.

Although you can derive a Fake database from a base class, you can still implement required interfaces - in this case `IUserReader` and `IUserRepository`. The `Update` method is the easiest one to implement, since it simply sets the `IsDirty` flag to `true` and adds the `user` if it's not already part of the collection.

The `IsDirty` flag is the only custom Retrieval Interface added to the `FakeDB` class. As the previous article explains, this flag provides a convenient was to verify whether or not the database has changed.

The `Lookup` method is a bit more involved, since it has to support all three outcomes implied by the protocol:

• If the `id` is invalid, a result to that effect is returned.
• If the user isn't found, a result to that effect is returned.
• If the user with the requested `id` is found, then that user is returned.
This is a typical quality of a Fake: it contains some production-like behaviour, while still taking shortcuts compared to a full production implementation. In this case, it properly adheres to the protocol implied by the interface and protects its invariants. It still doesn't implement persistent storage, though.

### Happy path test case #

This is all you need in terms of Test Doubles. You now have a test-specific `IUserReader` and `IUserRepository` implementation that you can pass to the `Post` method. Notice that a single class implements multiple interfaces. This is often key to be able to implement a Fake object in the first place.

Like in the previous article, you can start by exercising the happy path where a user successfully connects with another user:

```[Theory, UserManagementTestConventions]
[Frozen(Matching.ImplementedInterfaces)]FakeDB db,
User user,
User otherUser,
ConnectionsController sut)
{
db.IsDirty = false;

var actual = sut.Post(user.Id.ToString(), otherUser.Id.ToString());

var ok = Assert.IsAssignableFrom<OkNegotiatedContentResult<User>>(actual);
Assert.Equal(otherUser, ok.Content);
Assert.True(db.IsDirty);
Assert.Contains(otherUser.Id, user.Connections);
}```

This, and all other tests in this article use xUnit.net 2.3.1 and AutoFixture 4.1.0.

The test is organised according to my standard heuristic for formatting tests according to the Arrange Act Assert pattern. In the Arrange phase, it adds the two valid `User` objects to the Fake `db` and sets the `IsDirty` flag to false.

Setting the flag is necessary because this is object-oriented code, where objects have mutable state. In the previous articles with examples in F# and Haskell, the `User` types were immutable. Connecting two users didn't mutate one of the users, but rather returned a new `User` value, as this F# example demonstrates:

```// User -> User -> User
{ user with ConnectedUsers = otherUser :: user.ConnectedUsers }```

In the current object-oriented code base, however, connecting one user to another is an instance method on the `User` class that mutates its state:

```public void Connect(User otherUser)
{
}```

As a consequence, the `Post` method could, if someone made a mistake in its implementation, call `user.Connect`, but forget to invoke `UserRepository.Update`. Even if that happened, then all the other assertions would pass. This is the reason that you need the `Assert.True(db.IsDirty)` assertion in the Assert phase of the test.

While we can apply to object-oriented code what we've learned from functional programming, the latter remains simpler.

### Error test cases #

While there's one happy path, there's four distinct error paths that you ought to cover. You can use the Fake database for that as well:

```[Theory, UserManagementTestConventions]
public void UsersFailToConnectWhenUserIdIsInvalid(
[Frozen(Matching.ImplementedInterfaces)]FakeDB db,
string userId,
User otherUser,
ConnectionsController sut)
{
Assert.False(int.TryParse(userId, out var _));
db.IsDirty = false;

var actual = sut.Post(userId, otherUser.Id.ToString());

Assert.Equal("Invalid user ID.", err.Message);
Assert.False(db.IsDirty);
}

[Theory, UserManagementTestConventions]
public void UsersFailToConnectWhenOtherUserIdIsInvalid(
[Frozen(Matching.ImplementedInterfaces)]FakeDB db,
User user,
string otherUserId,
ConnectionsController sut)
{
Assert.False(int.TryParse(otherUserId, out var _));
db.IsDirty = false;

var actual = sut.Post(user.Id.ToString(), otherUserId);

Assert.Equal("Invalid ID for other user.", err.Message);
Assert.False(db.IsDirty);
}

[Theory, UserManagementTestConventions]
public void UsersDoNotConnectWhenUserDoesNotExist(
[Frozen(Matching.ImplementedInterfaces)]FakeDB db,
int userId,
User otherUser,
ConnectionsController sut)
{
db.IsDirty = false;

var actual = sut.Post(userId.ToString(), otherUser.Id.ToString());

Assert.Equal("User not found.", err.Message);
Assert.False(db.IsDirty);
}

[Theory, UserManagementTestConventions]
public void UsersDoNotConnectWhenOtherUserDoesNotExist(
[Frozen(Matching.ImplementedInterfaces)]FakeDB db,
User user,
int otherUserId,
ConnectionsController sut)
{
db.IsDirty = false;

var actual = sut.Post(user.Id.ToString(), otherUserId.ToString());

Assert.Equal("Other user not found.", err.Message);
Assert.False(db.IsDirty);
}```

There's little to say about these tests that hasn't already been said in at least one of the previous articles. All tests inspect the state of the Fake database after calling the `Post` method. The exact interactions between `Post` and `db` aren't specified. Instead, these tests rely on setting up the initial state, exercising the SUT, and verifying the final state. These are all state-based tests that avoid over-specifying the interactions.

Specifically, none of these tests use Mocks and Stubs. In fact, at this incarnation of the test code, I was able to entirely remove the reference to Moq.

### Summary #

The premise of Refactoring is that in order to be able to refactor, the "precondition is [...] solid tests". In reality, many development organisations have the opposite experience. When programmers attempt to make changes to how their code is organised, tests break. In xUnit Test Patterns this problem is called Fragile Tests, and the cause is often Overspecified Software. This means that tests are tightly coupled to implementation details of the SUT.

It's easy to inadvertently fall into this trap when you use Mocks and Stubs, even when you follow the rule of using Mocks for Commands and Stubs for Queries. Refactoring tests towards state-based testing with Fake objects, instead of interaction-based testing, could make test suites more robust to changes.

It's intriguing, though, that state-based testing is simpler in functional programming. In Haskell, you can simply write your tests in the State monad and compare the expected outcome to the actual outcome. Since state in Haskell is immutable, it's trivial to compare the expected with the actual state.

As soon as you introduce mutable state, structural equality is no longer safe, and instead you have to rely on other inspection mechanisms, such as the `IsDirty` flag seen in this, and the previous, article. This makes the tests slightly more brittle, because it tends to pull towards interaction-based testing.

While you can implement the State monad in both F# and C#, it's probably more pragmatic to express state-based tests using mutable state and the occasional `IsDirty` flag. As always, there's no panacea.

While this article concludes the series on moving towards state-based testing, I think that an appendix on Test Spies is in order.

Next: A pure Test Spy.

If we had checked the FakeDB contains to user (by retrieving, similar as in the F# case), and assert Connections property on the retrieved objects, would we still need the IsDirty flag? I think it would be good to create a couple of cases which demonstrates refactoring, and how overspecified tests break with the interaction based tests, while works nicely here.

2019-04-05 17:20 UTC

ladeak, thank you for writing. The `IsDirty` flag is essentially a hack to work around the mutable nature of the `FakeDB`. As the previous article describes:

"In the previous article, the Fake database was simply an immutable dictionary. This meant that tests could easily compare expected and actual values, since they were immutable. When you use a mutable object, like the above dictionary, this is harder. Instead, what I chose to do here was to introduce an `IsDirty` flag. This enables easy verification of whether or not the database changed."
The Haskell example demonstrates how no `IsDirty` flag is required, because you can simply compare the state before and after the SUT was exercised.

You could do something similar in C# or F#, but that would require you to take an immutable snapshot of the Fake database before exercising the SUT, and then compare that snapshot with the state of the Fake database after the SUT was exercised. This is definitely also doable (as the Haskell example demonstrates), but a bit more work, which is the (unprincipled, pragmatic) reason I instead chose to use an `IsDirty` flag.

Regarding more examples, I originally wrote another sample code base to support this talk. That sample code base contains examples that demonstrate how overspecified tests break even when you make small internal changes. I haven't yet, however, found a good home for that code base.

2019-04-06 10:25 UTC
Sven Grosen #

First of all, thank you for yet another awesome series.

The fragility of my various employers' unit tests has always bothered me, but I couldn't necessarily offer an alternative that reduced/removed that. After further thought, I initially came up with two objections to this approach (based on actual enterprise experience), but was easily able to dismiss them:

1. What if the SUT has a lot of dependencies?
• Then--following best practices--the SUT is doing too much
2. What if the dependency has a lot of methods
• Then--following best practices--the dependency is doing too much
The one point I wanted to seek clarification on though was that--as you spell out throughout the series--this "state-based" approach is no panacea and you may still need to do some test refactoring if you change the implementation of the SUT (e.g. if, referencing point #2 above, we break up a large dependency into a more targeted one). You may need to update your "fake" to account for that, but that that effort is much smaller than updating innumerable mock setup/verify calls, is that a correct summation? So I would have a "fake" per unit test fixture (to use nunit terminology) and would only need to update that one fake if/when the SUT for that fixture is refactored in such a way that impacts the fake.

After reading this series I was trying to imagine how I could introduce this into my team's codebase where both of the objections I listed above are very real problems (I am new to the team and trying to wrangle with these issues). I imagine a pragmatic first step would be to define multiple fakes for a given large SUT that attempt to group dependency behavior in some logical fashion. Per usual, you've given me a lot to think about and some motivation to clean up some code!

2019-12-12 15:24 UTC

Sven, thank you for writing. I think that your summary of my position is accurate. A Fake affords a 'one-stop' place where you can go and address changes in you SUT APIs. You'll still need to edit test code (your Fake implementation), but in single place.

We can, on the other hand, view multiple `Setup`/`Verify` changes as a violation of the DRY principle.

I don't understand, however, why you want to involve the concept of a Fixture, one way or another. A Fake is Fake, regardless of the Fixture in which it appears.

2019-12-12 19:47 UTC
Sven Grosen #

I don't understand, however, why you want to involve the concept of a Fixture, one way or another. A Fake is Fake, regardless of the Fixture in which it appears.
Mark, you are right and I had intended to remove that reference to fixtures but forgot to. I could easily see fakes living completely outside of any specific fixture.

2019-12-13 02:30 UTC

## An example of state based-testing in F#

Monday, 25 March 2019 06:34:00 UTC

While F# is a functional-first language, it's okay to occasionally be pragmatic and use mutable state, for example to easily write some sustainable state-based tests.

### A function to connect two users #

This article, like the others in this series, implements an operation to connect two users. I explain the example in details in my two Clean Coders videos, Church Visitor and Preserved in translation.

```// ('a -> Result<User,UserLookupError>) -> (User -> unit) -> 'a -> 'a -> HttpResponse<User>
let post lookupUser updateUser userId otherUserId =
let userRes =
lookupUser userId |> Result.mapError (function
| InvalidId -> "Invalid user ID."
| NotFound  -> "User not found.")
let otherUserRes =
lookupUser otherUserId |> Result.mapError (function
| InvalidId -> "Invalid ID for other user."
| NotFound  -> "Other user not found.")

let connect = result {
let! user = userRes
let! otherUser = otherUserRes
return otherUser }

match connect with Ok u -> OK u | Error msg -> BadRequest msg```

While the original C# example used Constructor Injection, the above `post` function uses partial application for Dependency Injection. The two function arguments `lookupUser` and `updateUser` represent interactions with a database. Since functions are polymorphic, however, it's possible to replace them with Test Doubles.

### A Fake database #

Like in the Haskell example, you can implement a Fake database in F#. It's also possible to implement the State monad in F#, but there's less need for it. F# is a functional-first language, but you can also write mutable code if need be. You could, then, choose to be pragmatic and base your Fake database on mutable state.

```type FakeDB () =
let users = Dictionary<int, User> ()

member val IsDirty = false with get, set

this.IsDirty <- true

member this.TryFind i =
match users.TryGetValue i with
| false, _ -> None
| true,  u -> Some u

member this.LookupUser s =
match Int32.TryParse s with
| false, _ -> Error InvalidId
| true, i ->
match users.TryGetValue i with
| false, _ -> Error NotFound
| true, u -> Ok u

member this.UpdateUser u =
this.IsDirty <- true
users.[u.UserId] <- u```

This `FakeDB` type is a class that wraps a mutable dictionary. While it 'implements' `LookupUser` and `UpdateUser`, it also exposes what xUnit Test Patterns calls a Retrieval Interface: an API that tests can use to examine the state of the object.

Immutable values normally have structural equality. This means that two values are considered equal if they contain the same constituent values, and have the same structure. Mutable objects, on the other hand, typically have reference equality. This makes it harder to compare two objects, which is, however, what almost all unit testing is about. You compare expected state with actual state.

In the previous article, the Fake database was simply an immutable dictionary. This meant that tests could easily compare expected and actual values, since they were immutable. When you use a mutable object, like the above dictionary, this is harder. Instead, what I chose to do here was to introduce an `IsDirty` flag. This enables easy verification of whether or not the database changed.

### Happy path test case #

This is all you need in terms of Test Doubles. You now have test-specific `LookupUser` and `UpdateUser` methods that you can pass to the `post` function.

Like in the previous article, you can start by exercising the happy path where a user successfully connects with another user:

```[<Fact>]
let ``Users successfully connect`` () = Property.check <| property {
let! user = Gen.user
let! otherUser = Gen.withOtherId user
let db = FakeDB ()

let actual = post db.LookupUser db.UpdateUser (string user.UserId) (string otherUser.UserId)

test <@ db.TryFind user.UserId
|> Option.exists
(fun u -> u.ConnectedUsers |> List.contains otherUser) @>
test <@ isOK actual @> }```

All tests in this article use xUnit.net 2.3.1, Unquote 4.0.0, and Hedgehog 0.7.0.0.

This test first adds two valid users to the Fake database `db`. It then calls the `post` function, passing the `db.LookupUser` and `db.UpdateUser` methods as arguments. Finally, it verifies that the 'first' user's `ConnectedUsers` now contains the `otherUser`. It also verifies that `actual` represents a `200 OK` HTTP response.

### Missing user test case #

While there's one happy-path test case, there's four other test cases left. One of these is when the first user doesn't exist:

```[<Fact>]
let ``Users don't connect when user doesn't exist`` () = Property.check <| property {
let! i = Range.linear 1 1_000_000 |> Gen.int
let! otherUser = Gen.user
let db = FakeDB ()
db.IsDirty <- false
let uniqueUserId = string (otherUser.UserId + i)

let actual = post db.LookupUser db.UpdateUser uniqueUserId (string otherUser.UserId)

test <@ not db.IsDirty @>
test <@ isBadRequest actual @> }```

This test adds one valid user to the Fake database. Once it's done with configuring the database, it sets `IsDirty` to `false`. The `AddUser` method sets `IsDirty` to `true`, so it's important to reset the flag before the act phase of the test. You could consider this a bit of a hack, but I think it makes the intent of the test clear. This is, however, a position I'm ready to reassess should the tests evolve to make this design awkward.

As explained in the previous article, this test case requires an ID of a user that doesn't exist. Since this is a property-based test, there's a risk that Hedgehog might generate a number `i` equal to `otherUser.UserId`. One way to get around that problem is to add the two numbers together. Since `i` is generated from the range 1 - 1,000,000, `uniqueUserId` is guaranteed to be different from `otherUser.UserId`.

The test verifies that the state of the database didn't change (that `IsDirty` is still `false`), and that `actual` represents a `400 Bad Request` HTTP response.

### Remaining test cases #

You can write the remaining three test cases in the same vein:

```[<Fact>]
let ``Users don't connect when other user doesn't exist`` () = Property.check <| property {
let! i = Range.linear 1 1_000_000 |> Gen.int
let! user = Gen.user
let db = FakeDB ()
db.IsDirty <- false
let uniqueOtherUserId = string (user.UserId + i)

let actual = post db.LookupUser db.UpdateUser (string user.UserId) uniqueOtherUserId

test <@ not db.IsDirty @>
test <@ isBadRequest actual @> }

[<Fact>]
let ``Users don't connect when user Id is invalid`` () = Property.check <| property {
let! s = Gen.alphaNum |> Gen.string (Range.linear 0 100) |> Gen.filter isIdInvalid
let! otherUser = Gen.user
let db = FakeDB ()
db.IsDirty <- false

let actual = post db.LookupUser db.UpdateUser s (string otherUser.UserId)

test <@ not db.IsDirty @>
test <@ isBadRequest actual @> }

[<Fact>]
let ``Users don't connect when other user Id is invalid`` () = Property.check <| property {
let! s = Gen.alphaNum |> Gen.string (Range.linear 0 100) |> Gen.filter isIdInvalid
let! user = Gen.user
let db = FakeDB ()
db.IsDirty <- false

let actual = post db.LookupUser db.UpdateUser (string user.UserId) s

test <@ not db.IsDirty @>
test <@ isBadRequest actual @> }```

All tests inspect the state of the Fake database after the calling the `post` function. The exact interactions between `post` and `db` aren't specified. Instead, these tests rely on setting up the initial state, exercising the System Under Test, and verifying the final state. These are all state-based tests that avoid over-specifying the interactions.

### Summary #

While the previous Haskell example demonstrated that it's possible to write state-based unit tests in a functional style, when using F#, it sometimes make sense to leverage the object-oriented features already available in the .NET framework, such as mutable dictionaries. It would have been possible to write purely functional state-based tests in F# as well, by porting the Haskell examples, but here, I wanted to demonstrate that this isn't required.

I tend to be of the opinion that it's only possible to be pragmatic if you know how to be dogmatic, but now that we know how to write state-based tests in a strictly functional style, I think it's fine to be pragmatic and use a bit of mutable state in F#. The benefit of this is that it now seems clear how to apply what we've learned to the original C# example.

## The programmer as decision maker

Monday, 18 March 2019 07:44:00 UTC

As a programmer, your job is to make technical decisions. Make some more.

When I speak at conferences, people often come and talk to me. (I welcome that, BTW.) Among all the conversations I've had over the years, there's a pattern to some of them. The attendee will start by telling me how inspired (s)he is by the talk I just gave, or something I've written. That's gratifying, and a good way to start a conversation, but is often followed up like this:

Attendee: "I just wish that we could do something like that in our organisation..."

Let's just say that here we're talking about test-driven development, or perhaps just unit testing. Nothing too controversial. I'd typically respond,

Me: "Why can't you?"

Attendee: "Our boss won't let us..."

That's unfortunate. If your boss has explicitly forbidden you to write and run unit tests, then there's not much you can do. Let me make this absolutely clear: I'm not going on record saying that you should actively disobey a direct order (unless it's unethical, that is). I do wonder, however:

Why is the boss even involved in that decision?

It seems to me that programmers often defer too much authority to their managers.

### A note on culture #

I'd like to preface the rest of this article with my own context. I've spent most of my programming career in Danish organisations. Even when I worked for Microsoft, I worked for Danish subsidiaries, with Danish managers.

The power distance in Denmark is (in)famously short. It's not unheard of for individual contributors to question their superiors' decisions; sometimes to their face, and sometimes even when other people witness this. When done respectfully (which it often is), this can be extremely efficient. Managers are as fallible as the rest of us, and often their subordinates know of details that could impact a decision that a manager is about to make. Immediately discussing such details can help ensure that good decisions are made, and bad decisions are cancelled.

This helps managers make better decisions, so enlightened managers welcome feedback.

### Technical decisions #

If your job is programmer, software developer, or similar, the value you add to the team is that you bring technical expertise. Maybe some of your colleagues are programmers as well, but together, you are the people with the technical expertise.

Even if the project manager or other superiors used to program, unless they're also writing code for the current code base, they only have general technical expertise, but not specific expertise related to the code base you're working with. The people with most technical expertise are you and your colleagues.

You are decision makers.

Whenever you interact with your code base, you make technical decisions.

In order to handle incoming HTTP requests to a `/reservations` resource, you may first decide to create a new file called `ReservationsController.cs`. You'd most likely also decide to open that file and start adding code to it.

Perhaps you add a method called `Post` that takes a `Reservation` argument. Perhaps you decide to inject an `IMaîtreD` dependency.

At various steps along the way, you may decide to compile the code.

Once you think that you've made enough changes to address your current work item, you may decide to run the program to see if it works. For a web-based piece of software, that typically involves starting up a browser and somehow interacting with the service. If your program is a web site, you may start at the front page, log in, click around, and fill in some forms. If your program is a REST API, you may interact with it via Fiddler or Postman (I prefer curl or Furl, but most people I've met still prefer something they can click on, it seems).

What often happens is that your changes don't work the first time around, so you'll have to troubleshoot. Perhaps you decide to use a debugger.

How many decisions are that?

I just described seven or eight types of the sort of decisions you make as a programmer. You make such decisions all the time. Do you ask your managers permission before you start a debugging session? Before you create a new file? Before you name a variable?

Of course you don't. You're the technical expert. There's no-one better equipped than you or your team members to make those decisions.

### Decide to add unit tests #

If you want to add unit tests, why don't you just decide to add them? If you want to apply test-driven development, why don't you just do so?

A unit test is one or more code files. You're already authorised to make decisions about adding files.

You can run a test suite instead of launching the software every time you want to interact with it. It's likely to be faster, even.

Why should you ask permission to do that?

### Decide to refactor #

Another complaint I hear is that people aren't allowed to refactor.

Why are you even asking permission to refactor?

Refactoring means reorganising the code without changing the behaviour of the system. Another word for that is editing the code. It's okay. You're already permitted to edit code. It's part of your job description.

I think I know what the underlying problem is, though...

### Make technical decisions in the small #

As an individual contributor, you're empowered to make small-scale technical decisions. These are decisions that are unlikely to impact schedules or allocation of programmers, including new hires. Big decisions probably should involve your manager.

I have an inkling of why people feel that they need permission to refactor. It's because the refactoring they have in mind is going to take weeks. Weeks in which nothing else can be done. Weeks where perhaps the code doesn't even compile.

Many years ago (but not as many as I'd like it to be), my colleague and I had what Eric Evans in DDD calls a breakthrough. We wanted to refactor towards deeper insight. What prompted the insight was a new feature that we had to add, and we'd been throwing design ideas back and forth for some time before the new insight arrived.

We could implement the new feature if we changed one of the core abstractions in our domain model, but it required substantial changes to the existing code base. We informed our manager of our new insight and our plan, estimating that it would take less than a week to make the changes and implement the new feature. Our manager agreed with the plan.

Two weeks later our code hadn't been in a compilable state for a week. Our manager pulled me away to tell me, quietly and equitably, that he was not happy with our lack of progress. I could only concur.

After more heroic work, we finally managed to complete the changes and implement the new feature. Nonetheless, blocking all other development for two-three weeks in order to make a change isn't acceptable.

That sort of change is a big decision because it impacts other team members, schedules, and perhaps overall business plans. Don't make those kinds of decisions without consulting with stakeholders.

This still leaves, I believe, lots of room for individual decision-making in the small. What I learned from the experience I just recounted was not to engage in big changes to a code base. Learn how to make multiple incremental changes instead. In case that's completely impossible, add the new model side-by-side with the old model, and incrementally change over. That's what I should have done those many years ago.

### Don't be sneaky #

When I give talks about the blessings of functional programming, I sometimes get into another type of discussion.

Attendee: It's so inspiring how beautiful and simple complex domain models become in F#. How can we do the same in C#?

Me: You can't. If you're already using C#, you should strongly consider F# if you wish to do functional programming. Since it's also a .NET language, you can gradually introduce F# code and mix the compiled code with your existing C# code.

Attendee: Yes... [already getting impatient with me] But we can't do that...

Me: Why not?

Attendee: Because our manager will not allow it.

Based on the suggestions I've already made here, you may expect me to say that that's another technical decision that you should make without asking permission. Like the previous example about blocking refactorings, however, this is another large-scale decision.

Your manager may be concerned that it'd be hard to find new employees if the code base is written in some niche language. I tend to disagree with that position, but I do understand why a manager would take that position. While I think it suboptimal to restrict an entire development organisation to a single language (whether it's C#, Java, C++, Ruby, etc.), I'll readily accept that language choice is a strategic decision.

If every programmer got to choose the programming language they prefer the most that day, you'd have code bases written in dozens of different languages. While you can train bright new hires to learn a new language or two, it's unrealistic that a new employee will be able to learn thirty different languages in a short while.

I find it reasonable that a manager has the final word on the choice of language, even when I often disagree with the decisions.

The outcome usually is that people are stuck with C# (or Java, or...). Hence the question: How can we do functional programming in C#?

I'll give the answer that I often give here on the blog: mu (unask the question). You can, in fact, translate functional concepts to C#, but the result is so non-idiomatic that only the syntax remains of C#:

```public static IReservationsInstruction<TResult> Select<T, TResult>(
this IReservationsInstruction<T> source,
Func<T, TResult> selector)
{
return source.Match<IReservationsInstruction<TResult>>(
isReservationInFuture: t =>
new IsReservationInFuture<TResult>(
new Tuple<Reservation, Func<bool, TResult>>(
t.Item1,
b => selector(t.Item2(b)))),
t.Item1,
d => selector(t.Item2(d)))),
create: t =>
new Create<TResult>(
new Tuple<Reservation, Func<int, TResult>>(
t.Item1,
r => selector(t.Item2(r)))));
}```

Keep in mind the manager's motivation for standardising on C#. It's often related to concerns about being able to hire new employees, or move employees from project to project.

If you write 'functional' C#, you'll end up with code like the above, or the following real-life example:

```return await sendRequest(
ApiMethodNames.InitRegistration,
new GSObject())
.Map(r => ValidateResponse.Validate(r)
.MapFailure(_ => ErrorResponse.RegisterErrorResponse()))
.Bind(r => r.RetrieveField("regToken"))
.BindAsync(token =>
sendRequest(
ApiMethodNames.RegisterAccount,
CreateRegisterRequest(
token))
.Map(ValidateResponse.Validate)
.Bind(response => getIdentity(response)
.ToResult(ErrorResponse.ExternalServiceResponseInvalid)))

(I'm indebted to Rune Ibsen for this example.)

A new hire can have ten years of C# experience and still have no chance in a code base like that. You'll first have to teach him or her functional programming. If you can do that, you might as well also teach a new language, like F#.

It's my experience that learning the syntax of a new language is easy, and usually doesn't take much time. The hard part is learning a new way to think.

Writing 'functional' C# makes it doubly hard on new team members. Not only do they have to learn a new paradigm (functional programming), but they have to learn it in a language unsuited for that paradigm.

That's why I think you should unask the question. If your manager doesn't want to allow F#, then writing 'functional' C# is just being sneaky. That'd be obeying the letter of the law while breaking the spirit of it. That is, in my opinion, immoral. Don't be sneaky.

### Summary #

As a professional programmer, your job is to be a technical expert. In normal circumstances (at least the ones I know from my own career), you have agency. In order to get anything done, you make small decisions all the time, such as editing code. That's not only okay, but expected of you.

Some decision, on the other hand, can have substantial ramifications. Choosing to write code in an unsanctioned language tends to fall on the side where a manager should be involved in the decision.

In between is a grey area.

I don't even consider adding unit tests to be in the grey area, but some refactorings may be.

"It's easier to ask forgiveness than it is to get permission."

Grace Hopper

To navigate grey areas you need a moral compass.

I'll let you be the final judge of what you can get away with, but I consider it both appropriate and ethical to make the decision to add unit tests, and to continually improve code bases. You shouldn't have to ask permission to do that.

Before all, I'd just like to thank all the content you share, they all make me think in a good way!

Now regarding to this post, while I tend to agree that a developer can take the decision to add (or not) unit tests by himself, there is no great value comming out of it, if that's not an approach of the whole development team, right? I believe we need the entire team on board to maximize the values of unit tests. There are changes we need to consider, from changes in the mindset of how you develop to actually running them on continuour integration pipelines. Doesn't all of that push simple decisions like "add unit test" from green area towards orange area?

2019-03-18 13:14 UTC

Francisco, thank you for writing. If you have a team of developers, then I agree that unit tests are going to be most valuable if the team decides to use them.

This is still something that you ought to be competent to decide as a self-organising team of developers. Do you need to ask a manager's permission?

I'm not trying to pretend that this is easy. I realise that it can be difficult.

I've heard about teams where other developers are hostile to the idea of unit testing. In that situation, I can offer no easy fixes. What a lone developer can try to do in that situation is to add and run unit tests locally, on his or her own machine. This will incur some friction, because other team members will be oblivious to the tests, so they'll change code that will cause those unit tests to break.

This might teach the lone developer to write tests so that they're as robust to trivial changes as possible. That's a valuable skill in any case. There's still going to be some overhead of maintaining the unit tests in a scenario like that, but if that overhead is smaller than the productivity gained, then in might still be worthwhile.

What might then happen could be that other developers who are on the fence see that the lone unit tester is more effective than they are. Perhaps they'll get curious about unit tests after all, once they can see the contours of advantages.

The next scenario, then, is a team with a few developers writing unit tests, and other who don't. At some number, you'll have achieved enough critical mass that, at least, you get to check in the unit tests together with the source code. Soon after, you may be able to institute a policy that while not everyone writes unit tests, it's not okay to break existing tests.

The next thing you can do, then, is to set up a test run as part of continuous integration and declare that a failing test run means that the build broke. You still have team members who don't write tests, but at least you get to do it, and the tests add value to the whole team.

Perhaps the sceptics will slowly start to write unit tests over time. Some die-hards probably never will.

You may be able to progress through such stages without asking a manager, but I do understand that there's much variation in organisation and team dynamics. If you can use any of the above sketches as inspiration, then that's great. If you (or other readers) have other success stories to tell, then please share them.

The point I was trying to make with this article is that programmers have agency. This isn't a licence to do whatever you please. You still have to navigate the dynamics of whatever organisation you're in. You may not, however, need to ask your manager about every little thing that you're competent to decide yourselves.

2019-03-19 7:57 UTC

Thank you A LOT for putting words on all these thought. You'll be my reference whenever I want to introduce unit test.

My usual example is "a surgeon doesn't need to ask to the manager if he can wash his hand. Whashing his hand is part of his job". (Not mine, but I can't remember where it comes from)

2019-03-19 20:15 UTC

## An example of state-based testing in Haskell

Monday, 11 March 2019 07:55:00 UTC

How do you do state-based testing when state is immutable? You use the State monad.

My experience is that functional programming is better aligned with unit testing because functional design is intrinsically testable. While I believe that functional programming is no panacea, it still seems to me that we can learn many valuable lessons about programming from it.

People often ask me about F# programming: How do I know that my F# code is functional?

I sometimes wonder that myself, about my own F# code. One can certainly choose to ignore such a question as irrelevant, and I sometimes do, as well. Still, in my experience, asking such questions can create learning opportunities.

The best answer that I've found is: Port the F# code to Haskell.

Haskell enforces referential transparency via its compiler. If Haskell code compiles, it's functional. In this article, then, I take the problem from the previous article and port it to Haskell.

### A function to connect two users #

In the previous article, you saw implementation and test coverage of a piece of software functionality to connect two users with each other. This was a simplification of the example running through my two Clean Coders videos, Church Visitor and Preserved in translation.

In contrast to the previous article, we'll start with the implementation of the System Under Test (SUT).

```post :: Monad m =>
(a -> m (Either UserLookupError User)) ->
(User -> m ()) ->
a ->
a ->
m (HttpResponse User)
post lookupUser updateUser userId otherUserId = do
userRes <- first (\case
InvalidId -> "Invalid user ID."
NotFound  -> "User not found.")
<\$> lookupUser userId
otherUserRes <- first (\case
InvalidId -> "Invalid ID for other user."
NotFound  -> "Other user not found.")
<\$> lookupUser otherUserId

connect <- runExceptT \$ do
user <- ExceptT \$ return userRes
otherUser <- ExceptT \$ return otherUserRes
lift \$ updateUser \$ addConnection user otherUser
return otherUser

return \$ either BadRequest OK connect
```

This is as direct a translation of the C# code as makes sense. If I'd only been implementing the desired functionality in Haskell, without having to port existing code, I'd designed the code differently.

This `post` function uses partial application as an analogy to dependency injection, but in order to enable potentially impure operations to take place, everything must happen inside of some monad. While the production code must ultimately run in the `IO` monad in order to interact with a database, tests can choose to run in another monad.

In the C# example, two dependencies are injected into the class that defines the `Post` method. In the above Haskell function, these two dependencies are instead passed as function arguments. Notice that both functions return values in the monad `m`.

The intent of the `lookupUser` argument is that it'll query a database with a user ID. It'll return the user if present, but it could also return a `UserLookupError`, which is a simple sum type:

`data UserLookupError = InvalidId | NotFound deriving (Show, Eq)`

If both users are found, the function connects the users and calls the `updateUser` function argument. The intent of this 'dependency' is that it updates the database. This is recognisably a Command, since its return type is `m ()` - unit (`()`) is equivalent to `void`.

### State-based testing #

How do you unit test such a function? How do you use Mocks and Stubs in Haskell? You don't; you don't have to. While the `post` method can be impure (when `m` is `IO`), it doesn't have to be. Functional design is intrinsically testable, but that proposition depends on purity. Thus, it's worth figuring out how to keep the `post` function pure in the context of unit testing.

While `IO` implies impurity, most common monads are pure. Which one should you choose? You could attempt to entirely 'erase' the monadic quality of the `post` function with the `Identity` monad, but if you do that, you can't verify whether or not `updateUser` was invoked.

While you could write an ad-hoc Mock using, for example, the `Writer` monad, it might be a better choice to investigate if something closer to state-based testing would be possible.

In an object-oriented context, state-based testing implies that you exercise the SUT, which mutates some state, and then you verify that the (mutated) state matches your expectations. You can't do that when you test a pure function, but you can examine the state of the function's return value. The `State` monad is an obvious choice, then.

### A Fake database #

Haskell's `State` monad is parametrised on the state type as well as the normal 'value type', so in order to be able to test the `post` function, you'll have to figure out what type of state to use. The interactions implied by the `post` function's `lookupUser` and `updateUser` arguments are those of database interactions. A Fake database seems an obvious choice.

For the purposes of testing the `post` function, an in-memory database implemented using a `Map` is appropriate:

`type DB = Map Integer User`

This is simply a dictionary keyed by `Integer` values and containing `User` values. You can implement compatible `lookupUser` and `updateUser` functions with `State DB` as the `Monad`. The `updateUser` function is the easiest one to implement:

```updateUser :: User -> State DB ()
updateUser user = modify \$ Map.insert (userId user) user```

This simply inserts the `user` into the database, using the `userId` as the key. The type of the function is compatible with the general requirement of `User -> m ()`, since here, `m` is `State DB`.

The `lookupUser` Fake implementation is a bit more involved:

```lookupUser :: String -> State DB (Either UserLookupError User)
lookupUser s = do
let maybeInt = readMaybe s :: Maybe Integer
let eitherInt = maybe (Left InvalidId) Right maybeInt
db <- get
return \$ eitherInt >>= maybe (Left NotFound) Right . flip Map.lookup db```

First, consider the type. The function takes a `String` value as an argument and returns a `State DB (Either UserLookupError User)`. The requirement is a function compatible with the type `a -> m (Either UserLookupError User)`. This works when `a` is `String` and `m` is, again, `State DB`.

The entire function is written in `do` notation, where the inferred `Monad` is, indeed, `State DB`. The first line attempts to parse the `String` into an `Integer`. Since the built-in `readMaybe` function returns a `Maybe Integer`, the next line uses the `maybe` function to handle the two possible cases, converting the `Nothing` case into the `Left InvalidId` value, and the `Just` case into a `Right` value.

It then uses the `State` module's `get` function to access the database `db`, and finally attempt a `lookup` against that `Map`. Again, `maybe` is used to convert the `Maybe` value returned by `Map.lookup` into an `Either` value.

### Happy path test case #

This is all you need in terms of Test Doubles. You now have test-specific `lookupUser` and `updateUser` functions that you can pass to the `post` function.

Like in the previous article, you can start by exercising the happy path where a user successfully connects with another user:

```testProperty "Users successfully connect" \$ \
user otherUser -> runStateTest \$ do

put \$ Map.fromList [toDBEntry user, toDBEntry otherUser]

actual <- post lookupUser updateUser (show \$ userId user) (show \$ userId otherUser)

db <- get
return \$
isOK actual &&
any (elem otherUser . connectedUsers) (Map.lookup (userId user) db)```

Here I'm inlining test cases as anonymous functions - this time expressing the tests as QuickCheck properties. I'll later return to the `runStateTest` helper function, but first I want to focus on the test body itself. It's written in `do` notation, and specifically, it runs in the `State DB` monad.

`user` and `otherUser` are input arguments to the property. These are both `User` values, since the test also defines `Arbitrary` instances for that type (not shown in this article; see the source code repository for details).

The first step in the test is to 'save' both users in the Fake database. This is easily done by converting each `User` value to a database entry:

```toDBEntry :: User -> (Integer, User)
toDBEntry = userId &&& id```

Recall that the Fake database is nothing but an alias over `Map Integer User`, so the only operation required to turn a `User` into a database entry is to extract the key.

The next step in the test is to exercise the SUT, passing the test-specific `lookupUser` and `updateUser` Test Doubles to the `post` function, together with the user IDs converted to `String` values.

In the assert phase of the test, it first extracts the current state of the database, using the `State` library's built-in `get` function. It then verifies that `actual` represents a `200 OK` value, and that the `user` entry in the database now contains `otherUser` as a connected user.

### Missing user test case #

While there's one happy-path test case, there's four other test cases left. One of these is when the first user doesn't exist:

```testProperty "Users don't connect when user doesn't exist" \$ \
(Positive i) otherUser -> runStateTest \$ do

let db = Map.fromList [toDBEntry otherUser]
put db
let uniqueUserId = show \$ userId otherUser + i

actual <- post lookupUser updateUser uniqueUserId (show \$ userId otherUser)

assertPostFailure db actual```

What ought to trigger this test case is that the 'first' user doesn't exist, even if the `otherUser` does exist. For this reason, the test inserts the `otherUser` into the Fake database.

Since the test is a QuickCheck property, `i` could be any positive `Integer` value - including the `userId` of `otherUser`. In order to properly exercise the test case, however, you'll need to call the `post` function with a `uniqueUserId` - thas it: an ID which is guaranteed to not be equal to the `userId` of `otherUser`. There's several options for achieving this guarantee (including, as you'll see soon, the `==>` operator), but a simple way is to add a non-zero number to the number you need to avoid.

You then exercise the `post` function and, as a verification, call a reusable `assertPostFailure` function:

```assertPostFailure :: (Eq s, Monad m) => s -> HttpResponse a -> StateT s m Bool
assertPostFailure stateBefore resp = do
stateAfter <- get
let stateDidNotChange = stateBefore == stateAfter
return \$ stateDidNotChange && isBadRequest resp```

This function verifies that the state of the database didn't change, and that the response value represents a `400 Bad Request` HTTP response. This verification doesn't actually verify that the error message associated with the `BadRequest` case is the expected message, like in the previous article. This would, however, involve a fairly trivial change to the code.

### Missing other user test case #

Similar to the above test case, users will also fail to connect if the 'other user' doesn't exist. The property is almost identical:

```testProperty "Users don't connect when other user doesn't exist" \$ \
(Positive i) user -> runStateTest \$ do

let db = Map.fromList [toDBEntry user]
put db
let uniqueOtherUserId = show \$ userId user + i

actual <- post lookupUser updateUser (show \$ userId user) uniqueOtherUserId

assertPostFailure db actual```

Since this test body is so similar to the previous test, I'm not going to give you a detailed walkthrough. I did, however, promise to describe the `runStateTest` helper function:

```runStateTest :: State (Map k a) b -> b
runStateTest = flip evalState Map.empty```

Since this is a one-liner, you could also write all the tests by simply in-lining that little expression, but I thought that it made the tests more readable to give this function an explicit name.

It takes any `State (Map k a) b` and runs it with an empty map. Thus, all `State`-valued functions, like the tests, must explicitly put data into the state. This is also what the tests do.

Notice that all the tests return `State` values. For example, the `assertPostFailure` function returns `StateT s m Bool`, of which `State s Bool` is an alias. This fits `State (Map k a) b` when `s` is `Map k a`, which again is aliased to `DB`. Reducing all of this, the tests are simply functions that return `Bool`.

### Invalid user ID test cases #

Finally, you can also cover the two test cases where one of the user IDs is invalid:

```testProperty "Users don't connect when user Id is invalid" \$ \
s otherUser -> isIdInvalid s ==> runStateTest \$ do

let db = Map.fromList [toDBEntry otherUser]
put db

actual <- post lookupUser updateUser s (show \$ userId otherUser)

assertPostFailure db actual

,
testProperty "Users don't connect when other user Id is invalid" \$ \
s user -> isIdInvalid s ==> runStateTest \$ do

let db = Map.fromList [toDBEntry user]
put db

actual <- post lookupUser updateUser (show \$ userId user) s

assertPostFailure db actual```

Both of these properties take a `String` value `s` as input. When QuickCheck generates a `String`, that could be any `String` value. Both tests require that the value is an invalid user ID. Specifically, it mustn't be possible to parse the string into an `Integer`. If you don't constrain QuickCheck, it'll generate various strings, including e.g. `"8"` and other strings that can be parsed as numbers.

In the above `"Users don't connect when user doesn't exist"` test, you saw how one way to explicitly model constraints on data is to project a seed value in such a way that the constraint always holds. Another way is to use QuickCheck's built-in `==>` operator to filter out undesired values. In this example, both tests employ the `isIdInvalid` function:

```isIdInvalid :: String -> Bool
isIdInvalid s =
let userInt = readMaybe s :: Maybe Integer
in isNothing userInt```

Using `isIdInvalid` with the `==>` operator guarantees that `s` is an invalid ID.

### Summary #

While state-based testing may, at first, sound incompatible with strictly functional programming, it's not only possible with the State monad, but even, with good language support, easily done.

The tests shown in this article aren't concerned with the interactions between the SUT and its dependencies. Instead, they compare the initial state with the state after exercising the SUT. Comparing values, even complex data structures such as maps, tends to be trivial in functional programming. Immutable values typically have built-in structural equality (in Haskell signified by the automatic `Eq` type class), which makes comparing them trivial.

Now that we know that state-based testing is possible even with Haskell's enforced purity, it should be clear that we can repeat the feat in F#.

## Code quality isn't software quality

Monday, 04 March 2019 07:38:00 UTC

You'd think that it's evident that code quality and software quality are two different things. Yet, I often see or hear arguments about one or the other that indicates to me that some people don't make that distinction. I wonder why; I do.

### Software quality #

There's a school of thought leaders who advocate that, ultimately, we write code to solve problems, or to improve life, for people. I have nothing against that line of reasoning; it's just not one that I pursue much. Why should I use my energy on this message when someone like Dan North does it so much better than I could?

Dan North is far from the only person making the point that our employers, or clients, or end-users don't care about the code; he is, in my opinion, one of the best communicators in that field. It makes sense that, with that perspective on software development, you'd invent something like behaviour-driven development.

The evaluation criterion used in this discourse is one of utility. Does the software serve a purpose? Does it do it well?

In that light, quality software is software that serves its purpose beyond expectation. It rarely, if ever, crashes. It's easy to use. It's sufficiently responsive. It's pretty. It works both on-line and off-line. Attributes like that are externally observable qualities.

You can write quality software in many different languages, using various styles. When you evaluate the externally observable qualities of software, the code is invisible. It's not part of the evaluation.

It seems to me that some people try to make an erroneous conclusion from this premise. They'd say that since no employer, client, or end user evaluates the software based on the code that produced it, then no one cares about the code.

### Code quality #

It's easy to refute that argument. All you have to do is to come up with a counter-example. You just have to find one person who cares about the code. That's easy.

Perhaps you react negatively to that assertion. Perhaps you say: "No! I'm not one of those effete aesthetes who only program in Plankalkül." Fine. Maybe you're not the type who likes to polish the code; maybe you're the practical, down-to-earth type who just likes to get stuff done, so that your employer/client/end-user is happy.

Even so, I think that you still care about the code. Have you ever looked with bewilderment at a piece of code and thought: "Who the hell wrote this piece of shit!?" How many WTFs/m is your code?

I think every programmer cares about their code bases; if not in an active manner, then at least in a passive way. Bad code can seriously impede progress. I've seen more than one organisation effectively go out of business because of bad legacy code.

Code quality is when you care about the readability and malleability of the code. It's when you care about the code's ability to sustain the business, not only today, but also in the future.

### Sustainable code #

I often get the impression that some people look at code quality and software quality as a (false) dichotomy.

Such arguments often seem to imply that you can't have one without sacrificing the other. You must choose.

The reality is, of course, that you can do both.

At the intersection between software and code quality the code sustains the business both now, and in the future.

Yes, you should write code such that it produces software that provides value here and now, but you should also do your best to enable it to provide value in the future. This is sustainable code. It's code that can sustain the organisation during its lifetime.

### No gold-plating #

To be clear: this is not a call for gold plating or speculative generality. You probably can't predict the future needs of the stake-holders.

Quality code doesn't have to be able to perfectly address all future requirements. In order to be sustainable, though, it should be easy to modify in the future, or perhaps just easy to throw away and rewrite. I think a good start is to write humane code; code that fits in your brain.

At least, do your best to avoid writing legacy code.

### Summary #

Software quality and code quality can co-exist. You can write quality code that compiles to quality software, but one doesn't imply the other. These are two independent quality dimensions.

Page 29 of 75

"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!