Hacktoberfest 2026：メンテナが10月に向けて印を付けた、オープンで初心者向けの issue。 Hacktoberfest の issue を見る

Proposal: A set of modules for list and tree zippers

オープン
  • 何か問題がありますか？
#538 コメント 1 件 リアクション 0 件 担当者 0 名 GitHub で見る

まだ誰も着手していません。

評価

難易度
5/5
見積もり時間
1週間以上
初心者へのやさしさ
25/100
issue の種類
機能追加
明瞭さ
説明が足りない
活発さ
停滞
技術スタック
fsharp
領域
backend-api-design

調査の方向性

ファイル、テスト、エントリーポイントは指定されていません。まず、提案されているリスト zipper と tree zipper の設計、およびリンクされている Huet と実装のリファレンスを確認し、その後、API に関する問題について合意された解決策があるかどうかを判断してください。完了とするには、明確なスコープと zipper モジュールの承認済み設計が必要です。

索引モデルが issue の本文から書いたものです。

説明

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:

主要言語
F#
スター
942
フォーク
105
30日以内にマージされた PR はありません

環境構築

このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

fsprojects/FSharpPlus のほかの issue

fsprojects/FSharpPlus の issue をすべて見る

似ている issue

Backend & API Design の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。