Skip to content

Instantly share code, notes, and snippets.

@uucidl uucidl/000-eop
Last active Apr 16, 2016

Embed
What would you like to do?
Elements Of Programming (Stepanov, Mc Jones) In Rust
Elements Of Programming (A.Stepanov, P.McJones) implemented in Rust
Generic programming Rust using traits and generic functions
/// requires(BinaryOperation(Op))
fn square<T : Copy, Op : Fn(T, T) -> T>(x : Op::Output, op : Op) -> Op::Output {
return op(x, x);
}
fn square_i64(x: i64) -> i64 {
return x * x;
}
fn multiply_i64(a : i64, b : i64) -> i64 {
return a * b;
}
fn xor(a : bool, b : bool) -> bool {
return a ^ b;
}
#[derive(PartialEq,Copy,Clone)]
struct vec2 {
x : f64,
y : f64
}
fn vec2_add(a : vec2, b : vec2) -> vec2 {
return vec2 { x: a.x + b.x, y: a.y + b.y }
}
impl std::fmt::Display for vec2 {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "({}, {})", self.x, self.y)
}
}
fn main() {
let x = 3;
println!("square: {} = {}", x, square_i64(x));
println!("generic square (mul): {} = {}", x, square(x, multiply_i64));
let y = true;
println!("generic square (xor): {} = {}", y, square(y, xor));
let p = vec2 { x: 0.0, y : 1.0 };
println!("generic square (vec2_add): {} = {}", p, square(p, vec2_add));
}
/// 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<F : Fn(T) -> 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 = <N as Integer>::sub(n, N::one());
x = f(x);
}
return x;
}
// requires(Transformation(F))
fn distance<F : Transformation + Fn(T) -> T, T : PartialEq>(mut x : F::Output, y : F::Output, f : F) -> <F as Transformation>::Distance {
// doesn't compile: type N = F::Distance;
let mut n = F::Distance::zero();
while x != y {
x = f(x);
n = <F::Distance as Integer>::add(n, F::Distance::one());
}
return n;
}
fn collision_point<F : Transformation + Fn(T) -> 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));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.