Rust中fold方法内实现提前返回的技术问题

原循环实现的minimum_length函数在遇到首尾字符不匹配时会直接返回当前长度，但改用fold方法后，闭包内的return只能退出闭包，无法终止整个函数，导致test_3测试失败（该测试需要中途终止遍历）。

原循环实现（正确） #

fn minimum_length(s: String) -> i32 {
    if s.len() <= 1 {
        return s.len() as i32;
    }

    let mut len_after_deleting_similar_ends = s.len();
    let x = len_after_deleting_similar_ends / 2;

    for (first_char, last_char) in zip(s.chars().take(x), s.chars().rev().take(x)) {
        if first_char == last_char {
            len_after_deleting_similar_ends -= 2
        } else {
            return len_after_deleting_similar_ends as i32
        }
    };

    len_after_deleting_similar_ends as i32
}

问题版fold实现（无法提前返回） #

fn minimum_length_fold(s: String) -> i32 {
    if s.len() <= 1 {
        return s.len() as i32;
    }

    let len_after_deleting_similar_ends = zip(s.chars().take(s.len() / 2), s.chars().rev().take(s.len() / 2))
        .fold(s.len(), |acc, (first_char, last_char)| {
            println!("{first_char} {last_char} {acc}");
            if first_char == last_char {
                acc - 2
            } else {
                return acc;
            }
     });

    len_after_deleting_similar_ends as i32
}

解决方案：使用try_fold实现提前终止 #

fold本身不支持提前终止遍历，而try_fold允许通过返回Result或Option来中断迭代。我们可以利用这一点，在遇到不匹配字符时返回Err(当前长度)，遍历完成后返回Ok(最终长度)，最后根据结果返回对应值。

修改后的代码：

use std::iter::zip;

fn minimum_length_fold(s: String) -> i32 {
    if s.len() <= 1 {
        return s.len() as i32;
    }

    let result = zip(s.chars().take(s.len() / 2), s.chars().rev().take(s.len() / 2))
        .try_fold(s.len(), |acc, (first_char, last_char)| {
            if first_char == last_char {
                Ok(acc - 2)
            } else {
                // 返回Err提前终止迭代，携带当前长度
                Err(acc)
            }
        });

    // 处理结果：Err则是提前终止的长度，Ok则是遍历完成后的长度
    match result {
        Ok(final_len) => final_len as i32,
        Err(early_len) => early_len as i32,
    }
}

测试验证 #

原测试用例全部可以通过：

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_1() {
        assert_eq!(minimum_length_fold(String::from("ca")), 2)
    }

    #[test]
    fn test_2() {
        assert_eq!(minimum_length_fold(String::from("cabaabac")), 0);
    }

    #[test]
    fn test_3() {
        assert_eq!(minimum_length_fold(String::from("caaaabac")), 4);
    }
}

替代方案：使用scan+状态标记终止迭代 #

如果不想用Result，也可以用scan维护一个状态标记是否需要继续遍历，通过返回None终止迭代：

use std::iter::zip;

fn minimum_length_scan(s: String) -> i32 {
    if s.len() <= 1 {
        return s.len() as i32;
    }

    let mut should_continue = true;
    let len_after_deleting_similar_ends = zip(s.chars().take(s.len() / 2), s.chars().rev().take(s.len() / 2))
        .scan(s.len(), |acc, (first_char, last_char)| {
            if !should_continue {
                return None;
            }
            if first_char == last_char {
                *acc -= 2;
                Some(*acc)
            } else {
                should_continue = false;
                Some(*acc)
            }
        })
        .last()
        .unwrap_or(s.len());

    len_after_deleting_similar_ends as i32
}

内容的提问来源于stack exchange，提问作者Pioneer_11