# RFC: hash table pattern matching **URL:** \ **Category:** General\ **Created:** [February 3, 2023, 10:00pm UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686 "2023-02-03T22:00:51Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![sorawee](https://avatars.discourse-cdn.com/v4/letter/s/ea5d25/32.png) [@sorawee](https://racket.discourse.group/u/sorawee)\ **Post date:** [February 3, 2023, 10:00pm UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/1 "2023-02-03T22:00:51Z")
The current `hash-table` pattern for `match` is problematic. It is buggy and inefficient. We would like to deprecate the `hash-table` pattern and create a new pattern that does a better job. A preliminary discussion is in [match: fix hash-table pattern and its doc, add more optimizations by sorawee · Pull Request #4532 · racket/racket · GitHub](https://github.com/racket/racket/pull/4532). I will summarize viewpoints from the discussion in each section to show possible design spaces. ## Naming Everyone seems to agree on the name `hash`. One downside of `hash` is that the `hash` constructor constructs only immutable hash tables, but the `hash` pattern should be able to destruct mutable hash tables. However, there doesn't seem to be a good alternative name. ## General syntax Should key and value be grouped together? One reason why we should _not_ group key and value together is to make the pattern resemble the constructor. The `hash` function is used like this: ```scheme (hash key-1 val-1 key-2 val-2) ``` So perhaps the `hash` pattern should do the same. On the other hand, one reason why we should group key and value together is to make it clearer to readers. I personally really don't like reading. ```scheme (hash 'abc 'def' 'ghi 'jkl 'mno 'pqr 'stu 'vwu) ``` Is `'mno` a key or a value? To answer that I need to start parsing from `'abc`. On the other hand, with grouping, I can immediately tell that `'mno` is a key. ```scheme (hash ['abc 'def'] ['ghi 'jkl] ['mno 'pqr] ['stu 'vwu]) ``` A counterargument is that one can use newline as a way to group already, which IIUC is the "Clojure style". ```scheme (hash 'abc 'def' 'ghi 'jkl 'mno 'pqr 'stu 'vwu) ``` A counter-counterargument is that it is unnecessarily verbose, and the "Racket style" tends to group things explicitly. One more datapoint is that the current `hash-table` pattern does group key and value together. Currently, @samth advocates for no grouping, while I (@sorawee) advocates for grouping. ## Features ### Full and partial matching A full matching requires that there is no keys besides those listed in the pattern. A partial matching allows extra keys. For example: ```scheme (match (hash 1 2 3 4) [(hash [1 a]) a] [_ 'none]) ``` would return `'none` under the full matching semantics, and `2` under the partial matching semantics. The question that I want to ask here is about what _could_ be supported. There are three choices. 1. Only support full matching. 2. Only support partial matching. 3. Support both. IIUC, currently @samth advocates for (1) for the initial implementation, though he is open to further extension in the future. @notjack advocates for (2). @AlexKnauth and I advocate for (3). ### Default matching behavior If you choose "support both" in the previous section, congrats, you have one more thing to think about: what should be the default matching behavior? Three possibilities: - Partial matching by default. That is to say the above program would return `2`. However, the pattern could support something like `(hash [1 a] #:full)` to fully match. - Full matching by default. - Explicit mode is required. Or perhaps there should be two separate patterns `full-hash` and `partial-hash`. Currently: - @AlexKnauth advocates for partial matching by default, but users can use the rest feature (see below) to do full matching. - I prefer full matching by default, but users can use the rest feature to do partial matching - My another preference is partial matching by default, but if `#:full` is given, it would do the full matching. ## Rest feature The rest feature allows users to extract the residue from matching. For example: ```scheme (match (hash 1 2 3 4 5 6) [(hash [1 a] #:rest h) h]) ``` would produce `(hash 3 4 5 6)`. There are many possibilities for this feature: ### Syntax: keyword vs ellipsis Should the rest feature be expressed by `#:rest`, as shown above, or ellipsis, as shown below? ```scheme (match (hash 1 2 3 4 5 6) [(hash [1 a] h ...) h]) ``` One reason to _not_ prefer ellipsis is that ellipsis-bound variable has always been a list in `match`. But we might not necessarily want a list as a result (see next section). ### Hash table vs list What should the residue be? A hash table or a list? The current `hash-table` pattern extracts the residue as a list (via ellipsis). ```scheme (match (hash 1 2 3 4 5 6) [(hash-table [1 _] h ...) h]) ``` produces `'((3 4) (5 6))`. A hash table extraction is much more efficient when the matching value is an immutable hash table, taking time proportional to the number of key-value pairs if keys are not arbitrary patterns (see next section). In contrast, list extraction takes linear time to the size of the hash table. I also believe that a hash table result is the preferred format that can be used in future computation. In contrast, for list extraction to be useful, the list probably needs to be converted back to a hash table. * * * Currently, @samth seems to be against the rest feature in general for the initial implementation, but seems to prefer ellipsis/list extraction if the rest feature is to be implemented. @notjack seems to prefer ellipsis/hash extraction, though not against keyword/hash extraction. I prefer the keyword/hash extraction. @AlexKnauth seems to prefer a hash extraction. ## Key position What should the key position be? A couple of possibilities: - The key position can be an arbitrary _pattern_. The `hash-table` pattern currently does this. The disadvantage is that it is _extremely_ inefficient in general and doesn't seem to be useful. We can of course specialize cases where we know how to make matching efficient. But is it worth supporting the feature in the first place? - The key position must be a literal. This is the specialized clause in the current `hash-table` pattern that can be matched efficiently. - The key position can be an arbitrary _expression_. This is like literals, but it would also allow variable reference, etc, without making matching inefficient. - Or maybe we could allow `id`, literals, and `(== expr)` but nothing else. The intention is that it could potentially be useful to extract one arbitrary key without any constraint out (via `hash-iterate-first`). However, for the `id` case, the corresponding value pattern must also be an `id` or `_`, so that there is no constraint from the value pattern. I'm not aware of anyone's position on this except mine, which is to support arbitrary expressions, but not arbitrary patterns. Ideally, I want to support `id` too, but that seems too complicated. ## Duplicate keys Should duplicate keys be allowed to successfully match? That is to say, should: ```scheme (hash [1 a] [1 b]) ``` be equivalent to: ```scheme (hash [1 (and a b)]) ``` ? Or should duplicate keys always fail matching? Or should it _error_? If literals are given, should `match` warn/error at compile-time? One data point is that the `hash-table` pattern always fail matching on duplicate keys, but doesn't cause an error (though there's a bug that could make matching successful). I'm not aware of anyone's position on this, and I personally don't have a preference either. Supporting duplicate keys is probably the cleanest semantics, I think? ---
**Author:** ![joeld](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/joeld/32/38_2.png) [@joeld](https://racket.discourse.group/u/joeld)\ **Post date:** [February 3, 2023, 10:34pm UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/2 "2023-02-03T22:34:09Z")
Disclaimer, these are the thoughts of a non-CS user. Regarding matching behavior, rest, and residue: If I knew only enough about `match` to be familiar with how it treated lists, and you forced me to guess what I would find in the Racket docs about `match`ing hash tables, here’s what I would guess we would find: > - `(hash 'abc 'def)` for a full match > - `(hash* 'abc 'def h)` for a partial match — with `h` being an actual hash table. Key position: in the guessing-about-the-docs thought experiment above, I would have supposed that just about anything allowed in a `list` pattern would also be allowed in a `hash` pattern. But after thinking about it for three minutes, I think I agree that arbitrary expressions, but not arbitrary patterns, might be the most reasonable. Duplicate keys: if you had duplicate _literal_ keys, that seems like it should raise an exception? But supporting arbitrary expressions for keys might mean it is best to just allow duplicates. I take it utterly for granted that a `hash` or `hash*` would never match on duplicate keys. ---
**Author:** ![alexh](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/alexh/32/315_2.png) [@alexh](https://racket.discourse.group/u/alexh)\ **Post date:** [February 3, 2023, 11:15pm UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/3 "2023-02-03T23:15:53Z")
There are two things I would like in the hash matching feature that I think are missing from this proposal: - Providing default values for the match - a discussion on the efficiency of a "rest" pattern when matching a subset of the keys **Providing default values for the match** : I noticed that it is a lot easier to provide a default value to `hash-ref` in cases where I want to handle a missing key immediately. That is, I think it is simpler to write code as shown below, than the alternative of using `with-handlers` to catch the exception. I also found that I almost always want to actually handle errors, since I can usually either handle the missing value, or provide a more appropriate error message to the user. For me, to be useful, a hash matching functionality needs to allow a default to the value if the key is not in the hash. ```scheme (let ([val (hash-ref key a-hash #f)]) (if val (begin ...) (error "Some meaningful error to the user")) ``` **Efficiency of a "rest" pattern when matching a subset of the keys** A lot of time I need to get a few keys out of a hash table that can contain many other keys. In such cases, I don't want the hash table matcher to allocate a new hash table with the remaining elements (which I would not use). * * * I would also like to see some concrete use cases of hash tables in the proposal. For example, it is not clear to me that the code below is more readable than just using `hash-remove ` (and would it be as efficient as the `hash-remove` ?): ```scheme (match (hash 1 2 3 4 5 6) [(hash-table [1 _] h ...) h]) ``` It is also not clear that the code: ```scheme (match (hash 1 2 3 4) [(hash [1 a]) a] [_ 'none]) ``` is more readable than using `hash-ref` with a `'none` default value; and it is not clear how it can be extended to look up two values: ```scheme (define h (hash 1 2 3 4)) (define a (hash-ref 1 h 'none-a)) (define b (hash-ref 2 h 'none-b)) ``` Also, would the match code allow users to concisely express an inefficient match? For example, if the user tries to find the key that is bound to the value 10 in a large hash table, would they get some warning? ```scheme (define k (match (make-some-hash-table-with-lots-of-keys) ((hash k 10) k) (_ 'none)) ``` I can imagine many ways in which users would be able to easily create inefficient code using the hash matching behaviour. Alex. ---
**Author:** ![sorawee](https://avatars.discourse-cdn.com/v4/letter/s/ea5d25/32.png) [@sorawee](https://racket.discourse.group/u/sorawee)\ **Post date:** [February 4, 2023, 6:24am UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/4 "2023-02-04T06:24:23Z")
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 `: ```scheme (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: ```scheme (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 ` 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/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/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/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](https://github.com/nix-community/dream2nix/blob/f61d9311e224a2c5f6691f8f8d7411e7284650fb/src/subsystems/racket/translators/racket-impure/generate-dream-lock.rkt#L182-L192) > 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. ---
**Author:** ![gus-massa](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/gus-massa/32/507_2.png) [@gus-massa](https://racket.discourse.group/u/gus-massa)\ **Post date:** [February 4, 2023, 8:18pm UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/5 "2023-02-04T20:18:29Z")
I don't use `match` too much, so I was surprised that the `hash-table` can match partial cases. I like `(hash a b c d h ...)`, where `h` is a hash like the initial hash. I don't expect too long list of key-values, and in that case I expect to use the vertical alignment. I used it to open `http` connections that is a function that has like 5 arguments and 5 keywords [(see for example http-sendrecv)](https://docs.racket-lang.org/net/http-client.html#%28def._%28%28lib._net%2Fhttp-client..rkt%29._http-sendrecv%29%29). Moreover I used comments as fake keywords for the first arguments. Does the macro detect `(hash a b c d _ ...)`. and avoid the creation of the rest part? It looks very difficult to remove the creation of the unused rest part later in the optimization. What about removing the `_` and allowing `(hash a b c d ...)`? Is it too weird to have a `...` that just match the rest and are not connected to any binding? A weird question: What happens with `(hash x 10 y 10)`? Can it bind `(hash 'a 10)`? I agree that the general case is very inefficient. Perhaps start the initial version very restrictive conditions in the keys (like only literals) and later add more case in case they are popular in the wild. The reverse option is harder due to backward compatibility. Another weird question: What happens with weak hashes? If the keys in the match clause can only be literals, I don't see any problem. But in a general case where the weak hash must be iterated, it can be a problem if the garbage collector removes something and the internal structure change and the iterator gets confused. ---
**Author:** ![pschlie](https://avatars.discourse-cdn.com/v4/letter/p/3d9bf3/32.png) [@pschlie](https://racket.discourse.group/u/pschlie)\ **Post date:** [February 4, 2023, 9:34pm UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/6 "2023-02-04T21:34:35Z")
IMO (key value) pairs should be represented as just that, "pairs"; if some folks would prefer to omit clarifying punctuation, why not simply introduce some syntactic sugar: (pair \ \ \ \ ...) =\> (\ \) (\ \) ... So either may be used as desired: (hash (\ \) (\ \) ...) -or- (hash (pair k.0\> \ \ \ ...)) As just a thought. ---
**Author:** ![shhyou](https://avatars.discourse-cdn.com/v4/letter/s/ccd318/32.png) [@shhyou](https://racket.discourse.group/u/shhyou)\ **Post date:** [February 4, 2023, 11:46pm UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/7 "2023-02-04T23:46:22Z")
I second the proposal that 1. Assumes the keys in the `hash` pattern are restricted to expressions, not other patterns 2. Defaults to full matching but supports the `#:rest` option, assuming that `#:rest _` is compiled to no-op and full match is just some additional size check. 3. Groups key-value pairs and uses keywords for the other options (like `#:rest`). In addition, I like @joeld's suggestion to have `hash*` for partial matches. The pattern `(hash* [k-expr v-pat] ...)` can just be a match expander that turns into `(hash #:rest _ [k-expr v-pat] ...)`. The name `hash*` is also consistent with the match expander `struct*`. For the syntax of `hash`, the 3rd point is very important for match expanders and for macros that generate match expanders. If the `hash` pattern splices the key-value sequences or uses ellipsis, the escape syntax would be challenging for everyone -- macro authors would need to escape `~@` and `...` one or two times in the syntax template. For example, consider this macro for defining JSON match expanders: > Had `hash` used ellipsis to express partial matching, in order to generate `_ ...` macro authors would have to write ```scheme #'(hash-table [k v] ... _ (... (... ...))) ``` because `define-json-expander` is a macro that generates another macro (a match expander) and thus requires two levels of escape. Similarly, macro authors would need to escape `~@` as `(... ~@)` in order to express the splicing in the generated macro. * * * I don't any opinion about what `#:rest` should do. Actually, what would be a practical use case of `(hash [k v] ... #:rest non-trivial-pattern)`? I assume that `hash*` would be the most popular case, so `hash` that supports `#:rest _` is a good solution without sacrificing the ability of expressing full-match semantics. However, I am curious what are the applications of `#:rest` given that it would just be removing some fixed & finite set of entries. I can understand samth's opposition to the `#:rest` feature. It is not clear what the semantics should be if we can't find applications other than `#:rest _` at the moment. Not adding `#:rest` right now makes it possible to choose the right behavior later. On a side note, I wonder whether there is a need to differentiate between mutable/immutable hashes, `hasheq`, `hasheqv`, `hash` (equal) and `hashalw`. For example, should the pattern `(hash-table [(== (expt 2 100)) val])` fail for the hash table `(hasheq (expt 2 100) "no-match")`? What if the keys contain some mutable boxes? ---
**Author:** ![shhyou](https://avatars.discourse-cdn.com/v4/letter/s/ccd318/32.png) [@shhyou](https://racket.discourse.group/u/shhyou)\ **Post date:** [February 4, 2023, 11:55pm UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/8 "2023-02-04T23:55:41Z")
> [@gus-massa](#): > > I don't use `match` too much, so I was surprised that the `hash-table` can match partial cases. This behavior was unintentionally introduced for the specific case where the keys are all literals and there is at least one key. The GitHub PR details the relevent commits. > [@gus-massa](#): > > What about removing the `_` and allowing `(hash a b c d ...)`? Is it too weird to have a `...` that just match the rest and are not connected to any binding? It's simply that partial matches are common for extracting fields in JSON hash tables: [RFC: hash table pattern matching - #4 by sorawee](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/4) > [@gus-massa](#): > > A weird question: What happens with `(hash x 10 y 10)`? Can it bind `(hash 'a 10)`? I think it is better to restrict the keys to expressions and ask the users to write `(app hash->list (list-no-order XYZ ...))` if they want to search for the keys. ---
**Author:** ![gus-massa](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/gus-massa/32/507_2.png) [@gus-massa](https://racket.discourse.group/u/gus-massa)\ **Post date:** [February 5, 2023, 2:11am UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/9 "2023-02-05T02:11:59Z")
Just to note that `list-no-order` already can(must?) produce very slow code to check all the cases, but the name is more scary. So it may be not so strange that `hash` produce slow code. Perhaps it would be better to allow any pastern for keys and values like in the other forms, but add a big warning in the docs. ---
**Author:** ![ryanc](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ryanc/32/71_2.png) [@ryanc](https://racket.discourse.group/u/ryanc)\ **Post date:** [February 5, 2023, 2:23am UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/10 "2023-02-05T02:23:12Z")
I feel strongly that when a constructor name is also used as a pattern form, they should use the same syntax. That is, `hash` should have ungrouped key-value pairs. On the other hand, I think it's reasonable for the pattern form to support a superset of the constructor's syntax, for example through keywords. So my preferences would be: - `hash` uses ungrouped key-value pairs. - `hash*` uses grouped key-value pairs (and maybe allows extensions like `#:default` clauses for missing keys). Both forms should allow keyword options to indicate complete vs partial matches and maybe other things like hash kind and key comparison (or maybe that's better left to `and` and predicates). I don't have a preference about complete vs partial matching for the default, but there should be explicit syntaxes for both behaviors. I think we should avoid automatically conflating partial matches with an optional "rest" pattern. I almost always want partial matches, but I have never wanted an updated hash with the matched keys removed. Avoiding that feature would avoid questions like whether mutable hashes (or weak/ephemeron hashes) are converted to immutable tables or copied, etc. ---
**Author:** ![shhyou](https://avatars.discourse-cdn.com/v4/letter/s/ccd318/32.png) [@shhyou](https://racket.discourse.group/u/shhyou)\ **Post date:** [February 5, 2023, 2:52am UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/11 "2023-02-05T02:52:19Z")
While `hash-table` in general is slow, the special case where the key patterns are all literals is very fast (just `hash-has-key?` checks and `hash-ref`s). This is also a very common use case. ---
**Author:** ![soegaard](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/soegaard/32/19_2.png) [@soegaard](https://racket.discourse.group/u/soegaard)\ **Post date:** [February 5, 2023, 11:36am UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/12 "2023-02-05T11:36:56Z")
> One reason to _not_ prefer ellipsis is that ellipsis-bound variable has always been a list in `match` . > But we might not necessarily want a list as a result (see next section). It makes sense to reserve the ellipsis for lists. In analogy with `list-rest` I suggest introducing a `hash-rest` where the last pattern is bound to a hash table with the rest of the pairings. If an ellipsis-like notation is needed for `hash`, how about `ht...` instead of `...`? ---
**Author:** ![benknoble](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/benknoble/32/16_2.png) [@benknoble](https://racket.discourse.group/u/benknoble)\ **Post date:** [February 5, 2023, 8:13pm UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/13 "2023-02-05T20:13:35Z")
Some datapoints, with a grain of salt. (Disclaimer, I started responding from the top, so if something is already covered, please ignore it.) ### Naming Probably not the immediate concern, but what about `dict` that could match any `gen:dict`? Then sticking with the constructor syntax isn't an issue, since there is no unified constructor syntax. OTOH, this is probably vastly more complex. ### General Syntax I prefer to think of hashes and dicts like binding pairs. Racket has many examples of grouping related items with square brackets when it doesn't indicate `#%app`. So I like `[key value]` syntax. A `dict` matcher being a future possibility, with the likelihood of using `[key value]` syntax, leads me to believe that some consistency with `hash` and `dict` would be nice. Let's also not forget that `hash` is not the only constructor, and both hash-literals and `make-hash`-style constructors take assoc-lists. I suggest we not write dotted-pairs `[key . value]`, though. ### Full/Partial Matching I like (3) support both, and I think they deserve something to distinguish them. Hypothetically, `hash` is full only, and a later `hash*` can be partial. This gives preference to @samth's (1) for the initial implementation. Looks like @joeld and I agree on this. ### Rest pattern This reminds me assoc lists and functional maps; I like the general idea. Seems to allow for partial matching as you wrote, and my `hash*` from above can be sugar for this. I suggest we pin down the semantics to avoid the original issues. Related to the later headings, I strongly prefer a hash residue in the spirit of functional immutable programming. ### Key Position I would have to think more about typical uses of match with hashes, and what uses would be supported by different options. As it is I rarely use `hash-table`, biased by my use of SML/NJs opaque mapping structures. I think @alexh raises good points here, where usage drives my opinions on some of these things (and existing APIs might be more suitable). ### Duplicate Keys The duplicate keys problem seems moot until "Key Position" is resolved. * * * Related work: - [The ORD\_MAP signature](https://www.smlnj.org/doc/smlnj-lib/Util/sig-ORD_MAP.html) from SML/NJ, where implementation's map types are opaque, so no matching can be done. But the API makes operations convenient in terms of an added or removed "binding" (key-value pair) and the residual hash. There are also plenty of functors for creating ORD\_MAPs over specific key types. ---
**Author:** ![sorawee](https://avatars.discourse-cdn.com/v4/letter/s/ea5d25/32.png) [@sorawee](https://racket.discourse.group/u/sorawee)\ **Post date:** [February 5, 2023, 9:32pm UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/14 "2023-02-05T21:32:29Z")
Thanks everyone! I will reply to points later this week. For now, here’s an initial implementation that is implemented as a match expander, so that you can run without modifying `match`. There’s also a test module attached at the end. [https://gist.github.com/sorawee/dcd9d365b30fff8ef8f65c5a53e92ed6](https://gist.github.com/sorawee/dcd9d365b30fff8ef8f65c5a53e92ed6) Some design decisions: - `hash` with no grouping but without `#:default` support. Full matching by default. - `hash*` with grouping and with `#:default` support. Partial matching by default. - `hash*` to `hash` is like `struct*` to `struct` rather than `list*` to `list`. In particular, `hash*` doesn’t mandate a “rest pattern” like `list*`. - `#:default` support. - Possible keywords at the end: `#:full` for explicit full matching, `#:partial` for explicit partial matching, `#:rest rest-pat` for full matching with residue. `#:rest _` specially recognized to be equivalent to `#:partial`. - Non-trivial `#:rest` would construct a residue hash table. This is only efficient for immutable hash tables. The residue hash table preserves key comparison and weak/strong/ephemeron-ness. - Key positions are expressions. - Duplicates are not allowed. This makes full matching easier to implement efficiently (esp. in presence of `#:default`). ---
**Author:** ![jbclements](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/jbclements/32/11_2.png) [@jbclements](https://racket.discourse.group/u/jbclements)\ **Post date:** [February 5, 2023, 11:54pm UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/15 "2023-02-05T23:54:35Z")
Generally speaking, I respect y'all's opinions enormously. I think the only area of this for which I'd like to put my coin on the scale is in the area of key/value grouping, and (like @shhyou and @sorawee ) I support it. Indeed, every time I construct a hash without grouping it feels slightly wrong to me. In addition, I think that @shhyou makes a compelling argument in the syntactic arena. ---
**Author:** ![sorawee](https://avatars.discourse-cdn.com/v4/letter/s/ea5d25/32.png) [@sorawee](https://racket.discourse.group/u/sorawee)\ **Post date:** [February 6, 2023, 12:02am UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/16 "2023-02-06T00:02:16Z")
On second thought, I think I would prefer allowing duplicates, which makes partial matching significantly faster, while full matching is still as slow as it currently is. In the current implementation of `hash*`, which disallows duplicates: ```scheme "partial match" cpu time: 2124 real time: 2218 gc time: 27 "full match" cpu time: 2152 real time: 2255 gc time: 8 "hash-table, which is buggy, but it allows partial match and duplications" cpu time: 1126 real time: 1220 gc time: 1 ``` But if `hash*` allows duplicates: ```scheme "partial match" cpu time: 589 real time: 624 gc time: 22 "full match" cpu time: 2052 real time: 2142 gc time: 7 "hash-table, which is buggy, but it allows partial match and duplications" cpu time: 1096 real time: 1173 gc time: 0 ``` Here’s the benchmark: ```scheme #lang racket (require "hash-pattern.rkt") (define N 10000000) (define (test h) (match h [(hash* [1 v] [2 v2] [3 v3]) (list v v2 v3)])) (define (test2 h) (match h [(hash* [1 v] [2 v2] [3 v3] #:full) (list v v2 v3)])) (define (test3 h) (match h [(hash-table [1 v] [2 v2] [3 v3]) (list v v2 v3)])) (define h (hash 1 2 2 3 3 4)) "partial match" (time (for ([i (in-range N)]) (test h))) "full match" (time (for ([i (in-range N)]) (test2 h))) "hash-table, which is buggy, but it allows partial match and duplications" (time (for ([i (in-range N)]) (test3 h))) ``` ---
**Author:** ![greghendershott](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/greghendershott/32/98_2.png) [@greghendershott](https://racket.discourse.group/u/greghendershott)\ **Post date:** [February 6, 2023, 4:23pm UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/17 "2023-02-06T16:23:27Z")
Super trivial bike-shedding about surface syntax "ergonomics": In a variant like the proposed `hash*` which groups using delimiters, ``` [key-pat val-pat] ``` it feels verbose needing to write `#:default`: ``` [key-pat val-pat #:default default-val] ``` Instead could it simply be (somewhat like Scribble `defproc` style): ``` [key-pat val-pat default-val] ``` After all, one reason for using delimiters (as well as for readability, and historically for want of `syntax-parse` splicing 😉) is it allows riffing on "arity" like this. * * * Maybe the `#:default` is allowed but optional for those who think it aids readability. (Although even here I'd suggest something shorter like `#:else` or even `#:or`?) So I guess: ``` mapping-pattern = [key-pat val-pat default] default = | val | #:or val ``` ---
**Author:** ![ryanc](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ryanc/32/71_2.png) [@ryanc](https://racket.discourse.group/u/ryanc)\ **Post date:** [February 7, 2023, 7:18am UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/18 "2023-02-07T07:18:01Z")
I forgot to mention this in my previous message, but I think it would be better to have key _patterns_ rather than key _expressions_. The patterns should be restricted to atomic datum patterns, quoted datum patterns, and explicit `==` patterns. The mixture of expressions and patterns is confusing/suprising. As evidence, see Greg's message above this one, where he talks about `key-pat`. Using restricted key patterns also makes it easier to correctly recognize the common case where the keys are constants: you can use the rules for patterns rather than trying to analyze Racket expressions. (No `local-expand` or `#%datum` checks needed.) ---
**Author:** ![notjack](https://avatars.discourse-cdn.com/v4/letter/n/e47774/32.png) [@notjack](https://racket.discourse.group/u/notjack)\ **Post date:** [February 8, 2023, 1:21am UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/19 "2023-02-08T01:21:59Z")
I strongly believe the default `hash` pattern should use partial matching, for the reasons I outlined in [my comment on the pull request](https://github.com/racket/racket/pull/4532#issuecomment-1414417270). To summarize, people are going to do this _a lot_: ```scheme (match (get-json-from-some-web-api) [(hash 'user user-id 'posts post-list) (do-stuff user-id post-list)]) ``` This will break whenever the web service being used decides to put a little more data in their response. Given the prevalence of JSON web APIs in the modern development landscape, this will catch a lot of people off guard. ---
**Author:** ![shhyou](https://avatars.discourse-cdn.com/v4/letter/s/ccd318/32.png) [@shhyou](https://racket.discourse.group/u/shhyou)\ **Post date:** [February 8, 2023, 2:04am UTC](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686/20 "2023-02-08T02:04:51Z")
I feel like it is sufficient to have two different patterns with examples in the docs, like using `hash*` for default partial matching and `hash` for default full matching. [Next page](https://racket.discourse.group/t/rfc-hash-table-pattern-matching/1686.md?page=2)