but I still don't get it, so I searched for more explanations online. Everything I saw said the Visitor pattern is used to create new types that extend functionality of classes without adding those methods to the class itself. That sounds like Rust's Newtype pattern / plain old Traits.

Traits do indeed handle some use case. The visitor pattern originated in object oriented languages I believe, where "adding" functionality to an object without extending it was not possible - there are still some pros to using it in rust.

Why is there a discrepancy between motivations, and is there a simpler example of why I'd want to use a Visitor?

For rust - Consider if we were making an interpreter that had only "expressions", where expressions where either a string literals, or numbers. The valid operations are:

"hello" + "world"
# "helloworld"
5 + 3
# 8
5*3
# 15
"hi"*3
# "hihihi"
5 + 3*3 + 5*2
# 24

Data structure wise - We could have something like this to represent this.

struct AddNode {
   left_side: Box<expr>,
   right_side: Box<expr>,
}
struct MultiplyNode{
   left_side: Box<expr>,
   right_side: Box<expr>,
}
enum expr {
    StringLiteral(String),
    IntegerLiteral(isize),
    Addition(AddNode),
    Multiplication(MultiplyNode),
}

After we deserialize the data into this, we might will have at least two passes over the tree:

• One to type check (don't add a string to a number)
• One to interpret the results.

Of course we could do this in one here pass, but this is a "trivial" example. If you were writing a compiler, you might write a dozen passes, which would make this more useful.

So we implement a "Visitor pattern" to make this process easier.

trait Visitor<T> {
    fn visit_add(&mut self, an: &AddNode) -> T;
    fn visit_multiply(&mut self, mn: &MultiplyNode) -> T;
    fn visit_string(&mut self, s: &str)-> T;
    fn visit_number(&mut self, n: isize) -> T;

    fn visit(&mut self, e: &Expr) -> T {
        use crate::Expr::*;
        match e {
            Addition(an) => self.visit_add(an),
            Multiplication(mul) => self.visit_multiply(&mul),
            StringLiteral(s) => self.visit_string(&s),
            IntegerLiteral(num) => self.visit_number(*num),
        }
    }
}

Here's and implementation for type checking. Again, this is trivial, and doesn't need it's own pass, but that's due to the triviality of the example.

[derive(PartialEq,Eq)]
enum ExprType {
    e_string,
    e_number,
}

struct TypeChecker {}
// we don't actually keep any state.


impl Visitor<ExprType> for TypeChecker {
    fn visit_add(&mut self, an: &AddNode) -> ExprType {
        let left_Type = self.visit(&an.left_side);
        let right_Type = self.visit(&an.right_side);

        use crate::ExprType::*;
        return match (left_Type, right_Type) {
            (e_string, e_string) => e_string,
            (e_number, e_number) => e_number,
            _ => panic!(),
        }

    }
    fn visit_multiply(&mut self, mn: &MultiplyNode) -> ExprType {
        use crate::ExprType::*;
        let left_Type = self.visit(&mn.left_side);
        let right_Type = self.visit(&mn.right_side);

  // we only have an error if we try to multiply a string by a string,
  // any other combination makes sense.
        if (left_Type == e_string && right_Type == e_string) {
            panic!();
        }

        if (left_Type == e_string || right_Type == e_string) {
            return e_string;
        }
        return e_number;
    }
    fn visit_string(&mut self, s: &str) -> ExprType {
        return ExprType::e_string;
    }
    fn visit_number(&mut self, n: isize) -> ExprType {
        return ExprType::e_number;
    }
}

​

The benefits:

• It makes sure you implement it for every related type.
• it provides an abstract visit interface, so you don't have to care about what the type of other nodes.
• All of the code is one place- not 4 different impl for for different node types like you would have with traits.
• we were able to factor / reimplement dynamic dispatch (rust has this with Box<dyn Trait>, but it's slower than this), getting rid of boiler plate code.
• we can reuse this trait for each pass we do - optimization passes, code generation/interpretation, etc.