How to write a recursive generic type in Rust?

Question

I want to define a HashMap with a key type of String and the value type is itself.

I tried to write something like:

HashMap<String, HashMap<String, ...>>

I found this requires recursion and I don't know how to write recursion in a type.

After reading Recursive generic types, I tried:

type HashToHash = HashMap<String, HashToHash>

However I got error:

error[E0391]: cycle detected when processing `HashToHash`
 --> src/lib.rs:3:35
  |
3 | type HashToHash = HashMap<String, HashToHash>;
  |                                   ^^^^^^^^^^
  |
  = note: ...which again requires processing `HashToHash`, completing the cycle

Is there a way to define this kind of type in Rust?

The duplicate is the wrong one. HashTable acts like a box, so you can have a recursive struct. — starblue
– starblue, Commented Dec 29, 2018 at 13:15
@trentcl Sure, there is no reason why it wouldn't work. A HashMap has a size known at compile time which is independent of the key and value types, so the problem of an infinitely sized type mentioned in the question marked as duplicate does not occur here. There is still a question how useful this type is, since you can't have any values in the leaf nodes, but I can't rule out that there are use cases for this data structure. — Sven Marnach
– Sven Marnach, Commented Dec 29, 2018 at 14:21

feldentm · Accepted Answer · 2022-03-18 20:27:41Z

The compiler is trying to tell you that you are about to define an infinite type. The reason for your mistake is that generics in C# and Java are ∀-polymorphic, i.e. one implementation exists for all parameters. Rust is λ-polymorphic, i.e. for each parameter an implementation is created (and optimized). This is what is usually called a template and you might know it from C++. If Rust developers of the early days would have had more experience, a lot of concepts in Rust would be known under different names. Generics is just one of it.

The only way to resort from the infinite loop is to use some sort of pointer to the type you define on your RHS.

Honstly, I found this question because I wanted to know if Rust can predeclare a template and use pointers to it without knowing the definition. As I did not find any documentation on the topic, the answer is likely no.

If you really need this, you can, in any λ-polymorphic language, resort to an untyped pointer to break the recursion. Doing so, you should wrap all data access behind an API.

Codebling · Accepted Answer · 2023-01-12 00:36:06Z

3

From comments:

use std::collections::HashMap;

struct HashToHash(HashMap<String, HashToHash>);

fn main() {
    let mut h = HashToHash(HashMap::new());
    h.0.insert("gloink".to_owned(), HashToHash(HashMap::new()));
}

Playground link

Reference to original comments: 1 2

answered Jan 12, 2023 at 0:36

Codebling

11.5k3 gold badges45 silver badges71 bronze badges

1 Comment

Codebling Over a year ago

Just putting comments in an answer so it's easier to find. Thanks Sven Marnach and starblue!

Collectives™ on Stack Overflow

How to write a recursive generic type in Rust?

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related