iterator,rust,immutability,lifetime , How to compose mutable Iterators?


How to compose mutable Iterators?

Question:

Tag: iterator,rust,immutability,lifetime

I would like to make an iterator that generates a stream of prime numbers. My general thought process was to wrap an iterator with successive filters so for example you start with

let mut n = (2..N)

Then for each prime number you mutate the iterator and add on a filter

let p1 = n.next()
n = n.filter(|&x| x%p1 !=0) 
let p2 = n.next()
n = n.filter(|&x| x%p2 !=0) 

I am trying to use the following code, but I can not seem to get it to work

struct Primes {
    base: Iterator<Item = u64>,
}

impl<'a> Iterator for Primes<'a> {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let p = self.base.next();
        match p {
            Some(n) => {
                let prime = n.clone();
                let step = self.base.filter(move |&: &x| {x%prime!=0});
                self.base = &step as &Iterator<Item = u64>;
                Some(n)                
            },
            _ => None
        }        
    }
}

I have toyed with variations of this, but I can't seem to get lifetimes and types to match up. Right now the compiler is telling me

  1. I can't mutate self.base
  2. the variable prime doesn't live long enough

Here is the error I am getting

solution.rs:16:17: 16:26 error: cannot borrow immutable borrowed content `*self.base` as mutable
solution.rs:16         let p = self.base.next();
                                                     ^~~~~~~~~
solution.rs:20:28: 20:37 error: cannot borrow immutable borrowed content `*self.base` as mutable
solution.rs:20                 let step = self.base.filter(move |&: &x| {x%prime!=0});
                                                                ^~~~~~~~~
solution.rs:21:30: 21:34 error: `step` does not live long enough
solution.rs:21                 self.base = &step as &Iterator<Item = u64>;
                                                                  ^~~~
solution.rs:15:39: 26:6 note: reference must be valid for the lifetime 'a as defined on the block at 15:38...
solution.rs:15     fn next(&mut self) -> Option<u64> {
solution.rs:16         let p = self.base.next();
solution.rs:17         match p {
solution.rs:18             Some(n) => {
solution.rs:19                 let prime = n.clone();
solution.rs:20                 let step = self.base.filter(move |&: &x| {x%prime!=0});
                                     ...
solution.rs:20:71: 23:14 note: ...but borrowed value is only valid for the block suffix following statement 1 at 20:70
solution.rs:20                 let step = self.base.filter(move |&: &x| {x%prime!=0});
solution.rs:21                 self.base = &step as &Iterator<Item = u64>;
solution.rs:22                 Some(n)                
solution.rs:23             },
error: aborting due to 3 previous errors

Why won't Rust let me do this?


Answer:

Here is a working version:

struct Primes<'a> {
    base: Option<Box<Iterator<Item=u64>+'a>>,
}

impl<'a> Iterator for Primes<'a> {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let p = self.base.as_mut().unwrap().next();
        p.map(|n| {
            let base = self.base.take();
            let step = base.unwrap().filter(move |x| x % n != 0);
            self.base = Some(Box::new(step));
            n                
        })
    }
}

impl<'a> Primes<'a> {
    #[inline]
    pub fn new<I: Iterator<Item=u64>+'a>(r: I) -> Primes<'a> {
        Primes {
            base: Some(Box::new(r))
        }
    }
}

fn main() {
    for p in Primes::new(2..).take(32) {
        print!("{} ", p);
    }
    println!("");
}

First, I'm using Box<Iterator> trait object. Boxing is unavoidable because the internal iterator must be stored somewhere between next() calls, and with reference trait objects there is nowhere you can store it.

Second, I made internal iterator an Option. This is necessary because you need to replace it with a value which consumes it, so it is possible that the internal iterator may be "absent" from the structure for a short time. Rust models absence with Option. take() method on Option replaces the value it is called on with None and returns whatever was there. This is useful when shuffling non-copyable objects around.

Note, however, that this sieve implementation is going to be both memory and computationally inefficient - for each prime you're creating an additional layer of iterators which takes heap space. Also the depth of stack when calling next() grows linearly with the number of primes, so you will get a stack overflow on a sufficiently large number:

fn main() {
    println!("{}", Primes::new(2..).nth(10000).unwrap());
}

