RFC: hash table pattern matching

General
33

Ironically, I think what you just mentioned supports my argument for expressions in key positions. If we have patterns in key positions, the key-comparison mode is probably going to be all wrong.

Consider:

(define x (list 42))
(define y (list 42))
(match (hasheq x 1)
  [(hash* [(== y) v]) v]
  [_ 'no-match])

What should this program evaluate to? If I read the doc of ==, I might think that the answer is 1. But a matching that actually returns 1 would be inefficient because now it needs to search the entire hash table for a key that is equal? to y.

In my proposal, guaranteeing efficient lookup is a design principle. I am matching a hasheq, so I want the key-comparison mode to be eq?, so that I can quickly hash-ref on y. In my proposal:

(define x (list 42))
(define y (list 42))
(match (hasheq x 1)
  [(hash* [y v]) v]
  [_ 'no-match])

would result in 'no-match

Indeed, the current hash-table pattern is similarly “wrong”:

(define x (list 42))
(define y (list 42))
(match (hasheq x 1)
  [(hash-table [(== y) v] [_ _]) v]
  [_ 'no-match])

evaluates to 1, instead of 'no-match.

To reiterate, I think using == and literal patterns is not a good idea. They already have their semantics, which are to use equal? for comparison (by default). But what we want for efficient matching on a hash table is to hash-ref on keys quickly, mandating that we use whatever key-comparison mode that the matching hash table has. Expressions in key positions allow us to do this.

2 Likes