Halfway through the first day of our walking tour of New York, Paul tweets me while Sue and I are riding the Statten Island Ferry, can I extend my lightning talk to the N.Y. F# meetup on Tuesday evening? OK, it ended up making for a much better presentation. I spent the evening cutting down my Lambda Jam presentation to its essence, which I pretentiously titled “Semantically Coherent Functional Linear Data Structures”. The video is here This is the latest incarnation of the thoughts I’ve been trying to express since this blog post about the unity of linear purely functional data structures providing alternate composeable linear views and their capabilities.

I was followed by Rachel Reese’s excellent presentation on F# Agents.

NY Progressive F# Tutorials

Wendy and the Skills Matter crew put on a really nice conference For the NY Progressive F# Tutorials. This was my first experience with a Skills Matter conference, and it won’t be my last. Their reputation preceeds them, and now I can vouch they put on no-nonsense hands-on learning conferences for real practitioners. It helps that they get the best speakers. Don Syme’s keynote is captured on video, and the rest of the sessions on audio.

	Keynote: F# in the Open Source World Don Syme : 18th Sep 2013
	Calling and extending the F# compiler Don Syme and Tomas Petricek : 18th Sep 2013
	FCell: Numerical Development in Excel Tomas Petricek and Adam Mlocek : 18th Sep 2013
	Try F# from Zero to Data Science Rachel Reese and Phil Trelford : 18th Sep 2013
	F# Koans: An Interactive Way to Learn Chris Marinos : 18th Sep 2013
	Keynote: F# Beyond Windows Miguel de Icaza : 18th Sep 2013
	Graph Man Contest Richard Minerich and Paulmichael Blasucci : 18th Sep 2013
	Machine Learning with F# Phil Trelford and Mathias Brandewinder : 18th Sep 2013
	Code Quotations: Code-as-Data for F# Dmitry Mozorov and Jack Pappas : 18th Sep 2013
	Pac-Man Kata Phil Trelford and Mathias Brandewinder : 18th Sep 2013

The finale of the conference was Tyler Smith mopping the floor with me in the Pac Man AI programming competition, a group photo,

and dinner.

The F# conversations lasted until late in the night, I met some more of the international F# set, and once again the F# community was friendly, inclusive, and interested in progressing everyone’s skills and the state of the art.

After the F#

I was kindly invited to see the keynote of the next day’s conference, “Agile Testing & BDD Exchange”, by Gojko Adzic. If you have any interest at all in testing or user experience, I highly recommend this keynote.

Then I was off to the simultaneous Global GameCraft event in the Dumbo Spot annex to Dumbo Loft hosted by Andrea and Phil, where Phil Trelford gave me a personal tutorial on TickSpec, and I could take the time to work up a draft of this article.

Great Lakes Functional Programming Conference and more

I want to give a plug for the upcoming Great Lakes Functional Programming Conference in Detroit, MI on November 9. If you don’t already know, there is a vibrant functional programming community in Detroit, and kudos to Onorio Catenacci for organizing this.

My next talk is coming up on October 3 in San Francisco to the Bay Area Clojure User Group, “F# for Functional Enthusiasts”. Check it out if you are in the area.

Finally, I just have to pass on this little gem which spilled out of this year’s Strange Loop (darn! missed it again this year).

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.

Bibliography for my presentation, Working with Functional Data Structures, Practical F# Application, February 4 at San Francisco F# User Group.

Slides

Purely Functional Data Structures (1996)
Purely Functional Data Structures (1998)

Purely Functional Stepchildren
F# Data Structure Libraries in FSharpx
A Unified Collection of Purely Functional List-like Data Structures
Comparing F# Queues
Semantics and List-like Data Structures
FSharpx.Collections
FSharpx.Collections.Experimental
Double-ended Queues for F#

DS_Benchmark
Benchmarking F# Data Structures — Introduction
Benchmarking F# Data Structures — Loading Data

Eric Lippert’s Comma Quibbling
Nick Palladinos Comma Quibbling
GC Performance Counters
LazyList
Are functional languages inherently slow?
The benefits of purely functional data structures
Functional Pearls Red-Black Trees in a Functional Setting
F# vs Mathematica: red-black trees
Red-Black Tree Remove
Implimenting IComparable in F#
Catamorphism

Last week I blogged about supplementing the FSharpx library with a collection of purely function sequential data structures. This week the news is a restructuring of FSharpx providing for the first time a separate project for experimental data structures. I really like this project set-up as opposed to an experimental branch for accessing experimental structures at the same time as the structures in Core.Collections.

Submit your Data Structures to FSharpx

