A normative immutable array type

[dsyme]

For people coming to this thread afresh, the RFC is here: https://github.com/fsharp/fslang-design/blob/main/RFCs/FS-1094-immarray.md

I propose we work out how to make one particular immutable array type normative in F# programming "in the box", including in Fable programming.

The existing way of approaching this problem in F# is to use a user-supplied package of collections such System.Collections.Immutable

Description

One particular thing that is a hole in our library is the lack of an immutable array data structure in regular F# coding. There are lots of use cases for this and it is easy enough to implement efficiently, e.g. here (originally from the compiler codebase) though there are other approaches.

I’m particularly aware that Fable and the Elmish design pattern is popularizing the use of immutable data for important model descriptions more and more and we should be helping improve the situation for that kind of programming

The main question is to how to make on immutable array type normative in F# coding

1. Add a bespoke immutable array to FSharp.Core.

2. Encourage people to take a dependency on System.Collections.Immutable and add a reference to it to our standard templates. However we would still presumably want an FSharp.Core module making it look and feel like a normal F# collection, but we wouldn't want FSharp.Core to have a dependency on System.Collections.Immutable.

Probably the hardest thing is to decide its name.

• ImmutableArray is too long, especially for a module
• IArray looks like an interface
• FlatList breaks with industry naming, it looks too odd.
• XArray, ZArray are possible if we are desperate – e.g. just make a new F# convention that ZThing is an immutable version of Thing
• Block wins the day

Related questions are

1. Would want a bespoke functional update syntax “{ arr with 3 = expr }” or “{ arr with n = expr } or “arr.[n=expr]”.
2. Would the type feel right from F# code – good ergonomics etc
3. What library dependencies would the type induce
4. How do other collections from System.Collections.Immutable feel to use from F#?

Extra information

Estimated cost (XS, S, M, L, XL, XXL): M

Affidavit (please submit!)

Please tick this by placing a cross in the box:

• [x] This is not a question (e.g. like one you might ask on stackoverflow) and I have searched stackoverflow for discussions of this issue
• [x] I have searched both open and closed suggestions on this site and believe this is not a duplicate
• [x] This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it.

Please tick all that apply:

• [x] This is not a breaking change to the F# language design
• [x] I or my company would be willing to help implement and/or test this

[lfr]

