Add ListBuilder API

[krauthaufen]

ListBuilder

I propose we add a new type to FSharp.Core that allows to build lists in a forward-manner (allowing for tail-recursive implementations).
This way we could expose a safe-way of building lists outside FSharp.Core.

I implemented the ListBuilder in my own project using Reflection.Emit but in FSharp.Core this could be done safely and I think many applications could benefit from this.

The existing way of approaching this problem in F# is building lists backwards and then reversing them which is costly and performs lots of allocations. Another way of doing that is by using a non-tail recursion but this tends to crash on large lists.

Pros and Cons

The advantages of making this adjustment to F# are that users could write their own efficient list-combinators that are tail-recursive.

Extra information

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

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

For Readers

If you would like to see this issue implemented, please click the 👍 emoji on this issue. These counts are used to generally order the suggestions by engagement.

[cartermp]

I personally think this would be helpful, but we'd need to consider this vs. taking a dependency on System.Collection.Immutable and offering a ToFSharpList extension on ImmutableListBuilder/ImmutableArrayBuilder etc.

[krauthaufen]

I think when implementing the ListBuilder the ImmutableCollections tools could easily be implemented as extensions using it. However I don't know how you feel about adding a reference to System.Collections.Immutable to FSharp.Core in general, so if this will be done anyways using its builders would certainly be a way to go...

[cartermp]

I would love to add that dependency. But @dsyme and @KevinRansom have expressed a distaste for additional dependencies in the past.

[dsyme]

I would love to add that dependency. But @dsyme and @KevinRansom have expressed a distaste for additional dependencies in the past.

A possibility is that we have a second library FSharp.NotSoCore or FSharp.Core.Extensions or something.

TBH we could even split up FSharp.Core and and use type forwarders, e.g.

 FSharp.Core.Basics.dll
 FSharp.Core.Reflection.dll
 FSharp.Core.Quotations.dll
 FSharp.Core.Query.dll

but it's tiresome and expensive to get that right

[krauthaufen]

I think the ListBuilder should really go into FSharp.Core nonetheless and there it can also be implemented without any reflection things afaik.

[teo-tsirpanis]

FWIW, I have written an implementation of ListBuilder that uses System.Runtime.CompilerSerivces.Unsafe in https://github.com/teo-tsirpanis/Farkle/blob/master/src/Farkle/Collections/ListBuilder.fs. It only supports appending single elements but feel free to customize it for your needs.

It does not use reflection but it is kind of brittle because it depends on the list type's internal structure. Code that is using it should add tests to validate that its behavior does not change in later versions of FSharp.Core.

[dsyme]

See https://github.com/fsharp/fslang-design/blob/main/FSharp-6.0/FS-1099-list-collector.md for fast list and array builders in F# compiler proper

[dsyme]

Completed in F# 6.0