A List Zipper in C
A List Zipper in C# #
Excerpt #
A port of a Haskell example, just because.
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.
<span>public</span> <span>sealed</span> <span>class</span> <span>ListZipper</span><<span>T</span>> : <span>IEnumerable</span><<span>T</span>>
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:
<span>private</span> <span>readonly</span> <span>IEnumerable</span><<span>T</span>> values;
<span>public</span> <span>IEnumerable</span><<span>T</span>> Breadcrumbs { <span>get</span>; }
<span>private</span> <span>ListZipper</span>(<span>IEnumerable</span><<span>T</span>> <span>values</span>, <span>IEnumerable</span><<span>T</span>> <span>breadcrumbs</span>)
{
<span>this</span>.values = <span>values</span>;
Breadcrumbs = <span>breadcrumbs</span>;
}
<span>public</span> <span>ListZipper</span>(<span>IEnumerable</span><<span>T</span>> <span>values</span>) : <span>this</span>(<span>values</span>, [])
{
}
<span>public</span> <span>ListZipper</span>(<span>params</span> <span>T</span>[] <span>values</span>) : <span>this</span>(<span>values</span>.<span>AsEnumerable</span>())
{
}
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:
<span>public</span> <span>IEnumerator</span><<span>T</span>> <span>GetEnumerator</span>()
{
<span>return</span> values.<span>GetEnumerator</span>();
}
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 IReadOnlyCollectionvalues 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:
<span>public</span> <span>ListZipper</span><<span>T</span>>? <span>GoForward</span>()
{
<span>var</span> <span>head</span> = values.<span>Take</span>(1);
<span>if</span> (!<span>head</span>.<span>Any</span>())
<span>return</span> <span>null</span>;
<span>var</span> <span>tail</span> = values.<span>Skip</span>(1);
<span>return</span> <span>new</span> <span>ListZipper</span><<span>T</span>>(<span>tail</span>, <span>head</span>.<span>Concat</span>(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:
<span>public</span> <span>ListZipper</span><<span>T</span>>? <span>GoBack</span>()
{
<span>var</span> <span>head</span> = Breadcrumbs.<span>Take</span>(1);
<span>if</span> (!<span>head</span>.<span>Any</span>())
<span>return</span> <span>null</span>;
<span>var</span> <span>tail</span> = Breadcrumbs.<span>Skip</span>(1);
<span>return</span> <span>new</span> <span>ListZipper</span><<span>T</span>>(<span>head</span>.<span>Concat</span>(values), <span>tail</span>);
}
This test may serve as an example of client code that makes use of those two operations:
[<span>Fact</span>]
<span>public</span> <span>void</span> <span>GoBack1</span>()
{
<span>var</span> <span>sut</span> = <span>new</span> <span>ListZipper</span><<span>int</span>>(1, 2, 3, 4);
<span>var</span> <span>actual</span> = <span>sut</span>.<span>GoForward</span>()?.<span>GoForward</span>()?.<span>GoForward</span>()?.<span>GoBack</span>();
<span>Assert</span>.<span>Equal</span>([3, 4], <span>actual</span>);
<span>Assert</span>.<span>Equal</span>([2, 1], <span>actual</span>?.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:
<span>public</span> <span>ListZipper</span><<span>T</span>> <span>Insert</span>(<span>T</span> <span>value</span>)
{
<span>return</span> <span>new</span> <span>ListZipper</span><<span>T</span>>(values.<span>Prepend</span>(<span>value</span>), 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:
[<span>Fact</span>]
<span>public</span> <span>void</span> <span>InsertAtFocus</span>()
{
<span>var</span> <span>sut</span> = <span>new</span> <span>ListZipper</span><<span>string</span>>(<span>"foo"</span>, <span>"bar"</span>);
<span>var</span> <span>actual</span> = <span>sut</span>.<span>GoForward</span>()?.<span>Insert</span>(<span>"ploeh"</span>).<span>GoBack</span>();
<span>Assert</span>.<span>NotNull</span>(<span>actual</span>);
<span>Assert</span>.<span>Equal</span>([<span>"foo"</span>, <span>"ploeh"</span>, <span>"bar"</span>], <span>actual</span>);
<span>Assert</span>.<span>Empty</span>(<span>actual</span>.Breadcrumbs);
}
Likewise, we may attempt to remove an element from the list:
<span>public</span> <span>ListZipper</span><<span>T</span>>? <span>Remove</span>()
{
<span>if</span> (!values.<span>Any</span>())
<span>return</span> <span>null</span>;
<span>return</span> <span>new</span> <span>ListZipper</span><<span>T</span>>(values.<span>Skip</span>(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):
[<span>Fact</span>]
<span>public</span> <span>void</span> <span>RemoveAtEnd</span>()
{
<span>var</span> <span>sut</span> = <span>new</span> <span>ListZipper</span><<span>string</span>>(<span>"foo"</span>, <span>"bar"</span>).<span>GoForward</span>()?.<span>GoForward</span>();
<span>var</span> <span>actual</span> = <span>sut</span>?.<span>Remove</span>();
<span>Assert</span>.<span>Null</span>(<span>actual</span>);
<span>Assert</span>.<span>NotNull</span>(<span>sut</span>);
<span>Assert</span>.<span>Empty</span>(<span>sut</span>);
<span>Assert</span>.<span>Equal</span>([<span>"bar"</span>, <span>"foo"</span>], <span>sut</span>.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:
<span>public</span> <span>ListZipper</span><<span>T</span>>? <span>Replace</span>(<span>T</span> <span>newValue</span>)
{
<span>return</span> <span>Remove</span>()?.<span>Insert</span>(<span>newValue</span>);
}
As the name implies, this operation replaces the value currently in focus with a completely different value. Here’s an example:
[<span>Fact</span>]
<span>public</span> <span>void</span> <span>ReplaceAtFocus</span>()
{
<span>var</span> <span>sut</span> = <span>new</span> <span>ListZipper</span><<span>string</span>>(<span>"foo"</span>, <span>"bar"</span>, <span>"baz"</span>);
<span>var</span> <span>actual</span> = <span>sut</span>.<span>GoForward</span>()?.<span>Replace</span>(<span>"qux"</span>)?.<span>GoBack</span>();
<span>Assert</span>.<span>NotNull</span>(<span>actual</span>);
<span>Assert</span>.<span>Equal</span>([<span>"foo"</span>, <span>"qux"</span>, <span>"baz"</span>], <span>actual</span>);
<span>Assert</span>.<span>Empty</span>(<span>actual</span>.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
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#.