ploeh blog

Full deck

Monday, 08 October 2018 06:17:00 UTC

An introduction to applicative functors in Haskell, with a translation to F#.

This article is an instalment in an article series about applicative functors. While (non-applicative) functors can be translated to an object-oriented language like C# in a straightforward manner, applicative functors are more entrenched in functional languages like Haskell. This article introduces the concept with a motivating example in Haskell, and also shows a translation to F#. In the next article, you'll also see how to implement an applicative functor in C#.

Deck of cards in Haskell #

Imagine that you want to model a card game. In order to do so, you start by defining data types for suits, faces, and cards:

data Suit =
  Diamonds | Hearts | Clubs | Spades deriving (Show, Eq, Enum, Bounded)
 
data Face =
    Two  | Three | Four | Five | Six | Seven | Eight | Nine | Ten
  | Jack | Queen | King | Ace
  deriving (Show, Eq, Enum, Bounded)
 
data Card = Card { face :: Face, suit :: Suit } deriving (Show, Eq)

Since both Suit and Face are instances of the Enum and Bounded typeclasses, you can easily enumerate them:

allFaces :: [Face]
allFaces = [minBound .. maxBound]
 
allSuits :: [Suit]
allSuits = [minBound .. maxBound]

For example, allSuits enumerates all four Suit values:

λ> allSuits
[Diamonds,Hearts,Clubs,Spades]

Notice, by the way, how the code for allFaces and allSuits is identical. The behaviour, however, is different, because the types are different.

While you can enumerate suits and faces, how do you create a full deck of cards?

A full deck of cards should contain one card of every possible combination of suit and face. Here's one way to do it, taking advantage of lists being applicative functors:

fullDeck :: [Card]
fullDeck = pure Card <*> allFaces <*> allSuits

This will give you all the possible cards. Here are the first six:

λ> forM_ (take 6 fullDeck) print
Card {face = Two, suit = Diamonds}
Card {face = Two, suit = Hearts}
Card {face = Two, suit = Clubs}
Card {face = Two, suit = Spades}
Card {face = Three, suit = Diamonds}
Card {face = Three, suit = Hearts}

How does it work? Let's break it down, starting from left:

λ> :type Card
Card :: Face -> Suit -> Card
λ> :type pure Card
pure Card :: Applicative f => f (Face -> Suit -> Card)
λ> :type pure Card <*> allFaces
pure Card <*> allFaces :: [Suit -> Card]
λ> :type pure Card <*> allFaces <*> allSuits
pure Card <*> allFaces <*> allSuits :: [Card]

From the top, Card is a function that takes a Face value and a Suit value and returns a Card value. Object-oriented programmers can think of it as a constructor.

Next, pure Card is the Card function, elevated to an applicative functor. At this point, the compiler hasn't decided which particular applicative functor it is; it could be any applicative functor. Specifically, it turns out to be the list type ([]), which means that pure Card has the type [Face -> Suit -> Card]. That is: it's a list of functions, but a list of only a single function. At this point, however, this is still premature. The type doesn't materialise until we apply the second expression.

The type of allFaces is clearly [Face]. Since the <*> operator has the type Applicative f => f (a -> b) -> f a -> f b, the expression on the left must be the same functor as the expression on the right. The list type ([]) is an applicative functor, and because allFaces is a list, then pure Card must also be a list, in the expression pure Card <*> allFaces. In other words, in the definition of <*>, you can substitute f with [], and a with Face. The interim result is [Face -> b] -> [Face] -> [b]. What is b, then?

You already know that pure Card has the type [Face -> Suit -> Card], so b must be Suit -> Card. That's the reason that pure Card <*> allFaces has the type [Suit -> Card]. It's a list of functions. This means that you can use <*> a second time, this time with allSuits, which has the type [Suit].

Using the same line of reasoning as before, you can substitute Suit for a in the type of <*>, and you get [Suit -> b] -> [Suit] -> [b]. What is b now? From the previous step, you know that the expression on the left has the type [Suit -> Card], so b must be Card. That's why the entire expression has the type [Card].

Deck of cards in F# #

You can translate the above Haskell code to F#. The first step is to make F# lists applicative. F# also supports custom operators, so you can add a function called <*>:

// ('a -> 'b) list -> 'a list -> 'b list
let (<*>) fs l = fs |> List.collect (fun f -> l |> List.map f)

This implementation iterates over all the functions in fs; for each function, it maps the list l with that function. Had you done that with a normal List.map, this would have returned a list of lists, but by using List.collect, you flatten the list.

It's worth noting that this isn't the only way you could have implemented <*>, but this is the implementation that behaves like the Haskell function. An alternative implementation could have been this:

// ('a -> 'b) list -> 'a list -> 'b list
let (<*>) fs = List.collect (fun x -> fs |> List.map (fun f -> f x))

This variation has the same type as the first example, and still returns all combinations, but the order is different. In the following of this article, as well as in subsequent articles, I'll use the first version.

Here's the playing cards example translated to F#:

type Suit = Diamonds | Hearts | Clubs | Spades
 
type Face =
    |  Two | Three | Four | Five | Six | Seven | Eight | Nine | Ten
    | Jack | Queen | King | Ace
 
type Card = { Face: Face; Suit : Suit }
 
// Face list
let allFaces = [
    Two; Three; Four; Five; Six; Seven; Eight; Nine; Ten;
    Jack; Queen; King; Ace]
 
// Suit list
let allSuits = [Diamonds; Hearts; Clubs; Spades]
 
// Card list
let fullDeck = [fun f s -> { Face = f; Suit = s }] <*> allFaces <*> allSuits

The F# code is slightly more verbose than the Haskell code, because you have to repeat all the cases for Suit and Face. You can't enumerate them automatically, like you can in Haskell.

It didn't make much sense to me to attempt to define a pure function, so instead I simply inserted a single lambda expression in a list, using the normal square-bracket syntax. F# doesn't have constructors for record types, so you have to pass a lambda expression, whereas in Haskell, you could simply use the Card function.

The result is the same, though:

> fullDeck |> List.take 6 |> List.iter (printfn "%A");;
{Face = Two; Suit = Diamonds;}
{Face = Two; Suit = Hearts;}
{Face = Two; Suit = Clubs;}
{Face = Two; Suit = Spades;}
{Face = Three; Suit = Diamonds;}
{Face = Three; Suit = Hearts;}

While the mechanics of applicative functors translate well to F#, it leaves you with at least one problem. If you add the above operator <*>, you've now 'used up' that operator for lists. While you can define an operator of the same name for e.g. option, you'd have to put them in separate modules or namespaces in order to prevent them from colliding. This also means that you can't easily use them together.

For that reason, I wouldn't consider this the most idiomatic way to create a full deck of cards in F#. Normally, I'd do this instead:

// Card list
let fullDeck = [
    for suit in allSuits do
    for face in allFaces do
    yield { Face = face; Suit = suit } ]

This alternative syntax takes advantage of F#'s 'extended list comprehension' syntax. FWIW, you could have done something similar in Haskell:

fullDeck :: [Card]
fullDeck = [Card f s | f <- allFaces, s <- allSuits]

List comprehension, however, is (as the name implies) specific to lists, whereas an applicative functor is a more general concept.

Summary #

This article introduced you to lists as an applicative functor, using the motivating example of having to populate a full deck of cards with all possible combinations of suits and faces.

The next article in the series shows another list example. The F# and Haskell code will be similar to the code in the present article, but the next article will also include a translation to C#.

Next: An applicative password list.

Applicative functors

Monday, 01 October 2018 06:34:00 UTC

An applicative functor is a useful abstraction. While typically associated with functional programming, applicative functors can be conjured into existence in C# as well.

This article series is part of a larger series of articles about functors, applicatives, and other mappable containers.

In a former article series, you learned about functors, and how they also exist in object-oriented design. Perhaps the utility of this still eludes you, although, if you've ever had experience with LINQ in C#, you should realise that the abstraction is invaluable. Functors are abundant; applicative functors not quite so much. On the other hand, applicative functors enable you to do more.

I find it helpful to think of applicative functors as an abstraction that enable you to express combinations of things.

In the functor article series, I mostly focused on the mechanics of implementation. In this article series, I think that you'll find it helpful to slightly change the perspective. In these articles, I'll show you various motivating examples of how applicative functors are useful.

You should consider reading one or more of these articles before continuing the present article.

A Haskell perspective #

