Support partial folds over Dict

[DavidDTA]

Currently, there is no performant way to query a subset (range) of keys in a dictionary. The best way currently involves converting the entire Dict to a list and then filtering, which runs in O(n). Theoretically, this should be able to be done in O(log(n) + size_of_results).

Concrete API proposal:

foldl : (k -> v -> b -> Maybe b) -> Maybe k -> b -> Dict k v -> b
foldl func startKeyInclusive initialAcc dict =
  -- func: If the returned value is `Nothing`, exclude this and all subsequent keys from the fold and return the passed in accumulation value.  Otherwise, pass the new accumulation value into func with the next key and value.
  -- startKeyInclusive: Skip all keys strictly less than this.  The first key passed into the func will be the first key greater than or equal to this.  `Nothing` is considered to be  less than all values.
  -- initialAcc: the initial accumulation value

foldr : (k -> v -> b -> Maybe b) -> Maybe k -> b -> Dict k v -> b
foldr func startKeyInclusive initialAcc dict =
  -- same as `foldl`, except that we fold from the right, we skip keys strictly greater than `startKeyInclusive`, and `Nothing` is considered greater than any value for `startKeyInclusive`.

The existing fold functions can be implemented using these new ones:

fold f initAcc dict = newFoldl (\k v acc -> Just (f k v acc)) Nothing initAcc dict

These functions also allow us to implement before and after as in IntDict, which is currently impossible with the existing API.

[github-actions]

Thanks for reporting this! To set expectations:

• Issues are reviewed in batches, so it can take some time to get a response.
• Ask questions a community forum. You will get an answer quicker that way!
• If you experience something similar, open a new issue. We like duplicates.

Finally, please be patient with the core team. They are trying their best with limited resources.