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.

Sunday 16 June 2024

Adding synchronous and asynchronous foreach support to Range in C#

In C# 8, we got Range and Index. This allows you to construct a sequence of values. This article will look at diferent ways of adding foreach support in C# to Range. Let's first look at enumeration in the synchronous case. This requires us to add an enumerator to Range as an extension method. We define the following extension method GetEnumerator on Range to achieve this: This requires us to create a custom enumerator class that has these methods :
  • MoveNext
  • Current
The rest of the custom enumerator is happening via the logic in these methods and the constructor of this custom enumerator.


public static class RangeExtensions
{
	public static CustomRangeEnumerator GetEnumerator(this Range range) => new CustomRangeEnumerator(range);

	public class CustomRangeEnumerator
	{

		private int _current;
		private readonly int _end;
		private readonly int _start;
		private readonly bool _isDescending;

		public CustomRangeEnumerator(Range range)
		{
			if (range.End.IsFromEnd)
			{
				throw new NotSupportedException();
			}
			_end = range.End.Value;
			_start = range.Start.Value;
			_isDescending = _start > _end;
			_current = _isDescending ? range.Start.Value + 1 : range.Start.Value - 1;
		}

		public int Current => _current;

		public bool MoveNext()
		{
			if (_isDescending)
			{
				_current--;
				return _current >= _end;
			}
			else
			{
				_current++;
				return _current <= _end;
			}
		}
	}
}



The following code tests out this range enumeration:


Console.WriteLine($"Iterating range 10..1");
	foreach (var num in (10..1))
	{
		Console.WriteLine(num);
	}

	Console.WriteLine($"Iterating range 20..30");
	foreach (var num in 20..30)
	{
		Console.WriteLine(num);
	}


And we get the following output, showing we can enumerate a range both increasing and decreasing :


10
9
8
7
6
5
4
3
2
1

Iterating range 20..30
20
21
22
23
24
25
26
27
28
29
30


Let's look next how we can implement async support for iterations. I first started with having a go with IAsyncEnumerator. But I could not make the cancellation token work, since I could not pass it in. Instead I landed on a method GetItemsAsync that supports cancellation tokens being passed in and will respect cancellation. Here is the extension methods I created :



public static class RangeExtensions
{

	public static async IAsyncEnumerable<int> GetItemsAsync(this Range range, CancellationToken cancellationToken = default)
	{
		await foreach (var num in range)
		{
			if (cancellationToken.IsCancellationRequested){
				Console.WriteLine($"Iteration FAILED: Exiting the IAsyncEnumerable iteration as soon as possible since cancellation was requested at index: {num}");
			}
			cancellationToken.ThrowIfCancellationRequested();
			await Task.Delay(100);
			yield return num;
		}
	}
	
	// Existing asynchronous enumeration with delay and cancellation token
	public static CustomIntAsyncEnumerator GetAsyncEnumerator(this Range range)
		=> new CustomIntAsyncEnumerator(range);

	public class CustomIntAsyncEnumerator : IAsyncEnumerator<int>
	{
		private int _current;
		private readonly int _start;
		private readonly int _end;
		private readonly bool _isDescending;

		public CustomIntAsyncEnumerator(Range range)
		{
			_start = range.Start.Value;
			_end = range.End.Value;
			_isDescending = _start > _end;
			_current = _isDescending ? _start + 1 : _start - 1;
		}

		public int Current => _current;

		public async ValueTask<bool> MoveNextAsync()
		{
			// Wait for the specified delay time
			await Task.Delay(0);

			if (_isDescending)
			{
				if (_current > _end)
				{
					_current--;
					return true;
				}
			}
			else
			{
				if (_current < _end)
				{
					_current++;
					return true;
				}
			}

			return false;
		}

		public ValueTask DisposeAsync()
		{
			// Perform any necessary cleanup here
			return new ValueTask();
		}
	}
}



The code below tests the async enumeration. The benefit of the IAsyncEnumerator is that you can iterate without any hassles with cancellation token, but you should respect cancellation tokens. So the last method call calling the method GetItemsAsync do respect the cancellation token and also accepts such a token being passed in. I tested out the code in this article with Linqpad 7, and developed it using this small IDE.


    var rangeOneHundredDownTo90 = 100..90;

	Console.WriteLine($"Await foreach over variable {nameof(rangeOneHundredDownTo90)}");
	await foreach (var num in rangeOneHundredDownTo90)
	{
		Console.WriteLine(num);
	}

	Console.WriteLine("Async iteration from 140 to 180, waiting 500 ms between each iteration");

	var range = 140..180;

	var cts = new CancellationTokenSource();
	var token = cts.Token;

	await foreach (var num in range.GetItemsAsync(token))
	{
		if (num >= 170)
		{
			cts.Cancel();
		}
		Console.WriteLine(num);
	}



The screen shot below shows that the cancellation token was throwing a OperationCanceledException as was the intent of the demo code.