Skip to content

Functional Programming

Reducing Bugs by Using the Model View Update Pattern

Note: This article is part of the 2025 C# Advent Calendar, so after you're done reading this, keep an eye out for the other cool articles coming out this month!

For those who've followed me for a bit, you know that I'm a big believer that functional programming is a great way of approaching problems.

One thing I've mentioned in my recent presentations is that we can take introductory concepts (pure functions, immutability, composition) and build real world software with them.

In this post, I'm going to show you a pattern that I've recently ported to C#, the Model View Update, also known as The Elm Architecture.

Inspiration of the Pattern

Back in 2017, I came across a new functional language called Elm that took a different approach for web development. At a high level, Elm argues that you can think of an application as four pieces.

  1. The Model - What data are we presenting to the user?
  2. The View - How should we format the model?

At this point, this seems very similar to other MV* patterns (Model View Controller, Model View Presenter, or Model View ViewModel).

The next two parts is what sets this pattern apart from the others.

  1. The Command - What things can the user do on the screen (button clicks, entering text, etc...)
  2. The Update function - Given a Model and a Command, what does the new model look like?

To me, this is an interesting concept because when the user makes changes, the model is being directly manipulated (generally through two-way binding) and then you had to make sure that you didn't put your business rules directly in the UI code. (For those who come from WinForms, how many times did you find business code in the code-behind?).

With this approach, however, we've narrowed down what the UI can do (it can render a model and return a command, but can't directly manipulate the model).

If you think that this approach isn't solid, you might be surprised to know that Elm inspired the creation of the following libraries in the JavaScript ecosystem:

  • ngrx (Angular state management system)
  • redux (React state management system)

I've recently been using this pattern for console applications and have been pleasantly surprised how well it's working out.

In this post, I'll walk you through how we can use this pattern to build out the "Hello World" equivalent application, manipulating a counter.

Implementing the Pattern

Defining the Command

Before we can model the Command, we need to think about what commands we want to support. In our example, let's say that we want the user to be able to do the following:

  • Increment the counter by 2
  • Decrement the counter by 1
  • Reset the counter to 0
  • Quit the application

