Plan for (immutable) lists?

A lot of effort has gone to moving arrays to be more first class in Rescript. This makes a lot of sense for the use case of interopping with JavaScript (which I think we all need).

However, we’re building a large application in ReScript. One of the great advantages of rescript is that it is (mostly) immutable; we love that about it and rely on it heavily. One part of that is that we use immutable lists a lot.

I’d love to know what the plans are for lists. I hope that they will stay around, since I can’t imagine something so fundamental as lists going away in an immutable functional language. But I especially hope that support for lists will be elevated to make them feel as first class as Arrays. Particularly I’d be interested in seeing:

  • a better syntactic option that list{}
  • more performant generated code for lists (possibly using JS arrays, especially for short lived lists)
  • using lists as argument types in more places (at lot of Belt APIs use arrays in places where lists seem to make more sense, such as Belt.List.concatMany!)

Could the core team let us know how they think about lists in the future of rescript?

I wonder if what you want can actually be achieved using some immutable API for arrays. E.g., creating (and opening everywhere) an Array module that doesn’t allow mutation, and a MutableArray module for cases where you really want mutation. And, e.g., copying every time you have to convert mutable arrays to immutable ones and vice versa.

Or do you really need something like O(1) on :: operations?

In other words, what do you want out of linked lists other than immutability? Pattern matching? Performance characteristics? Stack-like order?

1 Like

We don’t really use that at all. Lists for us are just immutable sequences (I personally feel that languages have over indexed on the idea that lists are linked lists, and all the things that entails, like O(1) push/pop).

We’re not doing hard data structure work (if we were, lists would be inappropriate). We barely use recursion. We do use pattern matching, but rarely need to use lists specific constructs. We just really like immutability (which is why we use rescript in the first place).

1 Like

Why not to use array then? If you are really worry about immutability you can disable the use of pop, push, shift, unshift, reverse, sort, and splice with eslint. But even without it we’ve never had a problem with somebody unconsciously mutating an array at Carla.
I see the only reason to use lists, it’s when you need a stack-like data structure.

1 Like

To be clear, the purpose of this post is to ask how the core team is thinking about this long term.

3 Likes

Both Flow and TypeScript have readonly variants of the Array type where methods that mutate aren’t available. Introducing MutableArray in ReScript seems like a reasonable suggestion.

Pattern matching?

ReScript supports pattern matching with arrays.

1 Like

It seems that all of this is doable in user-land, so wondering where the original question is heading.

E.g. there are examples of uses if immutable arrays (just a custom module that includes array and does not export mutating functions).

Also, lists are pretty much just one use of abstract data types, so they’re user land too.

Finally, the project has transitioned towards a more community-led approach with more frequent core contributors (frequency changes over time because of personal availability) rather than a formally defined core team.

2 Likes

Perhaps relevant to this, there have been discussions about supporting a native vector type. But I don’t think anything went past the initial idea stage.

For something central to the language like lists, the project leaderships view on direction is important. For example, changing the list syntax from [] to list{} has a huge bearing on the usability of the feature. Similarly, the performance of lists is part of the compiler and runtime, which is something you can’t deal with in userspace.

More importantly, it seems core APIs in Belt have support for arrays but not lists (eg HashSet has toArray and fromArray.

So I don’t think I’m off base for asking “what’s the plan here”? Are lists going away? Are there going to be deemphasized and deprecated? In this world, what’s the plan for first class immutable sequences (by “first class”, I mean something that the community is encouraged to use, and that forms a natural part of the language and ecosystem. It’s not really great to doing something in userspace if I need to convert it to an array every time I call a Belt function.

My personal feeling is that the presence of both Arrays and Lists was always a little untenable (including in OCaml). Immutability is core IMO to what makes Rescript good, so it feels like discarding the immutable choice does a real disservice to the language’s usability. I guess I was hoping the team had a plan to address this.

I’ll try to answer a simpler question: why was the syntax of list literals changed to list{}.
That was to save syntactic space. Either lists or arrays were going to take the [] syntax, and preference has been given to arrays.
No other change has been performed or planned.

One idea floating around has been to e.g. have vec{...} for vectors and set{...} for sets etc in future.

2 Likes

There is one of immutable vector implementation. rescript-collection/packages/vector at main · reason-seoul/rescript-collection · GitHub

4 Likes

@namenu and I have previously talked about promoting rescript-vector to vec { ... } in the Reason Seoul community, but never officially proposed it.

He also experimented with a HAMT(Hash Array Mapped Trie) Map/Set implementation to replace the current AVL-Tree implementation in the same repository. I’m not sure whether the result of that remains.

2 Likes