Hi, I'll try to be brief. I'm trying to write a function that, in a simplified form, resembles the following code, and I'm getting an error. Could anyone please advise how I could change it to achieve successful compilation?
I don't know the fix, but the problem (I believe) is that you're calling process with a slice of &T, which recursively calls process with a slice of &&T, and so on.
Thanks for the answer. I'm already understand where the problem is. The point is that I can't figure out how to avoid this. I'm thinking first of all about changing the signature of the recursive function, because... It seems that I cannot avoid the recursive call itself.
Even if the type error can be resolved, this function will never terminate— If the input length is greater than 4, you’re always recursing on a list of the same length, so none of the invocations will ever be able to proceed beyond that point.
Without a description of what outcome you want from this function, there’s not much advice to be given until this is resolved¹. Fixing this logic error first will probably help with figuring out a solution to the type error if it doesn’t resolve itself during the refactoring process.
¹ Except for the useless advice that this is logically equivalent without recursion:
fn process<T: Clone>(a: &[T]) -> Vec<T> { // I have even more constraints here
match a.len() {
0 => panic!("empty slice"),
l if l <= 4 => {
// Pick 2 random elements
a.iter().cloned()
.choose_multiple(&mut thread_rng(), 2)
}
_ => { loop {} }
}
}
The real function is fine. I made a mistake or several when I tried to simplify it in order to post the question. The point is not that the function doesn't bottom out, but that type resolving doesn't.
Once again: you are right that the internal part of the function in the branching part is bad, but that is not what is causing the error at the moment. What you're talking about works as expected.
I would like to thank everyone who took part in this issue.
I think I'll try to solve my problem myself, and maybe post the solution where I came up for reference. Because I don’t see a way to delete the post, I’ll mark as a solution the suggestion that I tried to use but so far without success.
Thanks again, I feel there are too many nuances in this question that I missed and I apologize.
The problem I’m having is that the minimization errors are inhibiting my ability to provide meaningful advice because I can’t understand what you’re trying to achieve. Any fix will involve changing something about the problematic recursive call, and I can’t change that without knowing what the semantic meaning of the recursive call is supposed to be— If I make a guess, it will probably be wrong and make the proposed solution inapplicable to your real application.
Yes, I understand what you are talking about and absolutely agree with you. I will close the question due to its inconsistency and try to come to a solution on my own. Thank you for taking the time to let me know that I should be more specific in communicating the semantic of what I'm trying to do within the code. Unfortunately, I am currently unable to move the question description forward in this direction.
I'm trying to follow your advice. I think you are pointing me in the right direction. Could you please clarify how I can convert [*const _] and to what. Please write the return type you mean and how I can use the as conversion.
I think the simplest solution is to just separate it into two functions:
fn process<T: Clone>(a: &[T]) -> Vec<T> {
process_inner(&a.iter().collect::<Vec<_>>())
.into_iter()
.cloned()
.collect()
}
fn process_inner<'a, T>(a: &[&'a T]) -> Vec<&'a T> {
match a.len() {
0 => panic!("empty slice"),
1..=4 => {
// Pick 2 random elements
a.iter().copied().choose_multiple(&mut thread_rng(), 2)
}
_ => {
// Construct "array of addreses"
let mut ar = a.to_vec();
let r = process_inner(&ar);
// Exclude already picked elements
ar.retain(|&e1| {
r.iter().all(|&e2|
// Since elements in `v` may repeat
// in sence of Eq, I want to compare
// by address
e1 as *const _ != e2 as *const _)
});
// Process retained elements
process_inner(&ar)
}
}
}
Otherwise, you can take an iterator instead.
fn process<'a, I, T>(a: I) -> Vec<T>
where
I: IntoIterator<IntoIter: ExactSizeIterator, Item = &'a T>,
T: Clone + 'a,
{
let a = a.into_iter();
match a.len() {
0 => panic!("empty slice"),
1..=4 => {
// Pick 2 random elements
a.cloned().choose_multiple(&mut thread_rng(), 2)
}
_ => {
// Construct "array of addreses"
let mut ar: Vec<_> = a.collect();
let r = process(ar.iter().copied());
// Exclude already picked elements
ar.retain(|&e1| {
r.iter().all(|e2|
// Since elements in `v` may repeat
// in sence of Eq, I want to compare
// by address
e1 as *const _ != e2 as *const _)
});
// Process retained elements
process(ar)
}
}
}
The first option you suggest is exactly what I used to solve the problem. It took me 4 hours to get this solution.
I really like the proposed iterator approach, but unfortunately it didn't work. The variable ar contains a vector of T, not a vector of &T, unless you explicitly ask to collect it as Vec<&T>.
Then, when you recursively call process() for the first time, the vector returned from it also contains (copied) elements, not references to original elements. Accordingly, .retain() compares addresses of original elements with copied ones; this does not allow filtering them out correctly.
I tried to explicitly ask to put in a reference to ar with Vec<&T> and got the same error as in the OP. In any case, the first solution works and I would stick with it.
I am very pleased that you took the time to read my post and help. I noted how you silently replaced the guard with a pattern matching, it looks very elegant, but it didn't work in my situation because 4 in my case is a variable that cannot be used in a pattern. Of course, you couldn’t know about this, and I’ll take note that I can supply the interval instead of comparing with some constant.
Ah, yeah that makes sense. It also makes it more clear that there needs to be two functions. A common problem in Rust is wanting to be able to flatten any &&&&...&T into &T, but this is not currently possible. You could make this work for some specific type, but not generically.
Glad you're continuing the conversation. It's a very interesting note that this is a relatively common problem. I stopped feeling so alone and silly with my question. Thank you very much.
I changed the description of the problem in such a way that now it does not contain shortcomings that the @2e71828 was talking about. Those the only problem is the unbounded recursion when defining the type.
Here is the code that, according to the new description, gives the correct solution, as well as code using the iterator approach, which unfortunately does not work, as I indicated above.
fn process<'a, I, T>(a: I, h: usize) -> Vec<T>
where
I: IntoIterator<IntoIter: ExactSizeIterator<Item=&'a T>, Item=&'a T>,
T: Clone + 'a
{
let a = a.into_iter();
if h <= 2 {
// Pick `h` random elements
a.cloned().choose_multiple(&mut thread_rng(), h)
} else {
let mut a: Vec<_> = a.collect();
let mut r1 = process(a.clone(), h / 2);
// Exclude already picked elements
a.retain(|&e1|
r1.iter().all(|e2| e1 as *const _ != e2 as *const _)
);
let mut r2 = process(a, h - h/2);
r1.append(&mut r2);
r1
}
}
I must say that your help is no longer needed, but you have made a great contribution in confirming my suspicions and @drewtato has provided a specific solution that seems to agree with your tip.
I have changed the description of the question to avoid the shortcomings that others have pointed out to me. You can see the final solution in my answer. Thanks for your time.
Replying to myself I must note that using &[*const T] approach seems not possible without unsafe. The following is the solution I wrote earlier with @user16251 suggestion but later I found out that I can change &[*const T] to &[&T] and keep the same effect.
Solution using raw pointers and unsafe code (don't use it, see other comments)
fn process1<T: Clone>(a: &[T], h: usize) -> Vec<T> {
let a: Vec<_> = a.iter().map(|e| e as *const T).collect();
fn inner<T: Clone>(a: &[*const T], h: usize) -> Vec<*const T> {
if h <= 2 {
// Pick `h` random elements
a.iter().cloned()
.choose_multiple(&mut thread_rng(), h)
} else {
let mut r1 = inner(a, h/2);
// Exclude already picked elements
let b: Vec<_> = a.iter().cloned().filter(|e1|
r1.iter().all(|e2| e1 != e2)
).collect();
let mut r2 = inner(&b, h - h/2);
r1.append(&mut r2);
r1
}
}
inner(&a, h).into_iter().map(
|e| unsafe{e.as_ref().unwrap()}.clone()
).collect()
}
Sorry to continue to bother you. After some time, I suddenly noticed an interesting thing. The error message reads: error: could not compile<...>. However, if I comment out a call to the function in question, the compilation will be successful.
I wouldn't want to get into the weeds of how this is evaluated, I just thought it was unusual that some parts are processed "lazy". Out of ignorance, it seemed to me that inference and type checking are "forced", but it seems that this is not the case.
I also recall that earlier with this function a encounter E0275"An evaluation of a trait requirement overflowed", but I can't reproduce this behavior now. The error message looked something like this:
error[E0275]: overflow evaluating the requirement `<type>: <constraints>`
|
= help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`rust_out`)
= note: required for `<type>` to implement `<constraints>`
= note: 128 redundant requirements hidden
= note: required for `&&&&&&&&...` to implement `<constraints>`
= note: the full name for the type has been written to '/tmp/**/*.txt'
= note: consider using `--verbose` to print the full type name to the console
I guess this is due to the fact that generic function can be fully type-checked only on instantiation - e.g. compiler must be sure that the actual types provided for generics meet all necessary bounds.
Indeed, this is actually a property which Rust tries to have as much as possible, so that you can write generic code and not be surprised later that it doesn’t work.
That's what I mean when I say I don't want to dig deeper. "Instantiation" seems to me to be an internal process carried out during some compilation stage, and I don’t know what it is and I’m afraid it will remain beyond my capabilities for a long time. On some very abstract level I understand what you are talking about. I don't think I can go further than this level of understanding and that's enough for now. I don’t want to guess about internal machinery, but your the remark is still useful.
I guess I would prefer not to have to deal with this problem, that's what the @drewtato is talking about here. But at the moment I am very glad that despite the fact that I encounter problems from time to time, what the language cannot solve at the moment, the community helps me to solve it instead here. After all, sometimes I'll try to implement a construct that I've seen in another language and think would work (like the recursion in this post), but which may fail because it's not a typical nor encouraged use case.