Immutable collections library

[sa-]

Scala has by far one of the most pleasant collections library (which is immutable by default) that I have ever used

If a similar implementation could be implemented in the std lib with the following syntax:

let arr = [1, 2, 3, 4, 5]

arr
  .map(lambda x: x*2)
  .filter(lambda x: x%2==0)

that would be awesome

[nmn]

The given example would be supported even if the collection was not immutable. Swift uses “value types” which are similar to Immutable Data Structures, and I would expect something similar in Mojo. In Swift, these types use a “copy on write” mechanic to minimize unnecessary copying. Still, Swift doesn’t help much if you write code that could cause many copies of large amounts of data.

There’s also the opportunity to support Persistent Immutable Data Structures that use trees internally to minimize the cost of “copies”, by “structural sharing”. However, the trade-off is that all operations are a bit slower.

Considering the fact that Mojo is being made primary for Machine Learning tasks, I’m not sure if Persistent Data Structures would be particularly useful. Happy to be wrong about that though! Using some of the lessons from Swift’s value types, Mojo could implement Persistent Data Structures that are better than what usually exists out in the world today. Mojo could smartly do in-place mutations when it wouldn’t cause side-effects, but do shallow copies otherwise.

Roc-lang is a great example of another language that supports Persistent data structures with extremely high performance!

[segeljakt]

I think given that Mojo supports ownership, mutable non-persistent data structures like Rust's make a lot of sense since you can guarantee that there is no sharing to support safe and efficient in-place updates.

[nmn]

I definitely don’t think the persistent data structures should be the only option. But it might make sense to include them for some use-cases.

[segeljakt]

I think it's worth discussing if Mojo should allow making it implicit that you are using an immutable data structure or explicit. In Rust, for example, you can have immutable data structures that are reference counted (Rc<T>), but you need to be explicit when you are creating a new reference to them with Rc::<T>::clone(). The same applies to copy-on-write (Cow<'a, T>). If Mojo wants to be zero-cost then I think it would make sense to bring all costs up-front, even though it might make functional programming less convenient. If Mojo wants to be convenient, then it could make sense to make things implicit.

[alexandergunnarson]

I'd say if Mojo is meant to be truly general, including persistent data structures in some sort of library would be pretty important. I come from a Clojure background and it makes life so much easier. I foresee it being tricky/less-performant in a non-GC context though.

[nmn]

@alexandergunnarson Having value types would give you the same experience in general. Whether it's using copy-on-write or persistent data structures only causes performance trade-offs.

Using copy-on-write (which is what Swift does by default), has been read performance in many cases as not everything needs to be a tree structure behind the scenes with lots of pointers. However, copying can be slower for sufficiently large data.

[soraros]

Given Mojo is a language for high performance math kernels, the data structures provide by its standard library (probably) better have SIMD friendly internals. Persistent array Clojure style, for instance, although very cool, doesn't have that property.
Nothing prevents community from implementing one though; I would be very happy to use it.