The library want to produce a tree for user to consume. What smart pointer to use and how to abstract it?

1

Suppose a simple code:

use std::rc::Rc;
use std::vec::Vec;

#[derive(Clone,Eq,PartialEq,Debug,Ord,PartialOrd)]
struct Tree<T:Clone+Eq+PartialEq+Ord+PartialOrd+Copy> {
    x : T,
    v : Vec<Rc<Tree<T>>>,
}

fn create_nice_tree<T:Clone+Eq+PartialEq+Ord+PartialOrd+Copy> (x : T) -> Tree<T> {
    Tree {x: x, v: vec![
        Rc::new(Tree{x: x, v: vec![]}),
        Rc::new(Tree{x: x, v: vec![]}),
    ]}
}

fn main() {
   let t : Tree<i32> = create_nice_tree(4);
   println!("{:?}", t);
}

It works. But what if user wants Arc? How do I abstract this out? Naive attempt fails:

use std::rc::Rc;
use std::vec::Vec;
use std::ops::Deref;

#[derive(Clone,Eq,PartialEq,Debug,Ord,PartialOrd)]
struct Tree<T:Clone+Eq+PartialEq+Ord+PartialOrd+Copy, U:Deref<Target = Tree<T,U>>+Clone > {
    x : T,
    v : Vec<U<Tree<T>>>,
}

fn create_nice_tree<T:Clone+Eq+PartialEq+Ord+PartialOrd+Copy, U:Deref<Target = Tree<T,U>>+Clone> (x : T) -> Tree<T,U> {
    Tree {x: x, v: vec![
        U::new(Tree{x: x, v: vec![]}),
        U::new(Tree{x: x, v: vec![]}),
    ]}
}

fn main() {
   let t : Tree<i32, Rc> = create_nice_tree(4);
   println!("{:?}", t);
}
2

Found obvious workaround:

use std::rc::Rc;
use std::sync::Arc;
use std::vec::Vec;
use std::ops::Deref;

macro_rules! tree {
    ($n: ident, $c:ident, $fnn:ident) => {
        #[derive(Clone,Eq,PartialEq,Debug,Ord,PartialOrd)]
        struct $n<T:Clone+Eq+PartialEq+Ord+PartialOrd+Copy> {
            x : T,
            v : Vec< $c <$n <T>>>,
        }
        
        fn $fnn <T:Clone+Eq+PartialEq+Ord+PartialOrd+Copy> (x : T) -> $n<T> {
            $n {x: x, v: vec![
                $c::new($n{x: x, v: vec![]}),
                $c::new($n{x: x, v: vec![]}),
            ]}
        }
    }
}

tree!(RcTree,  Rc,  create_nice_rc_tree);
tree!(ArcTree, Arc, create_nice_arc_tree);

fn main() {
   let tr : RcTree<i32>  = create_nice_rc_tree (4);
   let ta : ArcTree<i32> = create_nice_arc_tree(4);
   println!("{:?}", tr);
   println!("{:?}", ta);
}

But I don't like it.

3

I'd say that this would need higher-kinded types for smart pointers.

4

Will they be introduced to the language?

5

Yup, that's one very valid way of solving this, and it's a common reason to want HKT.

1 Like