Baseline: An Imperative Solution

Before delving into performance in the various functional solutions I have prepared, let’s first explore how performance looks in an imperative solution. This is something of a scientific experiment, and to be a proper experiment, we need a control—a baseline to compare all the functional results to.

For performance measuring, I’m using Benchmark.NET with .NET 7. For those of you not familiar with this tool, it’s similar in some ways to unit testing, except it’ll compare the performance of several versions of the same code. It runs the same code many times, in order to get a mean of things like time taken to run and the amount of memory used.

The level of performance may vary among versions of .NET too if you try this yourself in something other than .NET 7, as performance improvements are added all the time by Microsoft.

The following are solutions to the two puzzles entirely using imperative-style coding:

// i.e., the definite loop
public int GetFinalFloorNumber(string input)
{
    var floor = 0;
    foreach(var i in input)
    {
        if(i == '(')
            floor++;
        else
            i--;
    }
    return floor;
}

// i.e., the indefinite loop
public int WhichCharacterEntersBasement(string input)
{
    var floor = 0;
    var charNo = 0;

    foreach(var i in input)
    {
        charNo++;
        if(i == '(')
            floor++;
        else
            floor--;

        if(floor == -1)
            return charNo;
    }
}

There might be better solutions, but this one will serve.

Performance Results

Now, these tests were performed for a 7,000-character input on my developer’s laptop, so the actual numbers you might see when trying to replicate this experiment are likely to vary. The main point of the next few sections is to compare the results from the same test setup.

public int GetFinalFloorNumber(string input) =>
    input.Sum(x => x switch
    {
        '(' => 1,
        _ => -1
    });

public int GetFinalFloorNumber(string input) =>
    input.Select(x => x == '(' ? 1 : -1).Sum();

public int GetFinalFloorNumber(string input)
{
    var grouped = input.GroupBy(x => x).ToDictionary(x => x.Key, x => x.Count());
    var answer = grouped['('] - grouped[')'];
    return answer;
}

public int WhichCharacterEntersBasement(string input)
{
    int GetBasementFloor(string s, int currentFloor = 0, int currentChar = 0) =>
        currentFloor == -1
            ? currentChar
            : GetBasementFloor(s[1..], s[0] ==
                '(' ? currentFloor + 1 : currentFloor - 1, currentChar + 1);

    return GetBasementFloor(input);

}

public int WhichCharacterEntersBasement(string input)
{
    var startingInput = new FloorState
    {
        InputString = input,
        CurrentChar = 0,
        CurrentFloor = 0
    };

    var returnValue = startingInput.IterateUntil(x =>
     x with
    {
        CurrentChar = x.CurrentChar + 1,
        CurrentFloor = x.InputString[x.CurrentChar] ==
         '(' ? x.CurrentFloor + 1 : x.CurrentFloor - 1
    }
    , x => x.CurrentFloor == -1);

    return returnValue.CurrentChar;

}

public record FloorState
{
    public string InputString { get; set; }
    public int CurrentFloor { get; set; }
    public int CurrentChar { get; set; }
}

public int WhichCharacterEntersBasement(string input)
{
    var startingInput = (InputString: input, CurrentFloor: 0, CurrentChar: 0);

    var (_, _, currentChar) = startingInput.IterateUntil(x =>
    (
        x.InputString,
        x.InputString[x.CurrentChar] ==
         '(' ? x.CurrentFloor + 1 : x.CurrentFloor - 1,
        x.CurrentChar + 1
    ), x => x.CurrentFloor == -1);

    return currentChar;
}

public class LiftEnumerable : IEnumerable<int>
{
    private readonly string _input;

    public LiftEnumerable(string input)
    {
        this._input = input;
    }

    public IEnumerator<int> GetEnumerator() => new LifeEnumerator(this._input);

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

public class LifeEnumerator : IEnumerator<int>
{
    private int _currentFloorNumber = 0;
    private int _currentCharacter = -1;
    private readonly string input;


    public LifeEnumerator(string input)
    {
        this.input = input;
    }

    public bool MoveNext()
    {
        var startingFloorNumber = this._currentFloorNumber;

        this._currentCharacter++;
        this._currentFloorNumber = startingFloorNumber == -1
            ? -1
            : this.input[this._currentCharacter]

        return startingFloorNumber != -1;
    }

    public void Reset()
    {
        this._currentCharacter= -1;
        this._currentFloorNumber = 0;
    }

    public int Current => this._currentCharacter + 1;

    object IEnumerator.Current => Current;


    public void Dispose()
    {
    }
}


// The actual code call
public int WhichCharacterEntersBasement(string input)
{
    var result = new LiftEnumerable(input).Select(x => x);
    return result.Last();
}

module Advent =
    let calculateFinalFloor start input =
     input
        > Seq.fold (fun acc c -> match c
            with | '(' -> acc+1 | ')' -> acc-1 | _ -> acc) start


