Skip to content

Instantly share code, notes, and snippets.

@matarillo
Last active June 23, 2025 12:47
Show Gist options
  • Save matarillo/ce6ecd75d87bd34a913e8c4c36d8fc91 to your computer and use it in GitHub Desktop.
Save matarillo/ce6ecd75d87bd34a913e8c4c36d8fc91 to your computer and use it in GitHub Desktop.
Cons List for C# (before Type Unions)
using System.Collections;
using System.Text;
var xs = ConsList<int>.Create([7, 8, 9, 10]);
var ys = ConsList<int>.Create([0, 1, 2, 3]);
var product =
from x in xs
from y in ys
select $"{x * 10 + y}";
Console.WriteLine(product);
public sealed class ConsList<T> : IEnumerable<T>
{
private static readonly ConsList<T> _empty = new ConsList<T>();
private readonly T? _head;
private readonly ConsList<T>? _tail;
private ConsList()
{
_head = default;
_tail = default;
}
private ConsList(T head, ConsList<T> tail)
{
_head = head;
_tail = tail;
}
public bool IsEmpty => _tail is null;
public T Head => _head ?? throw new InvalidOperationException();
public ConsList<T> Tail => _tail ?? throw new InvalidOperationException();
public static ConsList<T> Empty => _empty;
public ConsList<T> Add(T head) => new(head, this);
public ConsList<TResult> Select<TResult>(Func<T, TResult> selector)
{
return this.FoldBack(ConsList<TResult>.Empty, (x, a) => a.Add(selector(x)));
}
public ConsList<TResult> SelectMany<TCollection, TResult>(Func<T, ConsList<TCollection>> collectionSelector, Func<T, TCollection, TResult> resultSelector)
{
return
this.FoldBack(ConsList<TResult>.Empty, (x, a) =>
collectionSelector(x).FoldBack(a, (y, b) =>
b.Add(resultSelector(x, y))));
}
public static ConsList<T> Create(IEnumerable<T> col)
{
ConsList<T> rev = ConsList<T>.Empty;
foreach (var item in col)
{
rev = rev.Add(item);
}
ConsList<T> result = ConsList<T>.Empty;
for (var c = rev; !c.IsEmpty; c = c.Tail)
{
result = result.Add(c.Head);
}
return result;
}
public override string ToString()
{
var sb = new StringBuilder();
sb.Append('[');
sb.AppendJoin(", ", this);
sb.Append(']');
return sb.ToString();
}
public ConsList<T> Reverse()
{
ConsList<T> result = ConsList<T>.Empty;
foreach (var item in this)
result = result.Add(item);
return result;
}
public TState Fold<TState>(TState seed, Func<TState, T, TState> folder)
{
TState acc = seed;
foreach (var item in this)
acc = folder(acc, item);
return acc;
}
public TState FoldBack<TState>(TState seed, Func<T, TState, TState> folder)
{
TState acc = seed;
foreach (var item in this.Reverse())
acc = folder(item, acc);
return acc;
}
public IEnumerator<T> GetEnumerator()
{
for (var c = this; !c.IsEmpty; c = c.Tail)
yield return c.Head;
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment