Created
July 5, 2018 06:40
-
-
Save dadhi/44cc08ffee341e32b15125e3d2019382 to your computer and use it in GitHub Desktop.
Persistent Zipper data-structure for the win in C#
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; | |
| 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