Getting Started With Rust

You're going to need to get Rust code running. Download and install Rust tools: a command-line compiler, or IDE, or whatever you like. Start by getting a “hello world” running: doing cargo init will create a package with a hello world in main.rs.

Download and extract the code skeleton for this exercise. The code includes an outline of how to organize your work for this exercise, some tests that should pass when you're done (more below), and a place for a main function if you want to use it to test your code.

It's not a requirement, but maybe have a look at The Rust Book. It is a good intro to the language, and more complete than what is discussed in lectures.

Rust Hailstone

The hailstone sequence provided many useful examples in Haskell, so let's revisit it in Rust. In exer7.rs, write a function hailstone that calculates the next element of a hailstone sequence: for even n, it should return n/2 and for odd n, it should return 3*n+1.

hailstone(17) == 52
hailstone(18) == 9

The function should take and return a u64 type:

pub fn hailstone(n: u64) -> u64 { … }

Hailstone Sequence

In this question, we will build the hailstone sequence in a Rust vector.

Attempt 1: grow the vector

For this implementation, write a function hailstone_sequence_append that starts with an empty Vec<u64> (with Vec::new). Calculate the elements of the hailstone sequence and use the push method to add it to the end as you go.

It is probably easiest to do this iteratively (not recursively). You should take a u64 argument and return the Vec<u64>:

hailstone_sequence_append(5) == Vec::<u64>::from([5, 16, 8, 4, 2, 1])

Attempt 2: pre-allocate the space

Appending to an vector could be expensive since we have to re-allocate more memory as we go. Maybe we can do better? Write a function hailstone_sequence_prealloc that generates the same result in a different way…

It is easy enough to figure out how much space we need: we did it before. This time, start by calculating the length of the vector we need by iterating hailstone. (In the above example, you should realize you need an array of length 6.)

Then, use Vec::with_capacity to create an empty vector with enough space pre-allocated. Then fill it in and return it. Results should be the same as hailstone_sequence_append in all cases.

Test and Benchmark

Rust has built-in testing functionality. The provided tests.rs includes some tests that should pass by the end of the exercise. You can run the tests with:

cargo test

There are also some benchmarks implemented with criterion.rs in hailstone_benchmarks.rs. We can use these to see which hailstone sequence approach is faster:

cargo bench

You will see output like this for each benchmark:

time:   [1.1 ms 1.2 ms 1.3 ms]

This indicates the range of running times: 1.1 to 1.3 ms, and the average of 1.2 ms. We are most concerned about the average. Criterion also creates beautiful HTML output: open target/criterion/report/index.html in a web browser to see it.

Add a comment to your hailstone.rs indicating the relative speed of the two hailstone_sequence_* functions (thus proving to us that you have figured out how to run the benchmarks).

Finding a Vector Element

We will repeat the "find the position of an element" problem that we did in Haskell: in Haskell, it explored the Maybe type; here it will need the exactly analogous Option type.

In find.rs, write a function find_elt that takes a vector and value, and returns an Option<usize> that is Some(p) if the first occurrence is in position p and None if the value is not in the vector. The given type signature will work for any types that implement the Eq trait.

let v1: Vec<i32> = Vec::from([4, 5, 2, 8, 7, 3, 1]);
println!("{:?}", find_elt(&v1, 8)); // Some(3)
println!("{:?}", find_elt(&v1, 6)); // None
let v2: Vec<char> = "Hello World!".chars().collect();
println!("{:?}", find_elt(&v2, 'o')); // Some(4)
println!("{:?}", find_elt(&v2, 'q')); // None

A Struct for Rational Numbers

In rational.rs, create a struct Rational for rational number: a numerator n and denominator d, both i64.

#[derive(Debug, Clone, PartialEq)]
pub struct Rational {
    …
}

For this struct, we will implement:

• a constructor Rational::new that takes two arguments (numerator and denominator), and returns a Rational.
• the From<i64> trait, so we can construct one from an integer.
• a method .reduce() that reduces the fraction to lowest terms in-place.

let mut r = Rational::new(6, 8);
println!("{:?}", r); // prints Rational { n: 6, d: 8 }
r.reduce();
println!("{:?}", r); // prints Rational { n: 3, d: 4 }
let n = Rational::from(4_i64);
println!("{:?}", n); // prints Rational { n: 4, d: 1 }
println!("{}", n == Rational::new(4,1)); // prints true

Submitting

Submit your files through CourSys for Exercise 7.