Recursive enums with changing types in Rust

[Genarito]

I'm trying to implement a simple recursive structure in Rust where the type of data stored can change with each recursion. The change occurs from any function that is also part of the structure:

// Type of function can receive Operation::Change
type ChangeFunction<T, U> = fn(T) -> U;

// Recursive structure
enum Operation<T, U, F = ChangeFunction<T, U>>
where
    F: Fn(T) -> U,
{
    Cons(Vec<T>),
    Change(F, Box<Operation<T, U>>),
}

// In each recursion if there are operations "Operation::Change", the return type change!
fn eval<T, U>(operation: &Operation<T, U, ChangeFunction<T, U>>) -> Vec<T>
where
    std::vec::Vec<T>: std::iter::FromIterator<U>,
{
    match operation {
        Operation::Cons(vector) => *vector,
        Operation::Change(a_function, recursion) => eval(&recursion)
            .into_iter()
            .map(a_function)
            .collect::<Vec<T>>(),
    }
}

fn main() {
    // I define a function that will change my data
    let a_map_funcion = |x| (1, x + 2);

    // I define recursive enum with the function
    let operation = Operation::Change(
        a_map_funcion,
        Box::new(Operation::Cons(vec![1, 2, 3])),
    );

    let result = eval(&operation);
    println!("Result -> {:?}", result); // Expected [(1,3),(1,4),(1,5)]
}

I've finished Rust's book and I still can't come up with a solution to this kind of problem. In Haskell I solved it in an extremely simple way and without any drama using GADTs:

data Operation a where
    Cons :: [a] -> (Operation a)
    Change :: (a -> b) -> (Operation a) -> (Operation b)

eval :: Operation a -> [a]
eval (Cons vector) = vector
eval (Change f recursion) = map f (eval recursion)

With that program I can do eval (Change (\x -> (1, x + 2)) (Cons [1, 2, 3])) and effectively throw [(1,3),(1,4),(1,5)] which is what I expected.

But I don't know if there will be an equivalent in Rust or I will have to face the problem with another approach.

Any light on the subject is going to be very grateful

[cbiffle]

Your Haskell code is using GADTs, which don't have a direct analog in Rust (or in older Haskell, for that matter). The Change constructor introduces an extra type parameter (b) that isn't part of the type Operation a. Your Rust code incorporates b into the type, which means something different, and winds up painting you into a corner.

In Haskell, you could avoid the GADT by expressing Operation a as a class instead of an ADT, because class instances can introduce new type parameters — and the same approach works in Rust (playground link):

trait Operation<T> {
    fn eval(&self) -> Vec<T>;
}

impl<T: Clone> Operation<T> for Vec<T> {
    fn eval(&self) -> Vec<T> {
        self.clone()
    }
}

impl<O, T, U> Operation<T> for (O, fn(U) -> T)
    where O: Operation<U>,
{
    fn eval(&self) -> Vec<T> {
        self.0.eval().into_iter().map(self.1).collect()
    }
}

fn main() {
    // I define a function that will change my data
    let a_map_funcion: fn(usize) -> (usize, usize) = |x| (1, x + 2);

    // I define recursive enum with the function
    let operation = (vec![1, 2, 3], a_map_funcion);

    let result = operation.eval();
    println!("Result -> {:?}", result); // Expected [(1,3),(1,4),(1,5)]
}

(Probably the most direct analog to the Haskell code would be to pass around iterators instead of Vecs, since Haskell lists are lazy like Rust iterators, while Vec will allocate and reallocate its contents each time you map it. This is significantly more involved, however.)

[Genarito]

Thank you so much for the answer! I'll try to adapt your code for a more complex example where I could have a lot of Operation::Change or other Operations like Filter, Fold, etc.

I was looking for GADTs as you said, I didn't realize that I hadn't mentioned in the question.

Thank you again!