Any possible improvements to this functional program?

On the bright side, being of a practical bent, I have all the solutions suggested in this thread run under "cargo bench".

Interestingly they all come in at about the same speed on my x86 PC:

test tests::burjui_b   ... bench:          91 ns/iter (+/- 2)
test tests::exphp_b    ... bench:          92 ns/iter (+/- 5)
test tests::jethrogb_b ... bench:          88 ns/iter (+/- 2)
test tests::marcianx_b ... bench:          93 ns/iter (+/- 4)
test tests::thor314_b  ... bench:         112 ns/iter (+/- 5)
test tests::zicog1_b   ... bench:         114 ns/iter (+/- 4)
test tests::zicog2_b   ... bench:          93 ns/iter (+/- 4)

Seems jethogb comes in the winner here. With that danm mem::replace thing :slight_smile:

There are a couple of functional solutions that loose badly. But otherwise they beat my imperative loop.

1 Like

One thing to consider (which I feel is often misunderstood) is that abstractions are not their to prevent you from having to learn the underlying details. Variables have to be mapped to memory addresses (or registers), but because the address is arbitrary, we prefer to refer to them by name instead, which abstracts over the address. But you are still advantaged to know that the underlying model is that of a memory address. So the purpose of the abstraction is to allow you to go farther with less knowledge, by allowing you to focus on the most relevant information. It is not to allow you to go on with no knowledge.

I do feel ones code should be readable by as many as possible without putting that wall of symbology and abstraction between them and what your code actually does.

Code becomes less readable when you include noise. By learning good abstractions, you learn what is noise and what is not. Of course if you lack the background to tell the difference, and everything looks like signal to you, then the abstraction will simply look like it is hiding information.

The symbology of calculus hides those sums and differences because those things are not necessary for calculus to work. They're simply one (arbitrary) way to apply that structure, just like a specific set of memory addresses are just one arbitrary way to store variables.

2 Likes

You have possibly said something profound there that I have not understood or not seen before. Despite years of studying maths in school and university.

The calculus that I know of uses symbols like dy/dx and that big integral sign, ∫. It very clearly speaks of differences and sums. It's there in the very names, Integral and Differential Calculus.

The wonder of differential calculus is that, in the limit, it reduces those differences to zero and produces a meaningful result for what would otherwise be 0/0. Magic!

Is there another way of thinking about calculus we should be aware of?

Yes, Exactly what I have been saying all along.

For the problem as stated in this thread I can almost be sure there would be less "noise" in the solution if I wrote it in assembly language. Let me work on that ....

There are plenty of ways to think of calculus without ever using limits. The idea is to create an abstract language that obeys the foundational rules (exponent, quotient, product, and chain rules, etc.) (Incidentally, this technique is also how we define exponentiation on real numbers, which you're probably more familiar with.) Analogously, you can define a programming language's semantics without ever referencing memory addresses, by highlighting the relationships between the language's structures.

Functional languages tend to define primitives that allow abstracting over variables (pipelines) or function arguments (point-free style,) and those languages can be given clear semantics without referencing the underlying machinery of addresses, indexes, or even statement order. This is very useful if you're modelling problems that look like pipelines (such as in this thread) or express declarative relationships, such as parsers.

2 Likes

I've been learning from this thread and playing with the code. Here's a version that abstracts out an "iterize" function that makes such Iterators for you.

fn main() {
    dbg!(fib().take(6).collect::<Vec<i32>>());
}

// Returns an Iterator for the Fibonacci sequence: 1 1 2 3 5 8 ...
fn fib() -> impl Iterator<Item = i32> {
    iterize((1,1), |(a,b)| (b, a+b))
}

// Produces an Iterator by induction.
// Given an initial state of type (R,S) and a function that produces
// the next state from an existing state, return an Iterator for the Rs.
// So in (R,S), R is the part that gets (R)eturned by the Iterator,
// and S is any additional (S)tate used internally.
fn iterize<R: Copy, S: Copy>(s0: (R,S), f: impl Fn((R,S)) -> (R,S)) -> impl Iterator<Item = R> {
    let mut state = s0;
    std::iter::repeat_with(
        move || { state.swap(f(state)).0 }
    )
}

// a.swap(b) sets a to b and returns the old value of a.
pub trait Swap: Sized {
    fn swap(&mut self, value: Self) -> Self;
}
impl<T> Swap for T {
    fn swap(&mut self, new: Self) -> Self {
        std::mem::replace(self, new)
    }
}

I don't know how well it benches.

This is long, of course, but in addition to fib() it offers two abstractions (a.swap(b) and iterize()) which are hopefully useful in other situations.

I think R and S need to be Copy for std::mem::replace.

Credit to KrishnaSannasi for the Swap trait, which cleans up the replace:

1 Like

Bind blowing.

I really don't want to bash on your code or Rust or anything.

I'm just wondering if I will ever live long enough to have that not look like line noise. Seems more an more unlikely...

I know what you mean. It's so easy to understand the use of it:

iterize((1,1), |(a,b)| (b, a+b))

but the function signature is just awful!

I'm not sure about that. I have no idea what the intention is there.

I'm wondering why there are tuples in there. Why not an array?

Oh, sorry -- I've been looking at it for so long....

It's basically induction. You provide an initial state s0 and a rule that produces s(n+1) from s(n).

The state, (R,S), is in two parts -- the part you want the iterator to (R)eturn, and any additional (S)tate. In this case (1,1) is just the first two numbers in the Fibonacci sequence.

What is returned by iterize() is an iterator over the R values.

So as you iterate, the state is getting modified like this:

(1,1) [the initial state]
(1,2) and the iterator produces 1
(2,3) and the iterator produces 1
(3,5) and the iterator produces 2
(5,8) and the iterator produces 3

R and S are both i32 here, but you could have an iterator that needed to keep around additional state.

As Alice pointed out (in another thread), the fact that R and S must be Copy is limiting, but it still covers a lot of simple cases. You could make a similar facility using Clone, but because std::mem::replace seemed to perform especially well in your benchmarks I wanted to stick with that.

iterize would be more intelligible if the above three comments were included as a prefix to its definition:

Without that explanation, R and S were no more intelligible to me than would have been left and right.

Thanks for the feedback. I modified the comments in the code of that earlier post.

1 Like

Would you mind sharing your benchmark setup?

Who me?

OK, I put all the codes we have in this thread into a repo here: https://github.com/ZiCog/rust_functional_fibo.git

The various functions are named after the forum user that posted them.

Test methods have a "_t" appended. The benches have an "_b".

However I did take the liberty of changing the codes to use u64 to stretch out the execution time a little bit.

2 Likes

Much appreciated.

Oddly, the iterize() version comes out to be slightly more efficient than all the rest, every time I run it. I don't know why; I was expecting it to be exactly the same as jethrogb's version, but it seems to be 1 or 2 ns/iter faster than the next best contender every time.

For example:

test tests::amigonico_b ... bench:          76 ns/iter (+/- 3)
test tests::burjui_b    ... bench:          78 ns/iter (+/- 11)
test tests::exphp_b     ... bench:          78 ns/iter (+/- 5)
test tests::jethrogb_b  ... bench:          78 ns/iter (+/- 3)
test tests::marcianx_b  ... bench:          78 ns/iter (+/- 4)
test tests::thor314_b   ... bench:          90 ns/iter (+/- 4)
test tests::zicog1_b    ... bench:          85 ns/iter (+/- 5)
test tests::zicog2_b    ... bench:          78 ns/iter (+/- 4)

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.