So let the experimenting begin! The experimental project is actually a copy of the old FSharpx.DataStructures namespace. That namespace has been marked “obsolete” going forward, so if you are using it, switch to FSharpx.Collections.Experimental, which is a separate NuGet package from FSharpx.Core.

Experimental is intended primarily for purely functional (immutable) structures, but feel free to add mutable structures of interest. Good candidates include F# ports of structures available in other functional languages and implementations from academic papers. The main criteria is the structure will be useful and interesting to others. Include some documenting comments and pointers to sources, if appropriate.

Do include tests with your submissions. Not only is that all the QA there is, they also serve as functionality samples.

Staging for the FSharpx.Core library

Collections.Experimental also serves as the staging area for promotion to the FSharpx.Collections and FSharpx.Collections.Mutable namespaces. There is higher acceptance criteria for pull requests here. See the core collections readme. Structures should generally have the look and feel of belonging to a professional library.

There are already several candidates in experimental (in my opinion) worthy of polishing for core collections. I have not taken the time to look closely at most of these, so please excuse me if some of my comments are “uninformed”:

BKTree

In addition to reviewing for core standards, this structure would benefit from review by someone experienced with practical application of distance measures, perhaps adding more distance measures. A quick search of recent F# blogs finds

Revisiting String Distances

F# on Algorithms – Wagner–Fischer algorithm

Edit Distance (EDIST) with F#

Levenshtein Distance and the Triangle Inequality

Metrics on Words

BottomUpMergeSort

Maybe. Needs polishing.

Zippers

There are a couple of zippers in experimental. I’ll leave it to someone who uses these more to determine what it takes to promote them (or not) to core.

IntMap

Needs review for function naming. (Should match naming standard set by MS.FSharp.Collections.Map where appropriate.) Remove some unnecessary module level functions. (E.g. ofArray, which only composes List.ofArray. Better not to hide this from users.) And hide behind an fsi file or entirely remove the “unsafe” functions.

RoseTree

Looks useful. Needs polishing.

TimeSeries

I don’t know about this one.

An exercise for the reader

I recently uploaded EagerRoseTree to experimental. (It’s “eager” because the first RoseTree in experimental implements LazyList for the children forest.) EagerRoseTree is unfinished in many ways.

For one thing it exposes an unsafe internal structure. A user could implement a dysfunctional tree. The children forest is a Vector. This allows for indexed lookups in the EagerRoseTree right out of the box, but updates to forest nodes will only return a new vector, not propagate up to returning a new tree.

Here’s a couple more possibilities:

1) Adapt a zipper to navigate in the tree.

2) Adapt the recently released FsCoreSerializer to serialize this, and other structures.

Upcoming talk on F# Data Structures

If you are in the area, come to my data structures talk at SF F# User Group Monday night, February 4. It’s a great and knowledgeable user group.

The FSharpx.Collections namespace now provides a collection of linear data structures deriving from the List signature. To emphasize the unity of the collection I implemented a standardized nomenclature expanding on the List value names. This is not without controversy. Structures like Queue are well-known in other (mostly imperative) languages, but I believe together these structures exhibit more similarities than differences, and bringing them all together in one F# collection is an opportunity to emphasize that logical unity.

My intent was to expand the List signature nomenclature with the naming standard favored by Okasaki, but “init” as the name for the inverse of “tail” would not do as this conflicts with a List module value. So this value is named “initial”. And I made one other change from Okasaki. In recognition of Steffen Forkmann’s F# implementation of the Vector structure from Clojure being the basis of two structures in this collection (Vector and RandomAccessList), I have opted to name the end-insertion function/member “conj” instead of “snoc”.

The List-like Immutable Data Structures

The following structures provide features perhaps available from List and Array, but not efficiently implemented and/or not in the right combination for a particular task, and the full composability and immutability you expect from purely functional data structures.

Deque (Double-ended queue) is an ordered linear structure implementing the signature of List (head, tail, cons) as well as the mirror-image Vector signature (last, initial, conj). “Head” inspects the first or left-most element in the structure, while “last” inspects the last or right-most element. Ordering is by insertion history.

DList is an ordered linear structure implementing the List signature (head, tail, cons), end-insertion (conj), and O(1) append. Ordering is by insertion history. DList is an implementation of John Hughes’ append list.

Heap is an ordered linear structure where the ordering is either ascending or descending. “Head” inspects the first element in the ordering, “tail” takes the remaining structure after head, and “insert” places elements within the ordering. PriorityQueue is available as an alternate interface.

LazyList is an ordered linear structure implementing the List signature (head, tail, cons), but unlike the other linear structures computation of elements is delayed, executed once on demand, and thereafter cached. Adapted from the PowerPack implementation with the List signature values available from within the type class.

