How to make integer array by a recurrence relation

help
1

How to generate Vec<u32> with a recurrence relation like a[n]=3a[n-1]+1, a[0] = 1 bounded by 1000?
Following code does but is there any better way? (does it use fold or something?)

let mut v = vec![];
let mut next = 1;
let f = |x: u32| x * 3 + 1;
loop {
    if next > 1000 {
        break;
    }
    v.push(next);
    next = f(next);
}
// v = [1, 4, 13, 40, 121, 364]

cf. Haskell:

takeWhile (<= 1000) $ iterate (\x -> x*3 + 1) 1

Thanks.

2

There are a couple ways. You can use a normal for loop similar to what you've already done. Otherwise you can even create your own iterator and build on top of all the really powerful iterator combinators.

I'm on my phone at the moment, but the most idiomatic solution would look somewhat like this.

3

Here is how you might define iterate if this comes up frequently for you. Playground

let v = iterate(1, |x| x * 3 + 1).take_while(|x| *x < 1000);
4

I wouldn't be surprised if something like that was available in the itertools crate.

EDIT: lol, turns out it already exists!

1 Like
5

I noticed both your iterate implementation and itertools' implementation use mem::replace. Why is that?

6

I believe it's just because mem::replace() skips the need to introduce an intermediate variable when swapping in the next element.

7

if you want to use kind of functional style, using a sequence with head and tail, please check the crate "seq" https://crates.io/crates/seq
Seq allows you to grow the sequence on Stack while performing recursive function calls.

8

I choose itertools crate which is just I want, but thank you everyone for shareing your knowledge!