Trait xpr::Fold [−][src]
Expand description
A trait for expression manipulation. Fold together with crate::Xpr are at the heart of this crate.
Fold<T>::fold will replace any instance of type T in an expression tree crate::Xpr<U> with
a value of type Fold::Output.
The usage of this trait is best explained with examples.
Examples
The following examples can also be found in the examples directory.
Evaluating expressions
We can replace all Term<i32> instances in an expression by their wrapped type.
This will effectively evaluate the expression.
use xpr::{ops::Term, Fold, Xpr};
struct Evaluator;
/// evaluates an expression of i32 terminals
impl Fold<Term<i32>> for Evaluator {
type Output = i32;
/// replaces Terminal values with their wrapped type
fn fold(&mut self, Term(x): &Term<i32>) -> i32 {
*x
}
}
// create a new expression representing a chained addition
let x = Xpr::new(20) / Xpr::new(2) + Xpr::new(3) * Xpr::new(5) + Xpr::new(23) - Xpr::new(6);
// use the Evaluator to evaluate the expression
let res = Evaluator.fold(&x);
assert_eq!(res, 42);
// note that `Xpr::eval` is syntactic sugar around a similar generic
// Evaluator struct
assert_eq!(res, x.eval());Substituting expressions
We can replace terminals by other expressions
use xpr::{
ops::{OutputOfSub, Term},
Fold, Xpr,
};
struct Substitution;
impl Fold<Term<i32>> for Substitution {
type Output = OutputOfSub<Term<i32>, Term<i32>>;
// replaces i32 terminals with a Sub expression
// that returns the same value
fn fold(&mut self, &Term(x): &Term<i32>) -> Self::Output {
Xpr::new(x + 42) - Xpr::new(42)
}
}
let x = Xpr::new(10) + Xpr::new(15) + Xpr::new(17);
assert_eq!(x.eval(), 42);
// let's use the Substitution folder
let x = Substitution.fold(&x);
assert_eq!(x.eval(), 42);
Improving performance: Avoiding temporaries
This is the test-piece for expression templates and the classical use case scenario. Image we are using
a linear algebra library that supplies a Vec type and implements std::ops::Add for it. Then, we could
write a chained addition of potentially large vectors x1, x2 and x3.
let x = x1 + x2 + x3;
Internally, the additon of x2 and x3 would yield a temporary vector containing the result of the addition.
This temporary vector is than added to x1 yielding yet another temporary vector, which is moved into x. The
allocation of these two temporary vectors can be avoided using expression templates.
Let’s pretend we want to write our own linear algebra library.
use xpr::{ops::Term, Expression, Fold, Xpr};
// This is our statically sized vector type
#[derive(Debug)]
struct Vec<const N: usize>(Box<[f64; N]>);
impl<const N: usize> Vec<{ N }> {
#[inline]
fn new(array: [f64; N]) -> Self {
Self(Box::new(array))
}
}
// a convenience trait for cnverting Vec instances to xpr terminals.
// this lets us call as_xpr and into_xpr on Vec instances.
impl<const N: usize> Expression for Vec<N> {}
struct IthElement<const N: usize>(usize);
// IthElement will match all Terminals wrapping a Vec and return it's i-th element.
impl<const N: usize> Fold<Term<Vec<{ N }>>> for IthElement<{ N }> {
type Output = f64;
// extracts the i-th element of a vector terminal
#[inline]
fn fold(&mut self, Term(v): &Term<Vec<{ N }>>) -> f64 {
v.0[self.0]
}
}
// convert any Xpr<T> to Vec
impl<T, const N: usize> From<Xpr<T>> for Vec<{ N }>
where
IthElement<N>: Fold<Xpr<T>, Output = f64>,
{
// conversion from a vector expression to a Vec instance
#[inline]
fn from(expr: Xpr<T>) -> Self {
// scary unsafe uninitialized array
let mut ret = Vec::new(unsafe { std::mem::MaybeUninit::uninit().assume_init() });
// apply the operations in the vector expression element-wise
for (i, e) in ret.0.iter_mut().enumerate() {
*e = IthElement(i).fold(&expr);
}
ret
}
}
// Now let's take it for a spin!
// Create a couple of vector expressions
let x1 = Vec::new([0.6; 5000]).into_xpr();
let x2 = Vec::new([1.0; 5000]).into_xpr();
let x3 = Vec::new([40.0; 5000]).into_xpr();
let x4 = Vec::new([100.0; 5000]).into_xpr();
let x5 = Vec::new([3000.0; 5000]).into_xpr();
// A chained addition without any Vec temporaries!
let v = Vec::from(x1 + x2 + x3 + x4 + x5);
assert_eq!(v.0[0], 3141.6);Granted, the example is a bit of an oversimplification because the addition consumes its summands and it would have been possible to write a fairly performant vector addition with the same functionality based on move semantics. But a sum that consumes its summands is something you usually don’t want. It takes only a little bit of tweaking to get the example to work on terminals that wrap references to vectors that will not be consumed. The tweaked example can be found in the examples subdirectory of the repository.
Associated Types
The output of Fold::fold, Self will replace all instances of T in an expression by values of this type.