In the Elm version (and it's equivalent TypeScript definition), a Command looks something like this:

type Command = {tag:'increment', value:2} | {tag:'decrement', value:1} | {tag:'reset'} | {tag:'quit'};

This takes advantage of algebraic data type known as a sum type, where the Command type has one of three different constructors (one called increment, another called decrement, one called reset, and finally, quit).

Even though C# doesn't have sum types (at least not yet), we can mimic this behavior using an abstract class.

1
2
3
4
5
6
7
// Abstract command that uses a string to
// denote which command it is
// (useful for casting later)
public abstract class Command<T> where T:Enum
{
  public abstract T Tag {get; }
}

Defining Commands for Counter

With the Command class defined, let's start implementing the various commands our program can have.

First, we'll define an enum to keep track of the types of Commands. We could omit this and just use strings, but the value of the enum is that we can have C# generate the cases (though we still have to have a default case given the nature of enums).

// Enum to help with exhaustive matching later
// on

public enum CommandType
{
  Increment,
  Decrement,
  Reset,
  Quit,
  Unknown
}

With the enum defined, we can start define the commands, some of which will have more information included (see the IncrementCommand and DecrementCommand).

public class IncrementCommand : Command<CommandType>
{
  public override CommandType Tag => CommandType.Increment;

  // Since some of the commands will have custom values and others not, 
  // we can inject those values through the constructor
  public int Value {get; init;}

  public IncrementCommand(int value)
  {
    Value = value;
  }
}

public class DecrementCommand : Command<CommandType>
{
  public override CommandType Tag => CommandType.Decrement;
  public int Value {get; init;}

  public DecrementCommand(int value)
  {
    Value = value;
  }
}

// In other cases, we don't need
// any other info, so we can inherit and implement the Tag property
public class ResetCommand : Command<CommandType>
{
  public override CommandType Tag => CommandType.Reset;
}

public class QuitCommand : Command<CommandType>
{
  public override CommandType Tag => CommandType.Quit;
}

public class UnknownCommand : Command<CommandType>
{
  public override CommandType Tag => CommandType.Unknown;
}

Implementing the Update Function

Now that we have our various commands created, we can start building out the Update function.

From our earlier description, we know that our Update function has to take in our model (a number) and a Command and then has to return a new model (a number).

// This example is a static method, but let's say that the rules were more complicated, 
// we could inject those into a class and make this method non-static.

public static int Update(int number, Command<CommandType> c)
{
  // I'm leveraging the new switch syntax, 
  // but you can use the original syntax
  // without issues

  return c.tag switch => {
    CommandType.Increment => number + ((IncrementCommand)c).Value,
    CommandType.Decrement => number - ((DecrementCommand)c).Value,
    CommandType.Reset => 0,
    // In the case we're told to quit or we
    // get an unknown command, we'll return
    // the model back
    CommandType.Quit => number,
    CommandType.Unknown => number,
    // Since C# doesn't have exhaustive matching, we still require the default case here
    _ => number
  };
}

Implementing the View Function

At this point, we could go ahead and start writing tests to verify that our model is being updated given the command, but our users are going to be interacting with the application, so let's build that out next.

From before, we know that the View function takes in the model (a number) and it will return a Command. Given that we need to interact with the user, this is an impure function by design, so we shouldn't put our business rules in here.

public static Command<CommandType> View(int model) {
  Console.WriteLine($"Counter: {model}");
  Console.WriteLine("(I)ncrement, (D)ecrement, (R)eset, or (Q)uit");

  return ConvertStringToCommand(Console.ReadLine());
}

// Even though this is called by the View
// function, this is a Pure function
// because it only depends upon a string
// for its logic
private static Command<CommandType> ConvertStringToCommand(string s) {
  return (s ?? "").Trim().ToLower() switch {
    "i" => new IncrementCommand(2), // will increment by 2
    "d" => new DecrementCommand(1), // will decrement by 1
    "r" => new ResetCommand(),
    "q" => new QuitCommand(),
    _ => new UnknownCommand()
  };
}

Wiring Everything Together

Now that we have our Model (a number), the View function, an Update function, and our list of Commands, we can wire everything together.

public static class Framework
{
  public static void Run<TModel, TCommandType>(
      Func<TModel, Command<TCommandType>> view,
      Func<TModel, Command<TCommandType>, TModel> update,
      TModel model)
  where TCommandType : Enum
  {
    // We need the Enum to have a Quit option
    // defined, otherwise, we won't know when
    // to quit the application.
    if (!Enum.IsDefined(typeof(TCommandType), "Quit"))
    {
      throw new InvalidOperationException("Command must have a Quit option");
    }
    var quitCommand = Enum.Parse(typeof(TCommandType), "Quit");

    // Getting our initial state
    var currentModel = model;
    Command<TCommandType> command;

    // While command isn't Quit
    do
    {
      // Clear the screen
      Console.Clear();
      // Get the command from when we render the view
      command = view(currentModel);
      // Get the new model from update
      currentModel = update(currentModel, command);
    } while (!command.Tag.Equals(quitCommand));
  }
}

Final Version

With the Framework.Run function defined, we can invoke it via our Program.cs file.

You can find the working version below (or you can clone a copy from GitHub)

Program.cs
internal class Program
{
  private static void Main(string[] args)
  {
    var startCounter = 0;
    Framework.Run(View, CounterRules.Update, startCounter);
  }

  public static Command<CommandType> View(int model)
  {
    Console.WriteLine("Counter: " + model);
    Console.WriteLine("Please enter a command:");
    Console.WriteLine("(I)ncrement, (D)ecrement, (R)eset, (Q)uit");
    var input = Console.ReadLine() ?? "";
    return ConvertStringToCommand(input);
  }

  private static Command<CommandType> ConvertStringToCommand(string s) => (s ?? "").ToLower().Trim() switch
  {
    "i" => new IncrementCommand(2),
    "d" => new DecrementCommand(1),
    "r" => new ResetCommand(),
    "q" => new QuitCommand(),
    _ => new UnknownCommand(),
  };
}
CounterRules.cs
public static class CounterRules
{
  public static int Update(int model, Command<CommandType> c)
  {
    return c.Tag switch
    {
      CommandType.Increment => model + (c as IncrementCommand)!.Value,
      CommandType.Decrement => model - (c as DecrementCommand)!.Value,
      CommandType.Reset => 0,
      CommandType.Quit => model,
      CommandType.Unknown => model,
      _ => model
    };
  }
}
Commands.cs
public enum CommandType
{
  Increment,
  Decrement,
  Reset,
  Quit,
  Unknown
}

public class IncrementCommand : Command<CommandType>
{
  public override CommandType Tag => CommandType.Increment;
  public int Value { get; init; }
  public IncrementCommand(int value)
  {
    Value = value;
  }
}

public class DecrementCommand : Command<CommandType>
{
  public override CommandType Tag => CommandType.Decrement;
  public int Value { get; init; }
  public DecrementCommand(int value)
  {
    Value = value;
  }
}

public class ResetCommand : Command<CommandType>
{
  public override CommandType Tag => CommandType.Reset;
}

public sealed class QuitCommand : Command<CommandType>
{
  public override CommandType Tag => CommandType.Quit;
}

public sealed class UnknownCommand : Command<CommandType>
{
  public override CommandType Tag => CommandType.Unknown;
}
Framework.cs
public abstract class Command<T> where T : Enum
{
  public abstract T Tag { get; }
}

public static class Framework
{
  public static void Run<TModel, TCommandType>(
      Func<TModel, Command<TCommandType>> view,
      Func<TModel, Command<TCommandType>, TModel> update,
      TModel model)
  where TCommandType : Enum
  {
    if (!Enum.IsDefined(typeof(TCommandType), "Quit"))
    {
      throw new InvalidOperationException("Command must have a Quit option");
    }
    var quitCommand = Enum.Parse(typeof(TCommandType), "Quit");
    var currentModel = model;
    Console.Clear();
    var command = view(currentModel);
    do
    {
      currentModel = update(currentModel, command);
      Console.Clear();
      command = view(currentModel);
    } while (!command.Tag.Equals(quitCommand));
  }
}

Conclusion

In this post, we built out a basic application using the Model View Update pattern that was first introduced by the Elm language. We also implemented a basic sum type, Command, using an abstract class that was then constrained to particular CommandTypes.

Simplifying Console Logic with the Model-View-Update

When I first started dabbling in Functional Programming, a new front-end language called Elm had been released and it was generating a lot of buzz about how it simplified web development by introducing four parts (i.e., The Elm Architecture" (TEA)) that provided a mental model when creating web pages. This way of thinking was so powerful that it inspired popular libraries like Redux and ngrx which took this architecture mainstream.

Spilling the TEA

At a high level, the architecture has four parts:

  1. Model -> What are we rendering?
  2. View -> How do we want to render it?
  3. Update -> Given the current model and a Command, what's the new model?
  4. Command -> What did the user do?

To help make this a bit more clear, let's define some types for these parts and see how they would work together

type Model = any;
type View = (m:Model)=>Promise<Command>;
type Update = (m:Model, c:Command)=>Model;
type Command = "firstOption" | "secondOption" ... | 'quit';

async function main(model:Model, view:View, update:Update): Promise<void>{
  const command = await view(model);
  if (command === 'quit'){
    return;
  }
  const newModel = update(model, command);
  return main(newModel);
}

With some types in play, let's go ahead and build out a small application, a counter (the "Hello World" for Elm).

Building a Counter

First, we need to figure out what the model will be. Since we're only keeping tracking of a number, we can define our model as a number.

type Model = number;

Next, we need to define what the user can do. In this case, they can either increment, decrement, or quit so let's set the command up.

type Command = 'increment' | 'decrement' | 'quit';

Now that we have Command, we can work on the update function. Given the type signature from before, we know its going to look like this:

1
2
3
function update(model:Model, command:Command): Model {
  // logic
}

We can leverage a switch and put in our business rules

1
2
3
4
5
6
7
function update(model:Model, command:Command): Model {
  switch(command){
    case 'increment': return model+1;
    case 'decrement': return model-1;
    case 'quit': return model;
  }
}

Finally, we need to define our view function. Like before, we can get the skeleton for the function based on the types from earlier.

1
2
3
async function view(model:Model): Promise<Command>{

}

Let's update the function with our rendering logic

1
2
3
4
async function view(model:Model): Promise<Command>{
  console.log("Counter:", model);
  console.log("Choose to (i)ncrement, (d)ecrement, or (q)uit");
}

We've got our render up and running, however, we need to get input from the user. Since we're working within Node, we could use readline, however, I've recently been using @inquirer/prompts and find it to be a nice abstraction to use. So let's use that package.

import {input} from "@inquirer/prompts";

async function getChoice(): Promise<Command>{
  console.log("Choose to (i)ncrement, (d)ecrement, or (q)uit");
  const validChoices = ["i", "d", "q"];
  const validator = (s:string) => validChoices.include(s?.trim().toLowerCase());
  const selection = await input({message:message, validate:validator});
  if (selection === "i") {
    return "increment";
  } else if (selection === "d"){
    return "decrement";
  } else {
    return "terminate"
  }
}
// Let's change the view function to use getChoice

async function view(model:Model): Promise<Command>{
  console.log("Counter:", model);
  return getChoice();
}

With these pieces defined, we can use the main function from before.

async function main(model:Model, view:View, update:Update): Promise<void>{
  const command = await view(model);
  if (command === 'quit'){
    return;
  }
  const newModel = update(model, command);
  return main(newModel);
}

// Invoking Main
main(10, view, update);

Starting Back at Zero

Now that we have increment and decrement working, it would be nice to be able to reset the counter without having to restart the application, so let's see how bad that would be.

First, we need to add a new choice to Command (called reset). This will force us to update the rest of the code that's working with Command.

type Command = "increment" | "decrement" | "reset" | "quit";

Next, we need to update the update function so it knows how to handle a reset command. In our case, we need to set the model back to zero.

1
2
3
4
5
6
7
8
function update(model:Model, command:Command): Model {
  switch(command){
    case 'increment': return model+1;
    case 'decrement': return model-1;
    case 'reset': return 0;
    case 'quit': return model;
  }
}

At this point, the application knows how to handle the new Command, however, we need to update our view function to allow the user to select reset.

async function view(model:Model): Promise<Command>{
  console.log("Counter:", model);
  return getChoice();
}

async function getChoice(): Promise<Command>{
  // updating the console.log
  console.log("Choose to (i)ncrement, (d)ecrement, (r)eset, or (q)uit"); 
  const validChoices = ["i", "d", "r", "q"];
  const validator = (s:string) => validChoices.include(s?.trim().toLowerCase());
  const selection = await input({message:message, validate:validator});
  if (selection === "i") {
    return "increment";
  } else if (selection === "d"){
    return "decrement";
  } else if (selection === "r"){
    return "reset";
  } else {
    return "terminate"
  }
}

What's Next?

Now that we have have a working version, you could start implementing some fun functionality. For example, how would you allow someone to set how much to increment or decrement by? What if you needed to keep track of previous values (i.e., maintaining history)? I highly encourage you trying this out with a simple kata (for example, how about giving Mars Rover a try?)

Full Working Solution

import {input} from "@inquirer/prompts";

type Model = number;
type Command = "increment" | "decrement" | "reset" | "quit";
type View = (model:Model) => Promise<Command>;
type Update = (model:Model, command:Command) => Model;

function update(model:Model, command:Command): Model {
  switch(command){
    case "increment": return model+1;
    case "decrement": return model-1;
    case "reset": return 0;
    case "quit": return model;
  }
}

function view(model:Model): Promise<Command>{
  console.log(`Counter:${model}`);
  return getChoice();
}

async function getChoice(): Promise<Command>{
  console.log("Choose to (i)ncrement, (d)ecrement, (r)eset, or (q)uit"); 
  const validChoices = ["i", "d", "r", "q"];
  const validator = (s:string) => validChoices.include(s?.trim().toLowerCase());
  const selection = await input({message:message, validate:validator});
  if (selection === "i") {
    return "increment";
  } else if (selection === "d"){
    return "decrement";
  } else if (selection === "r"){
    return "reset";
  } else {
    return "terminate"
  }
}

async function main(model:Model, view:View, update:Update): Promise<void>{
  const command = await view(model);
  if (command === 'quit'){
    return;
  }
  const newModel = update(model, command);
  return main(newModel, view, update);
}

main(10, view, update);

Functional Design Patterns - Missing Values

When working in software, a common problem that we run into is what should we do if we can't get a value or compute an answer.

For example, let's say that you go to the library to checkout the latest book from Nathalia Holt, but when you search for it, you realize that they don't have any copies in stock.

How do you handle the absence of value? From an Object Oriented Programming (OOP), you might be able to leverage a reasonable default or the Null Object Pattern. Another approach would be to return to always return a list and if there are no values, then the list would be empty.

No matter the choice you make, we need some way to model the lack of a value. Tony Hoare referred to null as his billion dollar mistake as its inclusion in languages have created countless bugs and errors.

In most functional languages, the idea of null doesn't exist, so how do they handle missing values?

Revisiting Functions

In a previous post, we mention that a function is a mapping between two sets such that every element on the left (first set) is mapped to a single element on the right (the second set). So what happens when we have a mapping that's not a function?

In these cases, we have two solutions to choose from:

  1. Restrict the function input to only be values that can be mapped (e.g., restrict the domain)
  2. Expand the possible values that the function can map to (e.g., expand the range)

When refactoring a mapping, I tend to stick with option 1 because if we can prevent bad data from being created or passed in, that's less error handling that needs to be written and it becomes simpler to reason about. However, there are plenty of times where our type system (or business rules) can't enforce the valid inputs.

Number Math

Let's say that we're working on a "word calculator" where the user can enter a phrase like "one thousand twelve" and it returns "1012" as output. If we think about our input set (domain) and outputs, we would have the following (mapping from string to number).

Mapping from string to number

The issue is that we can't guarantee that the strings the user gives us would represent a number (for example, how would you convert "platypus" to a number?)

Since we can't restrict the input, we have to expand the output. So let's update our output to be number | 'invalid'

Mapping from string to number or 'invalid'

With this change, anytime we call convertToNumber, we'll need to add some handling on what to do if the output is invalid.

Here's some pseudocode of what this mapping could look like

type WordCalculatorResult = number | 'invalid'

function convertToNumber(phrase:string): WorldCalculatorResult {
    if (phrase === 'one') return 1;
    if (phrase === 'two') return 2;
    // ... other logic
    return 'invalid';
}

console.log(convertToNumber('one')); // prints "1";
console.log(convertToNumber('kumquats')) // prints invalid

Leaky Context

So far, so good as we have a function that converts words to numbers. Let's now say that we want to square a number. Writing such a function is straightforward.

1
2
3
function square (x:number): number {
    return x*x;
}

With both convertToNumber and square defined, let's try to combine these together:

Compilation error when combining convertToNumber and Square

This doesn't work because convertToNumber can return invalid which there's no way for the square function to work with that. Due to this limitation, we could rewrite the code to check for invalid before calling square.

1
2
3
4
5
const result = convertToNumber('one');

if (result !== 'invalid') {
    console.log(square(result));
}

This approach will work, but the downside is that we need to add error handling logic in our pipeline now. If this was the only place where it's being used, then it's not too bad. However, if we were using convertToNumber in multiple places, then we have to remember to add this error handling logic. In fact, we would have almost the same if check everywhere.

Let's take a look at a different way of solving this problem by using the Maybe type.

Introducing the Maybe Type

In our original approach, we already had a type called WordCalculatorResult for the computation. Instead of it being a number or invalid, we could instead create a new type, called Maybe that looks like the following:

type Maybe<T> = { label: 'some', value: T } | { label: 'none' }

By leveraging generics and tagged unions, we have a way to represent a missing value for any type. With this new definition, we can rewrite the convertToNumber function to use the Maybe type.

1
2
3
4
5
6
function convertToNumber(phrase:string): Maybe<number> {
    if (phrase === 'one') return {label:'some', value:1};
    if (phrase === 'two') return {label:'some', value:2};
    // other logic
    return {label:'none'};
}

I don't know about you, but typing out {label:'some'} is going to get tiring, so let's create two helper functions, some and none that handle putting the right label if we have a value or not.

1
2
3
4
5
6
7
function some<T>(value:T): Maybe<T> {
    return {label:'some', value};
}

function none<T>(): Maybe<T> {
    return {label:'none'};
}

Which allows us to replace all of the {label:'some', value:x} with some(x) and {label:'none'} with none().

1
2
3
4
5
6
function convertToNumber(phrase:string): Maybe<number> {
    if (phrase === 'one') return some(1);
    if (phrase === 'two') return some(2);
    // other logic
    return none();
}

Now that convertToNumber returns a Maybe, our pipeline would look like the following:

1
2
3
4
5
const result = convertToNumber('one');

if (result.label === 'some') { // checking if we're a Some type
    console.log(square(result.value));
}

Introducing Transformations With Map

Now the problem we're wanting to solve is to get rid of having to do an if check on some in order to call the square function. Given that we're wanting to transform our number into a different number, we can write another function, called map that takes two parameters: the Maybe we want transformed and the function that knows how to transform it. Let's take a look at how to write such a function.

1
2
3
4
5
6
7
function map<T,U>(m:Maybe<T>, f:(t:T)=>U): Maybe<U> {
    if (m.label === 'some') { // Is Maybe a Some?
        const transformedValue = f(m.value); // Grab the value and transform it by calling function f
        return some(transformedValue) // return a new Maybe with the transformed value
    }
    return none(); // Return none since there's no value to transform
}

With map implemented, let's update our code to use it!

const convertResult = convertToNumber('one'); // 
const transformedResult = map(convertResult, square);

if (transformedResult.label === 'some') { // checking if we're a Some type
    console.log(transformedResult.value);
}

/* The above could be simplified as the following
const result = map(convertToNumber('one'), square);
if (result.label === 'some') {
  console.log(result.value)
}
*/

Thanks to map and Maybe, we're able to write two pure functions (convertToNumber and square), glue them together, and delegate our error handling to one spot (instead of having to sprinkle this throughout the codebase).

Calling Side Affects Using Tee

With the addition of map, we've now simplified our if check to only call console.log now (instead of calling the square function then console.log). If we wanted to truly get rid of this if statement, then we need a way to invoke the console.log as a side effect. We don't want to combine console.log into square because square is business rules and we don't want to add side effect logic to our business rules.

Similar to what we did for map, let's add a new function, called tee, that takes in three arguments: a Maybe, a function to call if the Maybe has a value, and then a function to call if Maybe doesn't have a value.

Let's take a look at what an implementation would look like:

/*
 Inputs:
    m: A Maybe to work with
    ifSome: A function that takes in a T (which comes from the Maybe) and returns void
    ifNone: A function that takes no inputs and returns void
 Outputs:
    Returns m so that we can continue chaining calls
*/
function tee<T>(m:Maybe<T>, ifSome:(t:T)=>void, ifNone:()=>void): Maybe<T> {
    if (m.label === 'some') {
        ifSome(m.value);
    } else {
        ifNone();
    }
    return m;
}

With tee implemented, we can update our pipeline to take advantage of it:

const convertResult = convertToNumber('one'); // 
const transformedResult = map(convertResult, square);

const ifSome = (t:number) => console.log(`Result is ${t}`);
const ifNone = () => console.log('Failed to calculate result.');

tee(transformedResult, ifSome, ifNone);

// if we wanted to get rid of the temp values, we could do the following
// const result = tee(map(convertToNumber('one'), square)), ifSome, ifNone);

Cleaning Up by using an Object

We've now centralized the if logic to the functions that work on Maybes which is helpful, but as we're already seeing, the code can be hard to parse as you need to read from the outside in (which is very Clojure or Scheme in nature).

Instead of building up functions this way, we can instead create a TypeScript class and use a fluent interface pattern by doing the following:

export class Maybe<T>
{
  private constructor(private readonly value:T|undefined=undefined){}
  map<U>(f:(t:T)=>U): Maybe<U> {
    return this.value !== undefined ? Maybe.some(f(this.value)) : Maybe.none();
  }
  tee(ifSome:(t:T)=>void, ifNone:()=>void) {
    if (this.value !== undefined) {
      ifSome(this.value);
    } else {
      ifNone();
    }
    return this;
  }
  static some<T>(value:T): Maybe<T> {
    return new Maybe(value);
  }
  static none<T>(): Maybe<T> {
    return new Maybe();
  }
}
// Defined in index.ts
function convertToNumber(phrase:string): Maybe<number> {
    if (phrase === 'one') return Maybe.some(1);
    if (phrase === 'two') return Maybe.some(2);
    // other logic
    return Maybe.none();
}

function square(x:number): number {
    return x*x;
}

// By using the fluent interface pattern, we can chain methods together and have this code read
// more naturally
convertToNumber("one")
  .map(square)
  .tee(
    (v)=> `Answer is ${v}`, 
    () => "Unable to calculate result"
  );

Wrapping Up

When writing software, a common problem we run into is what to do when we can't calculate a value or a result. In this post, we looked at techniques to restrict the function's input or expand their output to handle scenarios. From there, we looked into a type called Maybe and how it can represent the absence of value, but still provide a way to remove having to explicitly write error handling code by consolidating the checks into a map call. Lastly, we look into taking the various functions that we wrote and combine them into a formal Maybe class that allows us to leverage a fluent interface and chain our interactions together.

Functional Design Patterns - Reduce and Monoids

When learning about a loops, a common exercise is to take an array of elements and calculate some value based on them. For example, let's say that we have an array of numbers and we want to find their sum. One approach would be the following:

1
2
3
4
5
const values = [1, 2, 3, 4, 5];
let total = 0;
for (const val in values) {
    total += val;
}

This code works and we'll get the right answer, however, there's a pattern sitting here. If you find yourself writing code that has this shape (some initial value and some logic in the loop), then you have a reducer in disguise.

Let's convert this code to use the reduce function instead.

const values = [1, 2, 3, 4, 5];
const total = values.reduce((acc, curr) => acc + curr, 0);

The reduce function takes two parameters, the reducer and the initial value. For the initial value, this is the value that the result should be if the array is empty. Since we're adding numbers together, zero makes the most sense.

The reducer, on the other hand, says that if you give me the accumulated result so far (called acc in the example) and an element from the array (called curr in the above example), what's the new accumulation?

Reduce is an extremely powerful tool (in fact, I give a presentation where we rewrite some of C#'s LINQ operators as reduce).

But there's another pattern sitting here. If you find that the initial value and elements of the array have the same type, you most likely have a monoid.

Intro to Monoids

The concept of Monoid comes from the field of category theory where a Monoid contains three things

  1. A set of values (you can think about this as a type)
  2. Some binary operation (e.g., a function that takes two inputs and returns a single output of said type)
  3. Some identity element such that if you pass the id to the binary operation, you get the other element back.

There's a lot of theory sitting here, so let's put it in more concrete terms.

If we have a Monoid over the a type A, then the following must be true:

1
2
3
4
5
6
7
8
function operation<A>(x:A, y:A): A 
{
    // logic for operation
}
const identity: A = // some value of type A
operation(x, identity) === operation(identity, x) === x

operation(x, operation(y, z)) === operation(operation(x, y), z)

Here's how we would define such a thing in TypeScript.

1
2
3
4
export interface Monoid<A>{
    operation: (x:A, y:A)=> A;
    identity:A;
}

Exploring Total

With more theory in place, let's apply it to our running total from before. It turns out that addition forms a Monoid over positive numbers with the following:

1
2
3
4
const additionOverNumber: Monoid<number> = {
    identity: 0,
    operation: (a:number, b:number) => a+b;
}

Wait a minute... This looks like what the reduce function needed from before!

In the case where we have a Monoid, we have a way of reducing an array to a single value for free because of the properties that Monoid gives us.

Exploring Booleans

Thankfully, we're not limited to just numbers. For example, let's take a look at booleans with the && and || operators.

In the case of &&, that's our operation, so now we need to find the identity element. In other words, what value must id be if the following statements are true?

1
2
3
const id: boolean = ...
id && true === true
id && false === false

Since id has to be a boolean, the answer is true. Therefore, we can define our Monoid like so

1
2
3
4
const AndOverBoolean: Monoid<boolean> = {
    identity: true,
    operation: (a:boolean, b:boolean) => a && b
}

With this monoid defined, let's put it to use. Let's say that we wanted to check if every number in a list is even. We could write the following:

1
2
3
const values = [1, 2, 3, 4, 5];

const areAllEven = values.map(x=>x%2===0).reduce(AndOverBoolean.operation, AndOverBoolean.identity);

Huh, that looks an awful lot like how we could have used every.

const values = [1, 2, 3, 4, 5];
const areAllEven = values.every(x=>x%2===0);

Let's take a look at the || monoid now. We have the operation, but we now we need to find the identity. In other words, what value must id be if the following statements are true?

1
2
3
const id: boolean = ...;
id || true === true
id || false === false

Since id has to be a boolean, the answer is false. Therefore, we can define our monoid as such.

1
2
3
4
const OrOverBoolean: Monoid<boolean> = {
    identity: false,
    operation: (x:boolean, y:boolean) => x || y
} 

With this monoid defined, let's put it to use. Let's say that we wanted to check if some number in a list is even. We could write the following:

1
2
3
const values = [1, 2, 3, 4, 5];

const areAllEven = values.map(x=>x%2===0).reduce(OrOverBoolean.operation, OrOverBoolean.identity);

Similar to the AndOverBoolean, this looks very similar to the code we would have written if we had leveraged some.

1
2
3
const values = [1, 2, 3, 4, 5];

const isAnyEven = values.some(x => x%2 === 0);

Wrapping Up

When working with arrays of items, it's common to need to reduce the list down to a single element. You can start with a for loop and then refactor to using the reduce function. If the types are all the same, then it's likely that you also have a monoid, which can give you stronger guarantees about your code.

Functional Foundations - Functions

When leveraging functional programming, you're not going to go far without functions. It's literally in the name.

In this post, let's take a deeper look at what functions are and some of the benefits we gain.

What is a Function?

When we talk about functions, we're not talking about a programming construct (like the function keyword), but instead we're talking about functions from mathematics.

As such, a function is a mapping from two sets such that for every element of the first set, it maps to a single element in the second set.

Words are cool, but pictures are better. So let's look at the mapping for the square function.

Mapping for the Square Function

In this example, we have an arrow coming from an element on the left where it maps to an element on the right. To read this image, we have a mapping called Square that maps all possible numbers to the set of positive numbers. So -3 maps to 9 (-3-3), 2 maps to 4 (22), so on and so forth.

To check if our mapping is a function, we need to check that every element on the left is mapped to a single element on the right. If so, then we've got a function!

Sounds easy, right? Let's take a look at a mapping that isn't a function.

Love in the Air?

When working with dates, it's common to figure out how many days are in the month. Not only does this help with billable days, but it also makes sure that we don't try to send invoices on May 32nd.

So let's take a look at a mapping from month to the number of days it has.

Broken Mapping for the Days In Month Function

Looking at the mapping, we can tell that January, March, May map to 31, April and June both map to 30. But take a look at February. It's got two arrows coming out of it, one to 28 and the other to 29. Because there are two arrows coming out, this mapping isn't a function. Let's try to implement this mapping in TypeScript.

type Month = "Jan" | "Feb" | "Mar" | "Apr"
           | "May" | "Jun" | "Jul" | "Aug"
           |"Sept" | "Oct" | "Nov" | "Dec";

type DaysInMonth = 28 | 29 | 30 | 31;

function getDaysInMonth(month: Month): DaysInMonth {
  switch (month) {
    case "Jan":
    case "Mar":
    case "May":
    case "Jul":
    case "Oct":
    case "Dec":
      return 31;

    case "Feb":
      // what should this be?

    case "Apr":
    case "Jun":
    case "Aug":
    case "Sept":
    case "Nov":
      return 30;
  }
}

We can't return 28 all the time (we'd be wrong 25% of the time) and we can't return 29 all the time (as we'd be wrong 75% of the time). So how do we know? We need to know something about the year. One approach would be to check if the current year is a leap year (algorithm).

function isLeapYear(): boolean {
  const year = new Date().getFullYear();
  if (year % 400 === 0) return true;
  if (year % 100 === 0) return false;
  if (year % 4 === 0) return true;
  return false;
}

// Updated switch
case 'Feb':
  return isLeapYear() ? 29 : 28;

The problem with this approach is that the determination of what to return isn't from the function's inputs, but outside state (in this case, time). So while this "works", you can get bit when you have tests that start failing when the calendar flips over because it assumed that February always had 28 days.

If we look at the type signature of isLeapYear, we can see that it takes in no inputs, but returns a boolean. How can that be possible except if it always returned a constant value? This is a clue that isLeapYear is not a function.

The better approach is to change our mapping to instead of taking just a month name, it takes two arguments, a monthName and year.

Fixed Mapping For Days In Month

With this new mapping, our implementation would look like the following:

function isLeapYear(year:number): boolean {
  if (year % 400 === 0) return true;
  if (year % 100 === 0) return false;
  if (year % 4 === 0) return true;
  return false;
}

function getDaysInMonth(month: Month, year:number): DaysInMonth {
  const isLeap = isLeapYear(year);
  switch (month) {
    case "Jan":
    case "Mar":
    case "May":
    case "Jul":
    case "Oct":
    case "Dec":
      return 31;

    case "Feb":
      return isLeap ? 29 : 28

    case "Apr":
    case "Jun":
    case "Aug":
    case "Sept":
    case "Nov":
      return 30;
  }
}

Benefits of Functions

Now that we've covered what functions are and aren't, let's cover some of the reasons why we prefer functions for our logic.

First, mappings help us make sure that we've covered all our bases. We saw in the getDaysInMonth function we found a bug for when the month was February. Mappings can also be great conversation tools with non-engineers as they're intuitive to understand and to explain.

Second, functions are simple to test. Since the result is based solely on inputs, they are great candidates for unit testing and require little to no mocking to write them. I don't know about you, but I like simple test cases that help us build confidence that our application is working as intended.

Third, we can combine functions to make bigger functions using composition. At a high level, composition says that if we have two functions f and g, we can write a new function, h which takes the output of f and feeds it as the input for g.

Sounds theoretical, but let's take a look at a real example.

In the Mars Rover kata, we end up building a basic console application that takes the input from the user (a string) and will need to convert it to the action that the rover takes.

In code, the logic looks like the following:

1
2
3
let rover:Rover = {x:0, y:0, direction:'North'};
const action = input.split('').map(convertStringToCommand).map(convertCommandToAction);
rover = action(rover);

The annoying part is that we're iterating the list twice (once for each map call), and it'd be nice to get it down to a single iteration. This is where composition helps.

When we're running the maps back-to-back, we're accomplish the following workflow

Input to Command to Action Mapping

Because each mapping is a function, we can compose the two into a new function, stringToActionConverter.

1
2
3
4
5
6
// using our f and g naming from earlier, convertString is f, convertCommand is g
const stringToActionConverter = (s:string)=>convertCommandToAction(convertStringToCommand(s));

let rover = {x:0, y:0, direction:'North'}
const action = input.split('').map(stringToActionConverter);
rover = action(rover);

Why Not Function All the Things?

Functions can greatly simplify our mental model as we don't have to keep track of state or other side effects. However, our applications typically deal with side affects (getting input from users, reading from files, interacting with databases) in order to do something useful. Because of this limitation, we strive to put all of our business rules into functions and keep the parts that interact with state as dumb as possible (that way we don't have to troubleshoot as much).

What I've found is that when working with applications, you end up with a workflow where you have input come in, gets processed, and then the result gets outputted.

Here's what an example workflow would look like

// Logic to determine the 'FizzBuzziness' of a number
function determineFizzBuzz(input:number): string {
  if (input % 15 === 0) return 'FizzBuzz';
  if (input % 3 === 0) return 'Fizz';
  if (input % 5 === 0) return 'Buzz';
  return `${input}`;
}

function workflow(): void {
  // Input Boundary
  var prompt = require('prompt-sync')();
  const input = prompt();

  // Business Rules
  const result = (+input) ? `${input} FizzBuzz value is ${determineFizzBuzz(+input)}` : `Invalid input`;

  // Output boundary
  console.log(result);
}

What's Next?

Now that we have a rough understanding of functions, we can start exploring what happens when things go wrong. For example, could there have been a cleaner way of implementing the business rules of our workflow?

Today I Learned - Iterating Through Union Types

In a previous post, we cover on how using union types in TypeScript is a great approach for domain modeling because it limits the possible values that a type can have.

For example, let's say that we're modeling a card game with a standard deck of playing cards. We could model the domain as such.

1
2
3
4
5
type Rank = "Ace" | "Two" | "Three" | "Four" | "Five" | "Six" | "Seven"
           | "Eight" | "Nine" | "Ten" |"Jack" | "Queen" | "King"
