Rust 迭代 fold 概述 - 條件累加

Rust 迭代 fold 概述 - 條件累加

  11月 03, 2023    LaGee

---

fold

先看看文件[1]

文件寫到將每個元素放到累加器中，並返回結果

fn fold<B, F>(self, init: B, f: F) -> B

    where

        F: FnMut(B, Self::Item) -> B,

self是一個迭代器

init為初始值

f為一個閉包，裡面需要兩個元素，累積值B和自身元素Self::Item

例子

fold允許在每次迭代時將數值累加，並且傳到下一次迭代

常用於求累加值、最大值、字符拼接等任務

看一個簡單的例子

假設有一數組1,2,3,4,5，要求和可以利用fold

    let numbers = vec![1, 2, 3, 4, 5];

    let sum = numbers.iter().fold(0, |acc, &x| acc + x);

    println!("Sum: {}", sum);

第一行為一1到5數組

第二行先將數組透過iter放入迭代器中，並透過fold做相加，可看表1

表1. fold內部運作情況

第一行為第幾個元素，第二行為acc累加值，第三行為元素值，最後則是結果

第三行則是輸出

透過fold可以做累加的功能

另一個例子

這邊有個有趣的題目

做Codewar[2]題目刷到的

以下是原文

Given an array of ones and zeroes, convert the equivalent binary value to an integer.

Eg: [0, 0, 0, 1] is treated as 0001 which is the binary representation of 1.

Examples:

Testing: [0, 0, 0, 1] ==> 1

Testing: [0, 0, 1, 0] ==> 2

Testing: [0, 1, 0, 1] ==> 5

Testing: [1, 0, 0, 1] ==> 9

Testing: [0, 0, 1, 0] ==> 2

Testing: [0, 1, 1, 0] ==> 6

Testing: [1, 1, 1, 1] ==> 15

Testing: [1, 0, 1, 1] ==> 11

However, the arrays can have varying lengths, not just limited to 4.

給予一個只包含1和0的陣列，將二進制轉換成整數

例如0001轉換成1，永遠只會有四碼

fn binary_slice_to_number(slice: &[u32]) -> u32 {

    // your code here

}

解題思路

這題目有很多種作法

我預計以第一位元乘上2的0次方、第二位元乘上2的1次方、第三位元乘上2的2次方...以此類推

因此分享一種結合fold和enumerate的打法

    slice

        .iter()

        .rev()

        .enumerate()

        .fold(0, |res, (num, v)| res + 2_u32.pow(num as u32) * v)

第二行將slice放入迭代器

第三行需將其反轉，因為輸入是從最大位元輸入，我需要從最小位元開始處理

第四行透過enumerate，返回(id, val)，id為0, 1, 2, 3，val則是返回slice數值

第五行透過fold，將每個位元乘上2的n次方，並加起來

最後做測試

    assert_eq!(binary_slice_to_number(&vec![0,0,0,1]), 1);

    assert_eq!(binary_slice_to_number(&vec![0,0,1,0]), 2);

    assert_eq!(binary_slice_to_number(&vec![1,1,1,1]), 15);

    assert_eq!(binary_slice_to_number(&vec![0,1,1,0]), 6);

與預期結果相同

表2以最後一個0110當作範例

表2 0110範例

參考資料

[1] https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.fold

[2] https://www.codewars.com/kata/578553c3a1b8d5c40300037c