in haskell idioms, fused ana and cata - based on https://gist.github.com/Gankra/db892282bc7d579a0afe83c965f2320b

eval.rs

pub fn generate_layer(x: Box<ExprAST>) -> Expr<Box<ExprAST>> {
    match *x {
        ExprAST::Add(a, b) => Expr::Add(a, b),
        ExprAST::Sub(a, b) => Expr::Sub(a, b),
        ExprAST::Mul(a, b) => Expr::Mul(a, b),
        ExprAST::LiteralInt(x) => Expr::LiteralInt(x),
    }
}

pub fn eval_layer(node: Expr<i64>) -> i64 {
    match node {
        Expr::Add(a, b) => a + b,
        Expr::Sub(a, b) => a - b,
        Expr::Mul(a, b) => a * b,
        Expr::LiteralInt(x) => x,
    }
}

pub fn eval_lazy(expr: Box<ExprAST>) -> i64 {
    unfold_and_fold(expr, generate_layer, eval_layer)
}

fused_generate_and_fold.rs

pub fn unfold_and_fold<
    Seed,
    Out,
    GenerateExpr: Functor<(), Unwrapped = Seed, To = U>,
    ConsumeExpr,
    U: Functor<Out, To = ConsumeExpr, Unwrapped = ()>,
    Alg: FnMut(ConsumeExpr) -> Out,
    CoAlg: Fn(Seed) -> GenerateExpr,
>(
    seed: Seed,
    coalg: CoAlg,
    mut alg: Alg,
) -> Out {
    enum State<Pre, Post> {
        PreVisit(Pre),
        PostVisit(Post),
    }

    let mut vals: Vec<Out> = vec![];
    let mut todo: Vec<State<_, _>> = vec![State::PreVisit(seed)];

    while let Some(item) = todo.pop() {
        match item {
            State::PreVisit(seed) => {
                let node = coalg(seed);

                let mut topush = Vec::new();

                let node = node.fmap(|seed| {
                    topush.push(State::PreVisit(seed));
                    ()
                });

                todo.push(State::PostVisit(node));

                todo.extend(topush.into_iter());
            },
            State::PostVisit(node) => {
                let node = node.fmap(|_: ()| {
                    vals.pop().unwrap()
                });
                vals.push(alg(node))
            },
        };
    }
    vals.pop().unwrap()
}

pub trait Functor<B> {
    type Unwrapped;
    type To;
    /// fmap over an owned value
    fn fmap<F: FnMut(Self::Unwrapped) -> B>(self, f: F) -> Self::To;
}

types.rs

pub enum ExprAST {
    Add(Box<ExprAST>, Box<ExprAST>),
    Sub(Box<ExprAST>, Box<ExprAST>),
    Mul(Box<ExprAST>, Box<ExprAST>),
    LiteralInt(i64),
}

pub enum Expr<A> {
    Add(A, A),
    Sub(A, A),
    Mul(A, A),
    LiteralInt(i64),
}


impl<A, B> Functor<B> for Expr<A> {
    type To = Expr<B>;
    type Unwrapped = A;

    #[inline(always)]
    fn fmap<F: FnMut(Self::Unwrapped) -> B>(self, mut f: F) -> Self::To {
        match self {
            Expr::Add(a, b) => Expr::Add(f(a), f(b)),
            Expr::Sub(a, b) => Expr::Sub(f(a), f(b)),
            Expr::Mul(a, b) => Expr::Mul(f(a), f(b)),
            Expr::LiteralInt(x) => Expr::LiteralInt(x),
        }
    }
}