lifetimekata 最后的挑战求教

wukong 发表于 2023-03-04 17:45

Tags：lifetime, lifetimekata

在学习 lifetimekata 的 lifetime，学到了最后一个挑战（ https://tfpk.github.io/lifetimekata/chapter_9.html ），需要让下面的代码执行正确，同时文章也给了提示（ https://github.com/rust-lang/rust/issues/73788 ），但还是不太明白，请教一下各位如何改？并说明一下推理过程，感谢！

use std::collections::HashSet;

struct Difference<'first, 'second> {
    first_only: Vec<&'first str>,
    second_only: Vec<&'second str>
}

fn find_difference<'fst,'snd>(sentence1: &'fst str, sentence2: &'snd str) -> Difference<'fst, 'snd> {
    let sentence_1_words: HashSet<&str> = sentence1.split(" ").collect();
    let sentence_2_words: HashSet<&str> = sentence2.split(" ").collect();

    Difference {
        first_only: (&sentence_1_words - &sentence_2_words).into_iter().collect(),
        second_only: (&sentence_2_words - &sentence_1_words).into_iter().collect(),
    }

}

fn main() {
    let first_sentence = String::from("I love the surf and the sand.");
    let second_sentence = String::from("I hate the surf and the sand.");

    let first_only = {
        let third_sentence = String::from("I hate the snow and the sand.");
        let diff = find_difference(&first_sentence, &third_sentence);
        diff.first_only
    };

    assert_eq!(first_only, vec!["hate", "surf"]);

    let second_only = {
        let third_sentence = String::from("I hate the snow and the sand.");
        let diff = find_difference(&third_sentence, &second_sentence);
        diff.second_only
    };

    assert_eq!(second_only, vec!["snow"]);
}

playground 链接： https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=d89af7ce5f834f38d6caf0400eea2f3c

Ext Link: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=d89af7ce5f834f38d6caf0400eea2f3c

评论区

写评论

wangbyby 2023-03-06 10:28

问题是hashset的sub操作

impl<T, S> Sub<&HashSet<T, S>> for &HashSet<T, S>
where
    T: Eq + Hash + Clone,
    S: BuildHasher + Default,

这里的T:'first+'second 混合了额外的生命周期。自己单独写一个函数/接口会比较好

苦瓜小仔 2023-03-05 15:19

生命周期会影响类型，这在大多数情况下我们感受不到

这主要得益于 covariance，比如这样：例 1

它正常运行，并且与局部作用域无关。

而例 2，invariance 的加入不会阻止在其之前发生 covariance，但会维持之后的生命周期不变。

但这并不是标准库生命周期过度约束的问题，而是需要一个针对 T 为引用时的 API 来让例子中的代码通过。

对于这个问题里的例子，问题的关键的确在于 difference 的签名约束了第二个参数，见例 3，它是对此次问题的最简代码错误复现（注意，它并没有使用到 invariance！），并且包含一个看似可行的解决办法 —— 让 difference 的两个参数有各自的生命周期：

fn difference<'a, 'b>(&'a self, other: &'b HashSet<T, S>) -> Difference<'a, 'b, T, S>

但其实这并不可行，因为这个 API 依然只接受相同的 T，所以没有改变原问题中 T: 'fst 和 T: 'snd 两个隐含约束，但我说了，这里问题的关键在于，我们不想要 T: 'snd 的限制，所以你根本无法修复这个 API 来解决问题（不信的话自己去用 GAT 和 newtype 修正，你得不到解决方案），从而需要提出新的 API。

适用于这个问题的新的 API 候选签名（没有写完整的约束）：

fn difference<'a, 'b>(&'a HashSet<T, S>, other: &'b HashSet<U, S>) -> Difference<'a, 'b, T, U, S>

fn difference<'a, 'b, 'c>(&'c HashSet<&'a T, S>, other: &'c HashSet<&'b T, S>) -> Difference<'a, 'b, 'c, T, S> （这里使用相同的 'c 是因为 covariance 会处理好我们想要的临时引用；一楼的方案和这个在核心上一致，虽然你看到标注生命周期略有不同）