Queue is an ordered linear data structure where elements are added at the end (right) and inspected and removed at the beginning (left). Ordering is by insertion history. The qualities of the Queue structure make elements first in, first out (fifo). “Head” inspects the first or left-most element in the structure, while “conj” inserts an element at the end, or right of the structure.

RandomAccessList is an ordered linear structure implementing the List signature (head, tail, cons), as well as inspection (lookup) and update (returning a new immutable instance) of any element in the structure by index. Ordering is by insertion history.

Vector is an ordered linear structure implementing the inverse of the List signature, (last, initial, conj) in place of (head, tail, cons). Indexed lookup or update (returning a new immutable instance of Vector) of any element is O(log32n) — just about O(1). Length is O(1). Ordering is by insertion history.

Comparing Performance

I recently posted a performance preview of the Queue data structure. Here are the performance benchmarks across the list-like structures, including List and Array from the Microsoft.FSharp.Collections namespace for comparison.

Times are milliseconds on a 2.2GHz 4GB dual core 64-bit Windows 7 machine. Orders of magnitude represent either the beginning or resulting number of elements in the structure. Milliseconds is derived by dividing ticks by 10,000. More on the benchmarking methodology can be found here. The data structure benchmark application can be found here.

Add elements to empty structure

Comments

1) Depending on the structure’s signature by invoking cons or conj using seq.fold.

2) Source data is an ascending ordered integer array, except where noted.

3) Note that repeatedly adding an element to an existing array does not scale.

4) (*) I had trouble getting any Deque benchmarks at scale 1M to complete in reasonable time and have yet to establish whether this is a problem with my benchmark infrastructure or the Deque implementation or a combination thereof.

Initialize structure

Comments

1) Using the respective module’s ofSeq, or different function where indicated.

2) Source data is an ascending ordered integer array, except where noted.

3) Queue and Deque both support O(1) ofList which would load from a list in a fraction of a millisecond.

Peek and Dequeue until the structure is empty

Comments

1) Inspects element with either head or last and recursively takes tail or initial, depending on structure signature.

Use IEnumerable to iterate through each element

Reverse

Append

Comments

1) Using merge for the Heap structure.

Iterate by index

Random lookup (10,000)

Random update (10,000)

Implementation Notes

1) I borrowed the structural equality implementation from Vector for the other structures. Heap perhaps does not need to used Unckecked.equals, but I have not profiled that option to see whether it would actually improve performance. More attention to equality checks taking advantage of internal structure may prove to be somewhat more efficient.

2) The structural equality implementation puts an internal mutable reference value in each structure that gets updated at most once per lifetime. I don’t think this will impede multi-threading use of the structures, but I don’t know for sure either.

3) As noted above there may be issues with Deque at scales >>100K elements. Another Deque in the “experimental” DataStructures namespace may meet the needs of your application better.

There are some useful additions to the F# tool-belt coming up. Microsoft recently released a preview edition of immutable collections, and if all goes as planned I will release a suite of 6 purely functional linear data structures to FSharpx.Collections in just a couple of days.

Queue is a data structure that needs better representation in the functional world, and both collections make contributions, so this is an opportunity to do some performance comparisons of the queues available to F# programmers. The contenders are two queues from the .NET Framework, System.Collections.Generic.Queue and System.Collections.Concurrent.Queue, the upcoming FSharpx.Collections.Queue, and FSharpx.Datastructures.BatchedQueue, from which FSharpx.Collections.Queue was developed.

The first benchmark exercises something like “real world” usage of the queues with the following steps:

1) enqueue the number of elements indicated

2) peek and dequeue half that number

3) enqueue the same number to the resulting queue

4) peek and dequeue half the resulting size of that queue

5) enqueue one more time the original number

(Milliseconds on a 2.2GHz 4GB dual core 64-bit Windows 7 machine)

And then the obligatory “not so real world” benchmarks

Enqueue the indicated number of elements

Peek and Dequeue until the queue is empty

Initialize from a sequential source (an array unless otherwise indicated)

(The preview Immutable.Queue does not yet implement this capability.)

Use IEnumerable to iterate through each element

(queue of indicated size)

So which Queue is right for You?

That of course depends on your application. For raw speed the system generic queue is hard to beat. The concurrent queue compares well against generic in all categories in a single-threaded environment, so for raw speed it should be a contender in multi-threaded environments, unless composability and immutability is preferred.

Preview Immutable.Queue seems primarily intended for the C# world, but has adequate composability to make it suitable for F#. FSharpx.Collections.Queue performs just as well (sometimes better), and has a broader range of supporting functions including fold, foldback, reverse (usually O(1), worst case O(n)), ofSeq, and ofList.