Skip to content

Instantly share code, notes, and snippets.

Created March 3, 2015 18:03
Show Gist options
  • Save anonymous/a9c9c1c028d69e3b7219 to your computer and use it in GitHub Desktop.
Save anonymous/a9c9c1c028d69e3b7219 to your computer and use it in GitHub Desktop.
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))
}
},
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment