Rustで挿入ソート 配列を受け取り、配列を返す関数を作りたい

Question

Rust初心者です。基本的なアルゴリズムを実装してみようと考え、ソートアルゴリズム(挿入ソート)の実装にトライしました。しかし、タイトル通り、配列を受け取って配列を返す関数が上手く作れません。ライフタイムの関係でエラーが発生しているのは分かっているのですが、インターネットで調べたりドキュメントを読んだりしても全く解決しません。

fn insert<'a, T: Ord+Clone>(x: T, v: &'a [T]) -> &'a [T] {
    if v.len() == 0 {
        &[x]
    }else {
        if x < v[0] {
            let res = [&[x], v].concat();
            &res
        }else {
            let res = [&[v[0].clone()], insert(x, &v[1..])].concat();
            &res
        }
    }
}

fn isort<T: Ord+Clone>(v: &[T]) -> &[T] {
    if v.len() == 0 {
        &[]
    }else {
        let x = v[0].clone();
        insert(x, isort(&v[1..]))
    }
}

&[x]の部分でtemporary value does not live long enough、&resの部分でborrowed value does not live long enoughというエラーが発生しています。insert関数の中で有効でも、返り値として使用すれば、関数のスコープを抜けた際にアクセス出来ないようになるためエラーを出しているということでしょうか？

また、この問題はVecを使うことで解決することが出来たのですが、出来るだけVecではなく配列を使うべきだという話をよく聞きます。なので、配列ではどのような実装をすれば良いのか教えていただきたいです。

Answer 1

最初に知っておいてほしいのは、&[T]はスライス型であって、配列型ではないことです。配列型は[T; 10]のように、要素の型と要素数が入った型になります。

insert()関数は任意の長さ（Nとします）の配列を引数に取り、長さN + 1の配列を返しますが、Rustではそのような関数は定義できません。

// コンパイルエラーになる
fn insert()<T: Ord+Clone>(x: T, v: [T; N]) -> [T; N + 1] {

// これならコンパイルできるが、引数に長さ1の配列しか取れない
fn insert()<T: Ord+Clone>(x: T, v: [T; 1]) -> [T; 2] {

次にご質問のコードでなぜスライス&[T]を返せないかですが、

insert関数の中で有効でも、返り値として使用すれば、関数のスコープを抜けた際にアクセス出来ないようになるためエラーを出しているということでしょうか？

スライスは型に参照&が現れているように、それ自体は値の実体を持たず、別の場所にある実体（配列、Vecなど）を参照します。スライスは実体なしには存在できません。つまりスライスのライフタイム（生存期間）は実体のライフタイムよりも短くなければなりません。

ではご質問のコードでそれらの実体はどこにあるでしょうか？　以下のようになっています。

• &[x]では[x]が実体。[T; 1]型の配列
• [&[x], v].concat()では[&[x], v]が実体。[&[T]; 2]型の配列

insert()関数のスコープを抜けると、これらの実体のライフタイムが尽きます（メモリ領域が解放されます）。それらの実体を参照するスライスを返そうとしているので、スライスの方がライフタイムが長くなってしまいエラーになるわけです。

また、この問題はVecを使うことで解決することが出来たのですが、出来るだけVecではなく配列を使うべきだという話をよく聞きます。なので、配列ではどのような実装をすれば良いのか教えていただきたいです。

残念ながら、このプログラムですと配列またはスライスを返すことはできません。

• 最初の理由により、任意の長さの配列を返す関数が書けない
• 2番目の理由により、関数内で作った実体を参照するスライスは戻り値として返せない

すでにされているようにVecを返すことならできます。

fn insert<'a, T: Ord + Clone>(x: T, v: &[T]) -> Vec<T> {
    if v.is_empty() {
        vec![x]
    } else {
        if x < v[0] {
            let mut res = vec![x];
            res.extend_from_slice(v);
            res
        } else {
            let mut res = vec![v[0].clone()];
            res.append(&mut insert(x, &v[1..]));
            res
        }
    }
}

fn isort<T: Ord + Clone>(v: &[T]) -> Vec<T> {
    if v.is_empty() {
        Vec::new()
    } else {
        let x = v[0].clone();
        insert(x, &isort(&v[1..]))
    }
}

なお上の実装では、insert()関数が呼ばれるたびに新しいベクタを作るため効率はよくありません。これはもし配列が使えたとしても効率の面では同じです。

もしisort()とinsert()が引数にとったスライス（&mut [T]）をその場で変更してもよいのなら、効率の良い実装もできます。（その場合はかなり違ったプログラムになるので例は割愛します）

Answer 2

insert関数の中で有効でも、返り値として使用すれば、関数のスコープを抜けた際にアクセス出来ないようになるためエラーを出しているということでしょうか

このエラー自体の理解はそれで合っています。

より根本的な原因として、関数シグネチャからこれがほぼ無理なことがわかります。どちらの関数も入力スライスと出力スライスに同じライフタイムを使っています(というか、ほぼそうするしかないんですが)。後者の関数の場合はlifetime elisionという規則で、同じライフタイムが使われると解釈されます。また、スライス型 [T] は連続したメモリ領域を指しますから、これらの関数の戻り値は、入力されたスライスの連続した一部分しか(ほとんど)ありえないということになります。

また、この問題はVecを使うことで解決することが出来たのですが、出来るだけVecではなく配列を使うべきだという話をよく聞きます。なので、配列ではどのような実装をすれば良いのか教えていただきたいです。

Rust用語でいう配列は長さが決まってしまっているので、スライスのこととして説明します。確かにスライスはVecより低コストなので「できるだけ」スライスを使うべきですが、できないときはあります。(スライスで何でもできるわけではないからこそ、Vecがあります。)Vecのコストは他の多くの言語では常に支払っているようなコストなので、慣れないうちはあまり気にせずVecを使ってしまっていいと思います。

さて、最初のほうで説明したように、スライスを受け取ってスライスを返す方法では部分列しか返せませんから、この場合はスライスを受け取ってVecを返すのが妥当です。しかし、Vecを使わない方法もあります。可変スライスを受け取り、それ自体をその場でソートするインターフェースにすればよいです。標準ライブラリのsortメソッドはそのようなインターフェースになっています。