Rustの無限イテレータ

無限イテレータ

HaskellやClojureでは、遅延評価する無限リストから出発し、途中で打ち切ることで別のリストを作り出すというパターンがあったと思うが、Rustでも同じようなものがないかと思っていたら、あった。

0..

使い方の例
v = vec![a_1, a_2, ..., a_n]に対し、a_1, a_n, a_2, ...というvecを返す関数。(0..)とmap_while(Someが出る間mapを続け、ついでにunwrapするメソッド)を組み合わせる。

use std::collections::VecDeque;
fn head_tail<T>(v: Vec<T>) -> Vec<T> {
    let mut vd = VecDeque::from(v);
    (0..)
        .map_while(|i| {
            if i % 2 == 0 {
                vd.pop_front()
            } else {
                vd.pop_back()
            }
        })
        .collect()
}

もちろんたとえば次のように書けば無限イテレータも、そもそもイテレータ(に対するメソッド)も要らないのだが、変数がすくなくて済むのがなんとなく好き。

fn head_tail<T: Copy>(v: Vec<T>) -> Vec<T> {
    let mut a = 0;
    let mut b = v.len() - 1;
    let mut w = Vec::with_capacity(v.len());
    for i in 0..v.len() {
        if i % 2 == 0 {
            w.push(v[a]);
            a += 1;
        } else {
            w.push(v[b]);
            b -= 1;
        }
    }
    w
}

計算時間やメモリ的にはどうだろう。そこまで無駄はない(collect先のvecの大きさがわからないので再配置が生じうる点を除けば)と思うが、検証はまたいつか。

補足
さらに以下のようにシンプルに書けると気づいた。

fn head_tail<T>(v: Vec<T>) -> Vec<T> {
    let mut vd = VecDeque::from(v);
    (0..)
        .flat_map(|_| [vd.pop_front(), vd.pop_back()])
        .map_while(std::convert::identity)  // map_while(|x| x) と同じ
        .collect()
}

ただ、いずれの書き方でも、この関数であればイテレータの最大長はあらかじめvd.len()とわかっているので、(0..vd.len())と書けばよく、無限イテレータは不要であり、事前に長さのヒントがあった方が、collectするときにvecの再配置がなくて早いような気もする。(要検証)

他の無限イテレータ

std::iter::repeat

おなじ値を無限に繰り返す。takeなどと組み合わせて使う。

let i = std::iter::repeat(4).take(4) // vec![4; 4].iter()と同じ
i.eq(vec![4;4]) // => true

std::iter::repeat_with

同じ関数の結果を無限に繰り返す。

cycle

cloneできるイテレータを無限に繰り返す。

[1, 2, 3].iter().cycle().take(7).collect::<Vec<_>>() // => [1,2,3,1,2,3,1]