Rust - nth element
Tags: rust, 100daysofcode, programming, beginners
Published: 2021-01-02 10:48:26

I am new to Rust and have skimmed through most of the chapters of the [Rust Book](https://doc.rust-lang.org/book/). However, to get some programming practice, I decided to work through few of the [99 scheme problems](http://community.schemewiki.org/?ninety-nine-scheme-problems). The subject of this post is the third problem on that list.
```rust
// nth returns an optional value to the nth element
// of the list. The value of n indicates the position
// (= index + 1).

fn nth<T>(xs: &[T], n: usize) -> Option<T> {
    if (n < 1) || n > xs.len() {
        None
    } else {
        Some(xs[n-1])
    }
}
```
The code above was my first attempt at the problem. Well, how hard could indexing into a slice be? I had already checked the following worked.
```rust
let xs = &["he", "el", "lo"];
println!("{}", xs[0]); // he is printed out
```

But, to my surprise, the Rust compiler was unhappy.

```rust
error[E0508]: cannot move out of type `[T]`, a non-copy slice
  --> src/main.rs:18:14
   |
18 |         Some(xs[n-1])
   |              ^^^^^^^
   |              |
   |              cannot move out of here
   |              move occurs because `xs[_]` has type `T`, which does not implement the `Copy` trait

error: aborting due to previous error

For more information about this error, try `rustc --explain E0508`.

```

The way I interpret the error is that in the absence of a borrow, the indexed value either gets copied or moved out of the slice. The former isn't an option since the generic type `T` doesn't implement the `Copy` trait by default. And, I guess, for the latter to work, you'd need to give up the ownership of the value in that position, almost creating a hole in the slice which would be awkward. One could also argue maybe giving up the ownership of the entire slice is a decent compromise that works around the problem of leaving holes. But, then that means you can't de-allocate the rest of the slice anymore as long as the indexed value is in scope. I'm not sure if this was the reason behind the current behavior.

So, to fix, i could try taking a reference or constrain my slice to types that implement the `Copy` trait. Sure enough, the following code compiles:
```rust
// Option<&T> works
fn nth<T>(xs: &[T], n: usize) -> Option<&T> {
    if n < 1 || n > xs.len() {
        None
    }
    else{
        Some(&xs[n-1])
    }
}
```
And so does this too:
```rust
// <T: Copy> works
fn nth<T: Copy>(xs: &[T], n: usize) -> Option<T> {
    if n < 1 || n > xs.len() {
        None
    }
    else{
        Some(xs[n-1])
    }
}
```

So, what explains this?
```rust
let xs = &["he", "el", "lo"]; // xs: &[&str]
println!("{}", xs[0]);
```

`&str` is a shared/immutable reference to the static data. Copying the reference should be cheap enough and since it doesn't own the literal slice itself, it should be safe. It's expected that it follows `Copy` semantics. 

But what about `String` types? Would we run into trouble since `String` is a pointer to owned heap-allocated data and copying the pointer would simply create two owners to the same piece of data (causing double-free)? Since that can't happen, printing an indexed value from a slice of `String` values should fail to compile, right?

```rust
let xs = &["he", "el", "lo"];
let ys = &[String::from("he"), String::from("el"), String::from("lo")];

println!("{}", xs[0]);
println!("{}", ys[0]);
```
The code above compiles. However, this doesn't:
```rust
let xs = &["he", "el", "lo"];
let x: &str = xs[0];

let ys = &[String::from("he"), String::from("el"), String::from("lo")];
let y: String = ys[0];

println!("{}", xs[0]);
println!("{}", ys[0]);

``` 

```
error[E0508]: cannot move out of type `[std::string::String; 3]`, a non-copy array
  --> src/main.rs:50:21
   |
50 |     let y: String = ys[0];
   |                     ^^^^^
   |                     |
   |                     cannot move out of here
   |                     move occurs because `ys[_]` has type `std::string::String`, which does not implement the `Copy` trait
   |                     help: consider borrowing here: `&ys[0]`

error: aborting due to previous error; 2 warnings emitted

For more information about this error, try `rustc --explain E0508`.
```

It turns out `println!` macro has a special behavior. It borrows the value being formatted implicitly, which is why we never see those 'move out of type' errors.

##### References:
* [Does println borrow or own the variable?](https://stackoverflow.com/questions/30450399/does-println-borrow-or-own-the-variable)
* [https://users.rust-lang.org/t/why-cant-move-element-of-vector/30454](https://users.rust-lang.org/t/why-cant-move-element-of-vector/30454)