Interface the BTreeMap and HashMap in Rust

Question

I am implementing a tree data structure. My idea to do this is to have a struct Tree that have children:SomeMapType<Tree> field to keep track of its children nodes, where SomeMapType may be BTreeMap, HashMap or something else. So instead, I would like it be polymorphic on the map type I choose to use.

Code as follows:

trait Map {
    type Key;
    type Value;
    fn new() -> Self;
}

struct Tree<Symbol, MapType>
where
    MapType: Map<Key = Symbol, Value = Box<Self>>,
{
    children: MapType,
}

impl<Symbol, MapType> Tree<Symbol, MapType>
where
    MapType: Map<Key = Symbol, Value = Box<Self>>,
{
    fn new() -> Self {
        Self {
            children: Map::new(),
        }
    }
}
impl<Key,Value> Map for std::collections::BTreeMap<Key,Value> {
    type Key = Key;
    type Value = Value;
    fn new() -> Self {
        Self::new()
    }
}

So far, so good. However, when I am to use this data type, e.g., calling the new function, by instantiating with a specific map, say BTreeMap, like follows :

fn main() {
    let tree = Tree::<u8,std::collections::BTreeMap<u8,_>>::new();
}

it compiles to an error message :

error[E0271]: type mismatch resolving `<BTreeMap<u8, _> as Map>::Value == Box<Tree<u8, BTreeMap<u8, _>>>`
   --> src/zips.rs:162:16
    |
162 |     let tree = Tree::<u8,std::collections::BTreeMap<u8,_>>::new();
    |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ type mismatch resolving `<BTreeMap<u8, _> as Map>::Value == Box<Tree<u8, BTreeMap<u8, _>>>`
    |
note: cyclic type of infinite size
   --> src/zips.rs:155:18
    |
155 |     type Value = Value;
    |                  ^^^^^
note: required by a bound in `Tree`
   --> src/zips.rs:136:32
    |
134 | struct Tree<Symbol, MapType>
    |        ---- required by a bound in this struct
135 | where
136 |     MapType: Map<Key = Symbol, Value = Box<Self>>,
    |                                ^^^^^^^^^^^^^^^^^ required by this bound in `Tree`

My guess is that there is some trouble for the rust compiler to reason at that location about recursive types. My question is then how to actually achieve putting an interface that masks the implementation (BTreeMap or HashMap) details in my case.

Answer 1

I post the same question on the Rust-Lang forum, and this answer deal with my problem almost perfectly. To be self-contained, I copy-paste the code from there, the code completely thanks to steffahn user from the forum.

trait MapKind<Key, Value> {
    type MapType: Map<Key = Key, Value = Value>;
}

trait Map {
    type Key;
    type Value;
    fn new() -> Self;
    fn insert(&mut self, key: Self::Key, value: Self::Value);
}

struct Tree<Symbol, MK>
where
    MK: MapKind<Symbol, Box<Self>>,
{
    children: MK::MapType,
}

impl<Symbol, MK> Tree<Symbol, MK>
where
    MK: MapKind<Symbol, Box<Self>>,
{
    fn new() -> Self {
        Self {
            children: Map::new(),
        }
    }
}

impl<Key: Ord, Value> Map for std::collections::BTreeMap<Key, Value> {
    type Key = Key;
    type Value = Value;
    fn new() -> Self {
        Self::new()
    }
    fn insert(&mut self, key: Key, value: Value) {
        self.insert(key, value);
    }
}

struct BTreeMap_;

impl<Key: Ord, Value> MapKind<Key, Value> for BTreeMap_ {
    type MapType = std::collections::BTreeMap<Key, Value>;
}

fn main() {
    let tree = Tree::<u8, BTreeMap_>::new();
}

@eggyal also comes up with the same idea, but more complete, by giving me two methods, one using generic traits and the other using generalized associated type in trait.

EDIT

I come back after trying to digest these great answers a bit, in the framework of proof theory. I rename some of the identifiers as follows:

use std::collections::BTreeMap;

// A proposition stating that `ThatType<Key,Value>` implements the anonymously defined map interface
trait SomeTypeImplementsMapInterface {
    type ThatType<Key,Value>;
    
    // an anonymous definition of MapInterface as follows (the total of all specified behaviors in the trait)
    fn new<Key,Value>() -> Self::ThatType<Key,Value>;
}

/// A proof that BTreeMap implements the (anonymous) map interface
struct AProofThatBTreeMapImplementsMapInterface;
impl SomeTypeImplementsMapInterface for AProofThatBTreeMapImplementsMapInterface {
    type ThatType<Key,Value> = BTreeMap<Key,Value>;

    fn new<Key,Value>() -> Self::ThatType<Key,Value> {
        BTreeMap::new()
    }
}
 
struct Tree<Symbol,ProofThatSomeTypeImplementsMapInterface: SomeTypeImplementsMapInterface> {
    children: ProofThatSomeTypeImplementsMapInterface::ThatType<Symbol,Box<Self>>,
}

impl<Symbol,ProofThatSomeTypeImplementsMapInterface: SomeTypeImplementsMapInterface> Tree<Symbol,ProofThatSomeTypeImplementsMapInterface> {
    fn new() -> Self {
        Self {
            children: ProofThatSomeTypeImplementsMapInterface::new(),
        }
    }
}

fn main() {
    let tree = Tree::<u8,AProofThatBTreeMapImplementsMapInterface>::new();
}