Problems with fold in Rust

Question

Let's assume fn scan(int, int) -> int.

When using

fn count(x: int, y: int) -> int
{
    scan(x - 1, y - 1) + scan(x - 1, y) + scan(x - 1, y + 1) + scan(x, y - 1)
        + scan(x, y + 1) + scan(x + 1, y - 1) + scan(x + 1, y) + scan(x + 1, y + 1)
}

I get correct results. I am trying to get the same results by folding the scan function over the given value ranges; however, I can't seem to get it right. My current attempt is

fn count_fold(x: int, y: int) -> int
{
    std::iter::range_inclusive(-1, 1).zip(std::iter::range_inclusive(-1, 1)).fold(0, |a, (i, j)| { a + scan(x + i, y + j) })
}

which seems to return only a subset of the correct results. What am I doing wrong? TIA.

Answer 1

When you zip two iterators, you are not creating the "product" of the iterations, like you seem to be wanting to do. Rather, you are iterating both iterators at the same time and creating a pair with the iterated values. So in the count_fold version, the closure will only be called with the following pairs:

(-1, -1)
(0, 0)
(1, 1)

So your count_fold function is actually akin to

scan(x - 1, y - 1) + scan(x, y) + scan(x - 1, y + 1)

I can be wrong, but I don't think there is a function in std that create the product of two iterators.

Moreover, your count method do not use scan(x, y) in the sum, so it is not even really the product of the iterators; you have to be careful about that if you want to create your own product iterator and use it for that purpose.

Answer 2

Cyrille is correct in saying there is no iterator-product function. However, one can manually take the product of the two iterators by folding twice:

use std::iter::range_inclusive;

fn count_fold(x: int, y: int) -> int {
    range_inclusive(-1, 1).fold(0, 
         |a, i| range_inclusive(-1, 1).fold(a, |b, j| b + scan(x + i, y + j)))
}

Although it looks like you'll need to filter the case when i == 0 && j == 0, i.e.

fn count_fold(x: int, y: int) -> int {
    range_inclusive(-1, 1).fold(0, 
         |a, i| range_inclusive(-1, 1).fold(a, 
             |b, j| if i == 0 && j == 0 {b} else {b + scan(x + i, y + j)}))
}

or

fn count_fold(x: int, y: int) -> int {
    range_inclusive(-1, 1).fold(0, 
         |a, i| range_inclusive(-1, 1)
             .filter(|&j| !(i == 0 && j == 0))
             .fold(a, |b, j| b + scan(x + i, y + j)))
}

However, I'd almost say that this is clearer imperatively:

fn count_fold(x: int, y: int) -> int {
    let mut a = 0;
    for i in range_inclusive(-1, 1) {
        for j in range_inclusive(-1, 1) {
            if !(i == 0 && j == 0) { a += scan(x + i, y + j) }
        }
    }
    a
}