Linked list with zipper.

[hummy123]

Hi there. Thanks for this repository; I learned quite a bit from it.

I'm making my own Piece Table implementation in F# (slower than yours), hoping to transform it into a more efficient data like a Piece Tree eventually (maybe with on-disk persistence) and the "domain" types you mentioned here were quite helpful for organising it.

Here's the link if you want to see (although I don't expect you to read through all the code): https://github.com/hummy123/Functional-Piece-Table .

Anyway, one significant internal data structure improvement I found for my implementation (still slower than yours) was using zippers for the LinkedList.

A zipper is a bit like a gap buffer or splay tree in how it moves you to a specific node in a data structure when you operate it (linked lists and binary trees can have zipper implementations for example).

Then repeated edits that are close to your current position (called the focus) in that structure take less time since they are closer and faster to reach, which is helpful for a text editor context. I think this will speed up your implementation too (my repository has a before the zipper/after benchmark table) if you think it's worth the time/effort.

PS: Unrelated to your repository, but would you know why my BenchmarkDotNet output has the "DEBUG" label in the HTML output like this?

BenchmarkDotNet=v0.13.2, OS=Windows 11 (10.0.22000.1219/21H2)
AMD Ryzen 3 5300U with Radeon Graphics, 1 CPU, 8 logical and 4 physical cores
.NET SDK=6.0.402
  [Host]     : .NET 6.0.10 (6.0.1022.47605), X64 RyuJIT AVX2 DEBUG
  Job-IVWDGV : .NET 6.0.10 (6.0.1022.47605), X64 RyuJIT AVX2

When I run your benchmark project on my machine, the "DEBUG" part doesn't show up like that. I selected the release mode in Visual Studio to build my project too, so I'm confused about whether I'm doing something wrong. Appreciate your help if you have time/have any idea about the issue.