Proposal: A set of modules for list and tree zippers

[reinux]

Zippers are a convenient way to address individual elements within data structures, particularly in trees and lists. I find them especially useful in Elmish models, as they allow me to speak of a "current selection" -- a common task in UI dev, where data and operational state often exist together.

In a sense, they allow for O(1) "lenses" on recursive data structures.

Tomas Petricek has demonstrated writing a zipper computation expression for trees. I can't immediately think of usages for the computation itself, but it would be great to have a standard tree zipper and list zipper type in FSharpPlus.

Some things to think about:

• I don't know yet whether it makes sense to allow the focus to be optional or not. Making the focus non-optional makes it more difficult to model situations where there is no focus or where there are no elements (it would probably have to be wrapped in a Choice<'a ListZipper, 'a list>, for example), whereas allowing the focus to be optional makes for more opportunities for exceptions and a need for more tryX functions.
• A map on the entire zipper would be straightforward, but I'm not too sure what a fold would look like. Would it use the focus as the first element? Or would it ignore it?
• Would we want some operators for convenience?
• Entirely theoretical, but given that zippers are derivatives on data structures, is there some data structure for which the focus is a tree? It looks like there's such thing as a generic zipper, but I'm not smart enough to tell whether or not it would have any practical value, or whether such a thing could be implemented in F#. Maybe it could allow for zippers on tree types other than the built-in FSharp.Core.Map type?
• I'm not sure if there's a practical way to have multiple focuses on a list zipper. The focus on a map zipper is given by a a path which is a list (e.g. a directory path in a file tree), typically of length O(log n); but on a list zipper, although the focus is given by a single element, the path is an index and access is O(n). The path also cannot be expected to be static, as inserts and deletes will displace all subsequent items.

One solution I can think of is for a list zipper to be a zipper on list zippers, with navigation given by a path of left and right operations -- essentially a tree zipper, but without the need for an explicitly ordered key. The list zipper zipper itself would have to track cursors and issue tokens for them, as the actual path can change when a cursor hops from one sub-zipper to a sibling or cousin. Such navigation might also entail an O(n) reversal operation on half of the parent, and would probably lead to degenerate trees in a lot of circumstances without some automatic balancing on the cursors themselves.

Some more links:

• The original paper by Huet: https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf
• Example use in Xmonad tiling window manager: https://donsbot.com/2007/05/17/roll-your-own-window-manager-tracking-focus-with-a-zipper/
• Example use in a file server: https://okmij.org/ftp/continuations/zipper.html#zipper-fs

[gusty]

The zipper is a very interesting abstraction. They are related to Comonads and Lenses which are already included in this library so I think it would make totally sense to add some zipper stuff here.

I personally didn't have time to research and try but if you are willing to please go ahead. Adding some real-world scenarios would add a lot of value.