Proposal: A set of modules for list and tree zippers

Non vengono indicati file, test o punti di ingresso. Inizia esaminando i design proposti per i zipper di liste e alberi e i riferimenti collegati di Huet e di implementazione, quindi determina se esiste una risoluzione concordata per le questioni relative all’API. Per considerare il lavoro concluso, sarebbero necessari un ambito definito e un design accettato per i moduli zipper.

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