4 ms·

In theory I like this, but it raises the question of how it would work in practice; in practice people create non-sorted lists and then sort them in-place. Mayb

by im3w1l 2y ago

In theory I like this, but it raises the question of how it would work in practice; in practice people create non-sorted lists and then sort them in-place. Maybe you could have the sort method return a sorted-token that certifies that a given array is sorted. And the token would read-only borrow the array, to ensure no one can modify the array as long as the token is valid. Is it even possible for a rust function to take a mutable borrow as a parameter, decay it to an immutable borrow and store that somewhere, such that other people can borrow the parameter after the function has returned?

aw1621107 2y ago
> Is it even possible for a rust function to take a mutable borrow as a parameter, decay it to an immutable borrow and store that somewhere, such that other people can borrow the parameter after the function has returned? I think it's possible under some scenarios with the appropriate lifetimes? For example, https://rust.godbolt.org/z/6fe8c4sf4 https://rust.godbolt.org/z/6fe8c4sf4: struct Magic<'a> { reference: &'a i32 } impl<'a> Magic<'a> { fn new<'b: 'a>(source: &'b mut i32) -> Magic<'a> { Magic { reference: source } } } fn double(i: &i32) -> i32 { i * 2 } fn main() { let mut i = 0; let m = Magic::new(&mut i); double(m.reference); } I think this will stop working once the compiler can no longer see that the lifetimes work out, but I think that makes sense - there's a mutable object underlying the mutable borrow, and the compiler needs to verify that no one else can get another mutable borrow while the derived immutable borrows are live.
- im3w1l 2y ago
  So let's for completenes circle back to the usecase of a certified sorted array, it would be something like this struct Sorted<'a> { reference: &'a [i32] } impl<'a> Sorted<'a> { fn in_place<'b: 'a>(source: &'b mut [i32]) -> Sorted<'a> { source.sort(); Sorted { reference: source } } } fn use_sorted_array(sorted_arr: &Sorted) { let arr = sorted_arr.reference; println!("{} {} {}", arr[0], arr[1], arr[2]); } fn main() { let mut arr = [2, 3, 1]; let sorted_arr = Sorted::in_place(&mut arr); use_sorted_array(&sorted_arr); } You might also want to add methods on Sorted for creating a Option<Sorted> by verifying the sortedness of an immutable reference and a method that copies an array and sorts it (it would need to return a struct of a Box for managing the lifetime and a Sorted pointing into the box, or something I guess, probably need to use Pin?) --- On a completely separate note, this will actually not work for the binary search in the article in question, as it uses binary search on a predicate. Having a sorted array doesn't guarantee that the predicate will be monotonic.

by im3w1l 2y ago

aw1621107 2y ago

> Is it even possible for a rust function to take a mutable borrow as a parameter, decay it to an immutable borrow and store that somewhere, such that other people can borrow the parameter after the function has returned? I think it's possible under some scenarios with the appropriate lifetimes? For example, https://rust.godbolt.org/z/6fe8c4sf4 https://rust.godbolt.org/z/6fe8c4sf4: struct Magic<'a> { reference: &'a i32 } impl<'a> Magic<'a> { fn new<'b: 'a>(source: &'b mut i32) -> Magic<'a> { Magic { reference: source } } } fn double(i: &i32) -> i32 { i * 2 } fn main() { let mut i = 0; let m = Magic::new(&mut i); double(m.reference); } I think this will stop working once the compiler can no longer see that the lifetimes work out, but I think that makes sense - there's a mutable object underlying the mutable borrow, and the compiler needs to verify that no one else can get another mutable borrow while the derived immutable borrows are live.

im3w1l 2y ago
So let's for completenes circle back to the usecase of a certified sorted array, it would be something like this struct Sorted<'a> { reference: &'a [i32] } impl<'a> Sorted<'a> { fn in_place<'b: 'a>(source: &'b mut [i32]) -> Sorted<'a> { source.sort(); Sorted { reference: source } } } fn use_sorted_array(sorted_arr: &Sorted) { let arr = sorted_arr.reference; println!("{} {} {}", arr[0], arr[1], arr[2]); } fn main() { let mut arr = [2, 3, 1]; let sorted_arr = Sorted::in_place(&mut arr); use_sorted_array(&sorted_arr); } You might also want to add methods on Sorted for creating a Option<Sorted> by verifying the sortedness of an immutable reference and a method that copies an array and sorts it (it would need to return a struct of a Box for managing the lifetime and a Sorted pointing into the box, or something I guess, probably need to use Pin?) --- On a completely separate note, this will actually not work for the binary search in the article in question, as it uses binary search on a predicate. Having a sorted array doesn't guarantee that the predicate will be monotonic.