GADTs for multiple generics transformations in Rust

Question

I'm trying to design an execution graph with Recursive Generics Enums in Rust. I want to make an eval function which computes a predefined map closure recursively, but each map function could change the enum type so I get a compilation error due the different types. Here is my code:

use std::rc::Rc;

enum ExecutionGraph<T, H, F = fn(T) -> H> {
    Cons(Vec<T>),
    Map(F, Rc<ExecutionGraph<T, H>>),
}

// Impl for add a Cons "node" or a Map "node"
impl<T, H> ExecutionGraph<T, H, fn(T) -> H> {
    fn new_data(data: Vec<T>) -> Self {
        ExecutionGraph::Cons(data)
    }

    fn add_map(a_function: fn(T) -> H, execution_graph: ExecutionGraph<T, H, fn(T) -> H>) -> Self {
        ExecutionGraph::Map(a_function, Rc::new(execution_graph))
    }
}

// Complete evaluation of the execution graph
fn eval<T, H>(execution_graph: &ExecutionGraph<T, H, fn(T) -> H>) -> Vec<T>
where
    T: std::clone::Clone,
    std::vec::Vec<T>: std::iter::FromIterator<H>,
{
    match execution_graph {
        ExecutionGraph::Cons(data) => data.to_vec(),
        ExecutionGraph::Map(closure, e1) => eval(&(*e1)).into_iter().map(closure).collect(),
    }
}

fn main() {
    let execution_graph = ExecutionGraph::new_data(vec![1, 2, 3]);

    // let map_function: fn(u32) -> u32 = |x: u32| x * 8; // This work!
    let map_function: fn(u32) -> bool = |x: u32| x % 2 == 0; // This doesn't
    let execution_graph_2 = ExecutionGraph::add_map(map_function, execution_graph);
    let execution_result = eval(&execution_graph_2);

    println!("Result of execution = {:#?}", execution_result);
}

The add_data and add_map functions work as expected. But then when I call the eval function I'm getting the following error:

   |     let execution_result = eval(&execution_graph_2);
   |                                 ^^^^^^^^^^^^^^^^^^ expected u32, found bool
   |
   = note: expected type `&ExecutionGraph<_, _>`
              found type `&ExecutionGraph<u32, bool>`>`

Why am I getting this error? I defined to get a generic argument and a generic function which could change the result type. How could allow all posible transformations in the data? In the future, there will be a lot of more functions with the same proble, such as a cartesian product wich returns a tuple. Note that if the closure has the same return type as the input there is no problem. If someone could give me a hand with this problem I would appreciate it.

Thanks in advance and sorry about my English.

You wrote Vec<T>: std::iter::FromIterator<H>, but Vec<u32> does not implement FromIterator<bool>. — trentcl
How could solve the problem? If I remove that It throws a collection of type 'std::vec::Vec<T> cannot be built from std::iter::Iterator<Item=H>' in the collect() part. I need to return a generic type as the map function comes from the user and It could change the Vec type — Genarito
Sorry, I don't really understand what you're trying to do. If you want to turn an H into a T, you need fn(H) -> T, not fn(T) -> H -- is that the problem? — trentcl
Nono, I receive a fn(T) -> H. Because the Map enum could have a function which changes the type of the recursive Cons. The problem is that eval expects to return a T and not and H. That's why it throws that I can't have a fn(32) -> bool function. I would like to know if is possible to have generics Map functions like the one in the question, which transforms u32 to bool elements. — Genarito
Sorry, I just don't understand. A function can't change the type of a value; that's not how types work. I could guess you want some kind of wrapper that encapsulates the function and an inner type, but then first you'd need the wrapper to convert both ways -- not just T to H but H to T depending on how it's being used -- and secondly you'd need the "inner" ExecutionGraph to be a different type, not just the same as the "outer" type. Also, it kind of seems like you're trying to do things both at compile time and at run time in a way that doesn't jive, but that's a guess. — trentcl

Genarito Genarito · Accepted Answer · 2019-12-19T15:08:27

As mentioned by a user in my question in the official forum of Rust. This language has no support for Generalized Algebraic Data Types (GADTs) which would be the right tool to solve this kind of problems.

As an alternative, instead of proposing a scheme where the types belong to the ENUM making it not very flexible, a class approach is proposed, which is allowed to introduce new types.

I do not put the code here so that it can be consulted directly in the question with the edits or new answers that may arise.

GADTs for multiple generics transformations in Rust

1 Answers