Sunday 30 June 2024

Fork combinator revisited - supporting multiple part functions in C#

This article shows an example of a Fork combinator or 'monad' that will allow you to specify a join function that operates on all the part results and allow you to specify multiple part functions to be operated in sequence. First off, we define a simple map monad to map a value to another value of possibly other type. Then we define the fork combinator. The code below is very simple and short, it uses LINQ functionality to combine the results via the Select method, Linq is also functional so this is how we build up functional monads in C#, using Linq and Func and generics (and pattern matching and more).

Combinators.cs


public static class Combinators {
	
	public static TOut Map<TIn, TOut>(this TIn @this, Func<TIn, TOut> f) => f(@this);
	
	public static TOut Fork<TIn, TMiddle, TOut>(this TIn @this, Func<IEnumerable<TMiddle>, TOut> joinFunc,
		params Func<TIn, TMiddle>[] partFuncs) => partFuncs.Select(pf => pf(@this)).Map(joinFunc);
	
}


Let's look at a simple demo how to use this

Program.cs


public static class Program {
	
	string hello = "hhhhhheeeeeeeelllllllllllooooo";
	
	int sumOfLettersToLookFor = hello.Fork(results => (int)results.Sum(), 
				x => (double)x.Count(l => l == 'h'),
				x => (double) x.Count(l => l == 'e'),
				x => (double) x.Count(l => l == 'l'),
				x => (double) x.Count(l => l == 'o'));
	
	sumOfLettersToLookFor.Dump();
	
}


Functional programming has many of these monads that are very short and allows you to do combinations that would be lengthy and stateful in the procedural / object oriented way but elegant and short in the functional world. Finally a screenshot from Linqpad 7 showing the code above works : (A reference to Jerry Seinfeld to the right for those who know Seinfeld episodes)

Iterating a list using Span in C# - Benchmark

It is possible to iterate a list in C# using Span. This article shows a benchmark on that and how you can create a Span of a list. It is important to note that the Span will despite it is not doing any memory to memory copying and is performance optimized, it will not
detect changes done to the list after the span is created, therefore the iterations you perform should not be done on a list where you expect that the list is altered during the iteration using the Span. Let's first look at the Benchmark, BenchmarkDotNet will be used. The Github repo with the source code for the benchmark is here: https://github.com/toreaurstadboss/BenchmarkIterateCollections The program is started up using BenchmarkRunner
Program.cs


using BenchmarkDotNet.Running;

namespace BenmarkIterateCollections;


public class Program
{

    public static void Main(string[] args)
    {
        BenchmarkRunner.Run<IterateCollectionsBenchmark>();
        Console.WriteLine("Benchmark finished. Hit the any key to exit");
        Console.ReadKey();
    }
}



The benchmarks look like this, the base line is iterating an array.
BenchmarkIterateCollections.cs


using BenchmarkDotNet.Attributes;
using System.Runtime.InteropServices;

namespace BenmarkIterateCollections;

public class IterateCollectionsBenchmark
{

    private Random _rnd = new Random();
    private int[] _array = default!;

    private List<int> _list = default!;
    private const int ITEM_COUNT = 1001;

    [GlobalSetup]
    public void Init()
    {
        _array = Enumerable.Range(0, ITEM_COUNT).Select(_ => _rnd.Next(0, 1024)).ToArray();
        _list = _array.ToList();
    }

    [Benchmark(Description = "Iterate an array with foreach", Baseline = true)]
    public void IterateArray()
    {
        foreach (var item in _array)
        {
        }
    }

    [Benchmark(Description = "Iterate a list using a span with foreach")]
    public void IterateArrayUsingSpan()
    {
        Span<int> span = _array; //note : implicit operator used here to convert an array to a Span
        foreach (var item in span)
        {

        }
    }

    [Benchmark(Description = "Iterate a list with foreach")]
    public void IterateList()
    {
        foreach (var item in _list)
        {

        }
    }

    [Benchmark(Description = "Iterate a list using a span with foreach")]
    public void IterateListUsingSpan()
    {
        Span<int> span = CollectionsMarshal.AsSpan(_list);
        foreach (var item in span)
        {

        }
    }

}



Conclusions

Iterating an array using a span actually ran 6% faster than iterating an array without using the span. Iteating a list using a span ran some 50% faster than iterating the list using the span. The code above used the method CollectionsMarshal.AsSpan() in System.Runtime.InteropServices namespace - this has been available since .NET 5.x. Being aware of this method means we can iterate lists about 50% faster keeping in mind that changes to the list after the span was created from the list will not be shown in the span and we could show stale data if changes occur. You can also use this in .NET Framework using System.Memory Nuget package For large lists you know will not change, using spans to iterate could and should promise a large performance improvement. It is also possible to slice a portion of lists or arrays in case it is a case of iterating parts of a large list or array.

Wednesday 26 June 2024

Functional programming - Guarding against nulls with the Option monad

