diff options
| -rw-r--r-- | src/cexpr.rs | 223 |
1 files changed, 169 insertions, 54 deletions
diff --git a/src/cexpr.rs b/src/cexpr.rs index 1971feb..b183c4a 100644 --- a/src/cexpr.rs +++ b/src/cexpr.rs @@ -1,8 +1,7 @@ /* - * Canonical Expressions + * "Canonical" Expressions * * AKA, simplified, normalized algebraic expressions. - * */ use crate::sexpr::SExpr; @@ -10,25 +9,30 @@ use std::fmt; #[derive(Debug, Clone, PartialEq, PartialOrd)] pub enum NumericConstant { - Pi, // 3.141592... - E, // 2.718281... + Pi, + E, + GoldenRatio, } impl NumericConstant { - pub fn as_number(&self) -> CNumber { - use CNumber::*; - use NumericConstant::*; - match self { - Pi => Float(3.141592f64), - E => Float(2.718281f64), + /* + pub fn as_number(&self) -> CNumber { + use CNumber::*; + use NumericConstant::*; + match self { + Pi => Float(3.14159265358979323846f64), + E => Float(2.71828182845904523536f64), + GoldenRatio => Float(1.61803398874989484820f64), + } } - } + */ pub fn as_string(&self) -> String { use NumericConstant::*; match self { Pi => "pi".to_string(), E => "e".to_string(), + GoldenRatio => "golden-ratio".to_string(), } } } @@ -53,6 +57,46 @@ impl CNumber { CNumber::Float(v) => Ok(SExpr::SFloat(*v)), } } + + pub fn sum(&self, other: &CNumber) -> CNumber { + use CNumber::*; + match (self, other) { + (Integer(a), Integer(b)) => Integer(a + b), + (Integer(i), Rational(n, d)) | (Rational(n, d), Integer(i)) => Rational(n + d * i, *d), + (Rational(a, b), Rational(c, d)) if b == d => Rational(a + c, *d), + (Rational(a, b), Rational(c, d)) => Rational(a * d + c * b, b * d), + (Float(a), Float(b)) => Float(a + b), + (Integer(i), Float(f)) | (Float(f), Integer(i)) => Float((*i as f64) + f), + (Rational(n, d), Float(f)) | (Float(f), Rational(n, d)) => { + Float(f + (*n as f64) / (*d as f64)) + } + } + } + + pub fn product(&self, other: &CNumber) -> CNumber { + use CNumber::*; + match (self, other) { + (Integer(0), _) | (_, Integer(0)) => Integer(0), + (Integer(a), Integer(b)) => Integer(a * b), + (Integer(i), Rational(n, d)) | (Rational(n, d), Integer(i)) => Rational(i * n, *d), + (Rational(a, b), Rational(c, d)) if a == d && b == c => Integer(1), + (Rational(a, b), Rational(c, d)) => Rational(a * c, b * d), + (Float(a), Float(b)) => Float(a * b), + (Integer(i), Float(f)) | (Float(f), Integer(i)) => Float((*i as f64) * f), + (Rational(n, d), Float(f)) | (Float(f), Rational(n, d)) => { + Float(f * (*n as f64) / (*d as f64)) + } + } + } + + pub fn is_negative(&self) -> bool { + use CNumber::*; + match self { + Integer(i) => *i < 0, + Rational(n, _) => *n < 0, + Float(f) => *f < 0.0f64, + } + } } #[derive(Clone, PartialEq, PartialOrd)] @@ -68,6 +112,16 @@ pub enum CExpr { UnaryFunction(String, Box<CExpr>), } +fn compute_factorial(n: i64) -> i64 { + if n < 0 { + panic!("tried to compute negative factorial"); + } else if n == 0 { + return 1; + } else { + return n * compute_factorial(n - 1); + } +} + impl CExpr { pub fn from_sexpr(sexpr: &SExpr) -> Result<CExpr, String> { // not all cases are handled; some atoms are covered trivialy @@ -76,10 +130,11 @@ impl CExpr { SExpr::SBoolean(_) => Err("booleans not handled".to_string()), SExpr::SInteger(v) => Ok(CExpr::Number(CNumber::Integer(*v))), SExpr::SFloat(v) => Ok(CExpr::Number(CNumber::Float(*v))), - SExpr::SString(_) => Err("null not handled".to_string()), + SExpr::SString(_) => Err("strings not handled".to_string()), SExpr::SIdentifier(v) => match v.as_str() { "pi" => Ok(CExpr::Constant(NumericConstant::Pi)), "e" => Ok(CExpr::Constant(NumericConstant::E)), + "golden-ratio" => Ok(CExpr::Constant(NumericConstant::GoldenRatio)), _ => Ok(CExpr::Symbol(v.to_string())), }, SExpr::SList(l) => CExpr::from_sexpr_list(l), @@ -87,10 +142,19 @@ impl CExpr { } pub fn from_sexpr_list(list: &Vec<SExpr>) -> Result<CExpr, String> { + use CExpr::*; + use CNumber::*; + use SExpr::*; // https://adventures.michaelfbryan.com/posts/daily/slice-patterns/ if let [SExpr::SIdentifier(ident), rest @ ..] = list.as_slice() { match (ident.as_str(), rest.len()) { - ("factorial", 1) => Ok(CExpr::Factorial(Box::new(CExpr::from_sexpr(&rest[0])?))), + ("factorial", 1) => match CExpr::from_sexpr(&rest[0])? { + Number(n) if n.is_negative() => { + Err("negative factorial is not defined".to_string()) + } + Number(Integer(i)) if i <= 18 => Ok(Number(Integer(compute_factorial(i)))), + other => Ok(Factorial(Box::new(other))), + }, ("cos" | "sin" | "tan", 1) => Ok(CExpr::UnaryFunction( ident.to_string(), Box::new(CExpr::from_sexpr(&rest[0])?), @@ -98,40 +162,43 @@ impl CExpr { ("^", 2) => { let base = CExpr::from_sexpr(&rest[0])?; let power = CExpr::from_sexpr(&rest[1])?; - use CExpr::*; - use CNumber::*; match (base, power) { (Number(Integer(0)), _) => Ok(Number(Integer(0))), (Number(Integer(1)), _) => Ok(Number(Integer(1))), (_, Number(Integer(0))) => Ok(Number(Integer(1))), (base, Number(Integer(1))) => Ok(base), + (Number(Rational(1, d)), Number(Integer(-1))) => Ok(Number(Integer(d))), + (Number(Rational(n, d)), Number(Integer(-1))) => Ok(Number(Rational(d, n))), + (Exponent(base, p1), p2) => match (*p1, p2) { + (Number(n1), Number(n2)) => { + Ok(Exponent(base, Box::new(Number(n1.product(&n2))))) + } + (p1, p2) => { + Ok(Exponent(base, Box::new(CExpr::new_product(vec![p1, p2])?))) + } + }, (base, power) => Ok(Exponent(Box::new(base), Box::new(power))), } } - ("/", 2) => { - use CExpr::*; - use CNumber::*; - use SExpr::*; - match (&rest[0], &rest[1]) { - (_, SInteger(0)) => Err("division by zero".to_string()), - (SInteger(0), _) => Ok(Number(Integer(0))), - (se, SInteger(1)) => CExpr::from_sexpr(se), - (SInteger(a), SInteger(b)) if a == b => Ok(Number(Integer(1))), - (SInteger(a), SInteger(b)) if a % b == 0 => Ok(Number(Integer(a / b))), - (SInteger(a), SInteger(b)) => Ok(Number(Rational(*a, *b))), - (SInteger(1), b) => { - let denom = CExpr::from_sexpr(b)?; - Ok(Exponent(Box::new(denom), Box::new(Number(Integer(-1))))) - } - (a, b) => { - let (numer, denom) = (CExpr::from_sexpr(a)?, CExpr::from_sexpr(b)?); - CExpr::new_product(vec![ - numer, - Exponent(Box::new(denom), Box::new(Number(Integer(-1)))), - ]) - } + ("/", 2) => match (&rest[0], &rest[1]) { + (_, SInteger(0)) => Err("division by zero".to_string()), + (SInteger(0), _) => Ok(Number(Integer(0))), + (se, SInteger(1)) => CExpr::from_sexpr(se), + (SInteger(a), SInteger(b)) if a == b => Ok(Number(Integer(1))), + (SInteger(a), SInteger(b)) if a % b == 0 => Ok(Number(Integer(a / b))), + (SInteger(a), SInteger(b)) => Ok(Number(Rational(*a, *b))), + (SInteger(1), b) => { + let denom = CExpr::from_sexpr(b)?; + Ok(Exponent(Box::new(denom), Box::new(Number(Integer(-1))))) } - } + (a, b) => { + let (numer, denom) = (CExpr::from_sexpr(a)?, CExpr::from_sexpr(b)?); + CExpr::new_product(vec![ + numer, + Exponent(Box::new(denom), Box::new(Number(Integer(-1)))), + ]) + } + }, // TODO: how to make range unbounded? or less bounded? ("+", 2..=5000) => { CExpr::new_sum(rest.iter().map(|v| CExpr::from_sexpr(v)).collect::<Result< @@ -150,8 +217,6 @@ impl CExpr { ("-", 2) => { let a = CExpr::from_sexpr(&rest[0])?; let b = CExpr::from_sexpr(&rest[1])?; - use CExpr::*; - use CNumber::*; match (a, b) { (expr, Number(Integer(0))) => Ok(expr), (Number(Integer(a)), Number(Integer(b))) => Ok(Number(Integer(a - b))), @@ -171,27 +236,77 @@ impl CExpr { } } - pub fn new_sum(mut list: Vec<CExpr>) -> Result<CExpr, String> { + pub fn new_sum(list: Vec<CExpr>) -> Result<CExpr, String> { use CExpr::*; use CNumber::*; - list.sort_by(|a, b| a.partial_cmp(b).unwrap()); - match list.as_slice() { - [Number(Integer(0)), e] => Ok(e.clone()), // XXX: remove clone() - [Number(Integer(a)), Number(Integer(b))] => Ok(Number(Integer(a + b))), - [Number(Integer(a)), Number(Rational(n, d))] => Ok(Number(Rational(n + a * d, *d))), - _ => Ok(Sum(None, list)), + let (numeric, mut rest): (Vec<CExpr>, Vec<CExpr>) = list + .into_iter() + .flat_map(|e| match e { + Sum(None, l) => l, + Sum(Some(num), mut l) => { + l.push(Number(num)); + l + } + e => vec![e], + }) + .partition(|v| { + if let Number(Integer(_) | Rational(_, _)) = v { + true + } else { + false + } + }); + + let num: Option<CNumber> = numeric + .into_iter() + .map(|v| if let Number(n) = v { n } else { unreachable!() }) + .reduce(|a, b| a.sum(&b)); + + rest.sort_by(|a, b| a.partial_cmp(b).unwrap()); + + match (num, rest) { + (None, mut rest) if rest.len() == 1 => Ok(rest.remove(0)), + (None, rest) if rest.is_empty() => unreachable!("empty list passed to new_product()"), + (Some(n), rest) if rest.is_empty() => Ok(Number(n)), + (Some(Integer(0)), rest) => Ok(Sum(None, rest)), + (n, r) => Ok(Sum(n, r)), } } - pub fn new_product(mut list: Vec<CExpr>) -> Result<CExpr, String> { + pub fn new_product(list: Vec<CExpr>) -> Result<CExpr, String> { use CExpr::*; use CNumber::*; - list.sort_by(|a, b| a.partial_cmp(b).unwrap()); - match list.as_slice() { - [Number(Integer(1)), e] => Ok(e.clone()), // XXX: remove clone() - [Number(Integer(a)), Number(Integer(b))] => Ok(Number(Integer(a * b))), - [Number(Integer(a)), Number(Rational(n, d))] => Ok(Number(Rational(a * n, *d))), - _ => Ok(Product(None, list)), + let (numeric, mut rest): (Vec<CExpr>, Vec<CExpr>) = list + .into_iter() + .flat_map(|e| match e { + Product(None, l) => l, + Product(Some(num), mut l) => { + l.push(Number(num)); + l + } + e => vec![e], + }) + .partition(|v| { + if let Number(Integer(_) | Rational(_, _)) = v { + true + } else { + false + } + }); + + let num: Option<CNumber> = numeric + .into_iter() + .map(|v| if let Number(n) = v { n } else { unreachable!() }) + .reduce(|a, b| a.product(&b)); + + rest.sort_by(|a, b| a.partial_cmp(b).unwrap()); + + match (num, rest) { + (None, mut rest) if rest.len() == 1 => Ok(rest.remove(0)), + (None, rest) if rest.is_empty() => unreachable!("empty list passed to new_product()"), + (Some(n), rest) if rest.is_empty() => Ok(Number(n)), + (Some(Integer(1)), rest) => Ok(Product(None, rest)), + (n, r) => Ok(Product(n, r)), } } |