Monthly Archives: September 2012

My Suggestions for New F# Language Features

Posted on by
Reply

I recently had the opportunity to communicate my suggestions for F# to a member of the F# team. Here is my message.

Sorry I haven't used your unicode operator add-on yet. As I explained,
right now I am doing all open source development, so I currently need to
write source everyone can use. I do think this would be a good language
integrated feature. I am thinking of your examples of math-oriented
analysts like actuaries, etc. able to integrate the math and logic
symbols they use right into the language. (So that is feature #1.)

Feature #2a. I have been busy adding Functional Data Structures to
FSharpx.Core.Datastructures. There are now many (and more to come)
structures that implement "cons", "head", and "tail". It would be very
good if the List cons operator :: and cons pattern discriminator ::
could be reused by other data structures that implement cons, head, and
tail. Perhaps this could be done through an interface, call it ICons or
IHeadTail, or something like that. (Reference IRandomAccessList, IDeque,
and IHeap in FSharpx.Core.Datastructures.)

Feature #2b. Several FSharpx.Core.Datastructures structures (more to
come) implement snoc (the inverse of cons). A reusable snoc operator and
pattern discriminator would be good (I propose ;;). Once again maybe an
interface could enable this. (Reference IDeque and DList [conj in DList,
which could be implemented with a proper name of "snoc"] in
FSharpx.Core.Datastructures.)

Feature #2c. Easy reuse of some other operators. I haven't experimented
much with others, so I might be giving you a wrong example, but I think
there are issues with re-using + (plus), for example.

Feature #3. Not really a language feature. I have never used
Mathematica, but I have a vague understanding of Mathematica Notebooks.
An integrated scripts / type provider explorer / graphics environment
with intellisense and integrated help like this would be great.

Thanks for your interest in my opinion and your great work on F#.

I went to post one of these suggestions to Visual Studio User Voice, only to find I have run out of votes. Anyone interested (especially in item #2a) is invited to post these themselves.

It’s great the F# team is so interested in outreach and continues improving the language.

Silicon Valley Code Camp 2012

Posted on by
Reply

I’m pleased to announce I will be speaking at this year’s Silicon Valley Code Camp on Saturday, October 6 at 3:30 PM. My session, Working with Functional Data Structures, Practical F# Application, extends my recent articles on the topic. Here is the session description


Beyond the bread-and-butter singly linked list are dozens of practical Functional Data Structures available to mask complexity, enable composition, and open possibilities in pattern matching. This session focuses on data structures available today in F#, but has practical application to most any functional language. The session covers what makes these structures functional, when to use them, why to use them, choosing a structure, time complexity awareness, garbage collection, and practical insights into creating and profiling your own Functional Data Structure. This session is intended for intermediate level functional programmers and above, but should be of interest to functional programming newbies as well.

SVCC 2012 is two full days of tech talk, including breakfasts and lunches, and it’s all FREE! But you have to register. Dozens of interesting and useful sessions, great speakers, thousands of coders / hackers / technophiles, and did I mention free food?

So click my session above (it helps promote my talk) then check out the rest of the SVCC site and register.

Double-ended Queues for F#

Posted on by
Reply

Thanks to the FSharpx team I had the opportunity to add double-ended queues to FSharpx.Core. Think of double-ended queues, or deques (Okasaki’s spelling, which I like), as lists that work in both directions. They have mirror image values to the familiar head and tail, namely last and init, and a value doing the mirror image operation of cons named snoc (cons spelled backwards). Imagine the possibilities of list when you can also add and remove elements on the end. For instance use pattern matching on head and last.

match q with
| Cons(hd, Snoc(mid, lst)) -> hd, mid, lst  //first, middle, and last
| _ -> ...

Which deque is right for you?

The four deques available in FSharpx.Core implement the following signature

inherit System.Collections.IEnumerable
inherit System.Collections.Generic.IEnumerable<'a>

Cons : 'a -> IDeque<'a>
Head : unit -> 'a
Init : unit -> IDeque<'a>
IsEmpty : unit -> bool
Last : unit -> 'a
Length : unit -> int
Snoc : 'a -> IDeque<'a>
Tail : unit -> IDeque<'a>
Uncons : unit -> 'a * IDeque<'a>
Unsnoc : unit -> IDeque<'a> * 'a

They also all have a module level value of OfCatLists which concatenates two lists to create a deque. Deques internally implement two lists (or lazy lists) with the second list reversed. That’s basically all there is to allowing concatenations at both ends. (For in depth discussion of double-ended queues see either Okasaki’s thesis or his book.) This makes the OfCatLists operation a very fast way to concatenate two lists. Across all four deque implementations the operation is competitive with the FSharpx data structure DList (Difference List) which implements an append value that is truly O(1). OfCatLists is not truly O(1), but two of the deque structures, Deque and BatchedDeque, actually out-perform DList right through a scale of concatenating 10,000 element lists with DList only barely out-performing them at 100,000. (To be sure we are talking time scales of less than 0.3 milliseconds on a 64-bit system.)

Two deques, BankersDeque and RealTimeDeque implement additional values

Lookup : int -> BankersDeque<'a>
Remove : int -> BankersDeque<'a>
TryRemove : int -> BankersDeque<'a> option
Rev : unit -> BankersDeque<'a>
Update : int -> 'a -> BankersDeque<'a> option
TryUpdate : int -> 'a -> BankersDeque<'a> option

Rev is always O(1), a nice feature of deques.

Although nowhere near as adept at the update operation as the AltBinaryRandomAccessList data structure (specifically designed for update), deques exhibit good across the board performance in the index enabled operations Lookup, Remove and Update. They have a theoretical worst case time complexity of ~O(n/2) on index operations because the elements are partitioned in two lists.

But watch out! The actual time complexity on index operations is O(d), where “d” is the displacement into the internal list containing the indexed element. The relative sizes of the internal lists can vary. BankersDeque and RealTimeDeque require a “front-back stream ratio constant” in their construction. I’ve implemented a default value of 2 where this is required, but you can also specify a higher value. Essentially it insures neither list is ever larger than a constant times the size of the other list. BatchedDeque does nothing with the relative sizes until you request a Tail or Init, then it brings the lists into a relation of neither being more than twice the size of the other. And finally Deque is a naive implementation that does not regulate the relative sizes at all.

They all implement IEnumerable and have available all the Seq module values, but be sure to always use the native Lookup and not Seq.nth. This is one of those cases where straight-up comparisons of time complexity (~O(n/4) versus O(n) over many random iterations) does not tell the whole performance story. Actual Seq.nth performance is much worse than the time complexity would suggest.

So, which deque is right for your purposes? As is always the case with complexity that makes reasoning about performance hard, do your own profiling!