Last active
June 23, 2025 12:47
-
-
Save matarillo/ce6ecd75d87bd34a913e8c4c36d8fc91 to your computer and use it in GitHub Desktop.
Cons List for C# (before Type Unions)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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