C# List implementation using a delegate type

gistfile1.txt

using System;
using System.Linq;
using System.Threading;

namespace App
{
    public delegate ListItem<T> List<T>();

    public static class Program
    {
        static List<T> Cons<T>(T x, List<T> xs)
        {
            return List.Cons<T>(x, xs);
        }

        static List<T> Empty<T>()
        {
            return List.Empty<T>();
        }

        public static void Main()
        {
            //Test1();
            //Test2();
            //Test3();
            //Test4();
            //Test5();
            //Test6();
            //Test7();
            //Test8();
            //Test9();
            //Test10();
            Test11();
        }

        public static void Test11()
        {
            List.Random
                .Take(100)
                .Select(v => v % 100)
                .Do(WriteWithSpace)
                .Do(WriteSpace)
                .Sort()
                .Do(WriteWithSpace);
        }

        public static void Test10()
        {
            List.Integers.Do(v => {
                Console.Write("{0} ", v);
                Thread.Sleep(1);
            });
        }

        public static void Test9()
        {
            var list1 = Cons("A", Cons("B", Cons("C", Cons("D", Cons("E", Empty<string>())))));
            var list2 = Cons("F", Cons("G", Cons("H", Cons("I", Cons("J", Empty<string>())))));
            var list3 = Cons("K", Cons("L", Cons("M", Cons("N", Cons("O", Empty<string>())))));

            var lists = Cons(list1, Cons(list2, Cons(list3, Empty<List<string>>())));

            var sep = Cons("9", Cons("9", Cons("9", Empty<string>())));

            sep.Intercalate(lists).Do(Console.WriteLine);

        }

        public static void Test8()
        {
            var list = Cons("A", Cons("B", Cons("C", Cons("D", Cons("E", Empty<string>())))));

            list.Intersperse(",")
                .Do(Console.WriteLine);

            List.Integers
                .Take(20)
                .Intersperse(-1)
                .Do(Console.WriteLine);
        }

        public static void Test7()
        {
            var list1 = Cons(5, Cons(4, Cons(3, Cons(2, Cons(1, Empty<int>())))));
            var list2 = Cons(3, Cons(2, Empty<int>()));
            var list3 = Cons(3, Cons(5, Cons(4, Empty<int>())));

            Console.WriteLine(list2.IsInfixOf(list1));
            Console.WriteLine(list3.IsInfixOf(list1));
        }

        public static void Test6()
        {
            var list1 = Cons(5, Cons(4, Cons(3, Cons(2, Cons(1, Empty<int>())))));
            var list2 = Cons(3, Cons(2, Cons(1, Empty<int>())));
            var list3 = Cons(3, Cons(5, Cons(4, Empty<int>())));

            Console.WriteLine(list2.IsSuffixOf(list1));
            Console.WriteLine(list3.IsSuffixOf(list1));
        }

        public static void Test5()
        {
            var list1 = Cons(5, Cons(4, Cons(3, Cons(2, Cons(1, Empty<int>())))));
            var list2 = Cons(5, Cons(4, Cons(3, Empty<int>())));
            var list3 = Cons(6, Cons(5, Cons(4, Empty<int>())));

            Console.WriteLine(list2.IsPrefixOf(list1));
            Console.WriteLine(list3.IsPrefixOf(list1));
        }

        public static void Test4()
        {
            var list = Cons(5, Cons(4, Cons(3, Cons(2, Cons(1, Empty<int>())))));

            list.Find(v => v == 3).Do(Console.WriteLine);

            Console.WriteLine("Index at " + list.FindIndex(v => v == 2));
        }

        public static void Test3()
        {
            var list1 = Cons(5, Cons(4, Cons(3, Cons(2, Cons(1, Empty<int>())))));
            var list2 = Cons("A", Cons("B", Cons("C", Cons("D", Cons("E", Cons("F", Cons("G", Empty<string>())))))));

            list1.Zip(list2)
                 .Do(Console.WriteLine);

            list2.Zip(List.Integers)
                 .Select(t => t.Item2 + " -> " + t.Item1)
                 .Do(Console.WriteLine);

        }

        public static void Test2()
        {
            List<int> empty = Empty<int>();

            var list1 = Cons(5, Cons(4, Cons(3, Cons(2, Cons(1, empty)))));
            var list2 = Cons(5, Cons(4, Cons(3, Cons(2, Cons(1, empty)))));

            var list3 = list1.Concat(list2);
            list3.Do(Console.WriteLine);

            var list4 = Cons("A", Cons("B", Cons("C", Cons("D", Cons("E", Empty<string>())))));
            list4.Do(Console.WriteLine);

            var list5 = list4.Reverse();
            list5.Do(Console.WriteLine);

            Console.WriteLine("Items in list: " + list1.Count());
            Console.WriteLine("Min value: " + list1.Min());
            Console.WriteLine("Max value: " + list1.Max());

            var list = from v1 in list1
                       from v2 in list2
                       where v1 > 2 && v2 > 2
                       select v1 * v2;

            list.Do(Console.WriteLine);

            var result = list.Sum();

            Console.WriteLine("Result: " + result);
        }

