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:

• This is not a question (e.g. like one you might ask on stackoverflow) and I have searched stackoverflow for discussions of this issue
• I have searched both open and closed suggestions on this site and believe this is not a duplicate
• 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:

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

[gerardtoconnor]

ReadArray/RArray ? Core is developing Span that includes ReadOnlySpan , might this be a good representation to isolate underlying array?

If we could also implement an Array cursor that holds position small struct, we could pattern match like list to allow :: decomposition and reduce need to convert arrays to lists given lists usually twice size and array already allocated.

[tldrlol]

How about stealing terminology from other languages and calling them vectors?

[ijsgaus]

Maybe, FrozenArray

[forki]

FlatList is new react native component. Please don't use that

[forki]

@tldrlol are we really talking about vectors? We have persistentvector in FSharpx.Collections - it's a hash array mapped trie.

[gerardtoconnor]

Agree on flatmap not being great. I have never liked the blanket naming approach on vectors outside of linear algebra, like in c++. I do like the idea though of like vector using a simple name like Range, Span or something similarly simple. For perf it might be worth looking at how Span implements index access in .net core 2.0

[rmunn]

I'd rather not use the name "vector" for this, since that's already got a meaning (PersistentVector from FSharpx.Collections, inspired by Clojure) that is NOT an array. If F#'s immutable arrays got called vectors, I'm afraid it would cause user confusion between that and the very useful persistent vector structure. (I'd also like to see PersistentVector and PersistentHashMap promoted to some kind of "official" status in the FSharp.Core library, but that's a different suggestion).

I'll toss out another name suggestion or two to see how it sounds. How about FArray as shorthand for FrozenArray? Or ImmArray since IArray sounds too much like an interface. Or the most radical suggestion: just name it Array, and the C# class would be called MutableArray, just like how the C# List class is named ResizeArray in F#.

In the latter case, where we define Array as the name of the immutable-by-default type, there are many possible sources of confusion, such as "What's the difference between the types int [] and int array?" (The former would be a mutable array, and the latter would be an immutable array). But that name would make a statement that F#'s types (seq, list, and array) are all immutable by default — which might not be a bad thing.

[realvictorprm]

Just realized again, that I can modify arrays if I want to 😄

I'm for the radical version of naming our standard Arrays just Array and naming the C# or .NET regular Array just MutableArray.

But I like the ReadArray idea too 🙂

PS: Please don't call it Vector. Keep the mathematical meaning...

[mexx]

What would be the main difference to an immutable list which is already present?
Is it only performance? Maybe we could just annotate the list instance to be array-backed instead of linked list-backed?

[rmunn]

A list-like structure that's array-based already exists; it's called ResizeArray. The difference is indeed performance: the existing List, based on a linked list, is extremely efficient for operations at the head of the list (inserting or removing an item at the head is O(1)). Lots of F# code depends on that property, and changing to an array-backed data structure for the List type would change that and make a lot of O(N) code to be suddenly O(N²). So the suggestion of changing List to be array-backed turns out to be a bad idea, and thankfully it will never happen.

[smoothdeveloper]

@mexx

What would be the main difference to an immutable list which is already present?

The immutable list doesn't expose the same operations as arrays, like getting an item by index, or getting the length, or rather their performance characteristics make them bad practice to use.

@realvictorprm I like the idea to rename current Array into MutableArray, but how would you actually make that happen without breaking all the code? it sounds like we would need first to roll out a FSharp.Core with the MutableArray module so the code can start to explicitly use that, but we would still need to find a transition approach for existing code relying on Array.

Are there other languages we can draw inspiration from as to how to handle the concept of immutable arrays?

[mexx]

@rmunn and @smoothdeveloper you might have gotten my suggestion wrong.
It's not about changing the list to always be array-backed.

There are to levels of discussion, and I haven't made clear on which one I make my suggestion.

Concrete vs. abstract data type

The list and array data types are concrete data types and have their characteristics. However I see both to be an implementation detail of the same abstract data type collection, previously I used list for it, that was misleading. This ADT actually defines the possible operations, like getting an item by index, getting the count of the items (length, size).

So my suggestion was to define and see the current F# list as this collection ADT and be able to indicate which implementation should be used, linked list or array.

[dsyme]

One approach would be to add a new FSharp.Core.Extras.dll (exact naming TBD) to the set of default references in F# projects, with a dependency on System.Collections.Immutable.dll, with

type roarray<'T> = ReadOnlyArray<'T> = ImmutableArray<'T>
module ROArray = ...

Or

type immarray<'T> = ImmutableArray<'T>
module ImmArray = ...

Or

type iarray<'T> = ImmutableArray<'T>
module IArray = ...

The last one has the drawback that IArray may be thought to be an interface, but has the distinct advantage of being short and visually non-instrusive

[dsyme]

I'm labeling this as approved-in-principle - we should address this though the exact approach is far from decided

[Tarmil]

Do we want a new syntax for creating such an array? What about pattern matching on it?

[dsyme]

@Tarmil It's a very good question.

Pattern matching

Effective, performant pattern matching would likely need an extension to active patterns. Best syntax would be something like

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

etc. but 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 datastructures.

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 ]

It's going to be hard to justify adding more beyond these, assuming we have the regular functions in ImmArray.*

In some ideal world, we would also support syntax immarray { for x in 1 .. 1000 do yield 1; .... } etc. without creating an intermediate sequence and only an intermediate builder, but that is a stretch. Ideally that would be part of some more general treatment of the builder pattern for immutable data used in System.Collections.Immutable that would generalize to all collections following the pattern, but I think it's difficult to generalize

let x = ImmutableArray.CreateBuilder<int>(4).ToImmutableArray();;

[gerardtoconnor]

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

This is why I was thinking, additionally, we may want to include an ArrayCursor type that is a simple struct of standard array ref & index such that cons operator could be used on ArrayCursor to decompose to item at index, and new cursor with index incremented ... allowing for rec array traversal like list but without having to rebuild the array as a list. The ArrayCursor could also have item/index methods on it (although if struct, we risk boxing so best if we could index with static operator or similar) so we could do index jump & read to remain consistant and avoid boxing.

[gerardtoconnor]

Might need to be separated into different issue (as don't want to distract from immarray conv) but have mocked up basic idea for immutable array cursor which could pattern match (although extra operators etc all optional) so we could traverse arrays like lists with no additional allocations:

type ArrayCursor<'T> =
    struct
        val private iary : 'T []
        val position : int
    end
    static member empty (ac:ArrayCursor<'T>) = ac.position = -1 
    static member itemNext (ac:ArrayCursor<'T>) = 
        if ac.position + 1 < ac.iary.Length then 
            ac.iary.[ac.position] , ArrayCursor<'T>(ac.iary,ac.position + 1) 
        else 
            ac.iary.[ac.position]  , ArrayCursor<'T>(ac.iary,-1)
    static member next (ac:ArrayCursor<'T>) = ArrayCursor<'T>(ac.iary,if ac.position + 1 > ac.iary.Length then -1 else ac.position + 1)
    static member prev (ac:ArrayCursor<'T>) = ArrayCursor<'T>(ac.iary,if ac.position - 1 < 0 then -1 else ac.position - 1)
    static member jump (ac:ArrayCursor<'T>) (pos:int) = ArrayCursor<'T>(ac.iary,if pos < ac.iary.Length && pos > 0 then pos else -1 )
    static member item (ac:ArrayCursor<'T>) = ac.iary.[ac.position]
    static member jumpItem (ac:ArrayCursor<'T>) (pos:int) = if pos < ac.iary.Length && pos > 0 then ac.iary.[pos] else failwithf "Out of index exception"
    new (ary: 'T [],pos) = { iary = ary ; position = pos } // include pos bounds check on constructor 
    new (ary: 'T []) = { iary = ary ; position = 0 }

let inline (!+) (ac:ArrayCursor<'T>) = ArrayCursor<'T>.itemNext ac
let inline (~+) (ac:ArrayCursor<'T>) = ArrayCursor<'T>.next ac
let inline (~-) (ac:ArrayCursor<'T>) = ArrayCursor<'T>.prev ac
let inline (!) (ac:ArrayCursor<'T>) = ArrayCursor<'T>.item ac
let inline (@) (ac:ArrayCursor<'T>) (pos:int) = ArrayCursor<'T>.jump ac pos
let inline (!) (ac:ArrayCursor<'T>) (pos:int) = ArrayCursor<'T>.jumpItem ac pos

module Array =
    let toArrayCursor x = ArrayCursor<_>(x,0)

let acur = ArrayCursor<'T>([|1;2;3|])
let h,tail = !+acur        // value , ArrayCursor (next)
let nextCur = +acur        // ArrayCursor (next)
let prevCur = -acur        // ArrayCursor (prev)
let value = !acur          // value (at cursor)
let jumpCur = acur @ 4     // ArrayCursor (at index)
let jumpVal = acur ! 5     // value (at index)

[piaste]

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

I think one major reason people currently use Lists by default, even when they don't need a linked list at all and it just hurts performance, is that it has the cleanest literal syntax available in F#.

Notably, both Fable-React and Websharper go with lists. In their HTML DSLs, every element is followed by two collections (attributes and inner HTML) and even using a basic array would start to look 'noisy' really fast (div [||] [| foo |] versus div [] [ foo ], repeat for a thousand times). @Tarmil can you say if that was a consideration when designing Websharper?

Typing ImmArray.Create() would be a non-starter, and using a shortened function on a list (like dict [] does) would require first creating the linked list, partially defeating the point of using a more performant data structure.

I suspect that a collection type without its own (lightweight!) literal syntax would end up being used only when performance concerns begin to surface, and it would be largely absent from day-to-day usage.

[xperiandri]

Why not finally to deprecate F# specific collections and use System.Collections.Immutable with F# syntax used earlier for F# specific collections?
All names will left just point to types from System.Collections.Immutable.

System.Collections.Immutable are standard, performant, have perfect API and interoperable.
Why do you spend resources for F# specific collections support?
I used them through https://github.com/xperiandri/FSharp.Collections.Immutable and they work nice.

[rmunn]

Are the collections in System.Collections.Immutable really performant, compared to the collections in FSharpx.Collections (ported over from Clojure)? The ImmutableList implementation is an AVL tree, whereas PersistentVector is a 32-way B-tree structure. Have there been any performance comparisons of the two? I believe that the System.Collections.Immutable collections are not the most performant ones out there, but I don't know if they have been directly compared yet.

[Tarmil]

@piaste Well, in WebSharper these functions take seq<_>, but indeed 99% of the time you pass a list literal because it's what looks the cleanest. To the point that we added an optimization in WebSharper so that if you pas a list literal to a function that takes a seq<_>, it's compiled to an array literal instead.

[dsyme]

Are the collections in System.Collections.Immutable really performant, compared to the collections in FSharpx.Collections (ported over from Clojure)? ...

I think both may suffer somewhat because of this issue which can make a major difference to these collection implementations

[dsyme]

I suspect that a collection type without its own (lightweight!) literal syntax would end up being used only when performance concerns begin to surface, and it would be largely absent from day-to-day usage.

Thanks for making this case - it is a compelling argument and UI/HTML/JSON/DOM literals are a very fundamental use-case for immutable collections.

Are there any approaches to literal syntaxes would be acceptable? e.g.

• Add a range of new syntaxes [! a; b !] ?
• Have the [ ... ] syntax resolved in a type-directed way (e.g. "if the target type is known to be a collection C with a builder pattern or IEnumerable constructor, then treat the syntax as if it is constructing a C, otherwise treat it as a regular F# list"))? While plausible it is a significant addition which may give worse error messages, and increase reliance on typing context and type annotations.

but indeed 99% of the time you pass a list literal because it's what looks the cleanest. To the point that we added an optimization in WebSharper so that if you pas a list literal to a function that takes a seq<_>, it's compiled to an array literal instead.

Again an interesting observation, thanks

[vasily-kirichenko]

Have the [ ... ] syntax resolved in a type-directed way (e.g. "if the target type is known to be a collection C with a builder pattern or IEnumerable constructor

I like this idea a lot. I'd be very happy if [|...|] be deprecated.

[piaste]

🤘 I agree, type inference for collection literals sounds fantastic and, I suspect, a more efficient use of time than periodically introducing better data structures.

Handling ambiguous cases should require a lot of care though. Some food for thought: how should the following cases be resolved?

let x = [ ... something ... ]

a) let _ = x |> Seq.head or, in Fable/WS let _ = div x []
b) let _ = x.[0]
c) let _ = printfn "%A" x
d) x.[0] <- "foo"
e) let _ = match x with | [] -> 0 | [ _ ] -> 1

Possible approaches:

1. Best performance: infer the simplest collection type that supports the usage, either a basic array or the immutable array type being discussed.

   Disadvantage: would make this a potentially breaking change. Now, internal code would be pretty safe (unless the user did something weird like unsafe casting from a seq back to list), but if the collection was part of an assembly's public API, the inference would suddently change it to an array. Granted, most public APIs should have type annotations in a .fsi file or something.

2. Just infer as list to make the change non-breaking. Possibly add a compiler info that the structure usage could be optimized.

   Disadvantage: would significantly reduce the scope of the performance improvement. In theory library authors could update their APIs to take in arrays instead of seqs, but this would not only be a breaking change on their side, it might not be a valid choice since sometimes you do want to use a different type of collection.

[travis-leith]

Range, like Block has lots of existing meanings, none of which are as a collection type. Unlike Block, though, Range is a concept often applied in the collection space (the value passed to "slice" methods that get a "sub-collection"). I'd vote for Block before Range.

How would you feel about Bloc instead of Block?

[wekempf]

Bloc is just an abbreviation. Normally I dislike abbreviating, but in this case it at least addresses concerns about name clashes such as those that lead @lfr to claim he'll have to deprecate a repo. However, that's all it does. It doesn't help with the communication problems with overloading a name. That's why I prefer Arr. While that's also an abbreviation meant to avoid a name clash, at least both usages are talking about roughly the same concept.

[matthewcrews]

I would like to point out that bloc is not an abbreviation. The definition is a group of aligned political parties or countries which kind of makes sense (https://www.dictionary.com/browse/bloc). An immutable array is a set of aligned data underneath. Makes sense to me 🤷‍♂️.

[realparadyne]

Is there a reason range was never voted on?

Range is already a .net type. https://docs.microsoft.com/en-us/dotnet/api/system.range?view=net-5.0

[roboz0r]

I'd be quite happy with block as the new term. I dislike imray and variants as contractions and compound words are much worse to say and also difficult to distinguish from array at a glance in code. My only other suggestion would be column. It's short and has the right connotations. The use of a column in a database refers to elements of a single type which is consistent here and a column in a building refers to a core element that holds up the rest of the building and shouldn't be modified. I dislike row as a database row contains multiple types and an immutable array does not.

[lfr]

I also like that just by having one less letter, bloc makes signatures less clunky, here's the block's version of Array.append's tooltip:

// block1:'T block -> block2:'T block -> 'T block 😵
Block.append

And the version with bloc:

// bloc1:'T bloc -> bloc2:'T bloc -> 'T bloc
Bloc.append

Signature characters are prime real estate 🏛

[dsyme]

Hi all,

It's time to close out this long discussion. We will proceed to the RFC using block and Block.

Thanks
Don

[dsyme]

The RFC is here: https://github.com/fsharp/fslang-design/blob/master/RFCs/FS-1094-block.md

[dsyme]

Discussion can continue here: fsharp/fslang-design#528

[dsyme]

Just to say we started using the block naming in the F# compiler codebase and eventually backed it out in favour of explicit ImmutableArray. It was my choice to do this after experiencing it in practice. So my intuition that this naming was good enough was incorrect.

[SamuelBerger]

Just to say we started using the block naming in the F# compiler codebase and eventually backed it out in favour of explicit ImmutableArray. It was my choice to do this after experiencing it in practice. So my intuition that this naming was good enough was incorrect.

😭😭😭
(my code is full of blocks and I like it... a pity it does not become standard F#)

[matthewcrews]

@dsyme would it be possible to get some info on why block was not a good solution? I'm asking purely for my own understanding. I'm curious what the pain point is that precludes this addition to F#.

[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 #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: #619 (comment)

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 dotnet/fsharp#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?