Even though I no longer have a horse in this race after having replaced block with box in my own library, I still thought bloc was a great choice both semantically (a group of parties who work in unison) as well as aesthetically (it's super short).

In any case, I'm still happy an ubiquitous word such as block didn't get hijacked for this purpose, I think it may be for the best, though ImmutableArray is quite the mouthful and typeful 🤔

[dsyme]

@SamuelBerger @matthewcrews Certainly "Block" is a fine name and the best suggestion we have.

However in the compiler code, I guess I just came to realise that we will ultimately need multiple immutable collections (ImmutableList, ImmutableArray, ImmutableDictionary in particular), and it's just better and clearer and simpler if these all use some common prefix and naming scheme, and thus that we need to connect more solidly to the existing naming schemes. Diverging one of these for "block" just didn't help.

[reinux]

Not sure we need even more name ideas at this point, but how about "roar" or "roarr", as in "read only array"? It's fun to say 😁

[dsyme]

@reinux It's a long, long thread. I think given my comment above I guess I'd suggest back to this suggestion below.

BTW this whole topic makes the more common use of Fluent notation (as in #1073) more necessary/useful - the more collections you have, the more likely you crave to reach for fluent notation.

Module-qualified functions:

ImmArray.map
ImmList.map

Note modules are rarely needed for dictionaries and more exotic collections, as most interesting operations are available immediately via dot-notation.)

Types:

immarray<int>
immlist<int>

Pattern matching

    match x with 
    | ImmArray [ a; b ] -> ...
    | ImmArray [ a; b; c ] -> ...

To be performant the ImmArray active pattern would need to be a new kind of thing, e.g. if we allowed the use of list pattern syntax against indexable data-structures.

Without such an extension I don't think we would make any specific pattern matching available and would just ask the user to write their own active patterns.

Construction

In the simplest addition, creation would just use the existing API, which would give

immarray.Create(1,2,3)
immarray.CreateRange [1;2;3]

and so on. Adding an immarray function taking an IEnumerable seems reasonable.

immarray [ 1;2;3 ]

We would also support immarray { for x in 1 .. 1000 do yield (x+1); .... } etc. without creating an intermediate sequence and only an intermediate builder, as for list and array construction.

See also https://github.com/fsharp/fslang-suggestions/issues/625

[lfr]

Knowing that there's going to be a number of these things, I think ImmArray, ImmList, etc are definitely the better option. In isolation the "Imm" prefix seemed a bit jarring but as part of a collective, it makes sense.

In fact I'd bet that if you go with "Immutable", it's only a matter of time before you implement "Imm" as an alternative.

[NinoFloris]

I've never found ImmArray annoying as a name or frustrating to type since we started using it in 2020. So +1 for these new names!

[uxsoft]

I think the block was good if the goal was to patch the gap for an immutable array.

If the goal is broader support for immutable collections here are some interesting observations as food for thought:

• Is support for ImmutableList needed in the FSharp.Core?

  • What are the major differences between the two?
  • Can we pick a default and the other be supported as any other C# code without specific FSharp.Core alias?

• System.Collections.Immutable supports a number of immutable collections. Should more/all of them be supported in FSharp.Core?

  • How does the performance of the F# types compare to the System.Collections.Immutable counterparts?
  • In the ideal world would F# use these collections as a basis for the implementation of List/Set/Map?
    • If the answer is yes, do we want to take steps to get slowly closer to that world without breaking changes?
  • ImmutableArray
  • ImmutableList (counterpart to F# List)
  • ImmutableDictionary (counterpart to F# Map)
  • ImmutableHashSet (counterpart to F# Set)
  • ImmutableQueue
  • ImmutableSortedDictionary
  • ImmutableSortedSet
  • ImmutableStack

• Is the intention for F# collection types to be immutable by default and mutable explicitly?

  • This is what already happens with variables and let vs let mutable
  • Kotlin does this as well and the names of the collections it uses are List, MutableList, Set, MutableSet, Map, MutableMap
    • This is very clean and understandable for beginners (Simple F# theme)
    • If we'd like to go this way, we should also introduce an alias for Array (MutableArray) and deprecate it so that we could slowly migrate usage from Array and repurpose the Array for an immutable collection in the future.

• How will all of these collections be initialized? Is new syntax needed?

  • Kotlin doesn't have any syntax for collection initializers, instead, it makes use of "params" helper methods in the global scope like listOf(_, _, ...), mutableListOf(_, _, ...)
    • This is very handy because new collections can be easily introduced by libraries and they "feel" native
    • It's Much easier to implement, and doesn't add any new language features
    • The use of brackets might not feel too "ML"
  • Swift uses a combination of the following (both suggestions already appeared above in this thread I believe):
    • Distinguish mutability by how the variable is declared (var vs let).
    • The type of the variable decides the type of the collection var deque: Deque<String> = ["Ted", "Rebecca"]
    • This would help also with the Array syntax ([| |]) which comes from OCAML
  • F# CE's
    • Similar to the Kotlin proposal above the, this would be the generic F# equivalent
    • Like seq { ... } we could introduce block { ... } and mutableBlock { ... }, etc.
    • CE's are very expressive, also very easy to implement without the need for extra language features
    • Are there performance implications to using CE's?

[uxsoft]

My personal opinion of the ideas above:

• Let's take a broader look at F# collections to make them clean and easy to understand
• F# should be immutable first, explicit about mutability (even in collection types)
• I'd follow Kotlin in naming
• I'd use F# CE's for initialization
• I don't think we need both ImmutableList and ImmutableArray right now
• Block seems like a good bridge to an immutable array because making an array immutable would be a breaking change

So all in all it could look like this:

• List (exists)
• MutableList (missing, alias for C# LinkedList?)
• Block (this RFC)
• MutableBlock (= Array)
• Set (exists)
• MutableSet (missing, alias for C# HashSet?)
• Map (exists)
• MutableMap (missing, alias for C# Dictionary?)

On an unrelated note: I'd be willing to work on this / submit a pull request when there is a decision on how this should look.

[Happypig375]

@uxsoft The problem is seen here: https://github.com/fsharp/fslang-suggestions/issues/619#issuecomment-1154210776

The F# compiler makes use of ImmutableList, ImmutableArray, and ImmutableDictionary despite the presence of F# Lists and Maps. This is because F# collections and System.Collections.Immutable are fundamentally different - ImmutableArrays for small amounts of data, ImmutableLists for large amounts of data or frequent updates, ImmutableDictionary is unsorted unlike Map which provides performance benefits... Meanwhile, F# collections currently provide no support for comparers, and keys must be able to provide comparison (not just equality). Unifying these two is a guaranteed breaking change - F# Map is sorted while System.Collections.Immutable.ImmutableDictionary is not. F# Map requires comparison constraint and that will not be going away.

[charlesroddie]

I would rather we don't discuss the name any more! An abbreviated name doesn't need to go into any initial work on this. It can be added later without any breaking changes.

@uxsoft On an unrelated note: I'd be willing to work on this / submit a pull request when there is a decision on how this should look.

I believe the main piece of work is to create these things using [: :]. I started work on this in https://github.com/dotnet/fsharp/pull/12859 . I can fix the conflicts.

It's my first contribution to the compiler and I could use some help with it @uxsoft or anyone else! Feel free to message me on slack. I believe it's at the point where it ought to work but doesn't, so some help testing/debugging would be very appreciated. Could be over a screen share.

Module functions are already implemented and just need to be exposed.

[kimsey0]

Now that it was been decided in principle that FSharp.Core will depend on System.Collections.Immutable and will implement a module that makes it easy to interact with ImmutableArray<'T>, it would be lovely to make a similar module for ImmutableQueue<'T>. I assume that should be a separate issue?