Rust learning notes 2
The best way to learn is with doing and with failures.
Great Common Divisor of Strings
Solution #1
pub fn gcd_of_strings(str1: String, str2: String) -> String {
fn gcd_string<'a>(str1: &'a String, str2: &'a String) -> usize {
if str1.len() == str2.len() {
if str1 == str2 {
str1.len()
}
else {
0
}
} else {
let mut strs = str2;
let mut strl = str1;
if str1.len() < str2.len() {
strs = str1;
strl = str2;
}
if strs == &strl[0..strs.len()] {
gcd_string(&String::from(&strl[strs.len()..]),strs)
}
else {
0
}
}
}
str1[0..gcd_string(&str1,&str2)].to_string()
}
Solution #2
pub fn gcd_of_strings(str1: String, str2: String) -> String {
fn gcd_string<'a>(str1: &'a str, str2: &'a str) -> usize {
if str1.len() == str2.len() {
if str1 == str2 {
str1.len()
}
else {
0
}
} else {
let mut strs = str2;
let mut strl = str1;
if str1.len() < str2.len() {
strs = str1;
strl = str2;
}
if strs == &strl[0..strs.len()] {
gcd_string(&strl[strs.len()..],strs)
}
else {
0
}
}
}
str1[0..gcd_string(&str1,&str2)].to_string()
}
The below version of code is more concise but is more costly (involving a lot of copies)
pub fn gcd_of_strings(str1: String, str2: String) -> String {
if str1 == str2 {
str1
} else {
let mut strs = &str2;
let mut strl = &str1;
if str1.len() < str2.len() {
strs = &str1;
strl = &str2;
}
if strs == &strl[0..strs.len()] {
Solution::gcd_of_strings((&strl[strs.len()..]).to_string(),strs.to_string())
}
else {
"".to_string()
}
}
}
Actually we don’t need to return the dividing index, instead, we return references
pub fn gcd_of_strings(str1: String, str2: String) -> String {
fn gcd_string<'a>(str1: &'a str, str2: &'a str) -> &'a str {
if str1 == str2 {
str1
} else {
let mut strs = str2;
let mut strl = str1;
if str1.len() < str2.len() {
strs = str1;
strl = str2;
}
if strs == &strl[0..strs.len()] {
gcd_string(&strl[strs.len()..],strs)
}
else {
""
}
}
}
gcd_string(&str1,&str2).to_string()
}
Code data flow: both the two parameters are string and are moved to the function body. The function needs to return a string. In the function body, we define a function which will be called recursively. The inner function takes as input the references of the strings, because the function takes references as the parameters, we need to specify lifetimes.
Failure #1:
if (strs == strl[0..strs.len()])
If we do this, the compiler will complain like below
--> src/solution.rs:14:29
|
14 | if strs == strl[0..strs.len()] {
| ^^ no implementation for `&str == str`
|
= help: the trait `std::cmp::PartialEq<str>` is not implemented for `&str`
We can learn that, the == operator is actually implemented by a trait called std::cmp::PartialEq<str>. But why it says the PartialEq
if strl[0..strs.len()] == strs
Then the compiler says, PartialEq<&str> is not implemented for str! Why is that:
error[E0277]: can't compare `str` with `&str`
--> src/solution.rs:14:44
|
14 | if strl[0..strs.len()] == strs {
| ^^ no implementation for `str == &str`
|
= help: the trait `std::cmp::PartialEq<&str>` is not implemented for `str`
The reason is that, when evaluating the value of the == operator, the compiler will first decide to invoke which type is associated with the PartialEq trait. The compiler will decide which type to use by looking at the right side of == operator. In this first case, becasue the type of strl[..] is str, the compiler will apply PartialEq<str> to evaluate the value of the expression, and becasue the left side strs has a type of &str, the compiler cannot match the type for calling the function associated with PartialEq. Similar analysis can be applied to case 2.
Failure #2: If we do this for the type with &String, the compiler will complain
--> src/solution.rs:13:21
|
13 | if strs == strl[0..strs.len()] {
| ^^ no implementation for `&std::string::String == str`
|
= help: the trait `std::cmp::PartialEq<str>` is not implemented for `&std::string::String`
But if we apply the & operator to the right side of the operator, it is fine. But the type of the right is &str, the left side is &String, why compiler does not complain? It is because the Rust has a feature called deref coercion. In this case, the reference to string can be converted to the reference to string slice.
Failure #3: If we pass the type of str to String::from(), the compiler will complain like this
--> src/solution.rs:14:42
|
14 | Solution::gcd_of_strings(String::from(strl[strs.len()..]), strs.to_string())
| ^^^^^^^^^^^^ doesn't have a size known at compile-time