Skip to content

Instantly share code, notes, and snippets.

@Steven24K
Created January 4, 2021 15:43
Show Gist options
  • Save Steven24K/6dd508654bb7b7f392d6a10911acd1a2 to your computer and use it in GitHub Desktop.
Save Steven24K/6dd508654bb7b7f392d6a10911acd1a2 to your computer and use it in GitHub Desktop.
An immuatable linked list in C#
public interface IList<T>
{
public bool isEmpty { get; set; }
public IList<T> Add(T v);
public U Reduce<U>(Func<T, U, U> f, U init);
public IList<U> Map<U>(Func<T, U> f);
}
public class Node<T> : IList<T>
{
public bool isEmpty;
public T node;
public IList<T> tail;
public Node(T _node, IList<T> _tail)
{
this.node = _node;
this.tail = _tail;
this.isEmpty = false;
}
bool IList<T>.isEmpty { get => this.isEmpty; set => this.isEmpty = value; }
public IList<T> Add(T v)
{
return new Node<T>(v, this);
}
public IList<U> Map<U>(Func<T, U> f)
{
return this.Reduce<IList<U>>((x, xs) => new Node<U>(f(x), xs), new Empty<U>());
}
public U Reduce<U>(Func<T, U, U> f, U init)
{
return this.tail.Reduce<U>(f, f(this.node, init));
}
public override string ToString()
{
return this.Reduce((x, xs) => x + ", " + xs , "");
}
}
public class Empty<T> : IList<T>
{
public bool isEmpty;
public Empty()
{
this.isEmpty = true;
}
bool IList<T>.isEmpty { get => this.isEmpty; set => this.isEmpty = value; }
public IList<T> Add(T v)
{
return new Node<T>(v, this);
}
public IList<U> Map<U>(Func<T, U> f)
{
return new Empty<U>();
}
public U Reduce<U>(Func<T, U, U> f, U init)
{
return init;
}
public override string ToString()
{
return "";
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment