New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

A normative immutable array type #619

Open
dsyme opened this Issue Nov 14, 2017 · 41 comments

Comments

Projects
None yet
@dsyme
Collaborator

dsyme commented Nov 14, 2017

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

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

This comment has been minimized.

Show comment
Hide comment
@gerardtoconnor

gerardtoconnor Nov 14, 2017

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.

gerardtoconnor commented Nov 14, 2017

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

This comment has been minimized.

Show comment
Hide comment
@tldrlol

tldrlol Nov 14, 2017

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

tldrlol commented Nov 14, 2017

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

@ijsgaus

This comment has been minimized.

Show comment
Hide comment
@ijsgaus

ijsgaus Nov 14, 2017

Maybe, FrozenArray

ijsgaus commented Nov 14, 2017

Maybe, FrozenArray

@forki

This comment has been minimized.

Show comment
Hide comment
@forki

forki Nov 14, 2017

Member

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

Member

forki commented Nov 14, 2017

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

@forki

This comment has been minimized.

Show comment
Hide comment
@forki

forki Nov 14, 2017

Member

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

Member

forki commented Nov 14, 2017

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

@gerardtoconnor

This comment has been minimized.

Show comment
Hide comment
@gerardtoconnor

gerardtoconnor Nov 14, 2017

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

gerardtoconnor commented Nov 14, 2017

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

This comment has been minimized.

Show comment
Hide comment
@rmunn

rmunn Nov 15, 2017

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.

rmunn commented Nov 15, 2017

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

This comment has been minimized.

Show comment
Hide comment
@realvictorprm

realvictorprm Nov 15, 2017

Member

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...

Member

realvictorprm commented Nov 15, 2017

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

This comment has been minimized.

Show comment
Hide comment
@mexx

mexx Nov 15, 2017

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?

mexx commented Nov 15, 2017

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

This comment has been minimized.

Show comment
Hide comment
@rmunn

rmunn Nov 16, 2017

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(N2). So the suggestion of changing List to be array-backed turns out to be a bad idea, and thankfully it will never happen.

rmunn commented Nov 16, 2017

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(N2). So the suggestion of changing List to be array-backed turns out to be a bad idea, and thankfully it will never happen.

@smoothdeveloper

This comment has been minimized.

Show comment
Hide comment
@smoothdeveloper

smoothdeveloper Nov 16, 2017

@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?

smoothdeveloper commented Nov 16, 2017

@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

This comment has been minimized.

Show comment
Hide comment
@mexx

mexx Nov 16, 2017

@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.

mexx commented Nov 16, 2017

@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

This comment has been minimized.

Show comment
Hide comment
@dsyme

dsyme Nov 16, 2017

Collaborator

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

Collaborator

dsyme commented Nov 16, 2017

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

This comment has been minimized.

Show comment
Hide comment
@dsyme

dsyme Nov 16, 2017

Collaborator

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

Collaborator

dsyme commented Nov 16, 2017

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

@dsyme dsyme changed the title from What to do about an immutable array type to A normative immutable array type Nov 16, 2017

@Tarmil

This comment has been minimized.

Show comment
Hide comment
@Tarmil

Tarmil Nov 17, 2017

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

Tarmil commented Nov 17, 2017

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

@dsyme

This comment has been minimized.

Show comment
Hide comment
@dsyme

dsyme Nov 17, 2017

Collaborator

@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();;
Collaborator

dsyme commented Nov 17, 2017

@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

This comment has been minimized.

Show comment
Hide comment
@gerardtoconnor

gerardtoconnor Nov 17, 2017

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 commented Nov 17, 2017

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

This comment has been minimized.

Show comment
Hide comment
@gerardtoconnor

gerardtoconnor Nov 17, 2017

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)

gerardtoconnor commented Nov 17, 2017

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

This comment has been minimized.

Show comment
Hide comment
@piaste

piaste Nov 19, 2017

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.

piaste commented Nov 19, 2017

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

This comment has been minimized.

Show comment
Hide comment
@xperiandri

xperiandri Nov 19, 2017

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.

xperiandri commented Nov 19, 2017

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

This comment has been minimized.

Show comment
Hide comment
@rmunn

rmunn Nov 20, 2017

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.

rmunn commented Nov 20, 2017

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

This comment has been minimized.

Show comment
Hide comment
@Tarmil

Tarmil Nov 20, 2017

@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.

Tarmil commented Nov 20, 2017

@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

This comment has been minimized.

Show comment
Hide comment
@dsyme

dsyme Nov 23, 2017

Collaborator

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

Collaborator

dsyme commented Nov 23, 2017

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

This comment has been minimized.

Show comment
Hide comment
@dsyme

dsyme Nov 23, 2017

Collaborator

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

Collaborator

dsyme commented Nov 23, 2017

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

This comment has been minimized.

Show comment
Hide comment
@vasily-kirichenko

vasily-kirichenko Nov 23, 2017

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.

vasily-kirichenko commented Nov 23, 2017

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

This comment has been minimized.

Show comment
Hide comment
@piaste

piaste Nov 23, 2017

🤘 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.

piaste commented Nov 23, 2017

🤘 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.

@xperiandri

This comment has been minimized.

Show comment
Hide comment
@xperiandri

xperiandri Nov 23, 2017

Let it be breaking change. Just increment F# version to 5.0 and let's use new cool things.
The idea of resolving [] to the inferred collection type is the best change in my opinion.
I will finally be able to use my favorite System.Collections.Immutable and don't care about F# specific collection anymore.

xperiandri commented Nov 23, 2017

Let it be breaking change. Just increment F# version to 5.0 and let's use new cool things.
The idea of resolving [] to the inferred collection type is the best change in my opinion.
I will finally be able to use my favorite System.Collections.Immutable and don't care about F# specific collection anymore.

@smoothdeveloper

This comment has been minimized.

Show comment
Hide comment
@smoothdeveloper

smoothdeveloper Nov 23, 2017

Let it be breaking change. Just increment F# version to 5.0 and let's use new cool things.

We could take an approach which doesn't split the eco system (like the mistake which python did), by having those things behind flags which are set by default on new projects (like C# is doing with nullable reference type if I understand correctly).

I like the idea of list like literals to support different types depending on the type information at hand.

smoothdeveloper commented Nov 23, 2017

Let it be breaking change. Just increment F# version to 5.0 and let's use new cool things.

We could take an approach which doesn't split the eco system (like the mistake which python did), by having those things behind flags which are set by default on new projects (like C# is doing with nullable reference type if I understand correctly).

I like the idea of list like literals to support different types depending on the type information at hand.

@rmunn

This comment has been minimized.

Show comment
Hide comment
@rmunn

rmunn Nov 24, 2017

I was halfway through writing a suggestion for a custom literal syntax a couple days ago, but quit writing because I wasn't coming up with good ideas. But this suggestion of overloading [] to declare a literal of appropriate types is an excellent one, as long as the details can be worked out. I'll create a suggestion for it so that it can be tracked separately from the "immutable array" suggestion.

rmunn commented Nov 24, 2017

I was halfway through writing a suggestion for a custom literal syntax a couple days ago, but quit writing because I wasn't coming up with good ideas. But this suggestion of overloading [] to declare a literal of appropriate types is an excellent one, as long as the details can be worked out. I'll create a suggestion for it so that it can be tracked separately from the "immutable array" suggestion.

@alfonsogarciacaro

This comment has been minimized.

Show comment
Hide comment
@alfonsogarciacaro

alfonsogarciacaro Nov 27, 2017

For the record, about Fable it's necessary to tell the difference between the model (which is preferably immutable so it would benefit of an immutable array structure, though at the same time I need arrays usually for pools in games and this requires mutation) and the React bindings, which indeed use the list syntax because it's more idiomatic and convenient in F# but compile to neither a list nor an array, see #625 (comment)

alfonsogarciacaro commented Nov 27, 2017

For the record, about Fable it's necessary to tell the difference between the model (which is preferably immutable so it would benefit of an immutable array structure, though at the same time I need arrays usually for pools in games and this requires mutation) and the React bindings, which indeed use the list syntax because it's more idiomatic and convenient in F# but compile to neither a list nor an array, see #625 (comment)

@wanton7

This comment has been minimized.

Show comment
Hide comment
@wanton7

wanton7 Jan 30, 2018

ReadOnlySpan<T> won't work because it's a stack only type. How about using upcoming ReadOnlyMemory<T> for immutable array? Bonus is that it also supports native memory or slice of an array. It's also easily converted to ReadOnlySpan<T>. Implementation is here https://github.com/dotnet/corefx/blob/master/src/Common/src/CoreLib/System/ReadOnlyMemory.cs
Little bit more info about it here https://msdn.microsoft.com/en-us/magazine/mt814808.aspx

wanton7 commented Jan 30, 2018

ReadOnlySpan<T> won't work because it's a stack only type. How about using upcoming ReadOnlyMemory<T> for immutable array? Bonus is that it also supports native memory or slice of an array. It's also easily converted to ReadOnlySpan<T>. Implementation is here https://github.com/dotnet/corefx/blob/master/src/Common/src/CoreLib/System/ReadOnlyMemory.cs
Little bit more info about it here https://msdn.microsoft.com/en-us/magazine/mt814808.aspx

@realvictorprm

This comment has been minimized.

Show comment
Hide comment
@realvictorprm

realvictorprm Jan 30, 2018

Member
Member

realvictorprm commented Jan 30, 2018

@wanton7

This comment has been minimized.

Show comment
Hide comment
@wanton7

wanton7 Jan 31, 2018

Noticed one thing about ReadOnlyMemory is that it can it can't be enumerated. You have to corvert it to Span first using .Span property. Both are structs so this won't cause any memory allocations.

wanton7 commented Jan 31, 2018

Noticed one thing about ReadOnlyMemory is that it can it can't be enumerated. You have to corvert it to Span first using .Span property. Both are structs so this won't cause any memory allocations.

@Rickasaurus

This comment has been minimized.

Show comment
Hide comment
@Rickasaurus

Rickasaurus Feb 1, 2018

Please don't break the existing functionality. I know it would look nicer in demos but some of us have a whole lot of F# code to maintain at our companies and it would not be a good look to upper management to have delays because the language's compatibility was broken.

Keep in mind this would also break a huge number of existing training materials and online code samples too.

Rickasaurus commented Feb 1, 2018

Please don't break the existing functionality. I know it would look nicer in demos but some of us have a whole lot of F# code to maintain at our companies and it would not be a good look to upper management to have delays because the language's compatibility was broken.

Keep in mind this would also break a huge number of existing training materials and online code samples too.

@xperiandri

This comment has been minimized.

Show comment
Hide comment
@xperiandri

xperiandri Feb 2, 2018

@Rickasaurus, for major release it is OK.
You can stay on previous version or add annotations to some places in code.
Will we stop evolution only because it requires some changes?

Like with C# when you can set language version per project will allow to preserve compatibility.

xperiandri commented Feb 2, 2018

@Rickasaurus, for major release it is OK.
You can stay on previous version or add annotations to some places in code.
Will we stop evolution only because it requires some changes?

Like with C# when you can set language version per project will allow to preserve compatibility.

@cartermp

This comment has been minimized.

Show comment
Hide comment
@cartermp

cartermp Feb 3, 2018

Member

@xperiandri C# does not make (intentional) breaking changes, either. The philosophy for all .NET languages is that they are "append-only". I definitely don't think that a breaking change just to make array syntax nicer is worth it. A source-breaking change for F# would have to be a monumentally useful feature for us to even entertain the idea, let alone plan for it.

Member

cartermp commented Feb 3, 2018

@xperiandri C# does not make (intentional) breaking changes, either. The philosophy for all .NET languages is that they are "append-only". I definitely don't think that a breaking change just to make array syntax nicer is worth it. A source-breaking change for F# would have to be a monumentally useful feature for us to even entertain the idea, let alone plan for it.

@enricosada

This comment has been minimized.

Show comment
Hide comment
@enricosada

enricosada Feb 5, 2018

as previously said, .NET is finally adding high performance (who support both native and manager collections) as span and memory

With readonly version too (so immutable).

this is going to impact .net a lot. why?
because reader/mapper func are going to accept Span<char>, like for parsing json or such, removing lots of benefits of using System.Collections.Immutable and alike data structured (never performant because allocate and basic stuff doesnt work with that, instead work with array+position), who can be replaced by array casted as ReadonlySpan.
So in time, that usage will bubble up to all functions hopefully, making functions more pure ( https://github.com/dotnet/corefxlab/blob/master/docs/specs/span.md#data-pipelines ).

Continuing to allocate immutable arrays, just to say immutable as is fixed length + fixed values, is not the best perf wise (and if span is adopted a lot, mean friction with existing .net code).
just convert it as ReadonlySpan when done.

some info in https://msdn.microsoft.com/en-us/magazine/mt814808.aspx

Just to say, if we need to add a new sintax for immutable, use that for Span/ReadonlySpan/Memory/ReadonlyMemory, not ImmutableArray, who is just a time band-aid now. otherwise we lose an opportunity to remove friction with .net, using a "not so used" library

enricosada commented Feb 5, 2018

as previously said, .NET is finally adding high performance (who support both native and manager collections) as span and memory

With readonly version too (so immutable).

this is going to impact .net a lot. why?
because reader/mapper func are going to accept Span<char>, like for parsing json or such, removing lots of benefits of using System.Collections.Immutable and alike data structured (never performant because allocate and basic stuff doesnt work with that, instead work with array+position), who can be replaced by array casted as ReadonlySpan.
So in time, that usage will bubble up to all functions hopefully, making functions more pure ( https://github.com/dotnet/corefxlab/blob/master/docs/specs/span.md#data-pipelines ).

Continuing to allocate immutable arrays, just to say immutable as is fixed length + fixed values, is not the best perf wise (and if span is adopted a lot, mean friction with existing .net code).
just convert it as ReadonlySpan when done.

some info in https://msdn.microsoft.com/en-us/magazine/mt814808.aspx

Just to say, if we need to add a new sintax for immutable, use that for Span/ReadonlySpan/Memory/ReadonlyMemory, not ImmutableArray, who is just a time band-aid now. otherwise we lose an opportunity to remove friction with .net, using a "not so used" library

@kspeakman

This comment has been minimized.

Show comment
Hide comment
@kspeakman

kspeakman Apr 1, 2018

From the original post, my vote would be for a bespoke type that is a persistent "vector" or whatever you want to call it. The array from System.Collections.Immutable has O(n) add operations, and in general will not support a lot of copying or larger arrays since it duplicates the array each time it changes. What we need is a persistent structure with structural sharing. If the PersistentVector from Fsharpx is appropriate, I'd be for just including that. I'd love to see first class support including literal syntax for it.

kspeakman commented Apr 1, 2018

From the original post, my vote would be for a bespoke type that is a persistent "vector" or whatever you want to call it. The array from System.Collections.Immutable has O(n) add operations, and in general will not support a lot of copying or larger arrays since it duplicates the array each time it changes. What we need is a persistent structure with structural sharing. If the PersistentVector from Fsharpx is appropriate, I'd be for just including that. I'd love to see first class support including literal syntax for it.

@kkm000

This comment has been minimized.

Show comment
Hide comment
@kkm000

kkm000 Sep 19, 2018

Would it look weird to extend comprehension syntax with explicit construction head identifier, like we have with the seq, to other collection data types? If I can initialize a sequence as

seq { 1; 2; 3 }

would it make sense to extend that--to both existing and added data collections?

let yourOldFriendList = list { 1; 2; 3 }  // Same as [1;2;3]
let regularArray = array { 1..20 }  // Same as [| 1..20 |]
let immutable = roarray { for n in 1..10 -> n*n }  

Maybe not the sweetest syntactically, but adding [! !], [$ $], [@ @], [% %]--where does it end? The more of these compound braces are added, the more confusing is what is what. I'd prefer to go explicit, if the head id is not very long (a sesquipedalianimmutableArray won't do).

At the farthest reach, maybe allowing operator syntax

let inline ([! !]) = roarray

for the brace afficionados out there could bridge the gap?

This has a C# counterpart

var vector = new List<int>() { 1, 2, 3 };

This can work in pattern matching, too

match arr with
| roarray { 0; _; _ } -> ...

possibly optional for otherwise inferrible collection type

match (arr:roarray<_>) with
| { 0; x; _ } -> ...

The latter syntax is lighter, but might get a bit too LISPy if nested deeply.

Also, for inexplicable aesthetic reasons, roarray seems much better than immarray to me. I do not have an idea how to pronounce the latter.

kkm000 commented Sep 19, 2018

Would it look weird to extend comprehension syntax with explicit construction head identifier, like we have with the seq, to other collection data types? If I can initialize a sequence as

seq { 1; 2; 3 }

would it make sense to extend that--to both existing and added data collections?

let yourOldFriendList = list { 1; 2; 3 }  // Same as [1;2;3]
let regularArray = array { 1..20 }  // Same as [| 1..20 |]
let immutable = roarray { for n in 1..10 -> n*n }  

Maybe not the sweetest syntactically, but adding [! !], [$ $], [@ @], [% %]--where does it end? The more of these compound braces are added, the more confusing is what is what. I'd prefer to go explicit, if the head id is not very long (a sesquipedalianimmutableArray won't do).

At the farthest reach, maybe allowing operator syntax

let inline ([! !]) = roarray

for the brace afficionados out there could bridge the gap?

This has a C# counterpart

var vector = new List<int>() { 1, 2, 3 };

This can work in pattern matching, too

match arr with
| roarray { 0; _; _ } -> ...

possibly optional for otherwise inferrible collection type

match (arr:roarray<_>) with
| { 0; x; _ } -> ...

The latter syntax is lighter, but might get a bit too LISPy if nested deeply.

Also, for inexplicable aesthetic reasons, roarray seems much better than immarray to me. I do not have an idea how to pronounce the latter.

@dsyme

This comment has been minimized.

Show comment
Hide comment
@dsyme

dsyme Oct 12, 2018

Collaborator

From the original post, my vote would be for a bespoke type that is a persistent "vector" or whatever you want to call it. The array from System.Collections.Immutable has O(n) add operations, and in general will not support a lot of copying or larger arrays since it duplicates the array each time it changes.

This is a hard call and really depends on what average/max size you expect the collections to have. For a vast number of workaday symbolic programming purposes the use of an O(n) immutable array type is fine.

I'm particularly aware that Fable and Fabulous user interface models benefit enormously from better support for immutable collections, and that these nearly always need only small collections (e.g. < 1,000 elements). But equally there are use cases where incremental update with sharing is important too.

Collaborator

dsyme commented Oct 12, 2018

From the original post, my vote would be for a bespoke type that is a persistent "vector" or whatever you want to call it. The array from System.Collections.Immutable has O(n) add operations, and in general will not support a lot of copying or larger arrays since it duplicates the array each time it changes.

This is a hard call and really depends on what average/max size you expect the collections to have. For a vast number of workaday symbolic programming purposes the use of an O(n) immutable array type is fine.

I'm particularly aware that Fable and Fabulous user interface models benefit enormously from better support for immutable collections, and that these nearly always need only small collections (e.g. < 1,000 elements). But equally there are use cases where incremental update with sharing is important too.

@kspeakman

This comment has been minimized.

Show comment
Hide comment
@kspeakman

kspeakman Oct 12, 2018

When I originally commented, I was facing a case where I had a context, and I wanted to add things to it, and ordering is important. A list works perfectly fine here but I suppose I felt it has awkward semantics. I was looking for an immutable collection with value equality and append semantics. With list, I had taken to naming it something like ItemsRev. Hopefully whoever used the list would take the hint that they had to reverse the list to read it. Or else I kept the list in read order, and hopefully whoever added to it uses List.append. But even though the amount of items is low enough not to really matter for perf, it feels awkward to use either way.

So my consideration for something like a vector had more to do with semantics while keeping reasonable perf. The built in immutable array could work here, but it also feels awkward to use being object-based whereas most of our stuff uses data + functions semantics. I could write some helper functions to adapt usage like I did with StringBuilder.

I ended up just using List and appending every time.

kspeakman commented Oct 12, 2018

When I originally commented, I was facing a case where I had a context, and I wanted to add things to it, and ordering is important. A list works perfectly fine here but I suppose I felt it has awkward semantics. I was looking for an immutable collection with value equality and append semantics. With list, I had taken to naming it something like ItemsRev. Hopefully whoever used the list would take the hint that they had to reverse the list to read it. Or else I kept the list in read order, and hopefully whoever added to it uses List.append. But even though the amount of items is low enough not to really matter for perf, it feels awkward to use either way.

So my consideration for something like a vector had more to do with semantics while keeping reasonable perf. The built in immutable array could work here, but it also feels awkward to use being object-based whereas most of our stuff uses data + functions semantics. I could write some helper functions to adapt usage like I did with StringBuilder.

I ended up just using List and appending every time.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment