2

企図と実装に関して

お世話様です。

  • nightly-x86_64-pc-windows-msvc
  • rustc 1.74.0-nightly (bdb0fa3ee 2023-09-19)

を用いております。

RustのIteratorを拡張する場合どのようになるのか学ぶことを目的にしてfilter相当の機能を実装し、理解を深めようとしました。

そのコードが以下になります。

pub struct WinnowIterator<I, P>(I, P);

pub trait Winnow<I, P> {
    fn winnow(self, pred: P) -> WinnowIterator<I, P>;
}

impl<T, I: Iterator<Item = T>, P: Fn(&T) -> bool> Winnow<I, P> for I {
    fn winnow(self, pred: P) -> WinnowIterator<I, P> {
        WinnowIterator(self, pred)
    }
}

impl<T, I: Iterator<Item = T>, P: Fn(&T) -> bool> Iterator for WinnowIterator<I, P> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        for s in self.0.by_ref() {
            if (self.1)(&s) {
                return Some(s);
            } else {
                continue;
            }
        }
        None
    }
}

//Dispatchを確認するために追加した実装ここから
pub enum WinnowTypes {
    Even,
    Odd,
}

impl<I: Iterator<Item = i32>> Winnow<I, WinnowTypes> for I {
    fn winnow(self, pred: WinnowTypes) -> WinnowIterator<I, WinnowTypes> {
        WinnowIterator(self, pred)
    }
}

impl<I: Iterator<Item = i32>> Iterator for WinnowIterator<I, WinnowTypes> {
    type Item = i32;

    fn next(&mut self) -> Option<Self::Item> {
        fn odd(i: &i32) -> bool {
            i & 1 == 1
        }

        fn even(i: &i32) -> bool {
            i & 1 == 0
        }

        for e in self.0.by_ref() {
            let tmp = match self.1 {
                WinnowTypes::Even => even(&e),
                WinnowTypes::Odd => odd(&e),
            };

            return if tmp { Some(e) } else { continue };
        }

        None
    }
}

//Dispatchを確認するために追加した実装ここまで

#[cfg(test)]
mod tests {
    use super::Winnow;
    use crate::winnow::WinnowTypes::{Even, Odd};
    use std::fmt::Debug;

    fn assert<T: PartialEq + Debug, E: Iterator<Item = T>, A: Iterator<Item = T>>(
        mut expected: E,
        mut actual: A,
    ) {
        for e in expected.by_ref() {
            match actual.by_ref().next() {
                None => unreachable!(),
                Some(a) => assert_eq!(e, a),
            }
        }

        match actual.by_ref().next() {
            None => assert!(true),
            Some(_) => unreachable!(),
        }
    }
    #[test]
    fn closure_test() {
        let expected = (0..10).filter(|i| i & 1 == 0);

        //ここで、|i| i & 1 == 0とすると、コンパイルエラーが発生する。
        let actual = (0..10).winnow(|i| i & 1 == 0);

        assert(expected, actual)
    }

    #[test]
    fn enum_test() {
        let actual = (0..10).winnow(Even);
        let expected = (0..10).filter(|x| x % 2 == 0);
        assert(expected, actual);

        let actual = (0..10).winnow(Odd);
        let expected = (0..10).filter(|x| x % 2 != 0);
        assert(expected, actual)
    }
}

発生したエラーと試してみたこと

概略、型Tを返却するイテレータに、PredicatorとなるClosureを指定したfilter関数と全く同じ働きを持つ実装と、i32のイテレータのみを対象とし、OddまたはEvenの列挙子を取る実装をそれぞれに配置してテストしている形になっています。

これらは概ね僕の意図通り動いてくれたのですが、closure_test の部分で、与えるべきClosureがfilter関数は|x| x & 1 == 0で構わないのに対して、僕の自作したwinnowでは|i: &_| i & 1 == 0のように引数が参照であることを明示する必要があり、これを明示しない場合、以下のようなコンパイルエラーが発生しました。

error: implementation of `FnOnce` is not general enough
  --> src\winnow.rs:89:16
   |
89 |         let actual = (0..10).winnow(|i| i & 1 == 0);
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `FnOnce` is not general enough
   |
   = note: closure with signature `fn(&'2 i32) -> bool` must implement `FnOnce<(&'1 i32,)>`, for any lifetime `'1`...
   = note: ...but it actually implements `FnOnce<(&'2 i32,)>`, for some specific lifetime `'2`

エラーの内容を読み解くとどうやら所与のClosureがFnOnceとして評価されているように見受けられます。

但し、//Dispatchを確認するために追加した実装ここから から //Dispatchを確認するために追加した実装ここまでをコメントアウトし、

fn enum_test()もコメントアウトすると、問題なくコンパイルが通るのでFnとして評価されていると理解しました。

質問の趣旨

当該コンパイルエラーに関してはClosureの引数に参照で有ることを指定することで望む動作はしますから、実用上問題は無いと僕は現状考えています。

しかしながら、一見すると何の関係もない実装を追加した結果何故このようなコンパイルエラーが発生し、そして&_を明示することで解決できたのかがどうしても理解できません。

この件に関して何か知見をお持ちの方は何卒ご教授いただきますようよろしくお願い申し上げます。

1
  • 1
    精査していないですが users.rust-lang.org/t/… これと同じ問題を踏み抜いた可能性があるかも
    – 時計屋
    Commented 2023年9月20日 8:35

2 件の回答 2

3

https://github.com/rust-lang/rust/issues/64373 に基づいて説明してみます。
「特殊ケース」まではそこそこ自信ありますが、「本題」は挙動から見た推論になってしまったことをご了承ください。

高階トレイト境界 (HRTB)

既にご存じかもしれませんが一応。
ご提示のコードに、 P: Fn(&T) -> bool のようなトレイト境界がありますが、参照なので当然ライフタイムパラメータが省略されているはずです。これは内部的には P: for<'a> Fn(&'a T) -> bool となっており、全ての 'a に対して、 Fn('a T) -> bool であることを要求しています。これを高階トレイト境界 (HRTB) と呼びます。

参考: https://doc.rust-jp.rs/rust-nomicon-ja/hrtb.html

クロージャの型推論

let f = |a| foo(a); と書いた場合と let g = |a: &_| foo(a); と書いた場合では推論のされ方に違いがあり、前者は fn(?A) -> ?B、後者は for<'a> fn(&'a ?C) -> ?D のように一旦解釈されるそうです。
この後は、例えば ?A&'a i32 のように推論されるだけで、後からHRTBを満たすようにはならないわけです。

実際、以下のようなコードを書くとコンパイルエラーになりますが、|a: &_| のように型注釈を入れるとコンパイルが通ります。

fn hoge(_: impl Fn(&i32)) {}

fn main() {
    // コンパイルエラー
    let f = |a| ();
    hoge(f);
}

特殊ケース

では、なぜ以下のようなコードがコンパイルできるのかというと、引数に直接渡したクロージャは、関数の引数の型情報を使った、特殊な推論が行われることがあるからです。

(0..10).filter(|i| i & 1 == 0)

std::iter::Iteratorfilter は以下のような引数を取ります。

fn filter<P>(self, predicate: P) -> Filter<Self, P>
where
    Self: Sized,
    P: FnMut(&Self::Item) -> bool,

前述の通り、 P: FnMut(&Self::Item) -> boolP: for<'a> FnMut(&'a Self::Item) -> bool ですから、この情報から |i| i & 1 == 0 もHRTBを満たすように推論できるというわけです。

とはいえ、例えば Some で包むだけでコンパイルが通らなくなりますし、常にいい感じに推論してくれるというわけでもないようです。

fn hoge(_: impl Fn(&i32)) {}

fn fuga(_: Option<impl Fn(&i32)>) {}

fn main() {
    // OK
    hoge(|a| ());

    // コンパイルエラー
    fuga(Some(|a| ()));

    // OK
    fuga(Some(|a: &_| ()));
}

本題

長々と書きましたが、結局以下のコメントで大体あっていそうです。
個人的には、これが問題というよりは、 (0..10).filter(|i| i & 1 == 0) がコンパイル通る方が寧ろ例外的だという印象はありますが。

https://users.rust-lang.org/t/implementation-of-fnonce-is-not-general-enough/68294/2 これと同じ問題を踏み抜いた可能性があるかも

今回の件はおそらく、 winnow の2つの実装のうちどちらを使うのかを、クロージャをHRTBにするか決定する段階ではまだ決定できていないためだと思われます。
そういう意味だと、Option<impl Fn(&i32)> のケースは SomeNone のどちらに合わせるか決める必要があるという意味で、やはり似てるのかもしれません。

impl<T, I: Iterator<Item = T>, P: Fn(&T) -> bool> Winnow<I, P> for I {
    fn winnow(self, pred: P) -> WinnowIterator<I, P> {
        WinnowIterator(self, pred)
    }
}

impl<I: Iterator<Item = i32>> Winnow<I, WinnowTypes> for I {
    fn winnow(self, pred: WinnowTypes) -> WinnowIterator<I, WinnowTypes> {
        WinnowIterator(self, pred)
    }
}
1
  • 1
    高階トレイト境界というのが、当該エントリの文脈にも出ておりなんだこれ?とは言え高階というからには高階関数的な何かなのか?と変に類推し余計混乱しておりました。なのでHRTBの解説並びに詳細のドキュメントのご提示は大変助かりましたありがとうございます。 又様々なケースを提示いただいた上で機序を解説いただき自分の理解の助けになるところ非常に大きいものが有りました。 ご教授ありがとう御座いました
    – 時計屋
    Commented 2023年9月23日 3:28
1

あんまり自身がないのですが、自分の見解を記事にしてみました
参考になれば幸いです

https://zenn.dev/skanehira/articles/2023-09-23-rust-closure-lifetime-binder

1
  • 当該問題を切り分けて極小化した例を提示していただいたので問題の本質が何処にあったのか理解の助けになりました。 また、高階トレイト境界に対する知識不足があったので提示いただいたRust docも助けになります。 ご教授ありがとう御座いました
    – 時計屋
    Commented 2023年9月23日 3:30

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。