Skip to content

Instantly share code, notes, and snippets.

@dadhi
Created July 5, 2018 06:40
Show Gist options
  • Select an option

  • Save dadhi/44cc08ffee341e32b15125e3d2019382 to your computer and use it in GitHub Desktop.

Select an option

Save dadhi/44cc08ffee341e32b15125e3d2019382 to your computer and use it in GitHub Desktop.
Persistent Zipper data-structure for the win in C#
using System;
public class Test
{
public static void Main()
{
var x = ImZipper<int>.Empty.Pre(1).Pre(2);
Console.WriteLine(x);
Console.WriteLine(x.Focus);
}
}
public static class Ext
{
public static ImList<T> Reverse<T>(this ImList<T> l)
{
var r = ImList<T>.Empty;
for (var x = l; !x.IsEmpty; x = x.Tail)
r = r.Push(x.Head);
return r;
}
}
public class ImZipper<T>
{
public static readonly ImZipper<T> Empty = new ImZipper<T>(ImList<T>.Empty, ImList<T>.Empty);
public bool IsEmpty => this == Empty;
public readonly ImList<T> LRev, R;
public ImList<T> L => _l ?? (_l = LRev.Reverse());
private ImList<T> _l;
public T Focus => IsEmpty ? default (T) : R.IsEmpty ? LRev.Head : R.Head;
public ImZipper<T> Post(T x) => new ImZipper<T>(LRev, R.Push(x));
public ImZipper<T> Pre(T x) => new ImZipper<T>(LRev.Push(x), R);
public ImZipper(ImList<T> lrev, ImList<T> r)
{
LRev = lrev;
R = r;
}
public override string ToString() => L + "," + R;
}
public class ImList<T>
{
public static readonly ImList<T> Empty = new ImList<T>(default (T), null);
public bool IsEmpty => this == Empty;
public readonly T Head;
public readonly ImList<T> Tail;
public ImList<T> Push(T h) => new ImList<T>(h, this);
private ImList(T h, ImList<T> t)
{
Head = h;
Tail = t;
}
public override string ToString() => IsEmpty ? "()" : Head + "::" + Tail;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment