A List Zipper in C# by Mark Seemann
A port of a Haskell example, just because.
This article is part of a series about Zippers. In this one, I port the ListZipper data structure from the Learn You a Haskell for Great Good! article also called Zippers.
A word of warning: I'm assuming that you're familiar with the contents of that article, so I'll skip the pedagogical explanations; I can hardly do it better that it's done there.
The code shown in this article is available on GitHub.
Initialization and structure #
In the Haskell code, ListZipper is just a type alias, but C# doesn't have that, so instead, we'll have to introduce a class.
public sealed class ListZipper<T> : IEnumerable<T>
Since it implements IEnumerable<T>, it may be used like any other sequence, but it also comes with some special operations that enable client code to move forward and backward, as well as inserting and removing values.
The class has the following fields, properties, and constructors:
private readonly IEnumerable<T> values; public IEnumerable<T> Breadcrumbs { get; } private ListZipper(IEnumerable<T> values, IEnumerable<T> breadcrumbs) { this.values = values; Breadcrumbs = breadcrumbs; } public ListZipper(IEnumerable<T> values) : this(values, []) { } public ListZipper(params T[] values) : this(values.AsEnumerable()) { }
It uses constructor chaining to initialize a ListZipper object with proper encapsulation. Notice that the master constructor is private. This prevents client code from initializing an object with arbitrary Breadcrumbs. Rather, the Breadcrumbs (the log, if you will) is going to be the result of various operations performed by client code, and only the ListZipper class itself can use this constructor.
You may consider the constructor that takes a single IEnumerable<T> as the 'main' public constructor, and the other one as a convenience that enables a client developer to write code like new ListZipper<string>("foo", "bar", "baz").
The class' IEnumerable<T> implementation only enumerates the values:
public IEnumerator<T> GetEnumerator() { return values.GetEnumerator(); }
In other words, when enumerating a ListZipper, you only get the 'forward' values. Client code may still examine the Breadcrumbs, since this is a public property, but it should have little need for that.
(I admit that making Breadcrumbs public is a concession to testability, since it enabled me to write assertions against this property. It's a form of structural inspection, which is a technique that I use much less than I did a decade ago. Still, in this case, while you may argue that it violates information hiding, it at least doesn't allow client code to put an object in an invalid state. Had the ListZipper class been a part of a reusable library, I would probably have hidden that data, too, but since this is exercise code, I found this an acceptable compromise. Notice, too, that in the original Haskell code, the breadcrumbs are available to client code.)
Regular readers of this blog may be aware that I usually favour IReadOnlyCollection<T> over IEnumerable<T>. Here, on the other hand, I've allowed values to be any IEnumerable<T>, which includes infinite sequences. I decided to do that because Haskell lists, too, may be infinite, and as far as I can tell, ListZipper actually does work with infinite sequences. I have, at least, written a few tests with infinite sequences, and they pass. (I may still have missed an edge case or two. I can't rule that out.)
Movement #
It's not much fun just being able to initialize an object. You also want to be able to do something with it, such as moving forward:
public ListZipper<T>? GoForward() { var head = values.Take(1); if (!head.Any()) return null; var tail = values.Skip(1); return new ListZipper<T>(tail, head.Concat(Breadcrumbs)); }
You can move forward through any IEnumerable, so why make things so complicated? The benefit of this GoForward method (function, really) is that it records where it came from, which means that moving backwards becomes an option:
public ListZipper<T>? GoBack() { var head = Breadcrumbs.Take(1); if (!head.Any()) return null; var tail = Breadcrumbs.Skip(1); return new ListZipper<T>(head.Concat(values), tail); }
This test may serve as an example of client code that makes use of those two operations:
[Fact] public void GoBack1() { var sut = new ListZipper<int>(1, 2, 3, 4); var actual = sut.GoForward()?.GoForward()?.GoForward()?.GoBack(); Assert.Equal([3, 4], actual); Assert.Equal([2, 1], actual?.Breadcrumbs); }
Going forward takes the first element off values and adds it to the front of Breadcrumbs. Going backwards is nearly symmetrical: It takes the first element off the Breadcrumbs and adds it back to the front of the values. Used in this way, Breadcrumbs works as a stack.
Notice that both GoForward and GoBack admit the possibility of failure. If values is empty, you can't go forward. If Breadcrumbs is empty, you can't go back. In both cases, the functions return null, which are also indicated by the ListZipper<T>? return types; notice the question mark, which indicates that the value may be null. If you're working in a context or language where that feature isn't available, you may instead consider taking advantage of the Maybe monad (which is also what you'd idiomatically do in Haskell).
To be clear, the Zippers article does discuss handling failures using Maybe, but only applies it to its binary tree example. Thus, the error handling shown here is my own addition.
Modifications #
In addition to moving back and forth in the list, we can also modify it. The following operations are also not in the Zippers article, but are rather my own contributions. Adding a new element is easy:
public ListZipper<T> Insert(T value) { return new ListZipper<T>(values.Prepend(value), Breadcrumbs); }
Notice that this operation is always possible. Even if the list is empty, we can Insert a value. In that case, it just becomes the list's first and only element.
A simple test demonstrates usage:
[Fact] public void InsertAtFocus() { var sut = new ListZipper<string>("foo", "bar"); var actual = sut.GoForward()?.Insert("ploeh").GoBack(); Assert.NotNull(actual); Assert.Equal(["foo", "ploeh", "bar"], actual); Assert.Empty(actual.Breadcrumbs); }
Likewise, we may attempt to remove an element from the list:
public ListZipper<T>? Remove() { if (!values.Any()) return null; return new ListZipper<T>(values.Skip(1), Breadcrumbs); }
Contrary to Insert, the Remove operation will fail if values is empty. Notice that this doesn't necessarily imply that the list as such is empty, but only that the focus is at the end of the list (which, of course, never happens if values is infinite):
[Fact] public void RemoveAtEnd() { var sut = new ListZipper<string>("foo", "bar").GoForward()?.GoForward(); var actual = sut?.Remove(); Assert.Null(actual); Assert.NotNull(sut); Assert.Empty(sut); Assert.Equal(["bar", "foo"], sut.Breadcrumbs); }
In this example, the focus is at the end of the list, so there's nothing to remove. The list, however, is not empty, but all the data currently reside in the Breadcrumbs.
Finally, we can combine insertion and removal to implement a replacement operation:
public ListZipper<T>? Replace(T newValue) { return Remove()?.Insert(newValue); }
As the name implies, this operation replaces the value currently in focus with a completely different value. Here's an example:
[Fact] public void ReplaceAtFocus() { var sut = new ListZipper<string>("foo", "bar", "baz"); var actual = sut.GoForward()?.Replace("qux")?.GoBack(); Assert.NotNull(actual); Assert.Equal(["foo", "qux", "baz"], actual); Assert.Empty(actual.Breadcrumbs); }
Once more, this may fail if the current focus is empty, so Replace also returns a nullable value.
Conclusion #
For a C# developer, the ListZipper<T> class looks odd. Why would you ever want to use this data structure? Why not just use List<T>?
As I hope I've made clear in the introduction article, I can't, indeed, think of a good reason.
I've gone through this exercise to hone my skills, and to prepare myself for the more intimidating exercise it is to implement a binary tree Zipper.
Next: A Binary Tree Zipper in C#.