Running it:

% ./test1 

thread '<main>' has overflowed its stack
zsh: illegal hardware instruction (core dumped)  ./test1

Related:


Cannot infer appropriate lifetime for autoderef in Iterator impl


rust
I am trying to implement the Iterator trait for a struct which basically just acts as a borrower of an array of i32 values. However, I keep running into the compiler complaining about not being able to infer a lifetime inside the next method. I am aware of this answer,...

“conflicting implementations for trait” when trying to be generic


types,rust
Background: I'm using the nalgebra library and I want to create a structure that represents a multivariate normal distribution. M is the type of the matrix, e.g. Mat4<f64>. My current attempt looks like this: use std::ops::Mul; use std::marker::PhantomData; use nalgebra::*; #[allow(non_snake_case)] pub struct Multivar𝒩<N, V, M: SquareMat<N, V>> { μ:...

Conditionally compile only one module at a time


rust
Sometimes while refactoring a change in one of the modules has impact on every other module (or many others), because say a type has been changed or a function parameter has been changed etc. In this case instead of changing everything and then compiling at once is there a way...

Can I create a macro that unrolls loops?


macros,rust
I'm trying to write some fast matrix code in Rust and to do this needs to ensure that loops are unrolled. Is there a way to create a compile-time for-loop? E.g: I want unroll_loop!(f, a, 3); to generate f(a, 0); f(a, 1); f(a, 2); ...

Can Rust handle cyclic data structures without any garbage collector?


rust
Is it possible to completely avoid a garbage collector and manual deallocation? Is it possible to implement an interpreter for a language that needs garbage collection (say, Scheme) in Rust, without implementing or using any garbage collector? ...

Rust: Lifetime of String from file [duplicate]


file,io,rust
This question already has an answer here: Return local String as slice 1 answer I'm trying to read in some external GLSL code into Rust. The reading works properly, but I run into a lifetime issue in the final expression (in the Ok(_) branch) error: s does not live...

cannot move out of borrowed content - ref doesn't work [duplicate]


