[RFC FS-1094 Discussion] - "block" for immutable arrays

[dsyme]

Discussion thread for RFC FS-1094 block as FSharp.Core collection, an abbreviation for System.Collections.Immutable.ImmutableArray

[dsyme]

Please add comments below if you'd like to contribute to the implementation of this RFC.

Performance and correctness testing will be two important areas of work

[bmitc]

Will this include a 2D block type, similar to Array2D? I think that could be useful. If so, it would be nice to have a more complete collection of higher-order functions than Array2D.

[dsyme]

Good question.

FWIW I wonder if all this should go in a separate DLL FSharp.Collections.Block since we are not using the type in FSharp.Core.

[charlesroddie]

I wonder if it is worth adjusting the Block module rather than just adapting List/Array/Seq APIs verbatim, to smooth migration from list and emphasize performance. I recently did an ImmutableArray migration and found:

• It's convenient to have inputs to map take IReadOnlyCollection instead of block. This allows you, for example, to map an FSharpList into a Block. This helps to convert lists to blocks in APIs where existing users expect to input lists. Alternatively this could be an additional method Block.mapFromCollection. (IReadOnlyCollection rather than seq since getting the Length is important for efficient instantiation.)
• Existing collection functions tend to have null checks at the start, but that is not necessary now that .Net has NRTs.
• Some common module functions don't seem necessary, where Seq versions are efficient. Seq.iter, Seq.find, and others. (At least, they feel efficient to me because of how they work, but I haven't benchmarked.)
• Good to have V methods, i.e. ValueOption, since a theme of block is performance.

I copied my module implementing Block functions into this gist with the new terminology but it's all routine.

[Happypig375]

Maybe for all purposes of construction, ImmutableArray<'T> is returned, while for all purposes of deconstruction, IReadOnlyCollection<'T>/IReadOnlyList<'T> is accepted?

[dsyme]

I wonder if it is worth adjusting the Block module rather than just adapting List/Array/Seq APIs verbatim, to smooth migration from list and emphasize performance. I recently did an ImmutableArray migration and found:

I think inconsistency between Block and List/Array/Seq would be too high a price to pay.

Good to have V methods, i.e. ValueOption, since a theme of block is performance.

If we add for one collection type, we should add for all, per the design principles laid down in F# 4.0 collections revamp.

[mo-ba]

https://fsharp.github.io/fsharp-core-docs/reference/fsharp-collections-seqmodule.html#chunkBySize
https://fsharp.github.io/fsharp-core-docs/reference/fsharp-collections-seqmodule.html#windowed
https://fsharp.github.io/fsharp-core-docs/reference/fsharp-collections-seqmodule.html#splitInto

all three functions return: seq<'T[]>

would be nice to have equivalent functions in Seq Module return seq<'T block> and not have to map to block

[asik]

What is the rationale for basing Block on ImmutableArray vs ImmutableList? From my understanding, ImmutableList is optimized for fast updates and larger sets, ImmutableArray is designed to have array-like perf characteristics. What's more important?
See https://devblogs.microsoft.com/dotnet/please-welcome-immutablearrayt/#immutablearrayt-vs-immutablelistt for reference.

Being a value type, ImmutableArray can be default initialized, and it deliberately throws exceptions in that state. It does so for performance reasons - adding checks would prevent some inlining and specific optimizations. That makes it array-like in performance, but also trickier to work with.

Just pointing out some things to think about, I'd love to know more about your thought process in this.

[mo-ba]

imho, array is flawed because it is mutable.
block should give fast access but prevent mutation, for mutation a new block has to be created

[dsyme]

I've gone cold on the whole idea of block

@charlesroddie I've also gone cold on the [: ... :] syntax. It feels like we just need to do something type-directed here, if we do anything. In the long term we surely need something that works for any collection type initializable by enumeration. Would appreciate your thoughts - I guess we can revert back to the original suggestion.

[charlesroddie]

The name isn't very interesting and an abbreviation can be added later. We use ImmArray for module functions.

I think [: :] is great. It's short, ASCII which is an F# requirement, looks like other collections, and if anything is less obtrusive than array syntax.

As soon as you start to care moderately about performance in F# code, ImmutableArray and ValueOption become default choices. So while I don't usually care about brevity, for potentially really common things like ImmutableArray it becomes important.

Of the syntaxes below the second is the best by far. Did you have anything else in mind by type-directed?

ImmutableArray.Create(0, 1, 2) // Current
[: 1; 2; 3 :] // proposed
ImmutableArray { 0; 1; 2 } // type-directed A
{ 1; 2; 3 }: ImmutableArray<int> // type-directed B

I believe ImmutableArray is special and is not just any old collection type but the natural replacement of list/array in many contexts.

[Lanayx]

I also think with the raise of Frozen collections in dotnet8 we should not pay too much attention to particular collection type (and add a new syntax for it) and just converge to type directed collections

let x: Array<int> = [1; 2; 3]
let y: List<int> = [1; 2; 3]
let z: ImmutableArray<int> = [1; 2; 3]

[charlesroddie]

Frozen collections are not relevant because they are specialist dictionary/set functions. They are also specifically designed for creation to involve mutation and to be rare, so would not be candidates for special creation syntax even if they were list-like.

The idea that one would write let x: Array<int> = [ 1; 2; 3 ] instead of let x = [| 1; 2; 3; |], and similarly for list and immutablearray, would be horrifying to most F# programmers. There are more characters, but more importantly in F# you almost never have to add type arguments to known quantitites. In most codebases this never happens. Type-directed stuff is the exception.

The presence of type-directed stuff doesn't prevent the need for syntax, because it can't deprecate standard list and array definitions and will only be used by people who accept type-directed stuff. It will be a very large change to the language and will make the extremely common list syntax ambiguous in the same way that the string syntax is ambiguous now. The current string problem (where a user looks at an sprintf "%A" 0 and takes out the "%A" into a let s = "%A" and gets a build failure) would present itself, but 10,000 more often, since people define list-like things so much more than Printf.StringFormat<...>.

Type-directed collections would need a separate language suggestion and would be a very controversial multi-year debate so should be posted separately.

[Lanayx]

I don't think type directed should be horrifying, it's a very rare case you need to specify the type during the initialization, in most cases it will look like

[1; 2; 3] |> Array.max
[1; 2; 3] |> List.max
[1; 2; 3] |> ImmutableArray.max
[1; 2; 3] |> Set.contains 1
[1; 2; 3] |> FrozenSet.contains 1

Same goes with dictionary, it would be very convinient instead of two syntaxes

[(1, 2); (2, 3)] |> dict |> (fun d -> d.TryGetValue(1))
Map [ (1, 2); (2, 3) ] |> Map.tryFind 1 

to use unified

[(1, 2); (2, 3)] |> Dictionary.tryFind 1
[(1, 2); (2, 3)] |> Map.tryFind 1

As for separate suggestion - there are two and people like them fsharp/fslang-suggestions#625 and fsharp/fslang-suggestions#1086

[nojaf]

@dsyme if the [: :] syntax is still on the table, would it be expected that comprehensions are also supported?

[:
     if foo then yield bar
     match () with
     | _ -> yield! bar2
:]

[charlesroddie]

They are supported for list and array syntaxes so yes they should also be supported for immutablearray.

[dsyme]

So "block" is out the window, and we're back to this I think:

let f0 (xs: int immarray) = 1
let f1 (xs: ImmutableArray<int>) = 1

For collection syntax, there is clearly a need for very lightweight syntax, with comprehension, for every collection type.

I still don't see a "good" solution for this and will throw a few more ideas out there, They are a bit unfiltered but I want to get them into this discussion. TBH I'm feeling bad that after all this time I haven't settled on a design - or when I have I've felt it hasn't been good enough when I've come back to look at it again.

One idea is we could somehow make the [ ... ] and [| ... |] syntaxes optionally user-definable, e.g. some way to redefine this:

let ([_]) xs = ...
let ([|_|]) xs = ...

Then in each file you can get whatever effect you want. Additionally we could throw in a couple of other syntax options

let ([!_!]) xs = ...
let ([$_$]) xs = ...

allowing

[! 1;2;3 !]
[$ 1;2;3 $]

The exact form of the definitions I'm not sure of. Note it's possible [$ 1; 2; 3 $] and [! 1;2;3 !] are breaking changes but maybe not badly, i.e. that would be considered as acceptable.

Each of these definitions would work as eagerly-executing comprehensions. Perhaps the functions would have to provide a collector pattern. Perhaps somehow the functions could also define some kind of way to implement pattern matching for the collection type too.

We could perhaps also allow type, direction disambiguation of these, so instead of

let x: Array<int> = [1; 2; 3]
let y: List<int> = [1; 2; 3]
let z: ImmutableArray<int> = [1; 2; 3]

you could do

let ([_]) xs = ... // some magic to allow type-directed disambiguation of the collection type

let array (xs: 'T array) = xs 
let resizearray (xs: ResizeArray<'T>) = xs 
let immarray (xs: ImmutableArray<'T>) = xs 

let x = array [1; 2; 3]
let y = resizearray [1; 2; 3]
let z = immarray [1; 2; 3]

What would FSharp.Core contain? I'm not sure. Ideally at least a standard definition for immutable arrays.

[charlesroddie]

reconfiguration of existing [ 1; 2; 3 ] and [| 1; 2; 3 |]
FSharp.Core should still define standard, default support for immutable arrays even if it can be reconfigured
[: 1; 2 :] tied to immarray doesn't look right as the one and only thing to add.

The important immediate thing is that we need a definite syntax for immutable arrays. I assume this is what is meant by "standard, default support". To me [: :] is the best syntax, but at this point any concrete syntax will do. [! 1; 2 !] or [$ 1; 2; 3 $] both look stranger but people would get used to them and when I get the syntax PR working it would be easy to adjust to use one of the other two syntaxes to represent ImmutableArray.

The reconfiguration idea is separate and doesn't need deciding as part of this RFC: it's an add-on to default concrete collection syntaxes. We wouldn't want to make this a common thing to do or else all F# materials would need to be rewritten to explain the new (un)meaning of [] and [::]. As a niche thing where a user could redefine [] and which doesn't need to be explained to beginners or normally when reading F# code online, then it's OK. The advantage would be to allow some F# developers to make a local change that allows saving 2 characters. Seems unimportant to me but some people would like it.

[davidglassborow]

Looks like C# is looking at similar questions, providing a new standardised collection syntax that works across types (and guessing the types involved if not specified) - dotnet/csharplang#5354

[Happypig375]

@davidglassborow That's fsharp/fslang-suggestions#1086

[davidglassborow]

Ahh yes sorry. Also relevant to fsharp/fslang-suggestions#625, I'll link it there.

[jwosty]

With regards to the option of making [ ... ] and [| ... |] user-definable, we should consider how this would affect pattern matching, given that both of those can already be used in patterns. It would feel odd to be able to redefine construction but not patterns.

I'm warm to the idea of a new custom delimiter. The fact that it calls out pretty explicitly "hey, I'm using a special custom collection syntax" is a pretty good advantage IMO