        public static void Test1()
        {
            var r = List.Integers
                        .Skip(100)
                        .Take(104)
                        .Where(IsEven)
                        .Select(Times10)
                        .Do(Console.WriteLine)
                        .Average();

            Console.WriteLine("Average: " + r);

            Console.WriteLine("Sum 3000-4000: " + List.Range(3000, 4000).Sum());
        }

        private static void WriteSpace<T>(T value)
        {
            Console.Write(" ");
        }

        private static void WriteWithSpace<T>(T value)
        {
            Console.Write(value);
            Console.Write(" ");
        }

        public static int Succ(int v)
        {
            return v + 1;
        }

        public static bool IsEven(int v)
        {
            return (v % 2) == 0;
        }

        public static int Times10(int v)
        {
            return v * 10;
        }
    }


    public static class List
    {
        public static List<T> Sort<T>(this List<T> self)
            where T : IComparable<T>
        {
            return self.IsEmpty()
                ? self
                : (from a in self.Tail() where a.CompareTo(self.Head()) < 1 select a).Sort()
                    .Concat(List.Cons(self.Head()))
                    .Concat((from b in self.Tail() where b.CompareTo(self.Head()) == 1 select b).Sort());
        }

        public static List<int> Integers
        {
            get
            {
                Func<int, List<int>> inf = null;
                inf = (v) => List.Cons(v, () => inf(v + 1));
                return inf(0);
            }
        }

        public static List<int> Random
        {
            get
            {
                var rnd = new Random();
                Func<List<int>> inf = null;
                inf = () => List.Cons(rnd.Next(), () => inf());
                return inf();
            }
        }

        public static List<T> Intersperse<T>(this List<T> self, T sep)
        {
            return self.IsEmpty()
                ? self
                : self.Tail().IsEmpty()
                    ? self
                    : List.Cons(self.Head(), List.Cons(sep, self.Tail().Intersperse(sep)));
        }

        public static List<T> Concat<T>(List<List<T>> xs)
        {
            return xs.IsEmpty()
                ? List.Empty<T>()
                : xs.Tail().IsEmpty()
                    ? xs.Head()
                    : xs.Head().Concat(Concat(xs.Tail()));
        }

        public static List<T> Intercalate<T>(this List<T> self, List<List<T>> lists)
        {
            return List.Concat<T>(lists.Intersperse(self));
        }

        public static List<List<T>> Tails<T>(this List<T> self)
        {
            return self.IsEmpty()
                ? List.Cons(self, List.Empty<List<T>>())
                : List.Cons(self, Tails(self.Tail()));
        }

        public static bool Any<T>(this List<T> self, Func<T, bool> pred)
        {
            return self.IsEmpty()
                ? false
                : pred(self.Head())
                    ? true
                    : Any(self.Tail(), pred);
        }

        public static bool IsInfixOf<T>(this List<T> self, List<T> other)
        {
            return other.Tails().Any(xs => self.IsPrefixOf(xs));
        }

        public static bool IsPrefixOf<T>(this List<T> self, List<T> other)
        {
            return self.IsEmpty()
                ? true
                : other.IsEmpty()
                    ? false
                    : self.Head().Equals(other.Head()) && IsPrefixOf(self.Tail(), other.Tail());
        }

        public static bool IsSuffixOf<T>(this List<T> self, List<T> other)
        {
            return self.Reverse()
                       .IsPrefixOf(other.Reverse());
        }

        public static T Head<T>(this List<T> self)
        {
            return self().Head;
        }

        public static List<T> Tail<T>(this List<T> self)
        {
            return self().Tail;
        }

        public static List<T> Find<T>(this List<T> self, Func<T, bool> pred)
        {
            return self.IsEmpty()
                ? self
                : pred(self.Head())
                    ? self
                    : Find(self.Tail(), pred);
        }

        public static int FindIndex<T>(this List<T> self, Func<T, bool> pred)
        {
            return FindIndex(self, pred, 0);
        }

        private static int FindIndex<T>(this List<T> self, Func<T, bool> pred, int index = 0)
        {
            return self.IsEmpty()
                ? -1
                : pred(self.Head())
                    ? index
                    : FindIndex(self.Tail(), pred, index + 1);
        }

        public static List<int> Range(int from, int to)
        {
            return from == to
                ? List.Empty<int>()
                : List.Cons(from, () => List.Range(from + 1, to));
        }

        public static R Apply<T, R>(this List<T> self, Func<T, List<T>, R> fn)
        {
            return fn(self.Head(), self.Tail());
        }

        public static List<T> Skip<T>(this List<T> self, int count)
        {
            return count == 0
                ? self
                : self().Tail.Skip(count - 1);
        }

        public static List<T> Take<T>(this List<T> self, int count)
        {
            return count == 0
                ? List.Empty<T>()
                : List.Cons(self.Head(), Take(self.Tail(), count - 1));
        }

        public static List<T> Empty<T>()
        {
            return () => new EmptyListItem<T>();
        }

        public static bool IsEmpty<T>(this List<T> self)
        {
            return self().IsEmpty;
        }

        public static List<T> Cons<T>(T head)
        {
            return () => new ListItem<T>(head, Empty<T>());
        }

        public static List<T> Cons<T>(T head, List<T> tail)
        {
            return () => new ListItem<T>(head, tail);
        }

        public static List<T> Cons<T>(T head, Func<List<T>> tail)
        {
            return () => new ListItem<T>(head, tail());
        }

        public static List<R> Select<T, R>(this List<T> self, Func<T, R> map)
        {
            return self.IsEmpty()
                ? List.Empty<R>()
                : List.Cons(map(self.Head()), self.Tail().Select(map));
        }

        public static List<T> Concat<T>(this List<T> self, List<T> other)
        {
            return self.IsEmpty()
                ? other
                : List.Cons(self.Head(), self.Tail().Concat(other));
        }

        public static List<V> SelectMany<T, U, V>(
            this List<T> self,
            Func<T, List<U>> bind,
            Func<T, U, V> project
            )
        {
            return
                self.Select(t =>
                   bind(t).Select(u =>
                      project(t, u)
                   ))
                    .Reduce(List.Empty<V>(), (s, vs) => s.Concat(vs));
        }

        public static List<T> Where<T>(this List<T> self, Func<T, bool> filter)
        {
            return self.IsEmpty()
                ? self
                : filter(self.Head())
                    ? List.Cons(self.Head(), self.Tail().Where(filter))
                    : self.Tail().Where(filter);
        }

        public static S Reduce<S, T>(this List<T> self, S state, Func<S, T, S> reduce)
        {
            return self.IsEmpty()
                ? state
                : self.Tail().Reduce(reduce(state, self.Head()), reduce);
        }

        public static int Count<T>(this List<T> self)
        {
            return self.Reduce(0, (s, _) => s + 1);
        }

        public static int Sum(this List<int> self)
        {
            return self.Reduce(0, (s, v) => s + v);
        }

        public static int Max(this List<int> self)
        {
            return self.IsEmpty()
                ? 0
                : self.Reduce(Int32.MinValue, (s, v) => v > s ? v : s);
        }

        public static int Min(this List<int> self)
        {
            return self.IsEmpty()
                ? 0
                : self.Reduce(Int32.MaxValue, (s, v) => v < s ? v : s);
        }

        public static List<T> Do<T>(this List<T> self, Action<T> act)
        {
            return self.Select(v => { act(v); return v; });
        }

        public static List<T> Reverse<T>(this List<T> self)
        {
            return self.IsEmpty()
                ? self
                : List.Concat(Reverse(self.Tail()), List.Cons(self.Head(), List.Empty<T>()));
        }

        public static List<Tuple<T1, T2>> Zip<T1, T2>(this List<T1> list1, List<T2> list2)
        {
            return Zip(list1, list2, (a, b) => Tuple.Create(a, b));
        }

        public static List<R> Zip<T1, T2, R>(this List<T1> list1, List<T2> list2, Func<T1, T2, R> combine)
        {
            return list1.IsEmpty() || list2.IsEmpty()
                ? List.Empty<R>()
                : List.Cons(combine(list1.Head(), list2.Head()), Zip(list1.Tail(), list2.Tail(), combine));
        }

        public static int Average(this List<int> self)
        {
            return self.Sum() / self.Count();
        }
    }

    public class ListItem<T>
    {
        readonly T head;
        readonly List<T> tail;

        public ListItem(T head, List<T> tail)
        {
            this.head = head;
            this.tail = tail;
        }

        public virtual T Head
        {
            get
            {
                return head;
            }
        }

        public virtual List<T> Tail
        {
            get
            {
                return tail;
            }
        }

        public virtual bool IsEmpty
        {
            get
            {
                return false;
            }
        }
    }

    public class EmptyListItem<T> : ListItem<T>
    {
        public EmptyListItem()
            :
            base(default(T), null)
        { }

        public override bool IsEmpty
        {
            get
            {
                return true;
            }
        }

        public override T Head
        {
            get
            {
                throw new Exception("List is empty");
            }
        }

        public override List<T> Tail
        {
            get
            {
                throw new Exception("List is empty");
            }
        }
    }