# 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.