# Would it make sense to add a function for inverting a hash table to the standard library? **URL:** \ **Category:** General\ **Created:** [July 23, 2025, 8:43pm UTC](https://racket.discourse.group/t/would-it-make-sense-to-add-a-function-for-inverting-a-hash-table-to-the-standard-library/3869 "2025-07-23T20:43:51Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![ddrake](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ddrake/32/2353_2.png) [@ddrake](https://racket.discourse.group/u/ddrake)\ **Post date:** [July 23, 2025, 8:43pm UTC](https://racket.discourse.group/t/would-it-make-sense-to-add-a-function-for-inverting-a-hash-table-to-the-standard-library/3869/1 "2025-07-23T20:43:51Z")
If you have a hash table, there's a pretty reasonable "inverse" to that table: in the original, you have keys mapping to values. The obvious inverse would be a hash table whose keys are the values in the original table, and the values are lists of keys in the original table with that value. (Or perhaps sets, or some other suitable data structure.) Given that there are functions in the standard library for things like intersecting and unioning hash tables, it seems like this inverse operation would belong there, too. FWIW, I wrote this today: ```scheme (define (invert-hash-table ht) (define values-to-key-list (make-immutable-hash (for/list ([val (set->list (apply set (hash-values ht)))]) (cons val empty)))) (for/fold ([acc values-to-key-list]) ([pair (hash->list ht)]) (let* ([val (cdr pair)] [key (car pair)] [keylist (hash-ref acc val)]) (hash-set acc val (cons key keylist))))) ``` (1) is there a more standard, easy way to do this? Am I missing some existing library function or one-liner? (2) If not, would it make sense to add the above function (or something equivalent) to the standard library? (3) A question/feedback: it was counterintuitive to me to discover that I needed to use `car` and `cdr` for the pairs, and that `first` and `second` did not work. That seems weird to me. I know `car` and `cdr` (and I even know [their etymology as 'contents of the address/decrement register'](https://en.wikipedia.org/wiki/CAR_and_CDR#Etymology)) but I find it more readable to see `first` and `second`. And my guess was that `first` and `second` were just syntactic sugar / aliases for `car` and `cdr`. Although I do see some ambiguity for "second" for a list, even a list of two elements: is "second" the second element, or the list containing just the second element (that is, the `rest` of the list)...? ---
**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:** [July 23, 2025, 9:01pm UTC](https://racket.discourse.group/t/would-it-make-sense-to-add-a-function-for-inverting-a-hash-table-to-the-standard-library/3869/2 "2025-07-23T21:01:23Z")
To me it doesn't make sense to include operations the data structure can't implement efficiently. If I have a program that need an "inverse" I just use two hash tables. Do you have concrete examples where an inverse is needed? > 1. A question/feedback: it was counterintuitive to me to discover that I needed to use `car` and `cdr` for the pairs, and that `first` and `second` did not work. The names are somewhat historical, but `car` and `cdr` signals that one works with "a data structure built with pairs" - whereas `first` and `rest (and `second`) signal that one works with lists (which is a subset of "a data structure built with pairs"). Before contracts the names `first` and `rest` was just a help for readers of the program. After contracts were introduced, `first` and `rest` check whether they receive lists. Note: `second` is the same as a `cadr` that accepts lists only. ---
**Author:** ![shawnw](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/shawnw/32/1031_2.png) [@shawnw](https://racket.discourse.group/u/shawnw)\ **Post date:** [July 23, 2025, 10:21pm UTC](https://racket.discourse.group/t/would-it-make-sense-to-add-a-function-for-inverting-a-hash-table-to-the-standard-library/3869/3 "2025-07-23T22:21:32Z")
For cases where the same equality and hash functions can be used for both the keys and values, and values are unique, I'd just use ```scheme (define (invert-hash-table ht) (hash-map/copy ht (lambda (k v) (values v k)))) ``` * * * Edit: One that lets you specify which kind of hash table to return and stores keys as a list per distinct value: ```scheme (define (invert-hash-table ht #:kind [kind 'equal]) (for/fold ([new-ht (case kind [(equal) (hash)] [(eqv) (hasheqv)] [(eq) (hasheq)] [(equal-always) (hashalw)])]) ([(k v) (in-hash ht)]) (hash-update new-ht v (curry cons k) '()))) ``` (`hash-update` makes folding over things while accumulating results in a hash table so easy) ---
**Author:** ![notjack](https://avatars.discourse-cdn.com/v4/letter/n/e47774/32.png) [@notjack](https://racket.discourse.group/u/notjack)\ **Post date:** [July 24, 2025, 12:20am UTC](https://racket.discourse.group/t/would-it-make-sense-to-add-a-function-for-inverting-a-hash-table-to-the-standard-library/3869/4 "2025-07-24T00:20:01Z")
There's a lot of variation in how this could work, to the point where I'm not sure it merits its own function. All of these questions could have different answers: - Do you want a mutable or immutable hash table? - How do you want key comparisons to work? `equal?`, `eqv?`, `eq?`, `equal-always?`, or something else? - How do you want to handle duplicates? Error? Take the first or last one? Merge them into a collection? - And if you do want to gather all duplicates into a collection, do you want a list? A vector? A set? For that reason, I would reach for either `for/hash` to solve this problem in simple cases or [transducers](https://docs.racket-lang.org/rebellion/Transducers.html) and [reducers](https://docs.racket-lang.org/rebellion/Reducers.html) in complex cases. Your `invert-hash-table` definition can be implemented with transducers like this: ```scheme (define (invert-hash-table ht) (transduce (in-hash-entries ht) (bisecting entry-value entry-key) (grouping into-list) #:into into-hash)) ; returns (hash 1 '(a b) 2 '(e c) 3 '(d)) (invert-hash-table (hash 'a 1 'b 1 'c 2 'd 3 'e 2)) ``` ---
**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:** [July 24, 2025, 10:16pm UTC](https://racket.discourse.group/t/would-it-make-sense-to-add-a-function-for-inverting-a-hash-table-to-the-standard-library/3869/5 "2025-07-24T22:16:55Z")
Skip the extra `set->list`, you don't need it. ```scheme (for/list ([val (apply set (hash-values ht))]) …) ``` You could equally do something like (edit: GMail eats whitespace on outgoing messages): ```scheme (for/fold ([h (hash)]) ([pair (hash->list ht)]) (match-define (cons k v) pair) (hash-update h v (curry cons k) empty)) ``` ---
**Author:** ![ddrake](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ddrake/32/2353_2.png) [@ddrake](https://racket.discourse.group/u/ddrake)\ **Post date:** [July 25, 2025, 7:06pm UTC](https://racket.discourse.group/t/would-it-make-sense-to-add-a-function-for-inverting-a-hash-table-to-the-standard-library/3869/6 "2025-07-25T19:06:13Z")
> [@notjack](#): > > There's a lot of variation in how this could work, to the point where I'm not sure it merits its own function. All of these questions could have different answers: Those are good points. It does look like, since there are so many questions, and so many different answers, that any library function for inverting a hash table that attempted to serve all those different needs would at best be very complex, and possibly slow because of all the overhead of trying to be all things to all people. It could also just be difficult to use because anyone trying to use it for their specific situation would have to wade through all the documentation and examples for completely different situations. ---
**Author:** ![ddrake](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ddrake/32/2353_2.png) [@ddrake](https://racket.discourse.group/u/ddrake)\ **Post date:** [July 25, 2025, 7:09pm UTC](https://racket.discourse.group/t/would-it-make-sense-to-add-a-function-for-inverting-a-hash-table-to-the-standard-library/3869/7 "2025-07-25T19:09:45Z")
> [@notjack](#): > > or that reason, I would reach for either `for/hash` to solve this problem in simple cases or [transducers](https://docs.racket-lang.org/rebellion/Transducers.html) and [reducers](https://docs.racket-lang.org/rebellion/Reducers.html) in complex cases. Y Oh wow, transducers look pretty cool. That `transduce` expression is nicely readable. ---
**Author:** ![ddrake](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ddrake/32/2353_2.png) [@ddrake](https://racket.discourse.group/u/ddrake)\ **Post date:** [July 29, 2025, 11:25am UTC](https://racket.discourse.group/t/would-it-make-sense-to-add-a-function-for-inverting-a-hash-table-to-the-standard-library/3869/8 "2025-07-29T11:25:46Z")
> [@notjack](#): > > For that reason, I would reach for either `for/hash` to solve this problem in simple cases or [transducers](https://docs.racket-lang.org/rebellion/Transducers.html) and [reducers](https://docs.racket-lang.org/rebellion/Reducers.html) in complex cases. Y Are those tranducers and such the same sort of thing that Rich Hickey is talking about [in this Strange Loop conference talk](https://youtu.be/6mTbuzafcII?si=SuImo1fb_q-Z03-7)? ---
**Author:** ![notjack](https://avatars.discourse-cdn.com/v4/letter/n/e47774/32.png) [@notjack](https://racket.discourse.group/u/notjack)\ **Post date:** [July 30, 2025, 12:24am UTC](https://racket.discourse.group/t/would-it-make-sense-to-add-a-function-for-inverting-a-hash-table-to-the-standard-library/3869/9 "2025-07-30T00:24:26Z")
Yes. Slightly different API, same general idea.