Skip to content

Instantly share code, notes, and snippets.

@StephenCleary
Last active April 13, 2024 18:37
Show Gist options
  • Save StephenCleary/225f892861c3b7bbf7d1d3d369e8c18f to your computer and use it in GitHub Desktop.
Save StephenCleary/225f892861c3b7bbf7d1d3d369e8c18f to your computer and use it in GitHub Desktop.
Some types from Purely Functional Data Structures
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);
}
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment