Some types from Purely Functional Data Structures

Queue.cs

public readonly record struct Queue<T>(int FrontCount, Stream<T> Front, int RearCount, Stream<T> Rear)
{
	// val empty = Queue (0, $Nil, 0, $Nil)
	public static Queue<T> Empty { get; } = new(0, Stream<T>.Empty, 0, Stream<T>.Empty);

	// fun isEmpty (lenf, _, _, _) = (lenf = 0)
	public bool IsEmpty => FrontCount == 0;

	// fun snoc ((lenf, f, lenr, r), x) = check (lenf, f, lenr+1, $Cons (x, r))
	public Queue<T> Snoc(T item) => (this with { RearCount = RearCount + 1, Rear = new(item, Rear) }).Check();

	// fun head (lenf, $Nil, lenr, r) = raise Empty
	//   | head (lenf, $Cons (x, f'), lenr, r) = x
	public T Head => this switch
	{
		(0, _, _, _) => throw new InvalidOperationException("Queue is empty"),
		(_, { Value: var (item, _) }, _, _) => item,
	};

	// fun tail (lenf, $Nil, lenr, r) = raise Empty
	//   | tail (lenf, $Cons (x, f'), lenr, r) = check (lenf-1, f', lenr, r)
	public Queue<T> Tail() => this switch
	{
		(0, _, _, _) => throw new InvalidOperationException("Queue is empty"),
		(_, { Value: var (_, rest) }, _, _) => (this with { FrontCount = FrontCount - 1, Front = rest }).Check(),
	};

	// fun check (q as (lenf, f, lenr, r)) =
	//     if lenr <= lenf then q else (lenf + lenr, f ++ reverse r, 0, $Nil)
	private Queue<T> Check() => RearCount <= FrontCount ?
		this :
		new(FrontCount + RearCount, Front.Append(Rear.Reverse()), 0, Stream<T>.Empty);
}

Stream.cs

public sealed record class StreamCell<T>(T Item, Stream<T> Rest);

public sealed record class Stream<T>
{
	public Stream(Func<StreamCell<T>?> factory) => _lazy = new(factory);
	public Stream(StreamCell<T>? value) => _lazy = new(value);
	public Stream(T item, Stream<T> rest) => _lazy = new(new StreamCell<T>(item, rest));

	// Convenience/optimization members
	public static Stream<T> Empty { get; } = new((StreamCell<T>?)null);
	public static Stream<T> Unit(T item) => new(item, Empty);
	private static StreamCell<T> Cons(T item, StreamCell<T>? rest) => new(item, rest == null ? Empty : new(rest));
	public StreamCell<T>? Value => _lazy.Value;

	// fun lazy ($Nil) ++ t = t
	//        | ($Cons (x, s)) ++ t = $Cons (x, s ++ t)
	public Stream<T> Append(Stream<T> other) => new(() => this switch
	{
		{ Value: null } => other.Value,
		{ Value: var (item, rest) } => new(item, rest.Append(other)),
	});

	// fun lazy take (0, x) = $Nil
	//        | take (n, $Nil) = $Nil
	//        | take (n, $Cons (x, s)) = $Cons (x, take (n-1, s))
	public Stream<T> Take(int count) => new(() => (count, this) switch
	{
		(0, _) => null,
		(_, { Value: null }) => null,
		(_, { Value: var (item, rest) }) => new(item, rest.Take(count - 1)),
	});

	// fun lazy drop (0, s) = s
	//        | drop (n, $Nil) = $Nil
	//        | drop (n, $Cons (x, s)) = drop (n-1, s)
	public Stream<T> DropRecursive(int count) => count == 0 ? this : new(() => (count, this) switch
	{
		(0, _) => Value,
		(_, { Value: null }) => null,
		(_, { Value: var (_, rest) }) => rest.DropRecursive(count - 1).Value,
	});

	// fun lazy drop (n, s) =
	//     let fun drop' (0, s) = s
	// 	         | drop' (n, $Nil) = $Nil
	// 	         | drop' (n, $Cons (x, s)) = drop' (n-1, s)
	// 	   in drop' (n, s) end
	public Stream<T> DropRecursive2(int count)
	{
		static StreamCell<T>? DoDrop(int count, StreamCell<T>? current) => (count, cell: current) switch
		{
			(0, _) => current,
			(_, null) => null,
			var (_, (_, rest)) => DoDrop(count - 1, rest.Value),
		};

		return count == 0 ? this : new(() => DoDrop(count, Value));
	}

	// Imperative version of drop (.NET does not guarantee tail call optimization)
	public Stream<T> Drop(int count) => count == 0 ? this : new(() =>
	{
		var current = Value;
		while (count-- != 0 && current != null)
			current = current.Rest.Value;
		return current;
	});

	// fun lazy reverse s =
	//     let fun reverse' ($Nil, r) = r
	// 	         | reverse' ($Cons (x, s), r) = reverse' (s, $Cons (x, r))
	// 	   in reverse' (s, $Nil) end
	public Stream<T> ReverseRecursive()
	{
		static StreamCell<T>? DoReverse(StreamCell<T>? current, StreamCell<T>? result) => current switch
		{
			null => result,
			var (item, rest) => DoReverse(rest.Value, Cons(item, result)),
		};

		return new(() => DoReverse(Value, null));
	}

	// Imperative version of reverse (.NET does not guarantee tail call optimization)
	public Stream<T> Reverse() => new(() =>
	{
		StreamCell<T>? current = Value;
		StreamCell<T>? result = null;
		while (current != null)
		{
			var (item, rest) = current;
			current = rest.Value;
			result = Cons(item, result);
		}

		return result;
	});

	private readonly Lazy<StreamCell<T>?> _lazy;
}