RFC: hash table pattern matching

[sorawee]

Thanks, Joel and Alex!

guess what I would find in the Racket docs about matching hash tables, here’s what I would guess we would find:

I like the idea of hash* being ergonomic for partial matching, and hash being ergonomic for full matching, though it may still make sense to allow hash for partial matching, similar to how (list* x xs) would be equivalent to (list x xs ...). That is, (hash* [x y] h) would be equivalent to (hash [x y] #:rest h).

Providing default values for the match

I can see how this feature could be useful. One possible way to support the default value is with #:default <default-val>:

(match (hash 1 2)
  [(hash [1 x #:default #f])
   x]) ;=> 2

(match (hash 1 2)
  [(hash [3 x #:default #f])
   x]) ;=> #f

Here could be more advanced usage:

(match (hash 1 (list 2))
  [(hash [1 (or (list x) x) #:default #f])
   x]) ;=> 2

(match (hash 1 (list 100))
  [(hash [3 (or (list x) x) #:default #f])
   x]) ;=> #f

Note that #:default <default-val> would make most sense when there’s a key-value grouping, so that’s another reason to favor grouping.

Efficiency of a “rest” pattern

The intention of my proposal is that the rest pattern is efficient, provided that the matching value is an immutable hash table and key positions are not arbitrary patterns. It would use hash-remove under the hood, yes.

I would also like to see some concrete use cases of hash tables in the proposal.

That’s a good suggestion. Some examples of hash table pattern matching in the wild can be seen below (thanks to @shhyou for collecting these examples). Most of them are extracting JSON dictionary content.

• https://github.com/jeapostrophe/racket-langserver/blob/66641495b9723e44c8d2a915aca052951fca3d98/methods.rkt#L27-L46

• https://github.com/rmculpepper/crypto/blob/fec745e8af7e3f4d5eaf83407dde2817de4c2eb0/crypto-lib/pkcs8.rkt#L156-L167

• https://github.com/greghendershott/vestige/blob/ee7f0b35ba5e5d1a3e5ec90976c658bce24d0ba4/vestige-lib/vestige/receiving.rkt#L70-L72

• https://github.com/nix-community/dream2nix/blob/f61d9311e224a2c5f6691f8f8d7411e7284650fb/src/subsystems/racket/translators/racket-impure/generate-dream-lock.rkt#L182-L192

  With the default value feature, it could make these tasks even easier.

it is not clear to me that the code below is more readable

The programs in the proposal are toy examples meant to illustrate the semantics of the pattern. I wasn’t concerned about readability at all. See the list of links above for actual usage, which would need to be concerned with readability.

would the match code allow users to concisely express an inefficient match

That depends on whether the key position is a pattern OR an expression. In the current (or rather, previous) hash-table pattern, it allows any pattern, so yes, it is horribly inefficient with no warning. However, in the proposal, I proposed that the key position would be an expression. In that case, hash table pattern matching is guaranteed to be efficient (unless the rest pattern is used on a mutable hash table). Your example that tries to match "k 10" would be an error, since k is used as an expression, not as a binding pattern.