type Suite = "Hearts" | "Clubs" | "Spades" | "Diamonds"

type Card = {rank:Rank; suite:Suit}

With this modeling, there's no way to create a Card such that it has an invalid Rank or Suite.

With this definition, let's create a function to build the deck.

function createDeck(): Card[] {
  const ranks = ["Ace", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Jack", "Queen", "King"];
  const suites = ["Hearts", "Clubs", "Spades", "Diamonds"];

  const deck:Card[] = [];
  for (const rank of ranks) {
    for (const suite of suites) {
      deck.push({rank, suite});
    }
  }
  return deck;
}

This code works, however, I don't like the fact that I had to formally list the option for both Rank and Suite as this means that I have two different representtions for Rank and Suite, which implies tthat if we needed to add a new Rank or Suite, then we'd need to add it in two places (a violation of DRY).

Doing some digging, I found this StackOverflow post that gave a different way of defining our Rank and Suite types. Let's try that new definition.

1
2
3
4
const ranks = ["Ace", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Jack", "Queen", "King"] as const;
type Rank = typeof ranks[number];
const suites = ["Hearts", "Clubs", "Spades", "Diamonds"] as const;
type Suite = typeof suites[number]

In this above code, we're saying that ranks cannot change (either by assignment or by operations like push). With that definition, we can say that Rank is some entry in the ranks array. Similar approach for our suites array and Suite type.

I prefer this approach much more because we have our ranks and suites defined in one place and our code reads cleaner as this says Here are the possible ranks and Rank can only be one of those choices.

Limitations

The main limitation is that it only works for "enum" style unions. Let's change example and say that we want to model a series of shapes with the following.

1
2
3
4
5
type Circle = {radius:number};
type Square = {length:number};
type Rectangle = {height:number, width:number}

type Shape = Circle | Square | Rectangle

To use the same trick, we would need to have an array of constant values. However, we can't have a constant value for any of the Shapes because there are an infinite number of valid Circles, Squares, and Rectangles.

Exploring Map with Property Based Thinking

When thinking about software, it's natural to think about the things that it can do (its features like generating reports or adding an item to a cart).

But what about the properties that those actions have? Those things that are always true?

In this post, let's take a look at a fundamental tool of functional programming, the map function.

All the code examples in this post will be using TypeScript, but the lessons hold for other languages with Map (or Select if you're coming from .NET).

Examining Map

In JavaScript/TypeScript, map is a function for arrays that allow us to transform an array of values into an array of different values.

For example, let's say that we have an array of names and we want to ensure that each name is capitalized, we can write the following:

1
2
3
4
5
6
const capitalize = (name:string): string => {
  return n[0].toUpperCase() + n.substring(1);
}
const names = ["alice","bob","charlotte"];

const properNames = names.map(capitalize);

In our example, as long as we have a pure function that takes a string and returns a new type, then map will work.

What Does Map Guarantee?

Map is a cool function because it has a lot of properties that we get for free.

  1. Maintains Length - If you call map on an array of 3 elements, then you'll get a new array with 3 elements. If you call map on an empty array, you'll get an empty array.

  2. Maintains Type - If you call map on array of type T with a function that goes from T to U, then every element in the new array is of type U.

  3. Maintains Order - If you call map on array with one function, then call map with a function that "undoes" the original map, then you end up with the original array.

Writing Property Based Tests

To prove these properties, we can write a set of unit tests. However, it would be hard to write a single test that that covers a single property.

Most tests are example based in the sense that for a specific input, we get a specific output. Property based tests, on the other hand, uses random data and ensures that a property holds for all inputs. If it finds an input where the property fails, the test fails and you know which input caused the issue.

Most languages have a tool for writing property-based tests, so we'll be using fast-check for writing property based tests and jest for our test runner

Checking Length Property

import fc from "fast-check";

describe("map", () => {
  it("maintains length", () => {
    // This is known as the identify function
    // as it returns whatever input it received
    const identity = <T>(a: T): T => a;

    // Fast Check assert that the following holds for all arrays of integers
    fc.assert(
      // data is the array of numbers
      fc.property(fc.array(fc.integer()), (data): void => {
        // We call the map function with the identify function
        const result = data.map(identity);

        // We make sure that our result has the same length
        expect(result).toHaveLength(data.length);
      })
    );
  });

If we run this test, we'll end up passing. But what is the value of data?

By adding a console.log in the test, we'll see the following values printed when we run the test (there are quite a few, so we'll examine the first few).

console.log
    [
       2125251991,  1334674146,
      -1531633149,   332890473,
       1313556939,   907640912,
        887735692, -1979633703,
       -259341001,  2015321027
    ]

  console.log
    [ 1307879257 ]

  console.log
    []

  # quite a few more...

Checking Type Property

We've proven that the length property is being followed, so let's look at how we can ensure that result has the right type.

To keep things simple, we're going to start with a string[] and map them to their lengths, yielding number[].

If map is working, then the result should be all numbers.

We can leverage typeof to check the type of each element in the array.

// An additional test in the describe block

it("maintains type", () => {
  const getLength = (s:string)=>s.length;
  fc.assert(
    // asserting with an array of strings
    fc.property(fc.array(fc.string()), (data): void => {
      // mapping to lengths of strings
      const result = data.map(getLength);

      // checking that all values are numbers
      const isAllValid = result.every((x) => typeof x === "number");
      expect(isAllValid).toBeTruthy();
    })
  );
});

Like before, we can add a console.log to the test to see what strings are being generated

console.log
  [ 'ptpJTR`G4', 's >xmpXI', 'H++%;a3Y', 'OFD|+X8', 'gp' ]

console.log
  [ 'Rq', '', 'V&+)Zy2VD8' ]


console.log
  [ 'o%}', '$o', 'w7C', 'O+!e', 'NS$:4\\9aq', 'xPbb}=F7h', 'z' ]

console.log
  [ '' ]

console.log
  [ 'apply', '' ]

console.log
  []
## And many more entries...

Checking Order Property

For our third property, we need to ensure that the order of the array is being maintained.

To make this happen, we can use our identity function from before and check that our result is the same as the input. If so, then we know that the order is being maintained.

it("maintains order", () => {
  const identity = <T>(a: T) => a;

  fc.assert(
    fc.property(fc.array(fc.string()), (data): void => {
      const result = data.map(identity);

      expect(result).toEqual(data);
    })
  );
});

And with that, we've verified that our third property holds!

So What, Why Properties?

When I think about the code I write, I'm thinking about the way it works, the way it should work, and the ways it shouldn't work. I find example based tests to help understand a business flow because of it's concrete values while property based tests help me understand the general guarantees of the code.

I find that once I start thinking in properties, my code became cleaner because there's logic that I no longer had to write. In our map example, we don't have to write checks for if we have null or undefined because map always returns an array (empty in the worse case). There's also no need to write error handling because as long as the mapping function is pure, map will always return an array.

For those looking to learn more about functional programming, you'll find that properties help describe the higher level constructs (functors, monoids, and monads) and what to look for.

Finding properties can be a challenge, however, Scott Wlaschin (of FSharpForFunAndProfit) has a great post talking about design patterns that I've found to be immensely helpful.

Better Domain Modeling with Discriminated Unions

When I think about software, I like designing software so that doing the right things are easy and doing the wrong things are impossible (or at least very hard). This approach is typically called falling into the pit of success.

Having a well-defined domain model can prevent many mistakes from happening just because the code literally won't let it happen (either through a compilation error or other mechanisms).

I'm a proponent of functional programming as it allows us to model software in a better way that can reduce the number of errors we make.

Let's at one of my favorite techniques discriminated unions.

Motivation

In the GitHub API, there's an endpoint that allows you to get the events that have occurred for a pull request.

Let's take a look at the example response in the docs.

[
  {
    "id": 6430295168,
    "url": "https://api.github.com/repos/github/roadmap/issues/events/6430295168",
    "event": "locked",
    "commit_id": null,
    "commit_url": null,
    "created_at": "2022-04-13T20:49:13Z",
    "lock_reason": null
  },
  {
    "id": 6430296748,
    "url": "https://api.github.com/repos/github/roadmap/issues/events/6430296748",
    "event": "labeled",
    "commit_id": null,
    "commit_url": null,
    "created_at": "2022-04-13T20:49:34Z",
    "label": {
      "name": "beta",
      "color": "99dd88"
    }
  },
  {
    "id": 6635165802,
    "url": "https://api.github.com/repos/github/roadmap/issues/events/6635165802",
    "event": "renamed",
    "commit_id": null,
    "commit_url": null,
    "created_at": "2022-05-18T19:29:01Z",
    "rename": {
      "from": "Secret scanning: dry-runs for enterprise-level custom patterns (cloud)",
      "to": "Secret scanning: dry-runs for enterprise-level custom patterns"
    }
  }
]

Based on the name of the docs, it seems like we'd expect to get back an array of events, let's call this TimelineEvent[].

Let's go ahead and define the TimelineEvent type. One approach is to start copying the fields from the events in the array. By doing this, we would get the following.

type TimelineEvent = {
  id: number;
  url: string;
  event: string;
  commit_id?: string;
  commit_url?: string;
  created_at: string;
  lock_reason?: string;
  label?: {
    name: string;
    color: string;
  };
  rename?: {
    from: string;
    to: string;
  };
};

The Problem

This definition will work, as it will cover all the data. However, the problem with this approach is that lock_reason, label, and rename had to be defined as nullable as they can sometimes be specified, but not always (for example, the lock_reason isn't specified for a label event).

Let's say that we wanted to write a function that printed data about TimelineEvent, we would have to write something like the following:

1
2
3
4
5
6
7
8
9
function printData(event: TimelineEvent) {
  if (event.event === "labeled") {
    console.log(event.label!.name); // note the ! here, to tell TypeScript that I know it'll have a value
  } else if (event.event == "locked") {
    console.log(event.lock_reason);
  } else {
    console.log(event.rename!.from); // note the ! here, to tell Typescript that I know it'll have a value
  }
}

The main problem is that the we have to remember that the labeled event has a label property, but not the locked property. It might not be a big deal right now, but given that the GitHub API has over 40 event types, the odds of forgetting which properties belong where can be challenging.

The pattern here is that we have a type TimelineEvent that can have different, separate shapes, and we need a type that can represent all the shapes.

The Solution

One of the cool things about Typescript is that there is a union operator (|), that allows you to define a type as one of the other types.

Let's refactor our TimelineEvent model to use the union operator.

First, we need to define the different events as their own types

type LockedEvent = {
  id: number;
  url: string;
  event: "locked"; // note the hardcoded value for event
  commit_id?: string;
  commit_url?: string;
  created_at: string;
  lock_reason?: string;
};

type LabeledEvent = {
  id: number;
  url: string;
  event: "labeled"; // note the hardcoded value for event
  commit_id?: string;
  commit_url: string;
  created_at: string;
  label: {
    name: string;
    color: string;
  };
};

type RenamedEvent = {
  id: number;
  url: string;
  event: "renamed"; // note the hardcoded value for event
  commit_id?: string;
  commit_url?: string;
  created_at: string;
  rename: {
    from: string;
    to: string;
  };
};

At this point, we have three types, one for each specific event. A LockedEvent has no knowledge of a label property and a RenamedEvent has no knowledge of a lock_reason property.

Next, we can update our definition of TimelineEvent to use the union operator as so.

type TimelineEvent = LockedEvent | LabeledEvent | RenamedEvent;

This would be read as A TimelineEvent can either be a LockedEvent or a LabeledEvent or a RenamedEvent.

With this new definition, let's rewrite the printData function.

1
2
3
4
5
6
7
8
9
function printData(event: TimelineEvent) {
  if (event.event == "labeled") {
    console.log(event.label.name); // note that we no longer need !
  } else if (event.event == "locked") {
    console.log(event.lock_reason);
  } else {
    console.log(event.rename.to); // note that we no longer need !
  }
}

Not only do we not have to use the ! operator to ignore type safety, but we also have better autocomplete (note that locked_reason and rename don't appear when working with a labeled event). Better autocomplete

Deeper Dive

At a general level, what we've modeled is a sum type and it's great for when you have a type that can take on a finite number of differing shapes.

Sum types are implemented as either tagged unions or untagged unions. Typescript has untagged unions, however, other languages like Haskell and F#, use tagged unions. Let's see what the same implementation in F# would have looked like.

// specific type definitions omitted since they're
// similar to typescript definition
// ....
type TimelineEvent = Locked of LockedEvent | Labeled of LabeledEvent | Renamed of RenamedEvent

let printData e =
    match e with
    | Locked l -> printf "%s" l.lock_reason
    | Labeled l -> printf "%s" l.label.name
    | Renamed r -> printf "%s" r.rename.``to`` // the `` is needed here as to is a reserved word in F#

A tagged union is when each shape has a specific constructor. So in the F# version, the Locked is the tag for the LockedEvent, Labeled is the tag for the LabeledEvent, so on and so forth. In the Typescript example, we worked around it because the event property is on every TimelineEvent and is a different value.

If that wasn't true, then we would had to have added a field to TimelineEvent (typically called kind or tag) that would help us differentiate between the various shapes.

Wrapping Up

When defining domain models where the model can have different shapes, you can use a sum type to define the model.

Using F# To Solve a Constraints Problem

In this post, I’m going to solve a logic puzzle using C# and F#. First, I’ll define the problem being solved and what our restrictions are. Next, I’ll show how I’d break down the problem and write an easy-to-read, extendable solution using idiomatic C#. Afterwards, I’ll solve the same problem and write an easy-to-read, extendable solution writing in idiomatic F#. Finally, we’ll compare the two solutions and see why the F# solution is the better solution.

The Problem

For this problem, I’m going to write a constraint solver (thanks to Geoff Mazeroff for the inspiration).

If you’re not familiar with the concept, a constraint is simply some rule that must be followed (such as all numbers must start with a 4). So a constraint solver is something that takes all the constraints and a source of inputs and returns all values that fit all the constraints.

With that being said, our source will be a list of positive integers and our constraints are the following:

  • 4 digits long (so 1000 – 9999)
  • Must be even (so 1000, 1002, 1004, etc…)
  • The first digit must match the last digit (2002, 2012, 2022, etc…)

To further restrict solutions, all code will be production ready. This includes handling error conditions (like input being null), being maintainable (easily adding more constraints) and easy to read.

To quickly summarize, we need to find a robust, maintainable, and readable solution to help us find all 4 digit number that are even and that the first and last digit are equal.

Implementing a Solution in C

For the C# solution, I’m going to need a class for every constraint, a class to execute all constraints against a source (positive integers) and a runner that ties all the pieces together.

Starting with the smaller blocks and building up, I’m going to start with the constraint classes. Each constraint is going to take a single number and will return true if the number follows the constraint, false otherwise.

With that being said, I’d first implement the constraint that all numbers must be 4 digits long

1
2
3
4
5
6
7
class MustBeFourDigitsLongConstraint
{
    public bool FollowsConstraint(int value)
    {
        return value.ToString().Length == 4;
    }
}

Second, I’d write the constraint that all numbers must be even

1
2
3
4
5
6
7
class MustBeEvenConstraint
{
    public bool FollowsConstraint(int value)
    {
        return value % 2 == 0;
    }
}

Third, I’d implement the constraint that all numbers must have the same first digit and the last digit

1
2
3
4
5
6
7
8
class FirstDigitMustEqualLastDigitConstraint
{
    public bool FollowsConstraint(int value)
    {
        var valueString = value.ToString();
        return valueString[0] == valueString[valueString.Length-1];
    }
}

At this point, I have the constraints written, but I need them to follow a general contract so that the Constraint Solver (about to be defined) can take a list of these constraints. I’ll introduce an interface, IConstraint and update my classes to implement that interface.

1
2
3
4
5
6
7
8
9
public interface IConstraint
{
    bool FollowsConstraint(int value);
}
class MustBeFourDigitsLongConstraint : IConstraint {/* Implementation Details Omitted */}

class MustBeEvenConstraint : IConstraint {/* Implementation Details Omitted */}

class FirstDigitMustEqualLastDigitConstraint : IConstraint {/* Implementation Details Omitted */}

So now I have the constraints defined and they’re now implementing a uniform interface, I can now create the constraint solver. This class is responsible for taking the list of numbers and the list of constraints and then returning a list of numbers that follow all constraints.

class ConstraintSolver
{
    public List FindValues(List constraints, List values)
    {
        if (constraints == null) throw new ArgumentNullException("constraints");
        if (values == null) throw new ArgumentNullException("values");

        var result = values;
        foreach (var constraint in constraints)
        {
            result = result.Where(x => constraint.FollowsConstraint(x)).ToList();
        }
        return result;
    }
}

Finally, I can put all the pieces together using LINQPad (Full C# solution can be found here).

void Main()
{
    var numbers = Enumerable.Range(0, 10000).ToList();
    var constraints = new List<IConstraint>{new MustBeFourDigitsLongConstraint(), new MustBeEvenConstraint(), 
             new FirstDigitMustEqualLastDigitConstraint()};

    var constraintSolver = new ConstraintSolver();
    var result = constraintSolver.FindValues(constraints, numbers.ToList());

    result.Dump();
}

This solution is easily extendable because if we need to add another constraint, we just add another class that implements the IConstraint interface and change the Main method to add an instance of the new constraint to the list of constraints.

Implementing a Solution in F

Now that we have the C# solution, let’s take a look at how I would solve the problem using F#.

Similar to the C# solution, I’m going to create a function for every constraint, a function to execute all constraints against a source (positive integers) and a runner that ties all the pieces together.

Also similar to the C# solution, I’m going to start with creating the constraints and then work on the constraint solver function.

First, I’d implement that the number must be four digits long constraint.

let mustBeFourDigit number = 
    number.ToString().Length = 4

Next, the number must be even constraint.

let mustBeEven number =
    number % 2 = 0

Lastly, the first digit is the same as the last digit constraint.

1
2
3
4
5
let firstDigitMustBeEqualLast number =
    let numberString = number.ToString().ToCharArray()
    let firstDigit = numberString.GetValue(0)
    let lastDigit = numberString.GetValue(numberString.Length-1)
    firstDigit = lastDigit

At this stage in the C# solution, I had to create an interface, IConstraint, so that the constraint solver could take a list of constraints. What’s cool with F# is that I don’t have to define the interface. The F# type inference is saying that each of these functions are taking the same input (some generic `a) and returning a bool, so I can add all of them to the list. This is pretty convenient since I don’t have to worry about this piece of plumbing.

Now that the different constraints are defined, I’d go ahead and write the last function that takes a list of constraints and a list of numbers and returns the numbers that the constraints fit. (Confused by this function? Take a look at Implementing your own version of # List.Filter)

1
2
3
4
5
6
let rec findValidNumbers numbers constraints = 
    match constraints with
    | [] -> numbers
    | firstConstraint::remainingConstraints ->
        let validNumbers = numbers |> List.filter firstConstraint
        findValidNumbers validNumbers remainingConstraints

Finally, all the pieces are in place, so I can now put all the pieces together using LINQPad.

1
2
3
4
5
6
let numbers = [1000 .. 9999]
let constraints = [mustBeFourDigits; mustBeEven; firstDigitMustEqualLast;]

let result = findValidNumbers numbers constraints

printf "%A" result

Comparing Both Solutions

Now that we have both solutions written up, let’s compare and see which solution is better.

First, the same design was used for both solutions. I decided to use this design for both because it’s flexible enough that we could add new constraints if needed (such as, the 2nd digit must be odd). As an example, for the C# solution, I’d create a new class that implemented IConstraint and then update the runner to use the new class. For the F# solution, I’d create a new function and update the runner. So, I’d think it’s safe to say that both solutions score about the same from a maintainability and extendability point of view.

From an implementation perspective, both solutions are production ready since the code handles possible error conditions (C# with null checks in the ConstraintSolver class, F# with none because it doesn’t support null). In addition to being robust, both solutions are readable by using ample whitespace and having all variables, classes, and interfaces clearly described.

With that being said, this is where the similarities end. When we look at how much code was written to solve the problem, we have a stark difference. For the C# solution, I ended up with 48 lines of code (omitting blank lines), however, for the F# solution, it only took 19. Now you could argue that I could have written the C# solution in fewer lines of code by removing curly braces around one line statements or ignoring null inputs. However, this would lead the code to be less robust.

Another difference between the F# solution and C# is that I was able to focus on the solution without having to wire up an interface. You’ll often hear developers talk about the how little plumbing you need for F# to “just work” and this small example demonstrates that point.

Another difference (albeit subtle) is that the F# solution is that I can use the findValidNumbers function with any generic list of values and any generic list of functions that take the generic type and return true/false.

In other words, if I had another constraint problem using strings, I’d still implement the different constraints, but I could use the same findValidNumbers function. At that point, however, I’d probably rename it to findValidValues to signify the generic solution.

What’s awesome about this is that I didn’t have to do any more work to have a generic solution, F# did that for me. To be fair, the C# solution can easily be made generic, but that would have to be a conscious design decision and I think that’s a downside.

TL;DR

In this post, we took a look at solving a number constraint problem by using idiomatic C# and F#. Even though both solutions are easy to read and easy to extend, the F# version was less than 1/2 the size of the C# solution. In addition, I didn’t have to do any plumbing for the F# version, but had to do some for the C# solution, and to top it off, the F# solution is generically solved, whereas the C# solution is not.

Implementing Your Own Version of F#’s List.Filter

As I’ve been thinking more about F#, I began to wonder how certain methods in the F# stack work, so I decided to implement F#’s List.filter method.

For those of you who aren’t familiar, List.Filter takes a function that returns true or false and a list of values. The result of the call is all values that fulfill the fuction.

For example, if we wanted to keep just the even numbers in our list, then the following would accomplish that goal.

1
2
3
4
5
6
let values = [1;2;3;4]
let isItEven x = x % 2 = 0


let evenValues = List.filter isItEven values
// val it : int list = [2; 4]

Now that we know the problem, how would we begin to implement? First, we need to define a function called filter:

let filter () =

However, to match the signature for List.filter, it needs to take a function that maps integers to bools and the list of values to work on

let filter (func:int->bool) (values:int List) =

Now that we have the signature, let’s add some logic to match on the list of values. When working with lists, there are two possibilities, an empty list and a non-empty list. Let’s first explore the empty list option.

In the case of an empty list of values, then it doesn’t matter what the func parameter does, there are no possible results, so we should return an empty list for the result.

1
2
3
let filter (func:int->bool) (values:int List) =
    match values with
    | [] -> []

Now that we’ve handled the empty list, let’s explore the non-empty list scenario. In this branch, the list must have a head and a tail, so we can deconstruct the list to follow that pattern.

1
2
3
4
let filter (func:int->bool) (values:int List) =
    match values with
    | [] -> []
    | head::tail -> // what goes here?

Now that we’ve deconstructed the list, we can now use the func parameter with the head element. If the value satisfies the func parameter, then we want to add the head element to the list of results and continue processing the rest of the list. To do that, we can use recursion to call back into filter with the same func parameter and the rest of the list:

1
2
3
4
5
let rec filter (func:int->bool) (values:int List) =
    match values with
    | [] -> []
    | head::tail -> 
         if func head then head :: filter func tail

At this point, we need to handle the case where the head element does not satisfy the func parameter. In this case, we should not add the element to the list of results and we should let filter continue the work

1
2
3
4
5
6
let rec filter (func:int->bool) (values:int List) =
    match values with
    | [] -> []
    | head::tail -> 
         if func head then head :: filter func tail
         else filter func tail

By handling the base case first (an empty list), filter can focus on the current element in the list (head) and then recurse to process the rest of the list. This solution works, but we can make this better by removing the type annotations. Interestingly enough, we don’t care if we’re working with integers, strings, or whatever. Just as long as the function takes some type and returns bool and the list of values matches the same type as the func parameter, it works. So then we end up with the following:

1
2
3
4
let rec filter func values =
    match values with
    | [] -> []
    | head::tail -> if func head then head :: filter func tail else filter func tail

In general, when working with lists, I tend to start by matching the list with either an empty list or non-empty. From there, I’ve got my base case, so I can focus on the implementation for the first element. After performing the work for the first element, I can then recurse to the next element.