Monads are "elementary individual substances". We can call them "building blocks" in Functional Programming (FP) and FP is built upon such building blocks to compose more complex logic. This article sums up using the

Option

monad, which is described many places on the net and is wellknown. This article is just a walkthrough of this monad, which creates a wrapper for a value that will aid against guarding against nulls. We will effectively abstract away null, and using extension methods we will allow setting up a processing chain where nulls are wrapped inside a value inside the Option objects. First off, define a generic class for this monad and in this case we will consider reference types or classes (this includes strings). Also, equality operators can be added to make it easier to do equality checks. The class will be called Option and we will define two methods called None and Some. The field called _content of type T will be returned inside a Option wrapper instance and None will only return Option object where _content is null.
  • None() signals that the payload or _content is null. None method returns an instance of Option of T where the wrapped value is null.
  • Some() signals that the payload or _content> is not null. some method returns an instance of Option of T where the wrapped value is not null.
  • Both the None() and Some() are of type Option<T> and can be used in a chained expression.
Some concepts of what the Option should support :
  • A map method that allows transforming from T to TResult (both can be same type) along the chained expressions
  • A reduce method that allows retrieving the value inside the Option object that is wrapped
  • Extension methods for going from an object to an Option wrapper of the object
  • Predicate based filter methods for peeling away Option objects where the wrapped object which satisfy the filter can be filtered



public class Option<T> : IEquatable<Option<T>> where T : class {
	
	private T? _content;
	
	private Option(){}

	public static Option<T> None() => new();
	public static Option<T> Some(T obj) => new Option<T> { _content = obj };

	public override bool Equals(object? obj)
	{
		return this.Equals(obj as Option<T>);
	}
	
	public Option<T> Where(Func<T, bool> predicate) => 
		_content is not null && predicate(_content) ? this : Option<T>.None();

	public Option<T> WhereNot(Func<T, bool> predicate) =>
		_content is not null && !predicate(_content) ? this : Option<T>.None();

	public bool Equals(Option<T>? other) => other is null ? false :
		_content?.Equals(other._content) ?? false;
		
	public static bool operator ==(Option<T>? a, Option<T>? b) => 
		a is null ? b is null : a.Equals(b);
		
	public static bool operator !=(Option<T>? a, Option<T>? b) => !(a == b);
		
	public override int GetHashCode()
	{
		return _content?.GetHashCode() ?? 0;
	}

	public Option<TResult> MapOptional<TResult>(Func<T, Option<TResult>> map) where TResult : class =>
		_content is not null ? map(_content) : Option<TResult>.None();

	public Option<TResult> Map<TResult>(Func<T, TResult> map) where TResult : class =>
		new Option<TResult>() { _content = _content is not null ? map(_content) : null };
	
    public T Reduce(T orElse) => _content ?? orElse;
	
	public T Reduce(Func<T> orElse) => _content ?? orElse();
	
} 


We also add some extension methods to help using the monad Option above containing the Some and None methods :

 
 
 public static class OptionExtensions {
	
	public static Option<T> ToOption<T>(this T? obj) where T : class => obj is not null ? Option<T>.Some(obj) : Option<T>.None();

	public static Option<T> Where<T>(this T? obj, Func<T, bool> predicate) where T : class => obj is not null && predicate(obj) ? Option<T>.Some(obj) : Option<T>.None();
	
	public static Option<T> WhereNot<T>(this T? obj, Func<T, bool> predicate) where T : class => obj is not null && !predicate(obj) ? Option<T>.Some(obj) : Option<T>.None();

}

 
Let's also add a ForEach extension method for easier usage in chained expressions of ienumerable collections.
 
 
 public static class IEnumerableExtensions {
	
	public static IEnumerable<T> ForEach<T>(this IEnumerable<T> items, Action<T> action){
		foreach (var item in items){
			action(item);
		}
		return items;
	}
	
}
 
 

The demo code then looks like below, where we iterate through an array of names and grab the initials of the name with some simple logic. Note usage of WhereNot predicate to avoid having to think about null strings further down the chain and also the usage of the Reduce method to get the value which the Option monad wraps.


void Main()
{
	string?[] authors = new[]{
	 "Johan Bojer",
	 null,
	 "Henrik Ibsen",
	 "Kristoffer Updahl",
	};
	
    authors.Select(x => GetInitial(x).Reduce(() => string.Empty)).ForEach(Console.WriteLine);
    
    //using ToOption() method
    authors.Select(a => GetInitial(a.ToOption())).ForEach(o => Console.WriteLine(o.Reduce(() => "?")));

	
	
}

//methods GetInitial below

Option<string> GetInitial(Option<string> name) => name.WhereNot(string.IsNullOrWhiteSpace).Map(s => s.TrimStart().Substring(0, 1).ToUpper());


The example in this article with retrieving initial (first letter) of some names is trivial. The real benefit of using the Option is to safeguard against nulls in lengthy chained calls or other scenarios where you want to always return something and decide how to indicate that we got something back and decide what an empty object will be, in the example the letter "?" signals a null based name.