    let whichStepIsTheBasement start input =
     input
        |> Seq.scan (fun acc c -> match c with
            | '(' -> acc+1 | ')' -> acc-1 | _ -> acc) start
        |> Seq.findIndex(fun i -> i = -1)

How Functional Should I Make My Codebase?

One of the beauties of functional C# is that the functional content isn’t part of a framework. You can choose how much you want to do functionally or not, and that sliding scale can move just about as far to either side as you want it to.

You can decide to make your entire codebase functional-style. Or restrict it to a single project. A single class. A single function. Or, if necessary, a single line. Mix functional and nonfunctional in the same function. It can be done. As an entirely personal preference, I probably wouldn’t. But the point is you can, and there’s no reason why you shouldn’t.

I’m not a purist. I understand that sometimes in production all sorts of other concerns need to be considered beyond making the code exactly the way you want it.

You need to consider not just where you should be functional, but to what extent. Do you want to go all-out? Use partial application, monads, DUs, and the rest of it. Or you might feel like just using an awful lot of LINQ to replace while loops. That’s fine too—whatever you feel comfortable with. You don’t need to feel like a traitor to the cause.

Another consideration is the level of FP your colleagues are comfortable with. Do consider that however beautiful your functional code may be, it still has to be maintained by the team. I’d argue that monads aren’t really all that hard to understand, but you still need to convince everyone to learn how to use them before they’ll be ready to support code containing them—even if it might be in their best interests. You can lead a horse to water, and all that.

As I’m always saying, at the end of the day, the question you have to ask yourself is “What am I trying to achieve?” Once you’ve answered that truthfully, your decision-making process should be relatively easy.

You could always leave a few copies of this book lying around the office. See what happens. I don’t know how long after the publication date you’re reading this, but there’s even a chance that I may still be around. Feel free to get folks to reach out to me with questions.

How Should I Structure a Functional C# Solution?

You should structure a functional C# solution in classes and folders, largely the same as an existing OOP C# project. Strictly speaking, classes are not a functional concept. If you look at F# projects, they don’t necessarily have classes at all.

You can contain all your code in modules, but they aren’t really the same thing. They’re convenient ways for F# developers to group code. Modules are more like a C# namespace. There’s no functional meaning to a module.

In C#, on the other hand, there have to be classes. There’s no way around it, so that will still have to be a thing you do.

In pure functional-style C#, you could make every class and function static. If you did that, I feel sure you’re going to run into practical problems somewhere, especially when you have to try to interact with a nonfunctional class from NuGet or one of the built-in Microsoft classes.

Lack of dependency injection would also make unit testing far harder. Languages like Haskell get around this by using monads of various kinds. In C#, I’d say make your life easy and just use standard classes and an inversion-of-control (IoC) container, as hopefully you already have been.

A happy medium you could try is the Functional Core, Imperative Shell architectural model. Have all dependency injection carried out in the imperative outer layers; then the functional inner layers can be developed to have all dependencies passed in as parameters.

How Do I Share My Functional Methods Among Applications?

I maintain a set of functional libraries that are full of classes and extension methods, and these provide all my implementations of the monads, DUs, and other useful extension methods I want to use in my code. I usually have a separate project in the solution called Common, where I place anything generic like that. That way, the project can all sit somewhere in the codebase where I can use it, but I don’t necessarily have to look at it again while I’m getting on with my work.

The contents of my Common project are copied from solution to solution for the time being. At some point at work, we’re planning to set up our own local instance of NuGet, and when we do so, we’ll probably have the Common project set up as a consumable NuGet package. That’ll make it easy to distribute bug fixes, improvements, and new features. For now, copying over every time mostly works.

Did You Order This Pizza?

Erm, I’m not sure. That looks like it has got anchovies, so it’s probably not for me. I asked for a meat feast. Let me just check with Liam; I think it might be his. Give me five seconds, I’ll be right back.

How Do I Convince My Teammates to Do This Too?

Good question. When you work out how to do this consistently, let me know how you managed it.

I’ve been giving talks on this subject for a long time now, and reactions to FP seem to fall into one of a few categories:

• OMG! This is the holy grail of development! I want moooooore!

• Great ideas. I don’t want to commit to the whole functional paradigm, but I’m going to take a few bits that are especially cool away with me.

• This is vaguely interesting, but I think I’ll carry on working the way I always have, thanks.

• This is the worst. Boo!

I couldn’t give you any real statistics on how many people fall into each camp, but my feeling is it’s roughly a small number in the first and last group, and the vast majority in the other two in the middle.

That being the case, it’s our job as FP advocates to try to convince others of the benefit to changing their ways. Bear in mind, most human beings are creatures of habit who don’t really want to make huge changes to their daily lives like that, unless there’s a good reason.

The way to convince others also depends on where you work and what your project constraints are. If you’re creating mobile applications where every bit of memory is crucial, or a 3D graphics system for a virtual reality device and can’t afford even the tiniest bit of inefficiency in your code, then you probably will find FP quite a hard sell.

If, however, you don’t do those things, then there may well be a possibility you can convince everyone by talking about the benefits. Just don’t become an FP bore. At some point, it may become obvious there’s no traction with everyone else. Then it’s best to hold off and hope there’s a chance you can win the long game by attrition, rather than via a big, bold frontal attack.

The benefits I’d focus on, in roughly descending order, are as follows:

Reliability

Because functional-style applications are developed around the idea of consistent, predictable results with no side effects, they tend to be more robust and to consequently fail less. FP also massively enables unit testing. So by following this paradigm, you’ll end up with a higher-quality product that fails less. This will save the company a whole load of money in time that would otherwise be required to resolve bugs in production.

Development speed

It’s usually quicker and easier to write code using the functional paradigm (once you’re familiar with it, that is!), and enhancements tend to be especially easy because of the way that functional code is structured and tends to have fewer bugs. I’d talk about the amount of time and money that will be saved in the initial development effort, and in time no longer required following release to squash as many bugs as you might otherwise have to with OOP.

Domain-driven design

Although it’s not a stated goal of the paradigm, functional-style code tends to align well with DDD-style architecture, at least in comparison with OOP. If your team is interested in DDD, it’s perhaps worth mentioning that FP is a good fit in that case.

Microsoft support

It’s a stated goal of the .NET team to support the functional paradigm. Talk about how this style of programming isn’t abusing .NET; it’s actually using it the way it was intended (mostly).

Easy to learn

I hope you feel that way now, after getting to this point in the book. I don’t believe that FP is all that hard to learn, at least not once you dispense with all the formal definitions and scary-sounding terminology. In fact, adopting FP requires less to learn than a new developer faces in learning the object-oriented paradigm. Far more theory needs to be learned to fully master the OOP paradigm than FP. If you find OOP easier to grasp, you may be an experienced developer, well grounded in OOP after many years of experience. I don’t believe it takes as long to become proficient to the same extent with FP as it does with OOP. I’d reassure everyone that the learning overhead isn’t all that big.

Pick and choose

Mention also that you can adopt as much or as little of the paradigm as you want. You don’t need to throw away your old codebase and move to an entirely different one. You can start small by refactoring a single function or even just a single piece of a larger function, and you don’t even have to use monads (although I think you might get great results if you do!).

It’s not new!

It might finally be worth talking about how old the functional paradigm is. Many companies may be reluctant to adopt a new, trendy technology that hasn’t proven it’ll stay around long enough to be worth the investment. That’s a reasonable concern, but FP was first used as a software development concept in the 1960s, and its roots go back to the late 1800s. It’s already been proven a million times over in production environments.

I really wouldn’t necessarily start talking right away about monads, DUs, currying, or anything like that. Keep your points of discussion as familiar as you can.

Aside from talking about it yourself, there’s always this book and many more other good books on the subject. There’s a section coming up shortly in which I’ll recommend the ones I like the most.

Is It Worth Including F# Projects in My Solution?

Whether you include F# projects is up to you. Performance-wise, there’s no real issue with it I’m aware of.

The best usage might be to consider using F# for the deeper, rules-based parts of your codebase—for example, the functions that convert data from one form to another based on a set of business requirements. F# is likely to make those parts neater, more robust, and more efficient. Your code will also be a whole ton more functional than anything C# can do, if that’s what you’re after.

The only thing I’d consider is whether your team is willing to support F#. If so, great. Go for it. If not, get together with the team and have a discussion. That sort of decision needs to be made by everyone.

If your team isn’t comfortable with F#, you can at least take some comfort in the fact that most of the functional paradigm is still here in C#.

Connery, Moore, or Craig?

None of the above, I’m a big fan of Timothy Dalton. He deserved more attention.

How Do I Think Through a Problem Functionally?

There isn’t one way think through a problem functionally any more than there’s one way to develop a piece of software. If it helps, though, I’ll briefly describe my process.

I would start by thinking through the logical steps of the code you’re trying to write. Try splitting it into the steps you’d describe if you were talking through your work with someone else: “First I’d do X, then I’d do Y, then Z.” This isn’t a way you can work especially well with object-oriented-style code, but it’s the best way to split up functional code.

I’d then write each piece of functional code based on those steps.

Wherever possible as well, I’d consider making whatever you’re working on an IEnumerable of some kind, whether that be of primitives, complex objects, or Func delegates. FP is often at its most potent when you’re running list-based operations, as in T-SQL.

I would advise against making chains of functions too long. You want opportunities when you’re developing to be able to examine the previous steps of a complex calculation, to make sure everything is working the way you expect. Splitting up long chains of functions also gives you chances to apply meaningful names to what you store at each stage of the process.

FP supports unit testing very well, so I’d also suggest breaking the entire process into as many smaller functions as you can, and then make sure you’ve tested each one as thoroughly as possible. If you have the advantage of being able to break the steps up logically, use it to the best effect you can.

What If There’s No Way to Make a Bit of Code as High-Performant as I’d Like with Functional-Style Code?

Dude, there are no rules. Make that bit imperative. Have a look at articles like those written by Steve Gordon on how to write high-performance C#. At the end of the day, you have to be pragmatic. I love functional-style code. It has an awful lot of benefit to bring to a project, but if there’s one business-critical function somewhere that is run thousands of times a second and needs every last drop of performance that can be had—do it in the way that makes the best sense. I won’t tell on you.