gistfile1.rs

pub enum Expression {
    Identifier(String),
    Function(String, Box<Expression>),
    Application(Box<Expression>, Box<Expression>),
}

impl Expression {
    fn is_variable_free(&self, var: &str) -> bool {
        match *self {
            Expression::Identifier(ref id) => var != *id,
            Expression::Application(ref lhs, ref rhs) => {
                lhs.is_variable_free(var) || rhs.is_variable_free(var)
            },
            Expression::Function(ref param, ref body) => {
                var == *param && body.is_variable_free(var)
            },
        }
    }

    pub fn eta_reduce(self) -> Expression {
        match self {
            Expression::Identifier(id) => Expression::Identifier(id),
            Expression::Application(lhs, rhs) => {
                Expression::Application(Box::new(lhs.eta_reduce()), Box::new(rhs.eta_reduce()))
            },
            Expression::Function(param, body) => {
                let body_reduced = body.eta_reduce();

                if let Expression::Application(lhs, rhs) = body_reduced {
                    if let Expression::Identifier(id) = *rhs {
                        if param == id && !lhs.is_variable_free(&id) {
                            *lhs
                        } else {
                            let ident = Expression::Identifier(id);
                            let application = Expression::Application(lhs, Box::new(ident));

                            Expression::Function(param, Box::new(application))
                        }
                    } else {
                        let application = Expression::Application(lhs, rhs);

                        Expression::Function(param, Box::new(application))
                    }
                } else {
                    Expression::Function(param, Box::new(body_reduced))
                }
            },
        }
    }
}