A normal functor maps objects in an 'elevated world' (like C#'s IEnumerable<T> or IObservable<T>) using a function in the 'normal world'. As a variation, an applicative functor maps objects in an 'elevated world' using functions from the same 'elevated world'.

In Haskell, an applicative functor is defined like this:

class Functor f => Applicative f where
  pure  :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

This is a simplification; there's more to the Applicative typeclass than this, but this should highlight the essence. What it says is that an applicative functor must already be a Functor. It could be any sort of Functor, like [] (linked list), Maybe, Either, and so on. Since Functor is an abstraction, it's called f.

The definition furthermore says that in order for a functor to be applicative, two functions must exist: pure and <*> ('apply').

pure is easy to understand. It simply 'elevates' a 'normal' value to a functor value. For example, you can elevate the number 42 to a list value by putting it in a list with a single element: [42]. Or you can elevate "foo" to Maybe by containing it in the Just case: Just "foo". That is, literally, what pure does for [] (list) and Maybe.

The <*> operator applies an 'elevated' function to an 'elevated' value. When f is [], this literally means that you have a list of functions that you have to apply to a list of values. Perhaps you can already see what I meant by combinations of things.

This sounds abstract, but follow the above list of links in order to see several examples.

An F# perspective #

Applicative functors aren't explicitly modelled in F#, but they're easy enough to add if you need them. F# doesn't have typeclasses, so implementing applicative functors tend to be more on a case-by-case basis.

If you need list to be applicative, pure should have the type 'a -> 'a list, and <*> should have the type ('a -> 'b) list -> 'a list -> 'b list. At this point, you already run into the problem that pure is a reserved keyword in F#, so you'll have to find another name, or simply ignore that function.

If you need option to be applicative, <*> should have the type ('a -> 'b) option -> 'a option -> 'b option. Now you run into your second problem, because which function is <*>? The one for list, or the one for option? It can't be both, so you'll have to resort to all sorts of hygiene to prevent these two versions of the same operator from clashing. This somewhat limits its usefulness.

Again, refer to the above list of linked articles for concrete examples.

A C# perspective #

Applicative functors push the limits of what you can express in C#, but the equivalent to <*> would be a method with this signature:

public static Functor<TResult> Apply<T, TResult>(
    this Functor<Func<T, TResult>> selector,
    Functor<T> source)

Here, the class Functor<T> is a place-holder for a proper functor class. A concrete example could be for IEnumerable<T>:

public static IEnumerable<TResult> Apply<T, TResult>(
    this IEnumerable<Func<T, TResult>> selectors,
    IEnumerable<T> source)

As you can see, here you somehow have to figure out how to combine a sequence of functions with a sequence of values.

In some of the examples in the above list of linked articles, you'll see how this will stretch the capability of C#.

Summary #

This article only attempts to provide an overview of applicative functors, while examples are given in linked articles. I find it helpful to think of applicative functors as an abstraction that enables you to model arbitrary combinations of objects. This is a core feature in Haskell, occasionally useful in F#, and somewhat alien to C#.

Next: Full deck.

Asynchronous functors

Monday, 24 September 2018 03:37:00 UTC

Asynchronous computations form functors. An article for object-oriented programmers.

This article is an instalment in an article series about functors. The previous article covered the Lazy functor. In this article, you'll learn about closely related functors: .NET Tasks and F# asynchronous workflows.

A word of warning is in order. .NET Tasks aren't referentially transparent, whereas F# asynchronous computations are. You could argue, then, that .NET Tasks aren't proper functors, but you mostly observe the difference when you perform impure operations. As a general observation, when impure operations are allowed, the conclusions of this overall article series are precarious. We can't radically change how the .NET languages work, so we'll have to soldier on, pretending that impure operations are delegated to other parts of our system. Under this undue assumption, we can pretend that Task<T> forms a functor.

Task functor #

You can write an idiomatic Select extension method for Task<T> like this:

public async static Task<TResult> Select<T, TResult>(
    this Task<T> source,
    Func<T, TResult> selector)
{
    var x = await source;
    return selector(x);
}

With this extension method in scope, you can compose asynchronous computations like this:

Task<int> x = // ...
Task<string> y = x.Select(i => i.ToString());

Or, if you prefer query syntax:

Task<int> x = // ...
Task<string> y = from i in x select i.ToString();

In both cases, you start with a Task<int> which you map into a Task<string>. Perhaps you've noticed that these two examples closely resemble the equivalent Lazy functor examples. The resemblance isn't coincidental. The same abstraction is in use in both places. This is the functor abstraction. That's what this article series is all about, after all.

The difference between the Task functor and the Lazy functor is that lazy computations don't run until forced. Tasks, on the other hand, typically start running in the background when created. Thus, when you finally await the value, you may actually not have to wait for it. This does, however, depend on how you created the initial task.

First functor law for Task #

The Select method obeys the first functor law. As usual in this article series, actually proving that this is the case belongs to the realm of computer science. Instead of proving that the law holds, you can use property-based testing to demonstrate that it does. The following example shows a single property written with FsCheck 2.11.0 and xUnit.net 2.4.0.

[Property(QuietOnSuccess = true)]
public void TaskObeysFirstFunctorLaw(int i)
{
    var  left = Task.FromResult(i);
    var right = Task.FromResult(i).Select(x => x);
 
    Assert.Equal(left.Result, right.Result);
}

This property accesses the Result property of the Tasks involved. This is typically not the preferred way to pull the value of Tasks, but I decided to do it like this since FsCheck 2.4.0 doesn't support asynchronous properties.

Even though you may feel that a property-based test gives you more confidence than a few hard-coded examples, such a test is nothing but a demonstration of the first functor law. It's no proof, and it only demonstrates that the law holds for Task<int>, not that it holds for Task<string>, Task<Product>, etcetera.

Second functor law for Task #

As is the case with the first functor law, you can also use a property to demonstrate that the second functor law holds:

[Property(QuietOnSuccess = true)]
public void TaskObeysSecondFunctorLaw(
    Func<string, byte> f,
    Func<int, string> g,
    int i)
{
    var  left = Task.FromResult(i).Select(g).Select(f);
    var right = Task.FromResult(i).Select(x => f(g(x)));
 
    Assert.Equal(left.Result, right.Result);
}

Again the same admonitions apply: that property is no proof. It does show, however, that given two functions, f and g, it doesn't matter if you map a Task in one or two steps. The output is the same in both cases.

Async functor #

F# had asynchronous workflows long before C#, so it uses a slightly different model, supported by separate types. Instead of Task<T>, F# relies on a generic type called Async<'T>. It's still a functor, since you can trivially implement a map function for it:

module Async =
    // 'a -> Async<'a>
    let fromValue x = async { return x }
    // ('a -> 'b) -> Async<'a> -> Async<'b>
    let map f x = async {
        let! x' = x
        return f x' }

The map function uses the async computation expression to access the value being computed asynchronously. You can use a let! binding to await the value computed in x, and then use the function f to translate that value. The return keyword turns the result into a new Async value.

With the map function, you can write code like this:

let (x : Async<int>) = // ...
let (y : Async<string>) = x |> Async.map string

Once you've composed an asynchronous workflow to your liking, you can run it to compute the value in which you're interested:

> Async.RunSynchronously y;;
val it : string = "42"

This is the main difference between F# asynchronous workflows and .NET Tasks. You have to explicitly run an asynchronous workflows, whereas Tasks are usually, implicitly, already running in the background.

First functor law for Async #

The Async.map function obeys the first functor law. Like above, you can use FsCheck to demonstrate how that works:

[<Property(QuietOnSuccess = true)>]
let ``Async obeys first functor law`` (i : int) =
    let  left = Async.fromValue i
    let right = Async.fromValue i |> Async.map id
 
    Async.RunSynchronously left =! Async.RunSynchronously right

In addition to FsCheck and xUnit.net, this property also uses Unquote 4.0.0 for the assertion. The =! operator is an assertion that the left-hand side must equal the right-hand side. If it doesn't, then the operator throws a descriptive exception.

Second functor law for Async #

As is the case with the first functor law, you can also use a property to demonstrate that the second functor law holds:

[<Property(QuietOnSuccess = true)>]
let ``Async obeys second functor law`` (f : string -> byte) g (i : int) =
    let  left = Async.fromValue i |> Async.map g |> Async.map f
    let right = Async.fromValue i |> Async.map (g >> f)
 
    Async.RunSynchronously left =! Async.RunSynchronously right

As usual, the second functor law states that given two arbitrary (but pure) functions f and g, it doesn't matter if you map an asynchronous workflow in one or two steps. There could be a difference in performance, but the functor laws don't concern themselves with the time dimension.

Both of the above properties use the Async.fromValue helper function to create Async values. Perhaps you consider it cheating that it immediately produces a value, but you can add a delay if you want to pretend that actual asynchronous computation takes place. It'll make the tests run slower, but otherwise will not affect the outcome.

Task and Async isomorphism #

The reason I've covered both Task<T> and Async<'a> in the same article is that they're equivalent. You can translate a Task to an asynchronous workflow, or the other way around.

Equivalence of Task and Async.

There's performance implications of going back and forth between Task<T> and Async<'a>, but there's no loss of information. You can, therefore, consider these to representations of asynchronous computations isomorphic.

Summary #

Whether you do asynchronous programming with Task<T> or Async<'a>, asynchronous computations form functors. This enables you to piecemeal compose asynchronous workflows.

Next: The Const functor.

Comments

Tyson Williams #

As a general observation, when impure operations are allowed, the conclusions of this overall article series are precarious. We can't radically change how the .NET languages work, so we'll have to soldier on, pretending that impure operations are delegated to other parts of our system. Under this undue assumption, we can pretend that Task<T> forms a functor.

I am with you. I also want to be pragmatic here and treat Task<T> as a functor. It is definitely better than the alternative.

At the same time, I want to know what prevents Task<T> from actually being a functor so that I can compensate when needed.

A word of warning is in order. .NET Tasks aren't referentially transparent, whereas F# asynchronous computations are. You could argue, then, that .NET Tasks aren't proper functors, but you mostly observe the difference when you perform impure operations.

Can you elaborate about this? Why is Task<T> not referentially transparent? Why is the situation worse with impure operations? What issue remains when restricting to pure functions? Is this related to how the stack trace is closely related to how many times await appears in the code?

2020-07-16 13:23 UTC

Mark Seemann #

Tyson, thank you for writing. That .NET tasks aren't referentially transparent is a result of memoisation, as Diogo Castro pointed out to me.

The coming article about Task asynchronous programming as an IO surrogate will also discuss this topic.

2020-07-23 7:50 UTC

Tyson Williams #

Ha! So funny. It is the same caching behavior that I pointed out in this comment. I wish I had known about Diogo's comment. I could have just linked there.

You could argue, then, that .NET Tasks aren't proper functors, but you mostly observe the difference when you perform impure operations.

I am still not completely following though. Are you saying that this caching behavior prevents .NET Tasks from satisfying one of the functor laws? If so, is it the identity law or the composition law? If it is the composition law, what are the two functions that demonstate the failure? Even when allowing impure functions, I can't think of an example. However, I will keep thinking about this and comment again if I find an example.

2020-07-23 13:33 UTC

Mark Seemann #

Tyson, I am, in general trying to avoid claiming that any of this applies in the presence of impurity. Take something as trivial as Select(i => new Random().Next(i)), for Task or any other 'functor'. It's not even going to evaluate to the same outcome between two runs.

2020-07-31 10:54 UTC

Tyson Williams #

I think I understand your hesitation now regarding impurity. I also think I can argue that the existence of impure functions in C# does not prevent Task<T> from being a functor.

Before I give that argument and we consider if it works, I want to make sure there isn't a simpler issue only involving pure functions the prevents Task<T> from being a functor.

You could argue, then, that .NET Tasks aren't proper functors, but you mostly observe the difference when you perform impure operations.

Your use of "mostly" makes me think that you believe there is a counterexample only involving pure functions that shows Task<T> is not a functor. Do I correctly understanding what you meant by that sentence? If so, can you share that counterexample? If not, can you elaborate so that I can better understand what you meant.

2020-08-02 18:26 UTC

Mark Seemann #

Tyson, I wrote this article two years ago. I can't recall if I had anything specific in mind, or if it was just a throwaway phrase. Even if I had a specific counter-example in mind, I might have been wrong, just like the consensus is about Fermat's last theorem.

If you can produce an example, however, you'd prove me right 😀

2020-08-06 9:07 UTC

Typing is not a programming bottleneck

Monday, 17 September 2018 08:16:00 UTC

Some developers seem to think that typing is a major bottleneck while programming. It's not.

I sometimes give programming advice to people. They approach me with a software design problem, and, to the best of my ability, I suggest a remedy. Despite my best intentions, my suggestions sometimes meet resistance. One common reaction is that my suggestion isn't idiomatic, but recently, another type of criticism seems to be on the rise.

The code that I suggest is too verbose. It involves too much typing.

I'll use this article to reflect on that criticism.

The purpose of code #

Before we get into the details of the issue, I'd like to start with the big picture. What's the purpose of code?

I've discussed this extensively in my Clean Coders video on Humane Code. In short, the purpose of source code is to communicate the workings of a piece of software to the next programmer who comes along. This could easily include your future self.

Perhaps you disagree with that proposition. Perhaps you think that the purpose of source code is to produce working software. It's that, too, but that's not its only purpose. If that was the only purpose, you might as well write the software in machine code.

Why do we have high-level programming languages like C#, Java, JavaScript, Ruby, Python, F#, Visual Basic, Haskell, heck - even C++?

As far as I can tell, it's because programmers are all human, and humans have limited cognitive capacity. We can't keep track of hundreds, or thousands, of global variables, or the states of dozens of complex resources. We need tools that help us structure and understand complex systems so that they're broken down into (more) manageable chunks. High-level languages help us do that.

The purpose of source code is to be understood. You read source code much more that you write. I'm not aware of any scientific studies, but I think most programmers will agree that over the lifetime of a code base, any line of code will be read orders of magnitude more often that it's edited.

Typing speed #

How many lines of code do you produce during a productive working day?

To be honest, I can't even answer that question myself. I've never measured it, since I consider it to be irrelevant. The Mythical Man-Month gives the number as 10, but let's be generous and pretend it's ten times that. This clearly depends on lots of factors, such as the language in which you're writing, the state of the code base, and so on. You'd tend to write more lines in a pristine greenfield code base, whereas you'll write fewer lines of code in a complicated legacy code base.

How many characters is a line of code? Let's say it's 80 characters, because that's the maximum width code ought to have. I realise that many people write wider lines, but on the other hand, most developers (fortunately) use indentation, so as a counter-weight, code often has some blank space to the left as well. This is all back-of-the-envelope calculations anyway.

When I worked in a Microsoft product group, we typically planned that a productive, 'full' day of coding was five hours. Even on productive days, the rest was used in meetings, administration, breaks, and so on.

If you write code for five hours, and produce 100 lines of code, at 80 characters per line, that's 8,000 characters. Your IDE is likely to help you with statement completion and such, but for the sake of argument, let's pretend that you have to type it all in.

8,000 characters in five hours is 1,600 characters per hour, or 27 characters per minute.

I'm not a particularly fast typist, but I can type ten times faster than that.

Typing isn't a bottleneck.

Is more code worse? #

I tend to get drawn into these discussions from time to time, but good programming has little to do with how fast you can produce lines of code.

To be clear, I entirely accept that statement completion, refactoring support, and such are, in general, benign features. While I spend most of my programming time thinking and reading, I also tend to write code in bursts. The average count of lines per hour may not be great, but that's because averages smooth out the hills and the valleys of my activity.

Still, increasingly frequent objection to some of my suggestions is that what I suggest implies 'too much' code. Recently, for example, I had to defend the merits of the Fluent Builder pattern that I suggest in my DI-Friendly Library article.

As another example, consider two alternatives for modelling a restaurant reservation. First, here's a terse option:

public class Reservation
{
    public DateTimeOffset Date { get; set; }
    public string Email { get; set; }
    public string Name { get; set; }
    public int Quantity { get; set; }
    public bool IsAccepted { get; set; }
}

Here's a longer alternative:

public sealed class Reservation
{
    public Reservation(
        DateTimeOffset date,
        string name,
        string email,
        int quantity) :
        this(date, name, email, quantity, false)
    {
    }
 
    private Reservation(
        DateTimeOffset date,
        string name,
        string email,
        int quantity,
        bool isAccepted)
    {
        Date = date;
        Name = name;
        Email = email;
        Quantity = quantity;
        IsAccepted = isAccepted;
    }
 
    public DateTimeOffset Date { get; }
    public string Name { get; }
    public string Email { get; }
    public int Quantity { get; }
    public bool IsAccepted { get; }
 
    public Reservation WithDate(DateTimeOffset newDate)
    {
        return new Reservation(newDate, Name, Email, Quantity, IsAccepted);
    }
 
    public Reservation WithName(string newName)
    {
        return new Reservation(Date, newName, Email, Quantity, IsAccepted);
    }
 
    public Reservation WithEmail(string newEmail)
    {
        return new Reservation(Date, Name, newEmail, Quantity, IsAccepted);
    }
 
    public Reservation WithQuantity(int newQuantity)
    {
        return new Reservation(Date, Name, Email, newQuantity, IsAccepted);
    }
 
    public Reservation Accept()
    {
        return new Reservation(Date, Name, Email, Quantity, true);
    }
 
    public override bool Equals(object obj)
    {
        if (!(obj is Reservation other))
            return false;
 
        return Equals(Date, other.Date)
            && Equals(Name, other.Name)
            && Equals(Email, other.Email)
            && Equals(Quantity, other.Quantity)
            && Equals(IsAccepted, other.IsAccepted);
    }
 
    public override int GetHashCode()
    {
        return
            Date.GetHashCode() ^
            Name.GetHashCode() ^
            Email.GetHashCode() ^
            Quantity.GetHashCode() ^
            IsAccepted.GetHashCode();
    }
}

Which alternative is better? The short version is eight lines of code, including the curly brackets. The longer version is 78 lines of code. That's ten times as much.

I prefer the longer version. While it takes longer to type, it comes with several benefits. The main benefit is that because it's immutable, it can have structural equality. This makes it trivial to compare objects, which, for example, is something you do all the time in unit test assertions. Another benefit is that such Value Objects make better domain models. The above Reservation Value Object only shows the slightest sign of emerging domain logic in the Accept method, but once you start modelling like this, such objects seem to attract more domain behaviour.

Maintenance burden #

Perhaps you're now convinced that typing speed may not be the bottleneck, but you still feel that you don't like the verbose Reservation alternative. More code could be an increased maintenance burden.

Consider those With[...] methods, such as WithName, WithQuantity, and so on. Once you make objects immutable, such copy-and-update methods become indispensable. They enable you to change a single property of an object, while keeping all other values intact:

> var r = new Reservation(DateTimeOffset.Now, "Foo", "foo@example.com", 3);
> r.WithQuantity(4)
Reservation { Date=[11.09.2018 19:19:29 +02:00],
              Email="foo@example.com",
              IsAccepted=false,
              Name="Foo",
              Quantity=4 }

While convenient, such methods can increase the maintenance burden. If you realise that you need to change the name of one of the properties, you'll have to remember to also change the name of the copy-and-update method. For example, if you change Quantity to NumberOfGuests, you'll have to also remember to rename WithQuantity to WithNumberOfGuests.

I'm not sure that I'm ready to concede that this is a prohibitive strain on the sustainability of a code base, but I do grant that it's a nuisance. This is one of the many reasons that I prefer to use programming languages better equipped for such domain modelling. In F#, for example, a record type similar to the above immutable Reservation class would be a one-liner:

type Reservation =
    { Date : DateTimeOffset; Name : string; Email : string; Quantity : int; IsAccepted : bool }

Such a declarative approach to types produces an immutable record with the same capabilities as the 78 lines of C# code.

That's a different story, though. There's little correlation between the size of code, and how 'good' it is. Sometimes, less code is better; sometimes, more code is better.

Summary #

I'll dispense with the usual Edsger Dijkstra and Bill Gates quotes on lines of code. The point that lines of code is a useless metric in software development has been made already. My point is a corollary. Apparently, it has to be explicitly stated: Programmer productivity has nothing to do with typing speed.

Unless you're disabled in some way, you can type fast enough to be a productive programmer. Typing isn't a programming bottleneck.

Comments

James Curran #

While I accept most of what you say, you are overlooking one key point: Better typists are better typists. Speed of typing (and volume of code produced) is the only statistic you look at. But what about quality?
Watch a bad typist code. (It's easier with coding-heavy tutorial videos). It usually go as: type four or five characters, backspace, make a correction, type another six characters, backspace, make another fix, type a few more character, etc.
They rarely get more than 10 keystrokes out before have to stop and go back. This reeks havoc with your cognitive flow, and makes it much harder to get into the "groove" of coding. Once you can type fluidly, you can concetrate on the code itself, rather than the mechanics of entering it.

2018-09-19 02:02 UTC

Davide Guida #

Lines of code has nothing to do with productivity. As professionals I think we all know this.
Moreover, in many cases, too much verbosity might only lead to more defects (unless you're a strong advocate of TDD et similia)
That said, one thing that I really liked about your article is the version of the Builder pattern you've implemented in the Reservation class. I love immutability in my classes and I often use the Builder pattern implemented as a inner class, just to be able to access the private cTor.
One thing that I don't like with your approach is that in case you have a bit parameter list in your cTor (as you do in the example), the consumers are forced to create a "dummy" instance and then call the WithXXX() methods on it when possible. I guess it could be solved adding a static readonly Empty property on the Reservation class that can be used as a starting point.
Anyways thank you for sharing this!

2018-09-19 11:02 UTC

Mark Seemann #

James, thank you for writing. I agree that being able to type out your thoughts as fast as possible lowers the barrier between your brain and whatever medium you're working in. I had something similar in mind when I wrote

"I also tend to write code in bursts. The average count of lines per hour may not be great, but that's because averages smooth out the hills and the valleys of my activity."

I do, however, have mounting concerns about what you call the groove of coding. Flow state is generally characterised by a lack of reflection that I have often found to be counter-productive. These days, when programming, I deliberately use the Pomodoro technique - not to motivate me to code, but to force me to take breaks. Uncountable are the times I've had an important realisation about my work as soon as I'm away from the keyboard. These insights never seem to come to me when I'm in flow.

2018-09-21 4:53 UTC

Radek Kapka #

Perhaps you're now convinced that typing speed may not be the bottleneck, but you still feel that you don't like the verbose Reservation alternative. More code could be an increased maintenance burden. Consider those With[...] methods, such as WithName, WithQuantity, and so on. Once you make objects immutable, such copy-and-update methods become indispensable.

You could create a more generic With method that would enable modifying any property. Here is an alternative design of the Reservation class including such a method. It is untested, so it might not work properly in every case.

public sealed class Reservation
{
    public Reservation(
        DateTimeOffset date,
        string name,
        string email,
        int quantity) :
        this(date, name, email, quantity, false)
    {
    }

    private Reservation(
        DateTimeOffset date,
        string name,
        string email,
        int quantity,
        bool isAccepted)
    {
        Date = date;
        Name = name;
        Email = email;
        Quantity = quantity;
        IsAccepted = isAccepted;
    }

    private Reservation()
    {
    }

    public DateTimeOffset Date { get; private set; }
    public string Name { get; private set; }
    public string Email { get; private set; }
    public int Quantity { get; private set; }
    public bool IsAccepted { get; private set; }

    public Reservation With(string propertyName, object value)
    {
        if (propertyName == null)
        {
            throw new ArgumentNullException(nameof(propertyName));
        }

        var property = typeof(Reservation).GetProperty(propertyName);
        if (property == null)
        {
            throw new ArgumentException($"Property ${propertyName} does not exist.");
        }

        if (!IsAssignable(property, value))
        {
            throw new ArgumentException($"Value ${value} is not assignable to property ${propertyName}");
        }

        var result = new Reservation();

        foreach (var prop in typeof(Reservation).GetProperties())
        {
            prop.SetValue(result, prop.Name == propertyName ? value : prop.GetValue(this));
        }

        return result;
    }

    public Reservation Accept()
    {
        return new Reservation(Date, Name, Email, Quantity, true);
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Reservation other))
        return false;

        return Equals(Date, other.Date)
        && Equals(Name, other.Name)
        && Equals(Email, other.Email)
        && Equals(Quantity, other.Quantity)
        && Equals(IsAccepted, other.IsAccepted);
    }

    public override int GetHashCode()
    {
        return
        Date.GetHashCode() ^
        Name.GetHashCode() ^
        Email.GetHashCode() ^
        Quantity.GetHashCode() ^
        IsAccepted.GetHashCode();
    }

    private static bool IsAssignable(PropertyInfo property, object value)
    {
        if (value == null && property.PropertyType.IsValueType &&
            Nullable.GetUnderlyingType(property.PropertyType) == null)
        {
            return false;
        }

        return value == null || property.PropertyType.IsAssignableFrom(value.GetType());
    }
}

Of course this design is not type-safe and we are throwing exceptions whenever the types of property and value don't match. Property names can be passed using nameof which will provide compile-time feedback. I believe it would be possible to write a code analyzer that would help calling the With method by raising compilation errors whenever the types don't match. The With method could be even designed as an extension method on object and distributed in a Nuget package with the anayler alongside it.

2018-09-27 07:34 UTC

The Lazy functor

Monday, 10 September 2018 05:38:00 UTC

Lazy evaluation forms a functor. An article for object-oriented programmers.

This article is an instalment in an article series about functors. Previous articles have covered Maybe, rose trees, and other functors. This article provides another example.

Most programming languages are eagerly evaluated. Sometimes, however, you'd like to defer execution of an expensive operation. On .NET, you can use Lazy<T> to achieve that goal. This generic type, like so many others, forms a functor.

Functor #

You can implement an idiomatic Select extension method for Lazy<T> like this:

public static Lazy<TResult> Select<T, TResult>(
    this Lazy<T> source,
    Func<T, TResult> selector)
{
    return new Lazy<TResult>(() => selector(source.Value));
}

This would, for example, enable you to write code like this:

Lazy<int> x = // ...
Lazy<string> y = x.Select(i => i.ToString());

Or, using query syntax:

Lazy<int> x = // ...
Lazy<string> y = from i in x select i.ToString();

You can add more steps to such a pipeline of lazy computation until you finally decide to force evaluation with the Value property.

Notice that while the Select method looks like it might force evaluation as well, by accessing the Value property, this happens inside a new lazily evaluated lambda expression. Thus, all steps in a Lazy pipeline are deferred until evaluation is forced.

First functor law #

The Select method obeys the first functor law. As usual in this article series, actually proving that this is the case belongs in the realm of computer science. Instead of proving that the law holds, you can demonstrate that it does using property-based testing. The following example shows a single property written with FsCheck 2.11.0 and xUnit.net 2.4.0.

[Property(QuietOnSuccess = true)]
public void LazyObeysFirstFunctorLaw(int i)
{
    var left = Lazy.FromValue(i);
    var right = Lazy.FromValue(i).Select(x => x);
 
    Assert.Equal(left.Value, right.Value);
}

Even though you may feel that a property-based test gives you more confidence than a few hard-coded examples, such a test is nothing but a demonstration of the first functor law. It's no proof, and it only demonstrates that the law holds for Lazy<int>, not that it holds for Lazy<string>, Lazy<Address>, etcetera.

Both this property and the next uses this little static helper method:

public static Lazy<T> FromValue<T>(T value)
{
    return new Lazy<T>(() => value);
}

This helper method is only a convenience. You can put in a delay if you want to pretend that actual lazy evaluation takes place. It'll make the tests run slower, but otherwise will not affect the outcome.

Second functor law #

As is the case with the first functor law, you can also use a property to demonstrate that the second functor law holds:

[Property(QuietOnSuccess = true)]
public void LazyObeysSecondFunctorLaw(
    Func<string, byte> f,
    Func<int, string> g,
    int i)
{
    var left = Lazy.FromValue(i).Select(g).Select(f);
    var right = Lazy.FromValue(i).Select(x => f(g(x)));
 
    Assert.Equal(left.Value, right.Value);
}

Again the same admonitions apply: that property is no proof. It does show, however, that given two functions, f and g, it doesn't matter if you map a Lazy computation in one or two steps. The output is the same in both cases.

F# #

F# has built-in language support for lazy evaluations, but surprisingly doesn't supply a map function. You can, however, easily implement such a function yourself:

module Lazy =
    // ('a -> 'b) -> Lazy<'a> -> Lazy<'b>
    let map f (x : Lazy<'a>) = lazy f x.Value

This enables you to write code like this:

let (x : Lazy<int>) = // ...
let (y : Lazy<string>) = x |> Lazy.map string

The F# language feature is based on the same Lazy<T> class that you can use from C# (and Visual Basic .NET), so the behaviour is the same as described above. The functor laws hold for the Lazy.map function just like it holds for the above Select method.

Haskell #

Unlinke C#, F#, and most other programming languages, Haskell is lazily evaluated. All values, whether scalar or complex, are lazy by default. For that reason, there's no explicit Lazy type in Haskell.

Haskell values are, in themselves, not functors, but you can put any value into the Identity functor. Since all values are already lazy, you could view Identity as Haskell's Lazy functor.

The equivalence is only partial, however. .NET Lazy objects are small state machines. Before you've forced evaluation, they carry around the expression to be evaluated. Once you've evaluated the value once, Lazy objects effectively replace the lazy expression with its result. Thus, the next time you access the Value property, you immediately receive the result.

Haskell's lazily evaluated values are different. Since they're immutable, they don't 'change state' like that. On the other hand, sometimes the Haskell compiler can identify optimisations that it can apply to make lazily evaluated values more efficient. In other cases, you may have to apply more explicit memoisation.

Summary #

In languages with eager evaluation (which is most of them), you can model deferred execution as a functor. This enables you to compose lazily evaluated expressions piecemeal.

Next: Asynchronous functors.

The Identity functor

Monday, 03 September 2018 06:46:00 UTC

The Identity functor is a data container that doesn't do anything. It's a functor nonetheless. An article for object-oriented programmers.

This article is an instalment in an article series about functors. In previous articles, you've learned about useful functors such as Maybe. In this article, you'll learn about a (practically) useless functor called Identity. You can skip this article if you want.

If Identity is useless, then why bother?

The inutility of Identity doesn't mean that it doesn't exist. The Identity functor exists, whether it's useful or not. You can ignore it, but it still exists. In C# or F# I've never had any use for it (although I've described it before), while it turns out to be occasionally useful in Haskell, where it's built-in. The value of Identity is language-dependent.

You may still derive value from this article. My motivation for writing it is to add another example to the set of functor examples presented in this article series. By presenting a varied selection of functors, it's my hope that you, from examples, gain insight.

Identity objects #

You can implement Identity as a C# class:

public sealed class Identity<T>
{
    public Identity(T item)
    {
        Item = item;
    }
 
    public T Item { get; }
 
    public Identity<TResult> Select<TResult>(Func<T, TResult> selector)
    {
        return new Identity<TResult>(selector(Item));
    }
 
    public override bool Equals(object obj)
    {
        if (!(obj is Identity<T> other))
            return false;
 
        return Equals(Item, other.Item);
    }
 
    public override int GetHashCode()
    {
        return Item?.GetHashCode() ?? 0;
    }
}

This class is just a wrapper around any object of the generic type T. The value could even be null if T is a reference type.

Since Identity<T> exposes the Select instance method, you can translate wrapped values, as this C# Interactive example demonstrates:

> new Identity<string>("foo").Select(s => s.Length)
Identity<int> { Item=3 }

You can also, if you prefer, use query syntax:

> from i in new Identity<int>(2) select 'f' + new String('o', i)
Identity<string> { Item="foo" }

You can also unwrap the value:

> Identity<string> x = new Identity<string>("bar");
> x.Item
"bar"

Admittedly, this isn't the most exciting or useful class you could ever write. It is, however, a functor.

First functor law #

The Select method obeys the first functor law. As usual in this article series, actually proving that this is the case belongs in the realm of computer science. I would guess, however, that in this particular case, the proof would be manageable. Instead of proving this, though, you can demonstrate that the law holds using property-based testing. The following example shows a single property written with FsCheck 2.11.0 and xUnit.net 2.4.0.

[Property(QuietOnSuccess = true)]
public void IdentityObeysFirstFunctorLaw(int i)
{
    var left = new Identity<int>(i);
    var right = new Identity<int>(i).Select(x => x);
 
    Assert.Equal(left, right);
}

Even though you may feel that a property-based test gives you more confidence than a few hard-coded examples, such a test is nothing but a demonstration of the first functor law. It's no proof, and it only demonstrates that the law holds for Identity<int>, not that it holds for Identity<string>, Identity<Customer>, etcetera.

Second functor law #

As is the case with the first functor law, you can also use a property to demonstrate that the second functor law holds:

[Property(QuietOnSuccess = true)]
public void IdentityObeysSecondFunctorLaw(
    Func<string, byte> f,
    Func<int, string> g,
    int i)
{
    var left = new Identity<int>(i).Select(g).Select(f);
    var right = new Identity<int>(i).Select(x => f(g(x)));
 
    Assert.Equal(left, right);
}

Again the same admonitions apply: that property is no proof. It does show, however, that given two functions, f and g, it doesn't matter if you map an Identity object in one or two steps. The output is the same in both cases.

F# #

While the Identity functor is built into the Haskell standard library, there's no Identity functor in F#. While it can be occasionally useful in Haskell, Identity is useless in F#, like it is in C#. Again, that doesn't imply that you can't define it. You can:

type Identity<'a> = Identity of 'a
 
module Identity =
    // Identity<'a> -> 'a
    let get (Identity x) = x
    // ('a -> 'b) -> Identity<'a> -> Identity<'b>
    let map f (Identity x) = Identity (f x)

With this type, you can wrap, map, and unwrap values to your heart's content:

> Identity "foo" |> Identity.map Seq.length;;
val it : Identity<int> = Identity 3

> Identity 2 |> Identity.map (fun i -> "f" + String ('o', i));;
val it : Identity>string> = Identity "foo"

> let x = Identity "bar";;
val x : Identity<string> = Identity "bar"

> Identity.get x;;
val it : string = "bar"

There's not much point to this, apart from demonstrating that it's possible.

Summary #

The Identity functor exists, and you can implement it in C# and F#, although I don't see any use for it. Haskell has a type system that can express abstractions such as Functor in the type system itself. In that language, then, you can define functions that return any type of functor (e.g. Maybe, Tree, and so on). If you need a plain vanilla version of such a function, you can make it return Identity.

The point of this article was only to identify the existence of the Identity functor, and to perhaps illustrate that the concept of a functor encompasses various data structures and behaviours.

Next: The Lazy functor.

On Constructor Over-injection

Monday, 27 August 2018 07:11:00 UTC

Constructor Over-injection is a code smell, not an anti-pattern.

Sometimes, people struggle with how to deal with the Constructor Over-injection code smell. Often, you can address it by refactoring to Facade Services. This is possible when constructor arguments fall in two or more natural clusters. Sometimes, however, that isn't possible.

Cross-cutting concerns #

Before we get to the heart of this post, I want to get something out of the way. Sometimes constructors have too many arguments because they request various services that represent cross-cutting concerns:

public Foo(
    IBar bar,
    IBaz baz,
    IQux qux,
    IAuthorizationManager authorizationManager,
    ILog log,
    ICache cache,
    ICircuitBreaker breaker)

This Foo class has seven dependencies passed via the constructor. Three of those (bar, baz, and qux) are regular dependencies. The other four are various incarnations of cross-cutting concerns: logging, caching, authorization, stability. As I describe in my book, cross-cutting concerns are better addressed with Decorators or the Chain of Responsibility pattern. Thus, such a Foo constructor ought really to take just three arguments:

public Foo(
    IBar bar,
    IBaz baz,
    IQux qux)

Making cross-cutting concerns 'disappear' like that could decrease the number of constructor arguments to an acceptable level, thereby effectively dealing with the Constructor Over-injection smell. Sometimes, however, that's not the issue.

No natural clusters #

Occasionally, a class has many dependencies, and the dependencies form no natural clusters:

public Ploeh(
    IBar bar,
    IBaz baz,
    IQux qux,
    IQuux quux,
    IQuuz quuz,
    ICorge corge,
    IGrault grault,
    IGarply garply,
    IWaldo waldo,
    IFred fred,
    IPlugh plugh,
    IXyzzy xyzzy,
    IThud thud)
{
    Bar = bar;
    Baz = baz;
    Qux = qux;
    Quux = quux;
    Quuz = quuz;
    Corge = corge;
    Grault = grault;
    Garply = garply;
    Waldo = waldo;
    Fred = fred;
    Plugh = plugh;
    Xyzzy = xyzzy;
    Thud = thud;
}

This seems to be an obvious case of the Constructor Over-injection code smell. If you can't refactor to Facade Services, then what other options do you have?

Introducing a Parameter Object isn't likely to help #

Some people, when they run into this type of situation, attempt to resolve it by introducing a Parameter Object. In its simplest form, the Parameter Object is just a collection of properties that client code can access. In other cases, the Parameter Object is a Facade over a DI Container. Sometimes, the Parameter Object is defined as an interface with read-only properties.

One way to use such a Parameter Object could be like this:

public Ploeh(DependencyCatalog catalog)
{
    Bar = catalog.Bar;
    Baz = catalog.Baz;
    Qux = catalog.Qux;
    Quux = catalog.Quux;
    Quuz = catalog.Quuz;
    Corge = catalog.Corge;
    Grault = catalog.Grault;
    Garply = catalog.Garply;
    Waldo = catalog.Waldo;
    Fred = catalog.Fred;
    Plugh = catalog.Plugh;
    Xyzzy = catalog.Xyzzy;
    Thud = catalog.Thud;
}

Alternatively, some people just store a reference to the Parameter Object and then access the read-only properties on an as-needed basis.

None of those alternatives are likely to help. One problem is that such a DependencyCatalog will be likely to violate the Interface Segregation Principle, unless you take great care to make a 'dependency catalogue' per class. For instance, you'd be tempted to add Wibble, Wobble, and Wubble properties to the above DependencyCatalog class, because some other Fnaah class needs those dependencies in addition to Bar, Fred, and Waldo.

Deodorant #

Fundamentally, Constructor Over-injection is a code smell. This means that it's an indication that something is not right; that there's an area of code that bears investigation. Code smells aren't problems in themselves, but rather symptoms.

Constructor Over-injection tends to be a symptom that a class is doing too much: that it's violating the Single Responsibility Principle. Reducing thirteen constructor arguments to a single Parameter Object doesn't address the underlying problem. It only applies deodorant to the smell.

Address, if you can, the underlying problem, and the symptom is likely to disappear as well.

Guidance, not law #

This is only guidance. There could be cases where it's genuinely valid to have dozens of dependencies. I'm being deliberately vague, because I don't wish to go into an elaborate example. Usually, there's more than one way to solve a particular problem, and occasionally, it's possible that collecting many services in a single class would be appropriate. (This sounds like a case for the Composite design pattern, but let's assume that there could be cases where that's not possible.)

This is similar to using cyclomatic complexity as a guide. Every now and then, a big, flat switch statement is just the best and most maintainable solution to a problem, even when it has a cyclomatic complexity of 37...

Likewise, there could be cases where it's genuinely not a problem with dozens of constructor arguments.

Summary #

Constructor Over-injection is a code smell, not an anti-pattern. It's a good idea to be aware of the smell, and address it when you discover it. You should, however, deal with the problem instead of applying deodorant to the smell. The underlying problem is usually that the class with the many dependencies has too many responsibilities. Address that problem, and the smell is likely to evaporate as well.

Comments

Dominik Jeske #

Hi Mark, I have question about “Parameter Object” approach you mentioned. In my previous project we was using this approach heavily. I know disadvantages you described and honestly I was against this approach but after some time I saw some advantages I want to discuss.

We have a lot of services that was reading data from some external databases, do some basic validation and fixing and than save to other database – so it was most integration code. Every of our services had bootstrapper attached by attribute that was describing dependencies. Each have only one parameter with so called “catalog” that was façade over DI with read only properties (sometimes even in tree structure to make it simpler to use like Catalog.Repositories.Server.SomeRepository). We have some base class for common dependencies like logging, common infrastructure services etc (we also use interceptor for cross cutting concerns but sometimes we have to log something explicitly).

In unit tests we used same bootstrapper that service was using with repositories changed to mocks. Advantage that I’m seeing is that when using lot of unit tests and service like this when we are maintain the code when something is changing in service we don’t had to touch any unit test – it is similar to using parameter object in general even outside the scope of constructor – when using single complex object as input parameter there is also no problem when on 100 unit test break after we change add some method parameter. It is service locator antipattern but only in one place – other code is not using DI.

Sometimes when I’m thinking about anti pattern approach in general I have a feeling similar to you when you was explaining other approach to async injection “you cannot do that” – “Oh, really”? Maybe pattern police will hunt me but is this really so bad?

2019-08-01 9:07 UTC

Mark Seemann #

Dominik, thank you for writing. To be clear: there's no pattern police. Design patterns is (or was) an attempt to establish a vocabulary that can act as short-cuts for long, elaborate chains of arguments. The same goes for anti-patterns.

Most experienced programmers over time discover that certain ways of doing things yield more benefits than disadvantages (patterns) or yield more disadvantages than benefits (anti-patterns). Instead of having to explain the possible consequences every time we run into such situations, we can reach for a generalised description and refer to it by names such as Composite, Decorator, Service Locator, etc.

The same goes for more basic design principles such as the SOLID principles. If you find yourself writing code such as Catalog.Repositories.Server.SomeRepository, you're already in territory where the Law of Demeter (or the Occasionally Useful Suggestion of Demeter) applies. The Law of Demeter is less than a law and more like a code smell. If you find yourself 'dotting into' a deep object graph like that, you should stop and consider how that's going to impact long-term maintainability.

Either an object doesn't need everything that a service catalogue exposes, in which case it'd be at odds with the Interface Segregation Principle, or it does need all of those services, in which case the class in question most likely violates the Single Responsibility Principle.

You can address the first of these concerns by injecting only the services that a class needs. If you're concerned about the impact on unit tests of changing dependencies, consider using an Auto-mocking Container.

You can address the second of the above concerns by refactoring to Facade Services.

2019-08-03 10:17 UTC

Dominik Jeske #

Mark, thanks for detailed answer (as always).

In matter of catalog approach it was always smelly for me and honestly I was against using it but sometimes I had no good arguments to get rid of it. Automocking container is very promising for me – as matter of fact I saw this approach when analyzing one of your github samples and for start it looked like magic when xunit+autofixture+automoq was used and I have to admit it was love at first sight and I will absolutely deep dive into this topic.

When talking about pattern police I was some kind of joking. I understand the source and meaning of the patterns and it is very good that we have them but sometimes they are problematic. Many times some question / discussion on places like stuckoverflow is broken by some “police man” that is saying that “your approach is antipattern”. Even if this maybe is true it sometimes kills some new approaches because people are real believers and they believe in patterns as if they were some religion and they will be fight for it instead of discuss and assume that maybe it is not always true or maybe this case is not really antipattern.

Other thing is that people forgot after some time what is the real purpose / source of the pattern – the just use it automatically. My favorite anecdote/joke illustrate this

Mom why you are cutting edges of the cake
Becouse we should do this
But why
Becoue we have to
But why
Becouse… my mom did this
Grandma why you are cutting edges of the cake
Becouse… my mom did this
Great grandma why you are cutting edges of the cake
Becouse I have small stove

After your explanation I’m closer to see why this is antipattern but for understand thing like this for real it is no enough to say that this is antipattern but this ability is not given to all people 😊

2019-08-05 20:50 UTC

Reactive functor

Monday, 20 August 2018 05:58:00 UTC

IObservable<T> is (also) a functor.

This article is an instalment in an article series about functors. While the previous articles showed, in great detail, how to turn various classes into functors, this article mostly serves as a place-holder. The purpose is only to point out that you don't have to create all functors yourself. Sometimes, they come as part of a reusable library.

Rx is such a library, and IObservable<T> is a functor. (It's also a monad, but this is not a monad tutorial; it's a functor tutorial.) Reactive Extensions define a Select method for IObservable<T>, so if source is an IObservable<int>, you can translate it to IObservable<string> like this:

IObservable<string> dest = source.Select(i => i.ToString());

Since the Select method is, indeed, called Select and has the signature

public static IObservable<TResult> Select<TSource, TResult>(
    this IObservable<TSource> source,
    Func<TSource, TResult> selector)

you can also use C#'s query syntax:

IObservable<string> dest = from i in source
                           select i.ToString();

In both of the above examples, I've explicitly declared the type of dest instead of using the var keyword. There's no practical reason to do this; I only did it to make the type clear to you.

First functor law #

The Select method obeys the first functor law. As usual, it's proper computer-science work to actually prove that, but you can write some tests to demonstrate the first functor law for the IObservable<T> interface. In this article, you'll see a few parametrised tests written with xUnit.net. Here's one that demonstrates that the first functor law holds:

[Theory]
[InlineData(-101)]
[InlineData(-1)]
[InlineData(0)]
[InlineData(1)]
[InlineData(42)]
[InlineData(1337)]
public async Task ObservableObeysFirstFunctorLaw(int value)
{
    var sut = new[] { value }.ToObservable();
 
    IObservable<int> projected = sut.Select(x => x);
    var actual = await projected.FirstAsync();
 
    Assert.Equal(value, actual);
}

Here, I chose to implement the identity function as an anonymous lambda expression. In contrast, in a previous article, I explicitly declared a function variable and called it id. Those two ways to express the identity function are equivalent.

As always, I'd like to emphasise that this test doesn't prove that IObservable<T> obeys the first functor law. It only demonstrates that the law holds for those six examples.

Second functor law #

Like the above example, you can also write a parametrised test that demonstrates that IObservable<T> obeys the second functor law:

[Theory]
[InlineData(-101)]
[InlineData(-1)]
[InlineData(0)]
[InlineData(1)]
[InlineData(42)]
[InlineData(1337)]
public async Task ObservableObeysSecondFunctorLaw(int value)
{
    string g(int i) => i.ToString();
    string f(string s) => new string(s.Reverse().ToArray());
    var sut = new[] { value }.ToObservable();
 
    IObservable<string> projected = sut.Select(i => f(g(i)));
    var actual = await projected.FirstAsync();
 
    var expected = await sut.Select(g).Select(f).FirstAsync();
    Assert.Equal(expected, actual);
}

This test defines two local functions, f and g. Instead of explicitly declaring the functions as Func variables, this test uses a (relatively) new C# feature called local functions.

Again, while the test doesn't prove anything, it demonstrates that for the six test cases, it doesn't matter if you project the observable in one or two steps.

Summary #

The point of this article is mostly that functors are commonplace. While you may discover them in your own code, they may also come in a reusable library. If you already know C# LINQ based off IEnumerable<T>, much of Rx will be easy for you to learn. After all, it's the same abstraction, and familiar abstractions make code readable.

Next: The Identity functor.

A Visitor functor

Monday, 13 August 2018 06:56:00 UTC

Some Visitors can be functors. Another functor example for object-oriented programmers.

This article is an instalment in an article series about functors. In the previous article, you saw how to implement a generalised tree as a functor. In this article, you'll see another functor example, which will also be an application of the Visitor design pattern.

The Visitor design pattern is often described in such a way that it's based on mutation; the Visit and Accept methods in those descriptions typically return void. You can, however, also implement immutable variations. This blog already contains an older example of this.

Visitor #

In this article, you'll see how to implement a full binary tree using the Visitor design pattern. You can make the tree generic, so that each node can contain values of any generic type.

public interface IBinaryTree<T>
{
    TResult Accept<TResult>(IBinaryTreeVisitor<T, TResult> visitor);
}

As promised, this interface implies an immutable variant where the Accept method doesn't mutate the input Visitor, but rather returns a new value. You can learn how you arrive at this particular generic method signature in my article Visitor as a sum type.

A full binary tree is a tree where each node has either zero or two children. This means that a Visitor must have two methods, one for each case:

public interface IBinaryTreeVisitor<T, TResult>
{
    TResult Visit(Node<T> node);
 
    TResult Visit(Leaf<T> leaf);
}

The IBinaryTreeVisitor<T, TResult> interface introduces two new concrete classes: Node<T> and Leaf<T>. A leaf node is a node with zero children:

public sealed class Leaf<T> : IBinaryTree<T>
{
    public T Item { get; }
 
    public Leaf(T item)
    {
        if (item == null)
            throw new ArgumentNullException(nameof(item));
 
        Item = item;
    }
 
    public TResult Accept<TResult>(IBinaryTreeVisitor<T, TResult> visitor)
    {
        if (visitor == null)
            throw new ArgumentNullException(nameof(visitor));
 
        return visitor.Visit(this);
    }
 
    public override bool Equals(object obj)
    {
        if (!(obj is Leaf<T> other))
            return false;
 
        return Equals(Item, other.Item);
    }
 
    public override int GetHashCode()
    {
        return Item.GetHashCode();
    }
}

While a leaf node has no children, it still contains an Item of the generic type T. A leaf node still counts as a binary tree, so it implements the IBinaryTree<T> interface. Complying with the Visitor design pattern, its Accept method is implemented using double dispatch. Thereby, any visitor knows that it's now visiting a concrete Leaf<T> object.

Likewise, a node is a (sub)tree:

public sealed class Node<T> : IBinaryTree<T>
{
    public T Item { get; }
    public IBinaryTree<T> Left { get; }
    public IBinaryTree<T> Right { get; }
 
    public Node(T item, IBinaryTree<T> left, IBinaryTree<T> right)
    {
        if (item == null)
            throw new ArgumentNullException(nameof(item));
        if (left == null)
            throw new ArgumentNullException(nameof(left));
        if (right == null)
            throw new ArgumentNullException(nameof(right));
 
        Item = item;
        Left = left;
        Right = right;
    }
 
    public TResult Accept<TResult>(IBinaryTreeVisitor<T, TResult> visitor)
    {
        if (visitor == null)
            throw new ArgumentNullException(nameof(visitor));
 
        return visitor.Visit(this);
    }
 
    public override bool Equals(object obj)
    {
        if (!(obj is Node<T> other))
            return false;
 
        return Equals(Item, other.Item)
            && Equals(Left, other.Left)
            && Equals(Right, other.Right);
    }
 
    public override int GetHashCode()
    {
        return Item.GetHashCode() ^ Left.GetHashCode() ^ Right.GetHashCode();
    }
}

In addition to an Item, a Node<T> object also contains a Left and a Right sub-tree. Notice that the Accept method is literally identical to Leaf<T>.Accept. Its behaviour differs, though, because this has a different type.

A couple of static helper methods makes it a bit easier to create binary tree objects:

public static class BinaryTree
{
    public static IBinaryTree<T> Leaf<T>(T item)
    {
        return new Leaf<T>(item);
    }
 
    public static IBinaryTree<T> Create<T>(
        T item,
        IBinaryTree<T> left,
        IBinaryTree<T> right)
    {
        return new Node<T>(item, left, right);
    }
}

The main convenience of these two methods is that C# (limited) type inference enables you to create tree objects without explicitly typing out the generic type argument every time. You'll soon see an example of creating a binary tree of integers.

Functor #

Since IBinaryTree<T> is a generic type, you should consider whether it's a functor. Given the overall topic of this article, you'd hardly be surprised that it is.

In the previous two functor examples (Maybe and Tree), the Select methods were instance methods. On the other hand, the .NET Base Class Library implements IEnumerable<T>.Select as an extension method. You can do the same with this binary tree Visitor:

public static IBinaryTree<TResult> Select<TResult, T>(
    this IBinaryTree<T> tree,
    Func<T, TResult> selector)
{
    if (tree == null)
        throw new ArgumentNullException(nameof(tree));
    if (selector == null)
        throw new ArgumentNullException(nameof(selector));
 
    var visitor = new SelectBinaryTreeVisitor<T, TResult>(selector);
    return tree.Accept(visitor);
}

This Select method has the right signature for turning IBinaryTree<T> into a functor. It starts by creating a new instance of a private helper class called SelectBinaryTreeVisitor<T, TResult>. Notice that this class has two generic type arguments: the source type T and the destination type TResult. It also contains selector, so that it knows what to do with each Item it encounters.

SelectBinaryTreeVisitor<T, TResult> is a Visitor, so you pass it to the tree object's Accept method. The Accept method returns a variable that you can directly return, because, as you'll see below, the return type of SelectBinaryTreeVisitor<T, TResult>'s Visit methods is IBinaryTree<TResult>.

SelectBinaryTreeVisitor<T, TResult> is a private helper class, and is the most complex functor implementation you've seen so far. The Visitor design pattern solves a specific problem, but it was never the simplest of design patterns.

private class SelectBinaryTreeVisitor<T, TResult> :
    IBinaryTreeVisitor<T, IBinaryTree<TResult>>
{
    private readonly Func<T, TResult> selector;
 
    public SelectBinaryTreeVisitor(Func<T, TResult> selector)
    {
        if (selector == null)
            throw new ArgumentNullException(nameof(selector));
 
        this.selector = selector;
    }
 
    public IBinaryTree<TResult> Visit(Leaf<T> leaf)
    {
        var mappedItem = selector(leaf.Item);
        return Leaf(mappedItem);
    }
 
    public IBinaryTree<TResult> Visit(Node<T> node)
    {
        var mappedItem = selector(node.Item);
        var mappedLeft = node.Left.Accept(this);
        var mappedRight = node.Right.Accept(this);
        return Create(mappedItem, mappedLeft, mappedRight);
    }
}

Since the class implements IBinaryTreeVisitor<T, IBinaryTree<TResult>>, it must implement the two Visit overloads. The overload for Leaf<T> is simple: use the selector to map the Item, and use the Leaf convenience method to return a new Leaf<TResult> containing the mapped item. Notice that while SelectBinaryTreeVisitor<T, TResult> looks like it has a generic 'return' type argument of TResult, it implements IBinaryTreeVisitor<T, IBinaryTree<TResult>>, which means that the return type of each Visit method must be IBinaryTree<TResult>, and that matches Leaf<TResult>.

The overload for a Node<T> object looks twice as big, but it's still simple. Like the leaf overload, it uses selector to map the Item, but in addition to that, it must also recursively map the Left and Right sub-trees. It does this by passing itself, in its role as a Visitor, to the left and right nodes' Accept methods. This returns mapped sub-trees that can be used to create a new mapped tree, using the Create convenience method.

Usage #

While the implementation of such a Visitor is cumbersome, it's easy enough to use.

var source =
    BinaryTree.Create(42,
        BinaryTree.Create(1337,
            BinaryTree.Leaf(0),
            BinaryTree.Leaf(-22)),
        BinaryTree.Leaf(100));

You can translate this binary tree of integers to a tree of strings using method call syntax:

IBinaryTree<string> dest = source.Select(i => i.ToString());

or by using query syntax:

IBinaryTree<string> dest = from i in source
                           select i.ToString();

In both of these examples, I've explicitly declared the type of dest instead of using the var keyword. There's no practical reason to do this; I only did it to make the type clear to you.

Haskell #

Why would anyone ever do something so complicated as this?

The answer to such a question is, I believe, that it's only complicated in some programming languages. In Haskell, all of the above can be reduce to a single type declaration:

data BinaryTree a = Node a (BinaryTree a) (BinaryTree a) | Leaf a
  deriving (Show, Eq, Functor)

Notice that the Haskell compiler can automatically derive an implementation of the Functor typeclass, although that does require the DeriveFunctor language extension.

This may explain why binary trees aren't part of object-oriented programmers' normal tool box, whereas they are more commonplace in functional programming.

While not strictly required, in order to keep the examples equivalent, you can define these two aliases:

leaf :: a -> BinaryTree a
leaf = Leaf
 
create :: a -> BinaryTree a -> BinaryTree a -> BinaryTree a
create = Node

This enables you to create a binary tree like this:

source :: BinaryTree Int
source =
    create 42 (
        create 1337 (
            leaf 0) (
            leaf (-22))) (
        leaf 100)

As usual you can map the tree using the fmap function:

dest :: BinaryTree String
dest = fmap show source

or by using infix notation:

dest :: BinaryTree String
dest = show <$> source

The <$> operator is an alias for fmap.

F# #

As usual, F# lies somewhere between the extremes of C# and Haskell, although it's closer to Haskell in simplicity. The type declaration is similar:

type BinaryTree<'a> =
| Node of ('a * BinaryTree<'a> * BinaryTree<'a>)
| Leaf of 'a

Unlike Haskell, however, F# doesn't have any built-in functor awareness, so you'll have to implement the map function yourself:

// ('a -> 'b) -> BinaryTree<'a> -> BinaryTree<'b>
let rec map f = function
    | Node (x, left, right) -> Node (f x, map f left, map f right)
    | Leaf x -> Leaf (f x)

Notice that you have to use the rec keyword in order to make map recursive. Instead of having to create a new helper class, and all the byzantine interactions required by the Visitor design pattern, the implementation uses simple pattern matching to achieve the same goal. In the Node case, it uses f to translate x, and recursively calls itself on left and right. In the Leaf case, it simply returns a new Leaf value with x translated by f.

Create helper functions to keep all three examples aligned:

// 'a -> BinaryTree<'a>
let leaf = Leaf
 
// 'a -> BinaryTree<'a> -> BinaryTree<'a> -> BinaryTree<'a>
let create x left right = Node (x, left, right)

You can now create a binary tree of integers:

// BinaryTree<int>
let source =
    BinaryTree.create 42 (
        BinaryTree.create 1337 (
            BinaryTree.leaf 0) (
            BinaryTree.leaf -22)) (
        BinaryTree.leaf 100)

which you can translate like this:

// BinaryTree<string>
let dest = source |> BinaryTree.map string

Here, all of the above functions are defined in a module named BinaryTree.

First functor law #

The Select method obeys the first functor law. As usual, it's proper computer-science work to actually prove that, but you can write some tests to demonstrate the first functor law for the IBinaryTree<T> interface. In this article, you'll see a few parametrised tests written with xUnit.net. First, you can define some reusable trees as test input:

public static IEnumerable<object[]> Trees
{
    get
    {
        yield return new[] { BinaryTree.Leaf(0) };
        yield return new[] {
            BinaryTree.Create(-3,
                BinaryTree.Leaf(2),
                BinaryTree.Leaf(99)) };
        yield return new[] {
            BinaryTree.Create(42,
                BinaryTree.Create(1337,
                    BinaryTree.Leaf(0),
                    BinaryTree.Leaf(-22)),
                BinaryTree.Leaf(100)) };
        yield return new[] {
            BinaryTree.Create(-927,
                BinaryTree.Leaf(2),
                BinaryTree.Create(211,
                    BinaryTree.Leaf(88),
                    BinaryTree.Leaf(132))) };
        yield return new[] {
            BinaryTree.Create(111,
                BinaryTree.Create(-336,
                    BinaryTree.Leaf(113),
                    BinaryTree.Leaf(-432)),
                BinaryTree.Create(1299,
                    BinaryTree.Leaf(-32),
                    BinaryTree.Leaf(773))) };
    }
}

This is just a collection of five small binary trees that can be used as input for parametrised tests. The first tree is only a single node - the simplest tree you can make with the IBinaryTree<T> API.

You can use this static property as a source of input for parametrised tests. Here's one that demonstrates that the first functor law holds:

[Theory, MemberData(nameof(Trees))]
public void FirstFunctorLaw(IBinaryTree<int> tree)
{
    Assert.Equal(tree, tree.Select(x => x));
}

As always, I'd like to emphasise that this test doesn't prove that IBinaryTree<T> obeys the first functor law. It only demonstrates that the law holds for those five examples.

Second functor law #

Like the above example, you can also write a parametrised test that demonstrates that IBinaryTree<T> obeys the second functor law. You can reuse the Trees test case source for that test:

[Theory, MemberData(nameof(Trees))]
public void SecondFunctorLaw(IBinaryTree<int> tree)
{
    string g(int i) => i.ToString();
    bool f(string s) => s.Length % 2 == 0;
 
    Assert.Equal(tree.Select(g).Select(f), tree.Select(i => f(g(i))));
}

This test defines two local functions, f and g. Instead of explicitly declaring the functions as Func variables, this test uses a (relatively) new C# feature called local functions.

Again, while the test doesn't prove anything, it demonstrates that for the five test cases, it doesn't matter if you project the tree in one or two steps.

Summary #

Statically typed functional languages like F# and Haskell enable you to define sum types: types that encode a selection of mutually exclusive cases. Combined with pattern matching, it's easy to deal with values that can be one of several non-polymorphic cases. Object-oriented languages like C# or Java don't have good support for this type of data structure. Object-oriented programmers often resort to using type hierarchies, but this requires down-casting in order to work. It also comes with the disadvantage that with type hierarchies, the hierarchy is extensible, which means that as an implementer, you never know if you've handled all sub-types. The Visitor design pattern is a way to model sum types in object-oriented programming, although it tends to be verbose.

Nevertheless, if you have a generic type that models a set of mutually exclusive cases, it just may be a functor. In Haskell, you can make such a type a Functor with a mere declaration. In C#, you have to write considerable amounts of code.

Next: Reactive functor.

A Tree functor

Monday, 06 August 2018 06:00:00 UTC

A generalised tree object as a functor. Another functor example for object-oriented programmers.

This article is an instalment in an article series about functors. In a previous article, you saw how to implement the Maybe functor in C#. In this article, you'll get another functor example: a generalised tree (also known as a rose tree).

As opposed to a binary tree, any node in a generalised tree can have an arbitrary number of children, including none.

Implementation #

The following Tree<T> class can contain objects of the generic type T. Being generic, it's a candidate for a functor, and it does, in fact, turn out to be one:

public sealed class Tree<T> : IReadOnlyCollection<Tree<T>>
{
    private readonly IReadOnlyCollection<Tree<T>> children;
 
    public T Item { get; }
 
    public Tree(T item, IReadOnlyCollection<Tree<T>> children)
    {
        if (item == null)
            throw new ArgumentNullException(nameof(item));
        if (children == null)
            throw new ArgumentNullException(nameof(children));
 
        Item = item;
        this.children = children;
    }
 
    public Tree<TResult> Select<TResult>(Func<T, TResult> selector)
    {
        var mappedItem = selector(Item);
 
        var mappedChildren = new List<Tree<TResult>>();
        foreach (var t in children)
            mappedChildren.Add(t.Select(selector));
 
        return new Tree<TResult>(mappedItem, mappedChildren);
    }
 
    public int Count
    {
        get { return children.Count; }
    }
 
    public IEnumerator<Tree<T>> GetEnumerator()
    {
        return children.GetEnumerator();
    }
 
    IEnumerator IEnumerable.GetEnumerator()
    {
        return children.GetEnumerator();
    }
 
    public override bool Equals(object obj)
    {
        if (!(obj is Tree<T> other))
            return false;
 
        return Equals(Item, other.Item)
            && Enumerable.SequenceEqual(this, other);
    }
 
    public override int GetHashCode()
    {
        return Item.GetHashCode() ^ children.GetHashCode();
    }
}

As is usually the case, you can implement a tree in more than one way. Here, I chose an approach where Tree<T> contains an Item and is a collection of (sub)trees. Notice that the definition is recursive: in addition to its Item, each Tree<T> object also contains a finite collection of other trees. You create leaf nodes with empty collections.

This variation uses finite collections (IReadOnlyCollection<T>), but you could also enable infinite trees by instead using potentially infinite sequences (IEnumerable<T>). This would slightly complicate the implementation of the Select method, though, so I decided to leave that as an exercise to the reader.

The Select method first translates the contained Item using the selector function, and then recursively calls itself for each sub-tree in children. This method has the desired signature, and furthermore obeys the functor laws, as you'll see later in the article. Tree<T> is a functor.

Usage #

While you can create trees directly with the Tree<T> constructor, a few static helper methods makes it smoother:

public static class Tree
{
    public static Tree<T> Leaf<T>(T item)
    {
        return new Tree<T>(item, new Tree<T>[0]);
    }
 
    public static Tree<T> Create<T>(T item, params Tree<T>[] children)
    {
        return new Tree<T>(item, children);
    }
}

This enables you to create a tree like this:

var source =
    Tree.Create(42,
        Tree.Create(1337,
            Tree.Leaf(-3)),
        Tree.Create(7,
            Tree.Leaf(-99),
            Tree.Leaf(100),
            Tree.Leaf(0)));

This is a tree containing integers. You can translate it to a tree containing strings like this:

Tree<string> dest = source.Select(i => i.ToString());

or like this:

Tree<string> dest = from i in source
                    select i.ToString();

In both of these examples, I've explicitly declared the type of dest instead of using the var keyword. There's no practical reason to do this; I only did it to make the type clear to you.

Haskell #

Haskell has a more explicit model of functors, and the language features to support it. The Haskell equivalent to the above Tree<T> class is literally one line of code:

data Tree a = Tree a [Tree a] deriving (Show, Eq, Functor)

Notice that the Haskell compiler can automatically derive an implementation of the Functor typeclass, although that does require the DeriveFunctor language extension.

You can expend a few more lines of code for utility functions, so that it looks like you're actually programming:

leaf :: a -> Tree a
leaf x = Tree x []
 
create :: a -> [Tree a] -> Tree a
create = Tree

These functions correspond to the static methods on the above Tree class. With them, you can now create a tree:

source :: Tree Int
source =
  create 42 [
    create 1337 [
      leaf (-3)],
    create 7 [
      leaf (-99),
      leaf 100,
      leaf 0]]

You can translate such a tree of integers to a tree of strings with the fmap function:

dest :: Tree String
dest = fmap show source

or with the infix operator:

dest :: Tree String
dest = show <$> source

The <$> operator is an alias for fmap.

F# #

In F#, the type definition has the same structure as in Haskell:

type Tree<'a> = Tree of ('a * Tree<'a> list)

Unlike Haskell, however, F# doesn't have any built-in functor awareness, so you'll have to implement the map function yourself:

// ('a -> 'b) -> Tree<'a> -> Tree<'b>
let rec map f (Tree (x, children)) =
    let mappedX = f x
    let mappedChildren = children |> List.map (map f)
    Tree (mappedX, mappedChildren)

Notice that you have to use the rec keyword in order to make map recursive. The implementation is similar to the C# code: first use f to map the contained item, and then recursively map the children.

To keep all three examples equivalent, you can also define utility functions:

// 'a -> Tree<'a>
let leaf x = Tree (x, List.empty)
 
// 'a -> Tree<'a> list -> Tree<'a>
let create x children = Tree (x, children)

This enables you to create a tree like this:

// Tree<int>
let source =
    Tree.create 42 [
        Tree.create 1337 [
            Tree.leaf -3]
        Tree.create 7 [
            Tree.leaf -99
            Tree.leaf 100
            Tree.leaf 0]]

which you can translate like this:

// Tree<string>
let dest = source |> Tree.map string

Here, all of the above functions are defined in a module named Tree.

First functor law #

The Select method obeys the first functor law. As usual, it's proper computer-science work to actually prove that, but you can write some tests to demonstrate the first functor law for the Tree<T> class. In this article, you'll see a few parametrised tests written with xUnit.net. First, you can define some reusable trees as test input:

public static IEnumerable<object[]> Trees
{
    get
    {
        yield return new[] { Tree.Leaf(42) };
        yield return new[] { Tree.Create(-32, Tree.Leaf(0)) };
        yield return new[] {
            Tree.Create(99,
                Tree.Leaf(90),
                Tree.Leaf(2)) };
        yield return new[] {
            Tree.Create(99,
                Tree.Leaf(90),
                Tree.Create(2,
                    Tree.Leaf(-3))) };
        yield return new[] {
            Tree.Create(42,
                Tree.Create(1337,
                    Tree.Leaf(-3)),
                Tree.Create(7,
                    Tree.Leaf(-99),
                    Tree.Leaf(100),
                    Tree.Leaf(0))) };
    }
}

This is just a collection of five small trees that can be used as input for parametrised tests. The first tree is only a single node - the simplest tree you can make with the Tree<T> class.

You can use this static property as a source of input for parametrised tests. Here's one that demonstrates that the first functor law holds:

[Theory, MemberData(nameof(Trees))]
public void FirstFunctorLaw(Tree<int> tree)
{
    Assert.Equal(tree, tree.Select(x => x));
}

Here, I chose to implement the identity function as an anonymous lambda expression. In contrast, in the previous article, I explicitly declared a function variable and called it id. Those two ways to express the identity function are equivalent.

As always, I'd like to emphasise that this test doesn't prove that Tree<T> obeys the first functor law. It only demonstrates that the law holds for those five examples.

Second functor law #

Like the above example, you can also write a parametrised test that demonstrates that Tree<T> obeys the second functor law. You can reuse the Trees test case source for that test:

[Theory, MemberData(nameof(Trees))]
public void SecondFunctorLaw(Tree<int> tree)
{
    string g(int i) => i.ToString();
    bool f(string s) => s.Length % 2 == 0;
 
    Assert.Equal(tree.Select(g).Select(f), tree.Select(i => f(g(i))));
}

This test defines two local functions, f and g. Instead of explicitly declaring the functions as Func variables, this test uses a (relatively) new C# feature called local functions.

Again, while the test doesn't prove anything, it demonstrates that for the five test cases, it doesn't matter if you project the tree in one or two steps.

Summary #

This was the second example of a functor implemented in a statically typed object-oriented language, but contrasted with implementations in statically typed functional languages. The concept of a functor translates without much loss of fidelity, but you'll have to write more verbose code. A language like C# isn't optimised for functors or their like; Haskell and F# are.

The purpose of this article series is to show enough examples of functors that you should start to see a pattern. Keep in mind, though, that a functor isn't a design pattern. It's a mathematical concept.

Next: A rose tree functor.

Next Previous

Page 35 of 78

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

ploeh blog danish software design

Deck of cards in Haskell #

Deck of cards in F# #

Summary #

A Haskell perspective #

An F# perspective #

A C# perspective #

Summary #

Task functor #

First functor law for Task #

Second functor law for Task #

Async functor #

First functor law for Async #

Second functor law for Async #

Task and Async isomorphism #

Summary #

Comments

The purpose of code #

Typing speed #

Is more code worse? #

Maintenance burden #

Summary #

Comments

Functor #

First functor law #

Second functor law #

F# #

Haskell #

Summary #

Identity objects #

First functor law #

Second functor law #

F# #

Summary #

Cross-cutting concerns #

No natural clusters #

Introducing a Parameter Object isn't likely to help #

Deodorant #

Guidance, not law #

Summary #

Comments

First functor law #

Second functor law #

Summary #

Visitor #

Functor #

Usage #

Haskell #

F# #

First functor law #

Second functor law #

Summary #

Implementation #

Usage #

Haskell #

F# #

First functor law #

Second functor law #

Summary #