rust
This question already has an answer here: “cannot move out of borrowed context” and “use of moved value” 1 answer I have this code: enum MyEnum1 { val1, val2 } struct Struct1 { field1: MyEnum1, field2: String } fn fn1(a: Struct1, b: String, c: String) { let let1 =...

Result has no method called “unwrap()”?


rust
What a strange error: let res1 = get_res(); assert!(res1.is_ok()); assert_eq!("just for test", res1.unwrap()); //error The error is: type `core::result::Result<(MyStruct1, collections::btree::map::BTreeMap<collections::string::String, collections::string::String>), Error>` does not implement any method in scope named `unwrap` ...

Why do I need to use self::core::ops?


rust
I'm trying to use Mul from core. This is suggested by the compiler and works: extern crate core; use self::core::ops::Mul; but why doesn't extern crate core; use core::ops::Mul; work? I get the error error: unresolved import `core::ops::Mul`. Did you mean `self::core::ops`?...

Iterator for an array list of Class


java,collections,iterator,listiterator
Am New to Java so please bear with me if my question seems to be silly. I am learning collections,I have written a program which will store student names id and marks.I am storing all these in a Arraylist. Using for loop I am able to print the values in...

Multimap Iterator retrieve multiple values in Java [closed]


java,iterator,multimap
Is there a way to access each value to assign it to a variable from a java MultiValueMap from Apache commons while iterating? I have one key and two possible values that I would like to extract each iteration that are later written to a table. Currently the below produces...

Iterate through a specific directory tree and store all the .ttf files into an array in PHP


php,loops,iterator,directory,iteration
Lets say I have a lot of files, some of those are in these paths: root/fonts/folder1/font1.ttf root/fonts/folder1/font2.ttf root/fonts/folder2/font1.ttf root/fonts/folder2/font2.ttf root/scripts/file.php Remember that there are also other types of files in those folders. How can my "/scripts/file.php" iterate through the "../fonts/" directory tree and store all the TrueType font (.ttf) files...

What is the idiomatic way to write a linked list with a tail pointer?


linked-list,rust,reference-counting
As a learning project for Rust, I have a very simple (working, if incomplete) implementation of a singly linked list. The declaration of the structs looks like this: type NodePtr<T> = Option<Box<Node<T>>>; struct Node<T> { data: T, next: NodePtr<T>, } pub struct LinkedList<T> { head: NodePtr<T>, } Implementing size and...

Return a moving window of elements resulting from an iterator of Vec


iterator,rust
I'm trying to figure out how to return a window of elements from a vector that I've first filtered without copying it to a new vector. So this is the naive approach which works fine but I think will end up allocating a new vector from line 5 which I...

Concurrent modification exception when using iterator? (Java)


java,debugging,arraylist,iterator
I am trying to write code for the simulation WaTor in which sharks and fish eat each other and simulate population control etc. Anyways, the problem I am having is that i keep getting a concurrect modification exception even when using an iterator. Here is my code: private void updateSharks()...

Filter vector in place


iterator,rust
In Rust is it possible to operate on a vector in-place? I'd like to remove some elements from a Vec, but vec.iter().filter().collect() creates a new vector with borrowed items. I'd like to mutate the original Vec without extra memory allocation (and keep memory of removed elements as an extra capacity...

Implementing a generic conversion from an object implementing the `Error` trait


rust
I cannot get the following code to compile. I get an error that From is already implemented. If I remove the manual impl of From I get the error that From is not implemented. If I do not implement Error it works fine. I suppose that this is due to...

iterating over a table passed as an argument to a function in lua


for-loop,lua,iterator,lua-table
I am trying using the for _ in pairs() notation to iterate over a table within a function, but if I type anything, even gibberish like print('asdgfafs'), nested inside the for loop, it never gets printed. Code: record = {bid1,bid2,bid3} bid1 = {bidTime = 0.05,bidType = 'native'} bid2 = {bidTime...

Implement Debug trait for large array type


rust,traits
I gather that Rust provides Debug impl's for arrays size 32 and smaller. I also gather that I could implement Debug on a larger array by simply using write! with a very long format specifier. But I'm wondering if there's a better way. What is the recommended method for implementing...

vector method push_all is not found for a custom struct


rust
So in this simple example #![feature(collections)] struct User { reference: String, email: String } fn main() { let rows = vec![ vec!["abcd".to_string(), "[email protected]".to_string()], vec!["efgh".to_string(), "[email protected]".to_string()], vec!["wfee".to_string(), "[email protected]".to_string()], vec!["rrgr".to_string(), "[email protected]".to_string()] ]; let mut rows_mut: Vec<Vec<String>> = Vec::new(); rows_mut.push_all(&rows); let mut users_mut: Vec<User> = Vec::new(); let users = vec![ User { reference:...

Create shared C object linked to Rust dylib for use in R


c++,c,r,rust,ffi
I am trying to create a shared object I can load into R that calls Rust functions by way of R's C API. To call Rust from C, I am following this blog post. My problem arises when I try to create the shared library and link to the Rust...

Lifetime of a mutable element in struct


rust
How can I define a mutable element in a struct? If I have a following example struct User<'a> { reference: String, email: String, addresses: &'a mut Vec<Address> } struct Address { street: String, city: String } fn main() { let mut users = Vec::new(); users.push(User { reference: "ref".to_string(), email: "[email protected]".to_string(),...

How can I send a function to another thread?


multithreading,unit-testing,rust
I am attempting to write a simpler unit test runner for my Rust project. I have created a TestFixture trait that my test fixture structs will implement, similar to inheriting from the unit test base class in other testing frameworks. The trait is fairly simple. This is my test fixture...

How to use multiple variables in routes with Nickel?


rust,nickel
Nickel states that you can use variables in the URLs, which sounds very useful, but is it possible to use multiple variables? Something like: www.example.com/login/:userid?:apikey?:etc server.get("/start/:userid?:passwd", middleware! { |request| // format!("This is user: {:?} = {:?}", // request.param("userid"), // request.param("passwd") // ); }); ...

Passing iterator's element to a function: wrong type of pointer


c++,pointers,stl,iterator
I'm attempting to solve Project Euler's problem #3 using C++ to gain an understanding of how to use C++ iterators. According to the examples I've seen online, I can use the dereferened iterator as a parameter for cout, and it will print the elements successfully. By that same logic, I...

Writing Vec to a file


rust
I'm having trouble on writing Vec<u16> content to a file. #[derive(Debug, Copy, Clone, PartialEq)] pub enum ImageFormat { GrayScale, Rgb32, } #[derive(Debug, Copy, Clone, PartialEq)] pub struct ImageHeader { pub width: usize, pub height: usize, pub format: ImageFormat, } pub struct Image { pub header: ImageHeader, pub data: Vec<u16>, }...

How can I create Haskell-like functional dependencies


rust
Background: I'm using the nalgebra library and I want to create a structure that represents a multivariate normal distribution. The number and row type is uniquely determined by a square matrix type, so I want to write something like this: #[allow(non_snake_case)] pub struct Multivar𝒩<M: SquareMat<N, V>> { μ: V, Σ:...

Get next item in array using iterator using flags


javascript,jquery,loops,iterator,iteration
I am trying to obtain the next object in an object of objects (is you get my drift). I'm looking through the a list of songs, and trying to determine the next song to play. I use the flag playing to check if the song is being played, then i...

Indexing a String


rust
I want to perform a very simple task, but I cannot manage to stop the compiler from complaining. fn transform(s: String) -> String { let bytes = s.as_bytes(); format!("{}/{}", bytes[0..2], bytes[2..4]) } [u8] does not have a constant size known at compile-time. Some tips making this operation to work as...

Struct vs enum lifetime differences


rust,lifetime
Why does this work #[derive(Debug)] pub struct Foo<'a,'b> { s : &'a str, n : &'b i32 } #[test] fn test_struct() { let f = Foo { s : &"bar" , n : &17 }; println!("{:?}",f); } but this doesn't #[derive(Debug)] pub enum Bar<'a,'b> { Baz ( &'a str), Fub...

Autocreate nested foreach statement


c#,selenium-webdriver,foreach,iterator,auto
I have a simple scenario I am trying to workout which involves auto creating nested foreach statements. What the method is to do is take the int value passed into the method and based on this, it should automatically create nested foreach statements. public static String[] ValuesAdd1 = { "a",...

Does const containers have only const iterator?


c++,stl,iterator,standard-library
Why do const STL containers only return const_iterators? For example both std::vector and std::list have the method begin overloaded as: iterator begin(); const_iterator begin() const; const_iterator cbegin() const; I thought I could still modify values of a const vector but not the vector itself. According to the standard library there...

Pass Python list to Rust function


python,rust,ffi
I have a Rust library that needs to be imported into Python via the ctypes module. My goal is to use Rust functions that take Vec<T> / i32 as arguments and return those types, from Python. Currently, I can pass integers to the Rust functions, and have them return lists...

More convenient way to work with strings in winapi calls


string,winapi,rust
I'm looking for more convenient way to work with std::String in winapi calls in Rust. Using rust v 0.12.0-nigtly with winapi 0.1.22 and user32-sys 0.1.1 Now I'm using something like this: use winapi; use user32; pub fn get_window_title(handle: i32) -> String { let mut v: Vec<u16> = Vec::new(); v.reserve(255); let...

remove duplicates from vector of custom struct


rust
I'm trying to remove duplicates in the below example: struct User { reference: String, email: String } fn main() { let mut users: Vec<User> = Vec::new(); users.push(User { reference: "abc".into(), email: "[email protected]".into() }); users.push(User { reference: "def".into(), email: "[email protected]".into() }); users.push(User { reference: "ghi".into(), email: "[email protected]".into() }); users.sort_by(|a, b| a.email.cmp(&b.email));...

Java - Create sublist from a list based on suffix


java,arraylist,collections,iterator,sublist
I'm trying to create sublists from a list based on the suffix. public class Test { public static void main(String args[]) { List<List<String>> subList = new ArrayList<List<String>>(); List<String> myList = new ArrayList<String>(); myList.add("Text_1"); myList.add("XYZ_3"); myList.add("ABC_1"); myList.add("Text_2"); myList.add("Text_3"); myList.add("XYZ_1"); myList.add("XYZ_2"); myList.add("ABC_2"); for (String item : myList) { List<String> tempList = new...

Value does not live long enough when using multiple threads


rust
This is a simplified example of my situation: use std::sync::mpsc::{Sender, Receiver}; use std::sync::mpsc; use std::thread; struct User { reference: String, email: String } fn main() { let rows = vec![ vec!["abcd", "[email protected]"], vec!["efgh", "[email protected]"], vec!["wfee", "[email protected]"], vec!["rrgr", "[email protected]"] ]; let chunk_len = (rows.len() / 2) as usize; let mut chunks...

Bug in FFI when passing CString followed by an int


windows,rust,32-bit,ffi
My Rust test code extern "C" { fn test_int_only(n : libc::c_int); fn test_int_and_str(s : CString , n : libc::c_int); } pub fn test1() { unsafe { test_int_only(0); test_int_only(1); test_int_only(2); test_int_only(4); test_int_only(-12); } } pub fn test2() { unsafe { test_int_and_str(CString::new("Foo").unwrap(),0); test_int_and_str(CString::new("Bar").unwrap(),1); test_int_and_str(CString::new("Baz").unwrap(),2); test_int_and_str(CString::new("Fub").unwrap(),4); test_int_and_str(CString::new("Bub").unwrap(),-12); } } My C code void...

Immutable reference after mutable borrow


rust
I've been reading about rust for the past week and (trying) to play around with it. It seems I run into similar problems related to ownership/borrowing every time I use it, so here is the simplest piece of code that sort of illustrates the usual problems. use std::cell::RefCell; struct Res...

Load a shared library linked to Rust library in R


r,shared-libraries,rust
Following up on this question here, I am having issues using dyn.load to load a shared library that is linked to a Rust dylib. I suspect it has something to do with where R is looking for the Rust dylib, but I have not found a way to specify another...

Reading immutable value inside spawned thread


rust
I'm trying to make this example work use std::sync::mpsc::{Sender, Receiver}; use std::sync::mpsc; use std::thread; use std::sync::Arc; struct User { reference: String, email: String } struct UserIndex { reference: usize, email: usize } fn main() { let rows = vec![ vec!["abcd", "[email protected]"], vec!["efgh", "[email protected]"], vec!["wfee", "[email protected]"], vec!["rrgr", "[email protected]"] ]; let user_index...

What is the most appropriate way to convert nibbles to a u64?


rust
I am trying to learn Rust and decided to write a program that converts a hex string into a u64. Currently, I have parsed the string into a vector of u8 values, each representing four bits (or "nibble"). I wrote the following code to take a Vec<u8> and return a...

Debug error: Vector iterator not dereferencable and Vector subscript out of range [closed]


c++,vector,stl,iterator
I am trying to implement Rateless codes, but I have some issues in decoding. In the first implementation I used iterator to loop over a vector of vector and do some operation (like erase()) but I was getting this debug error: Vector iterator not dereferencable. After some googling I found...

c++ : double iteration through map


c++,dictionary,iterator
I would like to iterate through a map but the inner loop would just iterate through the upper part of the elements. With a vector it would look like that : for(auto element1 = myVector.begin() ; element1 != myVector.end() ; ++element1){ for(auto element2 = element1 + 1; element2 != myVector.end()...

How can I open a file with the standard text editor?


rust
My console based program has a config file which can be opened and edited in a text editor. How would I open said config file with the default text editor? I know there is std::process, but I can't get it to work. The program should be able to run on...

segfault accessing qlist element through an iterator


c++,iterator,qlist
I get a segfault while iterating over a QList. I don't understand what I am doing wrong. I have a QList of Conversation. Inside a Conversation I have a QList of Msg. Below are the class description : Msg class : class Msg { public: Msg(); Msg(const Msg& other); Msg&...

Why does Drop take &mut self instead of self?


rust
Why does Drop’s method have signature fn drop(&mut self) instead of fn drop(self)? This makes it difficult to move values out of the fields e.g. self.join_handle.join() or std::mem::drop(self.file) (error: cannot move out of type X, which defines the Drop trait).

the type of this value must be known in this context


rust
I want to get a length of a string which I've split: fn fn1(my_string: String) -> bool { let mut segments = my_string.split("."); if segments.collect().len() == 55 { //...... } // error: the type of this value must be known in this context How can I fix that error?...