Any possible improvements to this functional program?

The itertools crate has an iterate() method which can be used to generate the Fibonacci sequence in roughly the same way, but in this case the iterator produces tuples, so you have to map them to their first elements:

itertools::iterate((1,1), |&(a,b)| (b, a+b)).map(|p| p.0)

I added this version to @ZiCog's benchmarks:

test tests::amigonico_b ... bench:          76 ns/iter (+/- 9)
test tests::burjui_b    ... bench:          77 ns/iter (+/- 8)
test tests::exphp_b     ... bench:          77 ns/iter (+/- 4)
test tests::itertools_b ... bench:          79 ns/iter (+/- 4)
test tests::jethrogb_b  ... bench:          79 ns/iter (+/- 7)
test tests::marcianx_b  ... bench:          78 ns/iter (+/- 4)
test tests::thor314_b   ... bench:          83 ns/iter (+/- 4)
test tests::zicog1_b    ... bench:          84 ns/iter (+/- 6)
test tests::zicog2_b    ... bench:          78 ns/iter (+/- 4)
1 Like
fn orbit<X,Y>(f: impl Fn(&X)->X, proj: impl Fn(&X)->Y, mut x: X)
-> impl Iterator<Item=Y>
{
    std::iter::repeat_with(move || {x = f(&x); proj(&x)})
}

fn fib() -> impl Iterator<Item=u32> {
    orbit(|&(x,y)| (y,x+y), |&(x,_)| x, (1,1))
}

fn main() {
    let sum: u32 = fib().take_while(|&x| x < 4000000)
        .filter(|x| x % 2 == 0).sum();
    println!("{}",sum);
}

I had to read this a couple times to understand what was going on, but then it clicked, I think it's brilliant. Coming from [other?] functional languages, I would have used a higher-order function to capture state, but this is much simpler and clearer. I guess I just need to get used to using code blocks as expressions!

2 Likes

If anyone is interested in pursuing tests and benchmarks further, I added an "iterators" branch to this repo that cleanly tests/benches four styles of iterators against two sequences:

fib: 1 1 2 3 5 8 13 ...
n_ns: 1 2 2 3 3 3 4 4 4 4 ...

The results are pretty close across all of them, e.g.

test tests::byhand_fib_b   ... bench:          22 ns/iter (+/- 1)
test tests::byhand_n_ns_b  ... bench:       1,037 ns/iter (+/- 70)
test tests::iterate_fib_b  ... bench:          22 ns/iter (+/- 1)
test tests::iterate_n_ns_b ... bench:       1,018 ns/iter (+/- 75)
test tests::iterize_fib_b  ... bench:          22 ns/iter (+/- 1)
test tests::iterize_n_ns_b ... bench:       1,007 ns/iter (+/- 57)
test tests::tuple_fib_b    ... bench:          23 ns/iter (+/- 2)
test tests::tuple_n_ns_b   ... bench:       1,031 ns/iter (+/- 62)

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.