A C# implementation of the Haskell List

list.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

namespace Pauwels.AspNet.Controllers
{
    public abstract class FList<T> {
        public abstract FList<T> Tail();
        public abstract T Head();
        public abstract FList<T> Reverse();
        public abstract FList<T> Cons(T element);
        public abstract override string ToString();
        public readonly static FList<T> Empty = new EmptyFlist();

        protected abstract FList<T> ReverseAcc(FList<T> acc);

        private class EmptyFlist : FList<T>
        {
            public EmptyFlist() { }

            public override T Head()
            {
                throw new InvalidOperationException();
            }

            public override FList<T> Tail()
            {
                return this;
            }

            public override FList<T> Cons(T element)
            {
                return new SFlist(element, this);
            }

            public override FList<T> Reverse()
            {
                return this;
            }

            protected override FList<T> ReverseAcc(FList<T> acc)
            {
                return acc;
            }

            public override string ToString()
            {
                return "[]";
            }
        }

        private class SFlist : FList<T>
        {
            private T element;
            private FList<T> previous;

            public SFlist(T element, FList<T> previous)
            {
                this.element = element;
                this.previous = previous;
            }

            public override T Head()
            {
                return element;
            }

            public override FList<T> Tail()
            {
                return previous;
            }

            public override FList<T> Cons(T element)
            {
                return new SFlist(element, this);
            }

            public override FList<T> Reverse()
            {
                return this.ReverseAcc(FList<T>.Empty);
            }

            protected override FList<T> ReverseAcc(FList<T> acc)
            {
                return this.Tail().ReverseAcc(acc.Cons(element));
            }

            public override string ToString()
            {
                return element.ToString() + " : " + previous.ToString();
            }

        }

    }


}

test.fsi

Microsoft (R) F# Interactive version 12.0.21005.1
Copyright (c) Microsoft Corporation. All Rights Reserved.

For help type #help;;

> #I @"F:\dev\arealities\pauwels\Pauwels.AspNet\bin";;

--> Added 'F:\dev\arealities\pauwels\Pauwels.AspNet\bin' to library include path

> #r "Pauwels.AspNet.dll";;

--> Referenced 'F:\dev\arealities\pauwels\Pauwels.AspNet\bin\Pauwels.AspNet.dll' (file may be locked by F# Interactive process)

> open Pauwels.AspNet.Controllers;;
> FList<int>.Empty.Cons(5).Cons(4).Cons(3).Cons(2).Cons(1);;
val it : FList<int> = 1 : 2 : 3 : 4 : 5 : []
> FList<int>.Empty.Cons(5).Cons(4).Cons(3).Cons(2).Cons(1).Reverse();;
val it : FList<int> = 5 : 4 : 3 : 2 : 1 : []
> FList<int>.Empty.Cons(5).Cons(4).Cons(3).Cons(2).Cons(1).Reverse().Tail();;
val it : FList<int> = 4 : 3 : 2 : 1 : []
> FList<int>.Empty.Cons(5).Cons(4).Cons(3).Cons(2).Cons(1).Reverse().Head();;
val it : int = 5
>