#![deny(missing_docs)]
use Expr::*;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Expr {
J,
R(Box<Expr>),
F(Box<Expr>, Box<Expr>),
L(Box<Expr>, Box<Expr>),
I,
P(Box<Expr>, Box<Expr>),
A(Box<Expr>, Box<Expr>),
}
impl Expr {
pub fn reduce(self) -> Result<Expr, Expr> {
use Expr::*;
match &self {
A(a, b) => {
match **a {
J | R(_) | F(_, _) => Ok(F(a.clone(), b.clone())),
L(ref s, ref t) => Ok(A(P(b.clone(), s.clone()).into(), t.clone())),
I => Ok((**b).clone()),
P(ref u, ref s) => {
match **b {
J => Ok((**u).clone()),
R(ref t) => Ok(A(s.clone(), t.clone())),
F(ref r, ref t) =>
Ok(A(A(a.clone(), r.clone()).into(),
A(a.clone(), t.clone()).into())),
L(ref r, ref t) => Ok(L(A(a.clone(), r.clone()).into(), t.clone())),
I => Ok(I),
P(ref r, ref t) =>
Ok(P(A(a.clone(), r.clone()).into(),
A(a.clone(), t.clone()).into())),
A(_, _) => {
match (**b).clone().reduce() {
Ok(x) => Ok(A(a.clone(), x.into())),
Err(_) => Err(self),
}
}
}
}
A(_, _) => {
match (**a).clone().reduce() {
Ok(x) => Ok(A(x.into(), b.clone())),
Err(_) => Err(self),
}
}
}
}
R(a) => {
match (**a).clone().reduce() {
Ok(x) => Ok(R(x.into())),
Err(_) => Err(self),
}
}
J | I => Err(self),
F(a, b) => {
let a = a.clone().reduce();
let b = b.clone().reduce();
match (a, b) {
(Err(_), Err(_)) => Err(self),
(Ok(a), Ok(b)) |
(Ok(a), Err(b)) |
(Err(a), Ok(b)) => Ok(F(a.into(), b.into())),
}
}
L(a, b) => {
let a = a.clone().reduce();
let b = b.clone().reduce();
match (a, b) {
(Err(_), Err(_)) => Err(self),
(Ok(a), Ok(b)) |
(Ok(a), Err(b)) |
(Err(a), Ok(b)) => Ok(L(a.into(), b.into())),
}
}
P(a, b) => {
let a = a.clone().reduce();
let b = b.clone().reduce();
match (a, b) {
(Err(_), Err(_)) => Err(self),
(Ok(a), Ok(b)) |
(Ok(a), Err(b)) |
(Err(a), Ok(b)) => Ok(P(a.into(), b.into())),
}
}
}
}
pub fn reduce_all(self) -> Expr {
let mut x = self;
loop {
match x.reduce() {
Ok(y) => x = y,
Err(x) => return x,
}
}
}
}
impl Into<Expr> for usize {
fn into(self) -> Expr {
match self {
0 => J,
x => R(Box::new((x-1).into())),
}
}
}
pub fn id() -> Expr {L(I.into(), J.into())}
pub fn snd() -> Expr {L(I.into(), id().into())}
pub fn fst() -> Expr {
L(
I.into(),
L(
P(J.into(), I.into()).into(),
R(J.into()).into(),
).into()
)
}
pub fn app2(a: Expr, b: Expr, c: Expr) -> Expr {A(A(a.into(), b.into()).into(), c.into())}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
let a = A(J.into(), I.into());
assert_eq!(a.reduce().unwrap(), F(J.into(), I.into()));
}
#[test]
fn test_id() {
let x = J;
let a = A(id().into(), x.clone().into());
let a = a.reduce().unwrap();
assert_eq!(a, A(P(x.clone().into(), I.into()).into(), J.into()));
let a = a.reduce().unwrap();
assert_eq!(a, x);
}
#[test]
fn test_snd() {
let x: Expr = 2.into();
let y: Expr = 3.into();
let a = app2(snd(), x.clone(), y.clone());
let a = a.reduce().unwrap();
assert_eq!(a, app2(P(x.clone().into(), I.into()), id(), y.clone()));
let a = a.reduce().unwrap();
assert_eq!(a, A(
L(A(P(x.clone().into(), I.into()).into(), I.into()).into(), J.into()).into(),
y.clone().into()
));
let a = a.reduce().unwrap();
assert_eq!(a, A(P(y.clone().into(), A(P(x.clone().into(), I.into()).into(), I.into()).into()).into(), J.into()));
let a = a.reduce().unwrap();
assert_eq!(a, y);
}
#[test]
fn test_fst() {
let x: Expr = 2.into();
let y: Expr = 3.into();
let a = app2(fst(), x.clone(), y.clone());
assert_eq!(a.reduce_all(), x);
}
}