Newb question on immutable collections

help
1

Hi all - I am learning Rust and working on my first non-trivial program. I have a recursive descent parser, and one of the outputs is a set of strings which I'm using a HashSet for.

I'd like to keep everything immutable and have each recursive call take in a state struct containing a hash set, and return a new state struct.

Does Rust have the concept of taking an immutable collection, and returning a new immutable collection with an element added? Something like

Ok(MyState {
// other fields
syms_used: old_state.syms_used.with_added_value(symbol),
})

Or is practice just to make the set mutable?

2

It's usually easier (and considerably more efficient) to use a mutable collection. That said, there's nothing fundamental stopping you from using an immutable set, I'm just not familiar enough with immutable collections to know how it'd be implemented.

A quick google shows the im crate, which contains loads of nice looking immutable data structures. The crate itself looks quite complete and mature.

1 Like
3

To agree with @Michael-F-Bryan the idiomatic way to do things is just to make it mut.

An alternative is to clone the immutable collection into a new mut one, then make changes to the copy and return it.

A fancy way to do things is to use Rc and the Rust concept of interior mutability (types that claim to be immutable but are lying) to share the important parts of the structure. When you need this approach and an interface that just looks like a standard collection there are crates around for doing that, as already mentioned the im crate or rpds is also a good crate.

4

The crate "seq" provides an immutable list-collection (sequence), which can grow/shrink with the corresponding recursive calls (stack depth). This immutable list-collection can be used without any heap-allocation, using stack-memory only.
https://crates.io/crates/seq
and
https://github.com/frehberg/seq-rs

You could use the Seq-collection to implement kind of associative map, just, I am not sure this is efficient.
EDIT The example code from github-repo illustrates how to prepend two elements to an immutable sequence and returning the extended list (in this case heap-allocation is required)

fn prependTwoBoxedValues <'a> (v: u32, w: u32, seq: &'a Seq<u32> ) -> Box<Seq< 'a, u32>> {
   Box::new(Seq::ConsOwn(v +1,
      Box::new(Seq::ConsRef(w, seq))))
}