I wasn’t expecting it, but there have been some breakthroughs in available functional data structures for F#. I’m talking about speed and versatility, and as always, composability. Now available in FSharpx.Collections.Experimental (and on NuGet) is by far the fastest linear functional data structure (for what it does), FlatList. It’s been available as an internal type for some time as part of the OS F# compiler code. Now for the first time it’s available as a stand-alone type in a component library with intellisense documentation.
It’s implemented as a struct and uses an array as internal storage, so it is just blazing fast (as fast as an array) at what it does best:
Item get
ofSeq
IEnumerable
rev
…and almost all of the array module members (plus some).
What it’s not so fast at (like array) is append. So it’s best loaded from an IEnumerable object rather than built up one element at a time.
Try it out, and post any feedback to the FSharpx GitHub issues. After sufficient beta testing we will graduate it to the FSharpx.Collections namespace.
More to come
I don’t want to steal his thunder, but there is someone quietly working on some more functional data structures that I hope to see soon in FSharspx.
First there’s a performance improvement to the already fast FSharpx.Collections.Vector (actually a new implementation). The speed increases I’m talking about are in the range of 2:1 to 5:1. And a wider range of module function bindings. Very cool.
Next there’s a unique and very versatile functional structure that does about anything you would ever want from a linear structure. I already have some plans for this one.
I’ve already had my hands on these two. They are real. He’s also working on at least one non-linear functional structure I have not evaluated yet, but based on past performance I have high expectations.
Pingback: F# Weekly #14, 2013 | Sergey Tihon's Blog
Not sure if your interested in a port of a hybrid linear data-structure that I have used a bit which is available here – https://gist.github.com/anonymous/4560647 (or not sure if something like this already exists?)
It contains immutable access to an underlying array and a root object that allows you to add items to the start of the array (useful for things such as market data when the 0th index always refers to today, 1st index yesterday, etc.)
It has a infinite growth, or rolling window mode.
It has O(1) random access, amortized O(1) add item to start, O(N) to spawn another root.
Anyway, I’m happy to write a f# port if you think anyone would be interested.
Do some benchmarks with existing structures in FSharpx.Collections and see if FrontLoader is faster or has new features of interest. It sounds like similar functionality to RandomAccessList https://github.com/fsharp/fsharpx/blob/master/src/FSharpx.Core/Collections/RandomAccessList.fsi . Even if it is the same functionality, it may have interest for its unique implementation. One important interest for F# is composability, so take a look at these guidelines
https://github.com/fsharp/fsharpx/tree/master/src/FSharpx.Core/Collections and consider whether you want to add FrontLoader to FSharpx.Collections.Experimental. You might also look at this discussion thread https://github.com/fsharp/fsharpx/issues/214 .
Maybe this is a stupid question. But what would be the main advantage of using FlatList instead of the Array class?
Ist the FlatList basically an Array without all the methods that require mutability? like “x.Item with Set(i,T)”
“Advantage” is a loaded word. FlatList is another tool in your tool belt. In this case the tool is very much like another tool (Array), except, as you noted, it is immutable. So its advantage is when you either need or want immutability. Some people prefer to code by default in a purely functional style, and within the limits of its available functions, FlatList is way faster than other linear functional data structures, with the append function being a notable exception. There might be some case of functional composition where Array will not work and FlatList does, but I can’t think of it off the top of my head. You (and I also) should investigate its use in the compiler code, for which there is a link in the article. That will probably answer your questions better.