HeadTailSumBenchmarks.cs

using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace HeadTail
{
    [MemoryDiagnoser]
    public class Benchmark
    {
        int[] array;
        List<int> list;     
        ImmutableList<int> immutableList;   

        [Params(0, 100, 10000)]
        public int N;

        [GlobalSetup]
        public void Setup()
        {
            array = new int[N];
            Array.Fill(array, 1);

            list = new List<int>(array);
            immutableList = ImmutableList.Create<int>(array);
        }

        [Benchmark]
        public int List() => list.Sum();

        [Benchmark]
        public int Immutable_List() => immutableList.Sum();

        [Benchmark(Baseline = true)]
        public int Span() => array.Sum();
    }

    class Program
    {
        static void Main(string[] args)
        {
            _ = BenchmarkRunner.Run<Benchmark>();
        }
    }

    static class Extensions
    {
        public static void Deconstruct<T>(this List<T> list, out T head, out List<T> tail)
        {
            head = list.FirstOrDefault();
            tail = new List<T>(list.Skip(1));
        }

        public static int Sum(this List<int> list) 
            => list switch
            {
                { Count: 0 } => 0,
                var (head, tail) => head + Sum(tail),
            };

        public static void Deconstruct<T>(this ImmutableList<T> list, out T head, out ImmutableList<T> tail)
        {
            head = list.FirstOrDefault();
            tail = list.RemoveAt(0);
        }

        public static int Sum(this ImmutableList<int> list) 
            => list switch
            {
                { Count: 0 } => 0,
                var (head, tail) => head + Sum(tail),
            };

        public static void Deconstruct<T>(this Span<T> span, out T head, out Span<T> tail)
        {
            switch(span.Length)
            {
                case 0:
                    head = default;
                    tail = default;
                    break;
                
                case 1:
                    head = span[0];
                    tail = default;
                    break;

                default:
                    head = span[0];
                    tail = span[1..];
                    break;
            }
        }

        public static int Sum(this Span<int> list) 
            => list switch
            {
                { Length: 0 } => 0,
                var (head, tail) => head + Sum(tail),
            };
    }
}