Immutable collection operations

[alexfoxgill]

these basic functions may be useful to include with the library

impl IArray<A> {
  fn push(&self, item: A) -> IArray<A>;
  fn insert(&self, item: A, pos: usize) -> IArray<A>;
}

impl IMap<K, V> {
  fn upsert(&self, key: K, value: V> -> IMap<K, V>;
}

[cecton]

Yup I think the same! No bandwidth at the moment but feel free to open a PR

[cecton]

@kirillsemyonkin this one is a bit more complicated, you can check here how they did the API in Immutable.JS: https://immutable-js.com/

Ideally you don't want to reproduce the JS API but stay as close as possible to the Rust API.

Also you can clearly see in the API sample of this issue that we take an immutable in argument (&self) and we return a new owned value. That's the way to go because it's suppose to be immutable.

I think it's possible that the reason why I did not make this "building" API is because it's not very optimal for the allocations. The user should probably make standard rust types (Vec, String, etc...) and then .into() them to immutable ones. So if you decide to not implement it you might need to explain in the README why we don't implement it and/or maybe add methods like ".to_vec()" or ".to_string()" to get standard types instead.

[kirillsemyonkin]

@cecton

maybe add methods like ".to_vec()" or ".to_string()" to get standard types

This is already a thing because of Deref<[T]> and Display, by the looks of it (unless you meant add to README lol).

I did not make this "building" API is because it's not very optimal for the allocations

Yeah, JS APIs are full of such things - they really like their array clones, and this really contradicts Rust's "blazingly fast" motto (I thought this was a community meme, but apparently they have it on their main page).

I am also thinking of fn push(self, item: A) -> IArray<A>; (self) and others instead, but really they also would need to allocate (and unlike Vec, it would be an allocation on every push, since we probably don't want to work with capacities and turning it into whole another Vec), it's just that instead of cloning each item it would be a move, and we could maybe even hope for compiler to inline building an array like that. To match issue's examples it would have to be i_array.clone().push(...).push(...)..., but now that I think about it, it kinda defeats the purpose of "implicit clone", which is the name of the project lol

Also looking at Rust APIs for [T], they have methods like (&array).repeat(n), which returns a Vec, we could possibly add those functions in the issue and return Vec instead, which kinda makes API tell users that doing a push causes something more than IArray to IArray to happen - it gets converted to Vec, and user assumes a non-cheap clone even without reading into documentation.
The only thing is that you can't chain pushes like that, so it would lead to code that looks like this:

let mut vec = i_array.push(a);
vec.push(b);

At that point, I personally would prefer following (which should already work):

let mut vec = i_array.to_vec();
vec.push(a);
vec.push(b);

[futursolo]

One way to avoid a complete clone on every operation is to use collection types implemented with Hash Array Mapped Trie (HAMT), which is traditionally designed to return a new instance upon mutable operations.

However, this may introduce significant bundle size increase and I haven't found any actively maintained Rust implementation for it.

[cecton]

This is already a thing because of Deref<[T]> and Display, by the looks of it (unless you meant add to README lol).

No I just forgot what I implemented lol. Maybe just documenting the use of to_vec() and such would be enough.

Yeah, JS APIs are full of such things - they really like their array clones, and this really contradicts Rust's "blazingly fast" motto

Yeah it's not idiomatic rust.... so probably it's best to take a different approach than re-allocating on every single operation.

why I did not make this "building" API

@kirillsemyonkin I was thinking about this "building" API I have put on quotes lol. Why not actually use a builder pattern?

let mut builder = my_array.make_mut();
builder.push(x);
builder.push(y);
let new_array = builder.finish();

Maybe we can achieve this with a struct like this:

pub struct ArrayBuilder<T>(Vec<T>);

impl Deref for ArrayBuilder {
    // ...
}

impl DerefMut for ArrayBuilder {
    // ...
}

impl<T> ArrayBuilder<T> {
    pub fn finish(self) -> IArray<T> {
        // ...
    }
}

impl<T> IArray<T> {
    pub fn make_mut(&mut self) -> ArrayBuilder<T> {
        // ...
    }

    pub fn make_mut_with_capacity(&mut self) -> ArrayBuilder<T> {
        // ...
    }
}

I'm not sure this is worth it at all because in the end it does look very much like the to_vec() solution except that you can pre-allocate differently with make_mut_with_capacity().

I like the idea of @futursolo but it looks like a lot of work.

[kirillsemyonkin]

builder.push(x);
builder.push(y);

Just a little nitpick, but I would argue this is not builder pattern, and only .push(x).push(y).build() is. This is signaled by using self for all functions. There is some kind of documentation online, which says taking and returning &mut Builder in every function would let both variants work.
They also mention that using a builder as not only a builder is quite possible. In that case, my example with self from my first comment (where IArray becomes a builder in its own right) matches that description.

I like the idea of @futursolo but it looks like a lot of work.

I'm not familiar with the structure. It is described as a structure used for maps. The Wikipedia page mentions im crate, which uses the structure for maps. If a rust crate is not updated in a while it is probably means it is ready and should keep rusting, but by counting their valid but non-replied issues I'm not so sure.
It could be considered, but we would have to implement it first, and then test to confirm that it performs better than usual simplest flatly laid-out array. As mentioned, this is a lot of work, but also can even not pay off.