I continue to feel strongly that the natural behavior of all folds is to use current element then accumulator order, be they left or right.
When it comes to hash table folds (not that the concept of left or right makes sense for traditional hash table designs), this is the behavior of SRFI-146, 125, and 69, and at least Guile, Racket, and Gauche. Don't unnecessarily break established convention. On Wed, Dec 11, 2024, 9:07 AM Daphne Preston-Kendal <[email protected]> wrote: > Discussed today on the phone: > > • provide hash-table-fold-right > > • not clear if we need both vector and list versions of hash-table-keys > and hash-table-values ? > Vector versions originally provided for R6RS compat; list versions > originally for SRFI 69 compat. > Noted that the vector versions can return in O(1) for an immutable hash > table; (not mentioned on the phone:) the strategy for maintaining insertion > order makes this attractive, in fact, because the implementation doesn’t > even need to find a minimal perfect hash function for the set of keys in > order to do this > > • do we need to provide support for immutability? required by R6RS; > introduced to SRFI-land by 125; dpk will do a survey of which impls > actually enforce it > Answer to question (whether it makes sense) depends maybe in part on > answer to ballot question on immutability support for built-in Scheme types > > • sample implementation not tested since October last year; dpk recalls > that resizing was badly broken and will need to look at it again thoroughly > to determine what still needs to be done at the ‘base’ layer > > > Not mentioned, would also like to discuss in future: > > I intend to propose an R6RS/Haskell style resolution to the fold argument > order issue. > I.e. procedures currently called something-fold are near-universally > renamed to something-fold-left and use accumulator-then-inputs order; > something-fold-right takes inputs-then-accumulator. Full rationale to > follow. SRFI 250 should follow this pattern if agreed upon … or whatever > convention we eventually do adopt, if that proposal fails to find consensus. > > I would like to have a cursor-based iteration protocol like Racket’s: > < > https://docs.racket-lang.org/reference/hashtables.html#%28def._%28%28quote._~23~25kernel%29._hash-iterate-first%29%29 > > > > A procedure to move an existing entry to the end of the insertion order > was also discussed on the list; I think it would be useful for implementing > LRU caches. Although maybe only in conjunction with a hook allowing > programs to delete entries from the table when a resize is otherwise > demanded – which makes this sound like something for a different library > entirely, rather than a feature we should really consider for SRFI 250 … > > MNW’s concern that the insertion ordering might be suboptimal for an > algorithm which does a lot of deletions and so should be optional. (FWIW > JS’s Map type, introduced in ES6, has required insertion ordering all > along.) > > > Daphne > >
