7
\$\begingroup\$

I tried to implement an immutable list.

public class ImmutableList<T> : IEnumerable<T>
{
    public T Head { get; set; }
    public ImmutableList<T> Tail { get; set; }

    protected ImmutableList()
    {

    }

    public static ImmutableList<T> WithItems(IEnumerable<T> items)
    {
        if (items.Count() == 1)
        {
            return new ImmutableList<T>()
            {
                Head = items.Single(),
                Tail = new EmptyList<T>()
            };
        }

        return new ImmutableList<T>()
        {
            Head = items.First(),
            Tail = WithItems(items.Skip(1))
        };
    }

    public ImmutableList<T> Add(T item)
    {
        if (this is EmptyList<T>)
        {
            return new ImmutableList<T>() {Head = item, Tail = new EmptyList<T>()};
        }

        return new ImmutableList<T>()
        {
            Head = Head,
            Tail = Tail.Add(item)
        };
    }

    public IEnumerator<T> GetEnumerator()
    {
        if (this is EmptyList<T>) yield break;
        else
        {
            yield return Head;
            foreach (var elem in Tail)
                yield return elem;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

public sealed class EmptyList<T> : ImmutableList<T>
{

}

public static class ImmutableListExtensions
{
    public static ImmutableList<T> ToImmutableList<T>(this IEnumerable<T> sequence)
    {
        return ImmutableList<T>.WithItems(sequence);
    } 
}

Simple example of how to use:

private static void Main(string[] args)
{
    ImmutableList<int> list = new[] {1, 2, 3}.ToImmutableList();


    ImmutableList<int> list2 = new EmptyList<int>().Add(1).Add(2).Add(3).Add(4);

    foreach (var n in list)
    {
        Console.WriteLine(n);
    }
}

Is there a better and/or more efficient way to do this?

\$\endgroup\$
12
\$\begingroup\$

First of all, this class is not immutable at all. You can modify both the head and the tail at any given node in the list from calling code. Here are some quick fixes to make the list immutable:

public class ImmutableList<T> : IEnumerable<T>
{
    private static readonly ImmutableList<T> _Empty = new EmptyList<T>();

    private readonly T _Head;

    private readonly ImmutableList<T> _Tail;

    public static ImmutableList<T> Empty
    {
        get
        {
            return _Empty;
        }
    }

    public T Head
    {
        get
        {
            return this._Head;
        }
    }

    public ImmutableList<T> Tail
    {
        get
        {
            return this._Tail;
        }
    }

    protected ImmutableList(T head, ImmutableList<T> tail)
    {
        this._Head = head;
        this._Tail = tail;
    }

    public static ImmutableList<T> WithItems(IEnumerable<T> items)
    {
        return (items == null) || (!items.Any())
            ? _Empty
            : (items.Count() == 1
                ? new ImmutableList<T>(items.Single(), _Empty)
                : new ImmutableList<T>(items.First(), WithItems(items.Skip(1))));
    }

    public ImmutableList<T> Add(T item)
    {
        return this == _Empty
            ? new ImmutableList<T>(item, _Empty)
            : new ImmutableList<T>(this._Head, this._Tail.Add(item));
    }

    public IEnumerator<T> GetEnumerator()
    {
        if (this == _Empty)
        {
            yield break;
        }

        yield return this._Head;
        foreach (var elem in this._Tail)
        {
            yield return elem;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    private sealed class EmptyList<TU> : ImmutableList<TU>
    {
        public EmptyList() : base(default(TU), null)
        {
        }
    }
}

The calling code needs to change ever so slightly to accommodate:

var list2 = ImmutableList<int>.Empty.Add(1).Add(2).Add(3).Add(4);

You'll also note I added a null and empty sequence check in the WithItems static method. This simply allows any null/empty sequence call to return an empty list.

\$\endgroup\$
  • \$\begingroup\$ I forgot private setters on properties. But if I correct that my implementation will be immutable. \$\endgroup\$ – Raz Megrelidze Apr 8 '15 at 18:34
6
\$\begingroup\$

WithItems doesn't play nicely with empty sequences. This line will throw an exception, which I consider unexpected behaviour:

var xs = ImmutableList<int>.WithItems(new int[0]);

If that code seems contrived, consider this example where GetFoos returns an empty sequence:

var xs = GetFoos().ToImmutableList(); // throws InvalidOperationException
\$\endgroup\$
0
\$\begingroup\$

I would consider using a List internally and returning it's IEnumerator if I wanted to write such a class quick and dirty.

Your class will return a new ImmutableList<T> every time you add an element, using an List<T> will not do that every time. Depending on what you use this class for one or another implementation will be faster. If you want to heavily use the Add function consider this:

public class ImmutableList<T> : IEnumerable<T>
{
    private List<T> _list;

    public ImmutableList()
    {

    }

    public ImmutableList(IEnumerable<T> list)
    {
        _list = new List<T>(list); // clone the list
    }

    public void Add(T item)
    {
        _list.Add(item);
    }

    public void AddRange(IEnumerable<T> items)
    {
        _list.AddRange(items);
    }

    public IEnumerator<T> GetEnumerator()
    {
        return _list.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return _list.GetEnumerator();
    }
}

public static class ImmutableListExtensions
{
    public static ImmutableList<T> ToImmutableList<T>(this IEnumerable<T> list)
    {
        return new ImmutableList<T>(list);
    }
}
\$\endgroup\$
  • \$\begingroup\$ could you explain a little bit more why you would do it this way over the way the OP is doing it? \$\endgroup\$ – Malachi Apr 10 '15 at 16:54
  • 1
    \$\begingroup\$ Updated the post \$\endgroup\$ – four Apr 10 '15 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.