/// models(UnaryOperation) fn abs(x : i64) -> i64 { return x.abs(); } /// models(BinaryOperation) fn euclidean_norm2(x : f64, y : f64) -> f64 { let n = x * x + y * y; return n.sqrt(); } /// models(TernaryOperation) fn euclidean_norm3(x : f64, y : f64, z : f64) -> f64 { let n = x * x + y * y + z * z; return n.sqrt(); } trait SemiRegular : PartialEq + Copy {} impl SemiRegular for i64 {} impl SemiRegular for u64 {} /// zero : additive unit /// one : multiplicative unit trait Integer : SemiRegular { // doesn't work: const zero : Self; // doesn't work: const one : Self; fn zero() -> Self; fn one() -> Self; fn add(Self, Self) -> Self; fn sub(Self, Self) -> Self; } impl Integer for i64 { fn zero() -> Self { return 0; } fn one() -> Self { return 1; } fn add(a : Self, b : Self) -> Self { return a + b; } fn sub(a : Self, b : Self) -> Self { return a - b; } } impl Integer for u64 { fn zero() -> Self { return 0; } fn one() -> Self { return 1; } fn add(a : Self, b : Self) -> Self { return a + b; } fn sub(a : Self, b : Self) -> Self { return a - b; } } trait Transformation { type Distance : Integer; } impl Transformation for fn(i64) -> i64 { type Distance = u64; } impl Transformation for Fn(i64) -> i64 { type Distance = u64; } /// requires(Transformation(F) && Integer(N)) fn power_unary T, T, N : Integer>(mut x : F::Output, mut n : N, f : F) -> F::Output { // Precondition n>=0 && (\forall i \in N) 0 < i <= n \implies f^i(x) is defined while n != N::zero() { n = ::sub(n, N::one()); x = f(x); } return x; } // requires(Transformation(F)) fn distance T, T : PartialEq>(mut x : F::Output, y : F::Output, f : F) -> ::Distance { // doesn't compile: type N = F::Distance; let mut n = F::Distance::zero(); while x != y { x = f(x); n = ::add(n, F::Distance::one()); } return n; } fn collision_point T, T : SemiRegular, P : Fn(T) -> bool>(x : F::Output, f : F, p : P) -> T { // Precondition: p(x) \equiv f(x) is defined if !p(x) { return x; } let mut slow = x; let mut fast = f(x); while fast != slow { slow = f(slow); if !p(fast) { return fast; } fast = f(fast); if !p(fast) { return fast; } fast = f(fast); } return fast; } // we need to cast a function (fn(i64)->i64 {function_name}) to its more general type (fn(i64)->i64) in order to let the compiler find our Transformation trait's implementation macro_rules! unary_transformation { ($f : ident,$T : ident) => ($f as fn($T) -> \$T); } fn main() { let x = 1.0; let y = 2.0; let z = 3.0; println!("{} == {}", euclidean_norm3(x, y, z), euclidean_norm2(euclidean_norm2(x, y), z)); { let x : i64 = -5; let n : i64 = 8; let y = power_unary(x, n, abs); println!("power_unary(abs, {}, {}) = {}", n, x, y); println!("distance({}, {}, abs) = {}", x, y, distance(x, y, unary_transformation!(abs,i64))); let always_defined = |_| true; println!("collision_point({}, abs) = {}", x, collision_point(x, unary_transformation!(abs,i64), always_defined)); } }