Is there any beautiful solution to calculate Thue-Morse sequence?

TL;DR, I met a question that I have to extend a vector with data depends on this vector, a simple example is Thue-Morse sequence:

fn main(){
    let mut tms=vec![0u8]
    for _ in 0..10 {
        let tmp=tms.clone(); // is there anyway to avoid this unnecessary clone?
        tms.extend(tmp.iter().map(|&x|1-x))
// I tried unsafe{tms.extend((0..tms.len()).map(|x|1-tms[x]))} directly, but it fails to convince the borrow checker.
    }
    println!("{:?}",tms) // 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0, ...
}

To my best knowledge, I could not avoid this clone.

Is there anyway to avoid this clone?

The easiest way is probably to first double the length of the vector (zero-initializing the new elements), then call split_at_mut which gives you two separate slices that you can then use to compute values for the new elements.

If you want to avoid the unnecessary initializations, then you’ll probably have to use Vec<MaybeUninit> and a bit of unsafe.

You could also do what Vec itself does and reserve enough space for the new elements, use raw pointers to initialize the elems and then cal Vec::set_len().

2 Likes

Just use extend_from_within().

1 Like

split_at_mut seems perfect. Since only we should do is to know the exact length of the element we may append.

Sorry for not seeing such function, but it could not fit my actual problem. In my case, I must deal with some complicated thing like:

            mvbvn(
                lower[i as usize],
                lower[j as usize],
                upper[i as usize],
                upper[j as usize],
                c,
            )
            .max(4.9406564584124654417656879286822137208E-324)
            .ln()-logmvphi[i as usize]-logmvphi[j as usize]

where logmvphi is the calculated vector.

what's more, Shouldn't extend_from_within become a special case of my case? Is there any reason prevent us writting a function like fn extend_within<const N:usize,...>(&mut self,it:Iter<Item=(I,[usize;N])>, f:fn(I,[T;N])->T) which allow us write the following code equivlent to vec.extend_from_within(..)?

vec.extend_within({0..vec.len()}.map(|x|((),[x])),|_:(),item|item)

You should state your actual problem, then. My solution produces the exact same sequence as your original code; asking that and then expecting us to answer a different question is misleading to us and ultimately unhelpful to you.

I don't follow what you are trying to confer with the function signature above. What functionality/behavior are you looking for, i.e., what should that function do precisely?

That function is a part of the computation of a compoment (log)likelihood.

it calculate margainal (log)likelihood firstly, which generates logmvphi, and then, I want to extend the logmvphi vector to store pairwise (log)likelihood, all of the margainal and pairwise likelihood could be used for further computing.

I thought the background is too statistical, thus I provide a simple example to explain why I need such operations. I thought the Thue-Morse sequence might be enough since I didn't recognize the extend_from_within could solve this specific problem perfectly.

Anyway, thanks for your insight.