hax10 2023-03-04 23:51

我觉得不用专门学，你的代码作风已经很符合Haskell派的。

--
👇
苦瓜小仔: > 看你的代码就知道你肯定是Haskell爱好者

我不是。我没有学过 Haskell :(

苦瓜小仔 2023-03-04 22:29

看你的代码就知道你肯定是Haskell爱好者

我不是。我没有学过 Haskell :(

作者 wukong 2023-03-04 22:23

谢谢，受益匪浅

--
👇
苦瓜小仔: > 所以根本不能收集成 Vec 去断言！

如果有人想知道怎么写一个返回迭代器而不是 Vec 的函数的话...

fn difference_iter<'a, 'ref_, T>(
    set_a: &'ref_ HashSet<&'a T>,
    set_b: &'ref_ HashSet<&T>,
) -> impl Iterator<Item = &'a T> + 'ref_
where
    T: std::cmp::Eq + std::hash::Hash + ?Sized,
    'a: 'ref_,
{
    set_a.iter().filter(move |a| !set_b.contains(*a)).copied()
}

playground

顺便把结构体的 Vec 修正成了 HashSet ：）

hax10 2023-03-04 21:49

大师，看你的代码就知道你肯定是Haskell爱好者😁

对了，原代码不保证vec元素的顺序是因为HashSet用的杂凑函数本来有随机性，不是因为多线程的竞态条件。我原来看到报错消息含thread的时候想歪了。

--
👇
苦瓜小仔:

HashSet 的文档明确说明了，迭代元素的顺序任意，所以根本不能收集成 Vec 去断言！

苦瓜小仔 2023-03-04 21:48

给那个 issue 留言了

苦瓜小仔 2023-03-04 21:21

所以根本不能收集成 Vec 去断言！

如果有人想知道怎么写一个返回迭代器而不是 Vec 的函数的话...

fn difference_iter<'a, 'ref_, T>(
    set_a: &'ref_ HashSet<&'a T>,
    set_b: &'ref_ HashSet<&T>,
) -> impl Iterator<Item = &'a T> + 'ref_
where
    T: std::cmp::Eq + std::hash::Hash + ?Sized,
    'a: 'ref_,
{
    set_a.iter().filter(move |a| !set_b.contains(*a)).copied()
}

playground

顺便把结构体的 Vec 修正成了 HashSet ：）

苦瓜小仔 2023-03-04 21:02

一楼给了一个仿照标准库 Difference 结构体的例子。

但这并不是标准库生命周期过度约束的问题，而是需要一个针对 T 为引用时的 API 来让例子中的代码通过。

你完全可以自己写一个函数：

fn difference<'a, T>(set_a: &HashSet<&'a T>, set_b: &HashSet<&T>) -> Vec<&'a T>
// 即 fn difference<'a, 'b, T>(set_a: &HashSet<&'a T>, set_b: &HashSet<&'b T>) -> Vec<&'a T>
where
    T: std::cmp::Eq + std::hash::Hash + ?Sized,
{
    set_a
        .iter()
        .filter(|a| !set_b.contains(*a))
        .copied()
        .collect()
}

playground

它就能让例子通过。

这个函数的生命周期标注告诉了我们问题出在哪：

我们的返回值只需要元素为 &'a T 的集合的一部分，而不需要元素为 &'b T 的集合（的一部分）。这正是这个例子核心的要点。

它之所以能做到，是因为 fn contains<Q>(&self, value: &Q) -> bool 方法对 &Self 和 &Q 有各自的生命周期。

标准库的 fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S> 做不到，是因为这个 API 只接受相同的 T —— 当 T 为引用时，它们应具有相同的生命周期！而例子中，两个集合有不同的生命周期，从而引用的元素不一样 —— 一个是 HashSet<&'fst str>，另一个是 HashSet<'snd str>，从而让它们类型一致，必须添加编译器建议的 'fst: 'snd 和 'snd: 'fst，来保证元素的类型一致。是的生命周期会影响类型，这在大多数情况下我们感受不到，但在这里，就是关键所在。

此外，例子其实有误：

正如其他人提出来的，以及一楼和我的代码展示的那样，两个断言的逻辑不对！
HashSet 的文档明确说明了，迭代元素的顺序任意，所以根本不能收集成 Vec 去断言！

pub fn iter(&self) -> Iter<'_, T> An iterator visiting all elements in arbitrary order. The iterator element type is &'a T.

thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `["surf", "love"]`,
 right: `["love", "surf"]`', src/main.rs:43:5

hax10 2023-03-04 20:25

估计是吧，不过两个生命周期可能会让代码写起来更方便。不过，这需要你重新实现集合差集的计算。前面的人借鉴github上的贴子已经做好了。

--
👇
wukong: 我理解如果这样改的话，就不用两个生命周期了。见（ https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=3f74520bbf5120466d2dd34f7b6b0679 ）

应该是作者就要这样设计题目，通过题目加强对 lifetime 的理解和实践。

作者 wukong 2023-03-04 19:42

我理解如果这样改的话，就不用两个生命周期了。见（ https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=3f74520bbf5120466d2dd34f7b6b0679 ）

应该是作者就要这样设计题目，通过题目加强对 lifetime 的理解和实践。

--
👇
hax10: 这段代码会通过HashSet的difference方法比较一下两个集合里的单词，计算出哪些单词只出现在第一集合或只出现在第二集合里。

原代码存在几个方面的问题：

difference()返回的Difference值包含两个向量vec，即first_only和second_only。difference()会假设这两个向量拥有同样的生命周期，但代码要求difference()把结果放在两个生命周期不一定相同的Difference结构体里。这也是github的贴子上提到的问题，按理说difference()应该接受两个生命周期不一样的情况，但是一开始没这么做，现在为了保持跟现有代码的兼容性，就不扩生命周期了。为了解决问题可以通过where条款告诉编译器你的两个生命周期是相同的，或者直接改Difference结构体的定义也可以。更复杂的解决办法你可以自己去研究。
third_sentence不应该定义在代码块里头，把它拿出来才能让它不被删掉。
两个assert_eq断言都有问题。
因为竞态条件的原因，first_only里面的两个单词出现的顺序不能保证。

能运行的代码：

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=528f409da2fd79c1f0633fcf77528b2a

hax10 2023-03-04 19:37

这段代码会通过HashSet的difference方法比较一下两个集合里的单词，计算出哪些单词只出现在第一集合或只出现在第二集合里。

原代码存在几个方面的问题：

difference()返回的Difference值包含两个向量vec，即first_only和second_only。difference()会假设这两个向量拥有同样的生命周期，但代码要求difference()把结果放在两个生命周期不一定相同的Difference结构体里。这也是github的贴子上提到的问题，按理说difference()应该接受两个生命周期不一样的情况，但是一开始没这么做，现在为了保持跟现有代码的兼容性，就不扩生命周期了。为了解决问题可以通过where条款告诉编译器你的两个生命周期是相同的，或者直接改Difference结构体的定义也可以。更复杂的解决办法你可以自己去研究。
third_sentence不应该定义在代码块里头，把它拿出来才能让它不被删掉。
两个assert_eq断言都有问题。
因为竞态条件的原因，first_only里面的两个单词出现的顺序不能保证。

能运行的代码：

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=528f409da2fd79c1f0633fcf77528b2a

作者 wukong 2023-03-04 19:33

谢谢！👍🏻

--
👇
Grainspring: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=95ac4258edd7cddb2a3de3116589348b

Grainspring 2023-03-04 19:23

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=95ac4258edd7cddb2a3de3116589348b

1 共 14 条评论, 1 页