Hacktoberfest 2026: los issues que los mantenedores marcaron para octubre, abiertos y aptos para principiantes. Explorar issues de Hacktoberfest

Proposal: A set of modules for list and tree zippers

Abierto
  • ¿Algo no está bien?
#538 1 comentario 0 reacciones 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
25/100
Tipo de issue
Nueva funcionalidad
Claridad
Necesita aclaración
Estado de actividad
Estancado
Stack tecnológico
fsharp
Área
backend-api-design

Línea de trabajo

No se nombran archivos, pruebas ni puntos de entrada. Empieza revisando las propuestas de diseño de los zippers de listas y árboles, así como las referencias enlazadas de Huet y de implementación, y determina después si existe una resolución acordada para las cuestiones de la API. Para darlo por terminado, sería necesario definir el alcance y aceptar un diseño para los módulos de zipper.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

enhancement

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:

Lenguaje dominante
F#
Estrellas
942
Forks
106
Sin PR fusionados en 30 d

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de fsprojects/FSharpPlus

Todos los issues de fsprojects/FSharpPlus

Issues similares

Más issues de Backend & API Design

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.