Install Rust if you haven't done so already. On the
Linux VM for the class, just do a rustup update.
You can edit the following skeleton program for your assignment (copy it to your own file.)
/* optional compiler directives to avoid certain non-essential warnings
#![allow(dead_code)]
#![allow(unused_variables)]
#![allow(non_snake_case)]
#![allow(non_camel_case_types)]
#![allow(unused_parens)]
*/
use std::mem::{swap,replace,take};
use std::collections::{HashSet,HashMap};
// your code can go before or after main. make sure it's clearly marked.
// This main wont' compile until you've completed parts of your assignment.
fn main() {
let strs = ["c","kotlin","scala","perl","f#","c#","rust","c++","lambda7b"];
let mut v= Vec::<String>::new();
for s in strs.iter() { v.push(String::from(*s)); }
// note: strs is a vector containing values of type &str, which is a
// "string slice", which can be copied so *s is safe. But String type
// are vectors underneath and can't be copied. s by itself has type &&str
// so one * is required.
//for s in &v { print!("{} ",s) } println!();
//let flipv = flip(&v);
let flapv = flap(&v);
for s in &flapv { print!("{} ",s) } println!();
let v1 = vec!["ab","cd","ab","xz"];
let v2 = vec!["ef","ab","cd","gh"];
let rv3 = union(&v1,&v2);
println!("{:?}",rv3); //{:?} prints anything that implements Debug trait
} // main
Save the program with a .rs suffix and compile it with rustc. The executable will have the same name as the program.
The following generic function takes a borrow of a vector of :Copy values and returns the reverse of it (non-destructively).
fn rev_copy<T:Copy>(v:&Vec<T>) -> Vec<T>
{
let mut rev = Vec::new(); // rust should be able to infer the type
let mut i = v.len(); // prepare backwards loop
while i>0 { rev.push(v[i-1]); i-=1; }
rev // do not put ; here
}
Note that the type of i is usize, an unsigned integer type, which
is why the while loop is written the way it is. In other languages
you might write this as while i>=0, which will stop when i becomes -1.
But an unsigned value can't become -1. This is just one of the little
things you need to remember when writing rust. Instead of i<v.len()-1,
you should write i+1<v.len() else it may underflow.
But what if T can't be assumed to implement the Copy trait? You
can't copy the values so you have to take (move) them. This means
that your function must be destructive (mut). You can efficiently
take the last item out of a vector with .pop(), which returns an
Option<T>, which will be Some(x) or None if the vector was empty.
I'll write the reverse function in three ways:
fn rev1<T>(v:&mut Vec<T>) -> Vec<T>
{
let mut rv = Vec::new();
while v.len()>0 {
v.pop()
.map(|x|rv.push(x));
}//while
rv // don't add ; here
}
fn rev2<T>(v:&mut Vec<T>) -> Vec<T>
{
let mut rv = Vec::new();
while v.len()>0 {
rv.push( v.pop().unwrap() );
}//while
return rv; // need the ; if using "return" keyword
}
fn rev3<T>(v:&mut Vec<T>) -> Vec<T>
{
let mut rv = Vec::new();
while let Some(x) = v.pop() {
rv.push(x);
}
rv
}
The first version, rev1, is in the functional programming style with a
lambda-closure and your favorite monadic combinator map. The rev2
function calls .unwrap(), which will panic (crash the program) if called
on None. But since we've checked that v.len()>0, it's safe. But if
you call .unwrap() profusely in your programs, then None will start to
acquire many of the dangerous properties of the null pointer and will
cost you a billion dollars. This time it won't be Tony Hoare's fault.
The version that I prefer, rev3, uses a type of loop unique to Rust.
The while-let loop runs depending on whether the pattern Some(x)
matches v.pop(). There is also an "if-let" construct.
But what if we don't want to destroy the original vector? How can I create a reverse "copy" of the vector when the values can't be copied? I can create instead a vector of borrows, arranged in reverse order.
fn flip<T>(v:&Vec<T>) -> Vec<&T>
{
let mut rv:Vec<&T> = Vec::new();
let mut i=v.len();
while (i>0) { rv.push(&v[i-1]); i-=1; }
rv
}
This function takes a borrow of a vector and returns a vector of borrows. Each borrow in the returned vector refers to value of the original vector. This in most cases is as good as a non-destructive "copy" of the vector.
QUIZ: What's wrong with the following function?
fn flip2<T>(v:Vec<T>) -> Vec<&T>
{
let mut rv = Vec::new();
let mut i=v.len();
while (i>0) { rv.push(&v[i-1]); i-=1; }
rv
} // won't compile
This will give one of the most dreaded compiler errors in Rust:
"expected named lifetime parameter"
If you write a function that returns borrows, remember that these
borrows cannot outlive the values that they're borrowing. Since v is
a local var that owns the Vec<T>, its lifetime cannot possibly extend
beyond the function call. So returning a borrow to any part of it
would be futile. However, the first flip function is OK because rust
will infer that the lifetime of the borrows in the returned vector is
the same as the lifetime of the borrowed values in *v.
However, there are also situations that require you to declare lifetime variables. Consider the following function, which finds the intersection of two vectors: it returns a vector containing borrows of all values that appear in both vectors v1 and v2:
fn intersection<'t,'u,T:Eq>(v1:&'t Vec<T>, v2:&'u Vec<T>) -> Vec<&'t T>
{
let mut iv = Vec::new(); // intersection to be returned
for x in 0..v1.len()
{
for y in 0..v2.len()
{
if &v1[x]==&v2[y] { iv.push(&v1[x]); } // can it be iv.push(&v2[y])?
}
}
return iv; // same as iv without ;
}//intersection
The trait Eq allows you to use the == symbol between two values. The
generic variables 't and 'u are LIFETIME parameters. They allow you
to say more accurately what is the lifetime of the arguments and
return value of the function. Notice how we contructed the
intersection vector: all values are references to the first vector
(v1), and so the return type is Vec<&'t T> and not Vec<'u T>.
Write a function 'flap', in the style of flip, that reverses the
left half and the right half of a vector (of non-:COPY values and non
:Clone). The idea is that flap([a,b,c,d,e,f]) will give [c,b,a,f,e,d].
If there's a middle value, it should stay in place: flap([a,b,c,d,e])
should give [b,a,c,e,d]. However, you will have to return a vector of
references, just as flip does. The function you write MUST have the
following signature (name and type):
fn flap<T>(v:&Vec<T>) -> Vec<&T>
Write a function, similar to intersection, that returns the UNION of two vectors. FURTHERMORE, the union may not contain borrows of duplicate values. You will have to figure out the signature of the function (first line) but you MAY NOT assume the :Copy or :Clone traits! Your function must work on vectors of generic type T:Eq, just like in the intersection function.
Hint: first write a function to count how many times a value is contained inside a vector. This function had better take borrows and return usize. There are further examples of functions with lifetime parameters in the transition guide.
{ (a,b), (b,c), (c,d) }
would mean that a is a friend of b, b is a friend of c, and c is a friend of d.
The "transitive closure" of a relation is a relation such that, if
(a,b) and (b,c) are in the relation set then so is (a,c).
A friend of yours is a friend of mine (not really, but that's what
transitive means).
We can represent the friend-of relation in Rust using a
std::collections::HashSet<(String,String)>. Pairs are built-in
datatypes in Rust: (3,-4) has type (i32,i32).
We want to write a function that takes a relation and ADD new pairs to the relation to form its transitive closure. The function should destructively add new pairs to the set.
Here is an attempt, but it doesn't compile.
fn transitive_closure(friends: &mut HashSet<(String,String)>) {
let mut changes = true; //keep adding pairs until no new ones are added
while changes {
changes = false;
for (a,b) in friends.iter() {
for (c,d) in friends.iter() {
if b==c {
changes = friends.insert((a.clone(),d.clone())) || changes;
// .insert returns false if key already exists in set
// It's ok to clone if the algorithm calls for it.
}
}// inner for
}//outer for
}//while there are changes
}
You might think that it doesn't compile because Rust makes everything hard. On the contrary, Rust is helping you avoid a bad mistake that with other languages might be too late by the time you discover it.
EXPLAIN THE COMPILER ERROR. (warning: be specific to the code and the error given by the compiler for this code. Do not write a generic, vague explanation.)
Fix the error by writing a correct version. The following function tests your function
fn transitive_test() {
let mut friends = HashSet::new();
for (a,b) in
[("Nev","Isa"),("Isa","Haten"),("Haten","Arman"),("Isa","Artyan")]
{
friends.insert((a.to_owned(), b.to_owned()));
}
transitive_closure(&mut friends);
for (a,b) in friends.iter() {
println!("{} is a friend of {}",a,b);
}
}
Expected output of correct program (order may vary since it's a set):
Nev is a friend of Arman
Nev is a friend of Isa
Haten is a friend of Arman
Nev is a friend of Artyan
Isa is a friend of Haten
Isa is a friend of Artyan
Nev is a friend of Haten
Isa is a friend of Arman
A symmetric closure of a relation is a relation such that if
(x,y) is in the relation then (y,x) is also in the relation.
Write a function that generates the symmetric closure of a relation.
This time, be generic, though you can assume that type T can be cloned
in addition to being hashed and compared for == (required by Hash trait).
fn symmetric_closure<T:Clone+Hash+Eq>(relation: &mut HashSet<(T,T)>)
Write a function to create the transitive and symmetric closure of a relation:
fn transitive_symmetric_closure<T:Clone+Hash+Eq>(relation: &mut HashSet<(T,T)>)
Devise your own test for your function: you can still use the friend-of set.
(optional challenge) A permutation of size n is a vector/array of n unsigned integers with values 0 to n-1. The following program in F# applies a permutation to an array of the same size, scrambling it and returning the scrambled array.
let permute (a:'T [], perm:int []) =
let mutable b = Array.zeroCreate (a.Length)
for i in 0..a.Length-1 do
b.[i] <- a.[perm.[i]]
b;; // b is returned by function
let a = [|'a'; 'b'; 'c'; 'd'; 'e'|]
let p = [|1; 4; 2; 0; 3|]
let b = permute(a,p);
for c in b do printf "%c " c // prints b e c a d
That was easy to do back in the 'ole days when you can copy any T you
want, be it a primitive value or a pointer. You can have as many pointers
to something as you want, and they can even form cycles. Nanny GC will
create a spanning tree... But those days are over. With Rust you need
to be as tough as nails. Write the apply_permutation function in Rust.
You may not assume that T implement any trait at all.
fn apply_permutation<T>(mut a:Vec<T>, perm:&Vec<usize>) -> Vec<T>
Note that mut a means you can change it inside the function,
such as pop from it. But it's still a local variable and the vector
is owned by the function.
IMPORTANT REQUIREMENT: Your function must run in worst-case O(n) time.
Hint: consider using std::mem::swap. But what are you going to swap it with??