F#: Already Engineered for Testability

Posted on March 17, 2013 by Jack Fox

Reading the re-engineering for testability literature and sitting in on presentations on the topic reveals two interesting points. First, only a small minority of developers currently work on applications that have adequate testability built in, and second (and even more interesting) engineering OO applications for testability is a challenging proposition that consumes much of the time of the best people on the project.

OO/imperative computer languages have no inherent qualities that make applications testable. Building in testability requires adhering to conventions: methods that only do one “thing”, at most one side effect per method (and preferably none), no global variables, dependency injection, inversion of control, and so forth. Dependency injection and inversion of control insert their own kind of complexity into the application, and the first three practices can only be enforced by adhering to conventions, but are built-in features of functional language development.

C# code in.NET development for testability starts looking a lot like F#, but looks can be deceiving. In large OO systems C# testability involves thousands of methods held together by careful planning, developer education, an IoC container, and a mocking library, but ultimately it is all held together by relying on the humans writing code working within the conventions of the testability design. Maybe there are even more layers of software and process complexity to assure programmers adhere to the conventions.

So why not build your app in F# to begin with and let the F# compiler enforce testability? In F# functional development pretty much everything is already a function (either a let binding or member binding of a type) or computation expression. If you are re-engineering for testability, instead of incrementally migrating processes to re-engineered OO code written (by convention) to mimic functional code, try incrementally migrating to an F# project with compiler-enforced testability.

Exploiting the built-in testability of F# has been largely overlooked. Perhaps the built-in correctness of functional F# makes testability appear less significant in comparison to the other advantages it has to offer. While much work has been done in developing F# testing tools, much of it has focused on using F# as the test-build language for the other .NET languages. That is very useful, but F# testability spans the unit-integration-regression testing continuum. Let’s go straight to the heart of the matter and advance tools that exploit F#’s testability.

Here’s a place to start: create a Visual Studio add-in to generate function test stubs. I like NUnit and FsUnit so I’m working them into the design. I’ve also come to prefer fsi signature files as the means of exposing API to other files and the public, but currently you either have to hand build the signature file or use the --sig compile option. There needs to be a way to conveniently generate, properly place, and maintain signature files from within the IDE.

Once you have good signature file maintenance it opens up the next possibility, a “shadow” project containing your core project’s code files, but not the signature files. Why would you want to do this? To reference the shadow project in your test project so it has access to all function bindings, not just the ones exposed by the signature file. (There is likely a more clever way to accomplish the same thing, probably incorporating reflection, but this method follows the principle of least astonishment.)

Of course I’m thinking the shadow project and test project should have as much automated maintenance as possible built it. Stub test methods should be built for every let and member binding, and it should have a mechanism for remembering an exclude list of test methods you choose not to implement, so when you add new bindings you can “update” the test project with new stubs and not recreate the ones you don’t want.

Naming standards are important to get right from the beginning, and coherent test naming is definitely an area for more R&D! (But that would be a whole nother article, if not a book.) To begin with, I would like at least one of the available standards to implement the default stub names to be “[let module name (.) binding name | type name (.) member name] : test 1”. It’s easy to manually change “test 1″ to something more descriptive, if desired. The system should maintain the test methods in sorted order in keeping with the external NUnit test runner.

The stub code should consist of two FsUnit equality statements, one stubbing the function result to assert equality with default values (zero length string, zero, false, etc, and higher order types built from default values), and a second equality asserting true |> should equal false. (The second assert ensures the developer does something useful with the stub or removes it.)

 1: module NUnitFsUnitLibTest.MyLibTest
 2: 
 3: open System
 4: open NUnit.Framework
 5: open FsUnit
 6: open MyProject
 7: open MyProject.MyLib
 8: 
 9: [<Test>]
10: let ``MyLib.addToMyType: Test 1``() =
11:     addToMyType (MyType(0, "", false)) 
12:     |> should equal (MyType(0, "", false))
13:     true |> should equal false
14: 
15: let myType = MyType(0, "", false)
16: 
17: [<Test>]
18: let ``MyType.BoolMember: Test 1``() =
19:     myType.BoolMember |> should equal false
20:     true |> should equal false
21: 
22: [<Test>]
23: let ``MyType.IntMember: Test 1``() =
24:     myType.IntMember |> should equal 0
25:     true |> should equal false
26: 
27: [<Test>]
28: let ``MyType.StringMember: Test 1``() =
29:     myType.StringMember |> should equal ""
30:     true |> should equal false

This is just a starting point for exploiting F# testability. I’m sure more sophisticated test generation systems can (and should!) follow on. Perhaps inferring and generating stubs for edge cases or generating FsCheck stubs.

Testability is a huge hook to promoting F# as a general purpose language. This is an area project managers and enterprise executives can get interested in. What is a better allocation of their expensive programmer resources? Learning and maintaining um-teen design patterns all held together by convention or writing naturally maintainable and testable code from the beginning?

Those tending more towards functional puritanism should also find automating functional test code generation interesting. Because of inherent correctness, the immediate return of finding more bugs faster is not as great as it would be for OO/imperative languages, but near-ready-made regression unit tests really make the testability built-in and goes a long way in protecting against software fragility.

namespace MyProjectTest

module MyLibTest

from MyProjectTest

namespace System

namespace NUnit

namespace NUnit.Framework

module FsUnit

namespace MyProject

module MyLib

from MyProject

Multiple items
type TestAttribute =
  inherit Attribute
  new : unit -> TestAttribute
  member Description : string with get, set

Full name: NUnit.Framework.TestAttribute

——————–
TestAttribute() : unit

val addToMyType : x:MyType -> MyType

Full name: MyProject.MyLib.addToMyType

Multiple items
type MyType =
  new : myInt:int * myString:string * myBool:bool -> MyType
  member BoolMember : bool
  member IntMember : int
  member StringMember : string

Full name: MyProject.MyType

——————–
new : myInt:int * myString:string * myBool:bool -> MyType

val should : f:('a -> #Constraints.Constraint) -> x:'a -> y:obj -> unit

Full name: FsUnit.should

val equal : x:'a -> Constraints.EqualConstraint

Full name: FsUnit.equal

val myType : MyType

Full name: MyProjectTest.MyLibTest.myType

property MyType.BoolMember: bool

property MyType.IntMember: int

property MyType.StringMember: string

S.F. F# User Group: Working with Functional Data Structures, Bibliography

Posted on February 4, 2013 by Jack Fox

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

F# Data Structure Libraries in FSharpx

Posted on February 2, 2013 by Jack Fox

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.

A Unified Collection of Purely Functional List-like Data Structures

Posted on January 22, 2013 by Jack Fox

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

	10²	10³	10⁴	10⁵	10⁶
ms.f#.array	0.8	1.8	100.9	11771.4	n/a
ms.f#.array — list	0.3	1.0	69.5	n/a	n/a
ms.f#.list	0.4	0.4	0.4	1.0	13.8
ms.f#.list — list	0.7	0.7	0.9	2.3	45.3
fsharpx.deque — conj	0.3	0.3	0.5	4.7	*
fsharpx.deque — cons	0.3	0.3	0.5	4.7	*
fsharpx.dlist — conj	0.7	0.7	1.0	7.7	153.0
fsharpx.dlist — cons	0.7	0.7	1.0	6.4	118.4
fsharpx.heap	3.2	3.3	5.0	22.5	254.7
fsharpx.lazylist	0.9	0.9	1.0	2.6	108.3
fsharpx.queue	1.0	1.1	1.4	7.6	106.6
fsharpx.randomaccesslist	0.8	0.9	3.3	19.6	189.8
fsharpx.vector	0.8	0.9	3.3	19.7	189.1

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

	10²	10³	10⁴	10⁵	10⁶
ms.f#.array	0.1	0.1	0.1	0.2	1.3
ms.f#.array — ofList	0.2	0.2	0.3	0.5	2.5
ms.f#.list — ofArray	0.2	0.2	0.2	0.7	12.7
ms.f#.list	0.0	0.0	0.0	0.0	0.0
fsharpx.deque	0.6	0.6	0.6	1.0	*
fsharpx.dlist	1.5	1.5	1.7	3.5	49.8
fsharpx.heap	4.1	4.2	5.7	20.9	235.4
fsharpx.lazylist — ofArray	0.3	0.3	0.3	0.3	0.3
fsharpx.queue	1.0	1.0	1.1	1.6	13.5
fsharpx.randomaccesslist	4.4	4.5	5.2	11.5	156.5
fsharpx.vector	3.0	3.1	3.6	8.1	69.3

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

	10²	10³	10⁴	10⁵	10⁶
ms.f#.list	0.1	0.1	0.1	0.2	1.0
fsharpx.deque — tail	1.9	2.0	2.2	5.2	*
fsharpx.deque — initial	2.9	2.9	3.3	8.2	*
fsharpx.dlist	0.6	0.6	1.0	6.4	105.8
fsharpx.heap	0.5	0.6	0.7	1.9	13.5
fsharpx.lazylist	0.9	1.0	2.2	21.3	254.1
fsharpx.queue	0.5	0.5	0.9	1.8	48.2
fsharpx.randomaccesslist	0.9	1.0	2.1	13.6	108.9
fsharpx.vector	0.9	1.0	2.1	13.6	114.7

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

	10²	10³	10⁴	10⁵	10⁶
ms.f#.array	0.3	0.3	0.4	1.1	8.4
ms.f#.list	0.7	0.7	0.8	2.0	14.0
fsharpx.deque	2.2	2.3	2.6	5.5	*
fsharpx.dlist	1.7	1.8	3.3	22.1	214.1
fsharpx.heap	5.3	5.6	6.6	28.8	450.5
fsharpx.lazylist	3.1	3.2	4.4	23.0	278.3
fsharpx.queue	2.0	2.0	2.4	5.3	50.2
fsharpx.randomaccesslist	1.6	1.7	1.8	3.9	24.8
fsharpx.vector	1.7	1.7	1.9	3.9	26.2

Reverse

	10²	10³	10⁴	10⁵	10⁶
ms.f#.array	0.1	0.1	0.1	0.2	1.1
ms.f#.list	0.2	0.2	0.2	0.4	1.8
fsharpx.deque	0.0	0.0	0.0	0.0	*
fsharpx.heap	5.2	5.7	8.4	64.8	1097.1
fsharpx.queue	0.1	0.1	0.1	0.1	0.1
fsharpx.randomaccesslist	1.5	1.5	2.1	10.2	100.0
fsharpx.vector	1.4	1.4	2.0	7.7	97.4

Append

	10²	10³	10⁴	10⁵	10⁶
ms.f#.array	0.1	0.1	0.1	0.2	1.4
ms.f#.list	0.2	0.2	0.3	0.7	46.0
fsharpx.dlist	0.2	0.2	0.2	0.2	0.2
fsharpx.heap	0.4	0.4	0.4	0.4	0.4
fsharpx.lazylist	0.2	0.2	0.2	0.2	0.2

Comments

1) Using merge for the Heap structure.

Iterate by index

	10²	10³	10⁴	10⁵	10⁶
ms.f#.array	0.4	0.4	0.4	0.5	1.4
fsharpx.randomaccesslist	0.4	0.4	0.5	2.2	18.5
fsharpx.vector	0.4	0.4	0.5	2.0	19.1

Random lookup (10,000)

	10²	10³	10⁴	10⁵	10⁶
ms.f#.array	0.1	0.1	0.1	0.1	0.1
fsharpx.randomaccesslist	0.1	0.1	0.1	0.1	0.1
fsharpx.vector	0.1	0.1	0.1	0.1	0.1

Random update (10,000)

	10²	10³	10⁴	10⁵	10⁶
ms.f#.array	0.1	0.1	0.1	0.1	0.2
fsharpx.randomaccesslist	2.1	2.7	4.2	10.1	17.0
fsharpx.vector	2.2	2.7	3.4	6.9	17.0

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.

Comparing F# Queues

Posted on January 18, 2013 by Jack Fox

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)

	10²	10³	10⁴	10⁵	10⁶
sys.queue	0.8	0.8	1.2	5.2	45.7
sys.concurrentqueue	1.9	2.1	2.8	10.9	90.3
sys.immutablequeue	1.4	1.5	2.7	21.2	401.4
fsharpx.queue	1.5	1.6	2.7	20.8	404.3
fsharpx.batchedqueue	2.0	2.2	4.0	32.8	n/a

And then the obligatory “not so real world” benchmarks

Enqueue the indicated number of elements

	10²	10³	10⁴	10⁵	10⁶
sys.queue	0.3	0.3	0.4	1.1	8.8
sys.concurrentqueue	0.4	0.5	0.6	1.7	12.8
sys.immutablequeue	0.5	0.5	0.8	4.0	91.6
fsharpx.queue	1.1	1.2	1.4	3.7	102.4
fsharpx.batchedqueue	1.2	1.2	1.5	7.8	n/a

Peek and Dequeue until the queue is empty

	10²	10³	10⁴	10⁵	10⁶
sys.queue	0.2	0.2	0.2	0.7	6.2
sys.concurrentqueue	0.7	0.7	0.8	2.4	18.9
sys.immutablequeue	0.5	0.5	0.7	3.3	74.7
fsharpx.queue	0.6	0.6	0.7	1.3	26.8
fsharpx.batchedqueue	0.7	0.7	0.9	1.8	n/a

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

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

	10²	10³	10⁴	10⁵	10⁶
sys.queue	0.3	0.3	0.4	1.2	9.6
sys.concurrentqueue	0.3	0.3	0.3	0.9	6.6
fsharpx.queue ofList	0.1	0.1	0.1	0.1	0.1
fsharpx.queue	0.7	0.7	0.7	1.2	13.1
fsharpx.batchedqueue	0.8	0.8	0.8	1.3	n/a

Use IEnumerable to iterate through each element

(queue of indicated size)

	10²	10³	10⁴	10⁵	10⁶
sys.queue	0.1	0.1	0.2	0.7	6.9
sys.concurrentqueue	0.7	0.7	0.8	1.3	7.0
sys.immutablequeue	0.7	0.7	0.9	2.4	55.8
fsharpx.queue	2.1	2.1	2.4	4.7	27.6
fsharpx.batchedqueue	2.1	2.2	2.4	4.7	n/a

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.

Semantics and List-like Data Structures

Posted on January 5, 2013 by Jack Fox

List as a Semantic Element

The singly-linked list is the fundamental data structure of functional programming. Suspending concern with how it is implemented (forward-linked elements) and dealing with it strictly as an abstract construct of its host language, List is an extension of the programming language, which in turn brings semantic structure to data. Growing and shrinking linear data representations is so powerful List alone suffices for solving a vast number of problems.

Eventually we do need to concern ourselves with implementation. There is a class of purely functional List-like data structures that extend List, either substituting more efficient versions of existing functions or supplementing additional functions for working with linear data representations.

The supplemental List-like data structures derive from familiar structures in imperative programming, but once constructed as purely functional (immutable) data structures, thinking of them as algebraic mutations of List reveals semantic cohesion.

List’s core functionality consists of three functions. (These are the names used in F#, and for clarity I will adhere mostly to the naming standard favored by Okasaki for extension functions, rather than the more familiar function names from imperative programming.)

cons — returns List with new element added to left

head — returns left-most element

tail — returns List excluding left-most element

F# List also provides non-core functionality (again, disregarding implementation you could do without these).

rev — returns reversed List

append — returns List of first List elements followed by second List elements

length — returns count of elements in the List

Extending Serial Representation

The extensions we will consider for our List-like vocabulary:

conj — returns List with new element added to right

initial — returns List excluding right-most element

last — returns right-most element

iLookup — returns element at index

iUpdate — returns List with element at index updated

It is perhaps surprising that List is so useful given that only the most recently added element is accessible! Significantly, you can readily see the extension functions either invert one of the core functions or provide short-cut access to an interior element. RandomAccessList provides indexed lookup and update.

RandomAccessList = List + iLookup + iUpdate

LazyList is one List-like data structure that most probably comes from a functional programming heritage. It is the only List-like structure reviewed here incorporating functionality the core List functions alone cannot replicate, namely lazy evaluation. Significantly in F# it already uses the List-like functional naming standard.

LazyList = List^Lazy

Heap is frequently overlooked as being a List-like data structure. Even Okasaki reverted to using function names from imperative programming that obscure the close relationship to List. Heap is always sorted and provides a more efficient, O(log n), append (merge).

Heap = List + sorted + append

Difference List facilitates adding elements to the other end of the List, whether singly or another entire Difference List in O(1) time.

DList = List + conj + append

After introducing adding elements to both ends, now consider the fully symmetrical linear representation provided by a Double-ended Queue. Deque is the union of its tail and tail’s compliment, initial. This symmetry finds additional expression in an O(1) rev.

Deque = List + conj + last + initial + rev = initial U tail

Queue, a workhorse in imperative programming, is simply a List that can only add elements on the right, but still extracts them on the left with head.

Queue = List - cons + conj

While the algebra deriving Vector from List is the longest, it is simply an inverted RandomAccessList.

Vector = List - cons - head - tail + conj + last + initial + iLookup + iUpdate
Vector = RandomAccessList^-1

Why the Cacophony of Names?

Perhaps perfect computer language implementations are an unrealizable ideal, but consistent nomenclature reveals semantics otherwise easily overlooked. Data structures from imperative programming take on a new character when made purely functional, and it is appropriate for them to give up part of their former identity (function names) in the functional realm.

All of the these F# Data Structures and more are available in the FSharpx.Collections and FSharpx.Datastructures namespaces here or from Nuget in FSharpx.Core.

UPDATE: Updated to naming standard adopted in FSharpx.Collections.

Engineering Random Bits: F# Generics

Posted on December 22, 2012 by Jack Fox

This is the first in a series of articles demonstrating some software engineering concepts in F# programming. The vehicle for my demonstrations is RandomBits, which derives random numbers from bits supplied by the ANU Quantum Random Numbers Server. Good pseudo-random number generators are perfectly adequate for almost any random number generation need you may ever encounter, but the application is nonetheless interesting from a software engineering standpoint. It consumes a web service, does bit-twiddling, implements generic functions, and presents a nice set of testing requirements.

F# Generic Functions

RandomBits provides true (not pseudo-random) signed and unsigned 8, 16, 32, and 64 bit random numbers from the bits served up from the Australian National University Centre for Quantum Computation & Communication Technology. As you can well imagine the basic processing for different bit-sized integers is essentially the same, yet most typed languages would limit code sharing among different data types. Chapter 5 of Expert F# 3.0 describes three techniques for writing generic algorithm functions, allowing you to write functions which support all numeric types.

I chose the inlining technique for this project. Take a look at the first snippet:

216:     member inline private this.rndSignRangeSeq (inclLower : 'a) (exlUpper : 'a) length 
217:         (nextZero : 'b) (nextOne : 'b)  (nextSigned : 'a -> 'b) (signed : 'b -> 'a) = 
218:         
219:         let lower = nextSigned inclLower
220:         let range =  (nextSigned exlUpper) - lower
221: 
222:         if range < nextOne then 
223:             invalidArg  "range" (sprintf "%i %i range must be greater than 0" inclLower exlUpper)
224:         if length < 1 then 
225:             invalidArg  "length" (sprintf "%i must be greater than 0" length)
226:         
227:         let upper = (nextSigned exlUpper) - (lower + nextOne)
228: 
229:         seq {for i = 1 to length do
230:                 yield this.randomWalk lower upper nextZero nextOne |> signed
231:              }

rndSignRangeSeq validates user parameters and generates a sequence of signed random numbers of any type from sbyte to int64. Because there are arithmetic operations involved, generically typing the input parameters is not sufficient to use this function for more than one number type. The input parameters operated upon by +, -, &#60 would default to the first number type passed by another function and attempts to use additional types would fail at compile time, but by inlining this member the input parameters stay generic and the F# compiler assigns an implicit constraint that the generic be a type supporting the math operators involved. Mouse-over one of the range delimter parameters (inclLower or exlUpper) and you will see

Part of the logic (in the succeeding generic function randomWalk, not described in this article) requires casting and computations at the next larger size of number. Note the parameters of type 'b

'b (requires member (-) and comparison and member (+) and member (>>>) and member (<<<))

whose implicit constraints the compiler also derives. When writing the code you just need to keep track of the roles of types 'a and 'b.

This allows simple code that can handle all signed number types. Here are the public members for different kinds of random ranges calling rndSignRangeSeq

489:     (* random numbers in range sequences *)
490: 
491:     ///random signed 8-bit integer in range inclusive of lower and exclusive of upper, seq of length
492:     member this.RndSByteSeq (inclLower, exlUpper, length)  = 
493:         this.rndSignRangeSeq inclLower exlUpper length 0s 1s (int16) (sbyte)
... 
498: 
499:     ///random signed 16-bit integer in range inclusive of lower and exclusive of upper, seq of length
500:     member this.RndInt16Seq (inclLower, exlUpper, length)  = 
501:         this.rndSignRangeSeq inclLower exlUpper length 0 1 (int32) (int16)
... 
506: 
507:     ///random signed 32-bit integer in range inclusive of lower and exclusive of upper, seq of length
508:     member this.RndInt32Seq (inclLower, exlUpper, length)  = 
509:         this.rndSignRangeSeq inclLower exlUpper length 0L 1L (int64) (int)
... 
513:         this.rndUnsignRangeSeq inclLower exlUpper length 0u 1u
514: 
515:     ///random signed 64-bit integer in range inclusive of lower and exclusive of upper, seq of length 
516:     member this.RndInt64Seq (inclLower, exlUpper, length) = 
517:         this.rndSignRangeSeq inclLower exlUpper length 0I 1I (this.bigint) (int64)

val int : 'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

val int64 : 'T -> int64 (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int64

val this : RandomBits

type: RandomBits
implements: IDisposable

member private RandomBits.waiting : unit -> unit

Full name: RandomBits.waiting

val loop : (int -> unit)

val x : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val not : bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not

property BackgroundWorker.IsBusy: bool

BackgroundWorker.CancelAsync() : unit

BackgroundWorker.RunWorkerAsync() : unit
BackgroundWorker.RunWorkerAsync(argument: obj) : unit

namespace System.Threading

type Thread =
  class
    inherit System.Runtime.ConstrainedExecution.CriticalFinalizerObject
    new : System.Threading.ThreadStart -> System.Threading.Thread
    new : System.Threading.ThreadStart * int -> System.Threading.Thread
    new : System.Threading.ParameterizedThreadStart -> System.Threading.Thread
    new : System.Threading.ParameterizedThreadStart * int -> System.Threading.Thread
    member Abort : unit -> unit
    member Abort : obj -> unit
    member ApartmentState : System.Threading.ApartmentState with get, set
    member CurrentCulture : System.Globalization.CultureInfo with get, set
    member CurrentUICulture : System.Globalization.CultureInfo with get, set
    member DisableComObjectEagerCleanup : unit -> unit
    member ExecutionContext : System.Threading.ExecutionContext
    member GetApartmentState : unit -> System.Threading.ApartmentState
    member GetCompressedStack : unit -> System.Threading.CompressedStack
    member GetHashCode : unit -> int
    member Interrupt : unit -> unit
    member IsAlive : bool
    member IsBackground : bool with get, set
    member IsThreadPoolThread : bool
    member Join : unit -> unit
    member Join : int -> bool
    member Join : System.TimeSpan -> bool
    member ManagedThreadId : int
    member Name : string with get, set
    member Priority : System.Threading.ThreadPriority with get, set
    member Resume : unit -> unit
    member SetApartmentState : System.Threading.ApartmentState -> unit
    member SetCompressedStack : System.Threading.CompressedStack -> unit
    member Start : unit -> unit
    member Start : obj -> unit
    member Suspend : unit -> unit
    member ThreadState : System.Threading.ThreadState
    member TrySetApartmentState : System.Threading.ApartmentState -> bool
    static member AllocateDataSlot : unit -> System.LocalDataStoreSlot
    static member AllocateNamedDataSlot : string -> System.LocalDataStoreSlot
    static member BeginCriticalRegion : unit -> unit
    static member BeginThreadAffinity : unit -> unit
    static member CurrentContext : System.Runtime.Remoting.Contexts.Context
    static member CurrentPrincipal : System.Security.Principal.IPrincipal with get, set
    static member CurrentThread : System.Threading.Thread
    static member EndCriticalRegion : unit -> unit
    static member EndThreadAffinity : unit -> unit
    static member FreeNamedDataSlot : string -> unit
    static member GetData : System.LocalDataStoreSlot -> obj
    static member GetDomain : unit -> System.AppDomain
    static member GetDomainID : unit -> int
    static member GetNamedDataSlot : string -> System.LocalDataStoreSlot
    static member MemoryBarrier : unit -> unit
    static member ResetAbort : unit -> unit
    static member SetData : System.LocalDataStoreSlot * obj -> unit
    static member Sleep : int -> unit
    static member Sleep : System.TimeSpan -> unit
    static member SpinWait : int -> unit
    static member VolatileRead : System.Byte -> System.Byte
    static member VolatileRead : int16 -> int16
    static member VolatileRead : int -> int
    static member VolatileRead : int64 -> int64
    static member VolatileRead : System.SByte -> System.SByte
    static member VolatileRead : uint16 -> uint16
    static member VolatileRead : uint32 -> uint32
    static member VolatileRead : System.IntPtr -> System.IntPtr
    static member VolatileRead : System.UIntPtr -> System.UIntPtr
    static member VolatileRead : uint64 -> uint64
    static member VolatileRead : float32 -> float32
    static member VolatileRead : float -> float
    static member VolatileRead : obj -> obj
    static member VolatileWrite : System.Byte * System.Byte -> unit
    static member VolatileWrite : int16 * int16 -> unit
    static member VolatileWrite : int * int -> unit
    static member VolatileWrite : int64 * int64 -> unit
    static member VolatileWrite : System.SByte * System.SByte -> unit
    static member VolatileWrite : uint16 * uint16 -> unit
    static member VolatileWrite : uint32 * uint32 -> unit
    static member VolatileWrite : System.IntPtr * System.IntPtr -> unit
    static member VolatileWrite : System.UIntPtr * System.UIntPtr -> unit
    static member VolatileWrite : uint64 * uint64 -> unit
    static member VolatileWrite : float32 * float32 -> unit
    static member VolatileWrite : float * float -> unit
    static member VolatileWrite : obj * obj -> unit
    static member Yield : unit -> bool
  end

Full name: System.Threading.Thread

  type: Threading.Thread
  implements: Runtime.InteropServices._Thread
  inherits: Runtime.ConstrainedExecution.CriticalFinalizerObject

Threading.Thread.Sleep(timeout: TimeSpan) : unit
Threading.Thread.Sleep(millisecondsTimeout: int) : unit

member private RandomBits.next64 : unit -> uint64

Full name: RandomBits.next64

val success : bool

  type: bool
  implements: IComparable
  implements: IConvertible
  implements: IComparable<bool>
  implements: IEquatable<bool>
  inherits: ValueType

val ru64 : uint64

  type: uint64
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<uint64>
  implements: IEquatable<uint64>
  inherits: ValueType

ConcurrentQueue.TryDequeue(result: byref<uint64>) : bool

member private RandomBits.waiting : unit -> unit

member private RandomBits.nextBit : unit -> bool

Full name: RandomBits.nextBit

member private RandomBits.next64 : unit -> uint64

static member private RandomBits.unsignedOfBit : displ:int -> bitOffset:int -> bit64:uint64 -> bitSize:int -> zero:'a -> one:'a -> 'a (requires member ( <<< ))

Full name: RandomBits.unsignedOfBit

val displ : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val bitOffset : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val bit64 : uint64

  type: uint64
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<uint64>
  implements: IEquatable<uint64>
  inherits: ValueType

val bitSize : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val zero : 'a (requires member ( <<< ))

val one : 'a (requires member ( <<< ))

val x' : uint64

  type: uint64
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<uint64>
  implements: IEquatable<uint64>
  inherits: ValueType

member private RandomBits.bitsToNumber : bitSize:int -> zero:'a -> one:'a -> 'g

Full name: RandomBits.bitsToNumber

val zero : 'a

val one : 'a

val loop : ('g -> int -> 'g)

val acc : 'g

val offset : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

member private RandomBits.bitsToNumber2 : bitSize:int -> zero:'a -> one:'a -> bit64:'d -> displ:'e -> 'f

Full name: RandomBits.bitsToNumber2

val bit64 : 'd

val displ : 'e

val loop : ('f -> int -> 'f)

val acc : 'f

member private RandomBits.randomWalk : lower:'a -> upper:'a -> zero:'a -> one:'a -> 'a (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

Full name: RandomBits.randomWalk

val lower : 'a (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

val upper : 'a (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

val zero : 'a (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

val one : 'a (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

val pwr : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val loop : ('a -> int -> int) (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

val u : 'a (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

val acc : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val u' : 'a (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

val loop : ('a -> int -> 'a) (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

val acc : 'a (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

val pwrDec : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

member private RandomBits.nextBit : unit -> bool

val loop2 : ('a -> 'a) (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

val x : 'a (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

val myRnd : 'a (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

member private RandomBits.rndInRange : inclLower:'a -> exlUpper:'a -> zero:'a -> one:'a -> 'a (requires member ( – ) and comparison and member ( >>> ) and member ( + ) and member ( <<< ))

Full name: RandomBits.rndInRange

val inclLower : 'a (requires member ( – ) and comparison and member ( >>> ) and member ( + ) and member ( <<< ))

val exlUpper : 'a (requires member ( – ) and comparison and member ( >>> ) and member ( + ) and member ( <<< ))

val zero : 'a (requires member ( – ) and comparison and member ( >>> ) and member ( + ) and member ( <<< ))

val one : 'a (requires member ( – ) and comparison and member ( >>> ) and member ( + ) and member ( <<< ))

val range : 'a (requires member ( – ) and comparison and member ( >>> ) and member ( + ) and member ( <<< ))

member private RandomBits.randomWalk : lower:'a -> upper:'a -> zero:'a -> one:'a -> 'a (requires member ( >>> ) and comparison and member ( + ) and member ( <<< ))

Full name: RandomBits.rndSignInRange

val uZero : 'c

val nextOne : 'b (requires member ( – ) and comparison and member ( + ))

val nextSigned2 : ('c -> 'b) (requires member ( – ) and comparison and member ( + ))

val unsigned : ('b -> 'c) (requires member ( – ) and comparison and member ( + ))

val uConv : ('c * 'c -> 'c)

val lower : 'b (requires member ( – ) and comparison and member ( + ))

val range : 'b (requires member ( – ) and comparison and member ( + ))

val invalidArg : string -> string -> 'T

Full name: Microsoft.FSharp.Core.Operators.invalidArg

val sprintf : Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf

member private RandomBits.rndSeq : length:int -> bitSize:int -> zero:'a -> one:'a -> signed:('a -> 'b) -> seq<'b>

Full name: RandomBits.rndSeq

val length : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val signed : ('a -> 'b)

val ptr : int ref

  type: int ref
  implements: Collections.IStructuralEquatable
  implements: IComparable<Ref<int>>
  implements: IComparable
  implements: Collections.IStructuralComparable

Multiple items
val ref : 'T -> 'T ref

Full name: Microsoft.FSharp.Core.Operators.ref

——————–
type 'T ref = Ref<'T>

Full name: Microsoft.FSharp.Core.ref<_>

  type: 'T ref
  implements: Collections.IStructuralEquatable
  implements: IComparable<Ref<'T>>
  implements: IComparable
  implements: Collections.IStructuralComparable

val n' : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val i : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

member private RandomBits.bitsToNumber2 : bitSize:int -> zero:'a -> one:'a -> bit64:'d -> displ:'e -> 'f

Full name: RandomBits.rndSignRangeSeq

val nextZero : 'b (requires member ( – ) and comparison and member ( + ) and member ( >>> ) and member ( <<< ))

val nextOne : 'b (requires member ( – ) and comparison and member ( + ) and member ( >>> ) and member ( <<< ))

val lower : 'b (requires member ( – ) and comparison and member ( + ) and member ( >>> ) and member ( <<< ))

val range : 'b (requires member ( – ) and comparison and member ( + ) and member ( >>> ) and member ( <<< ))

val upper : 'b (requires member ( – ) and comparison and member ( + ) and member ( >>> ) and member ( <<< ))

Full name: RandomBits.rndUnsignRangeSeq

member private RandomBits.rndInRange : inclLower:'a -> exlUpper:'a -> zero:'a -> one:'a -> 'a (requires member ( – ) and comparison and member ( >>> ) and member ( + ) and member ( <<< ))

Full name: RandomBits.rndSignUniqueSeq

val nextZero : 'b (requires comparison and member op_Explicit and member ( >>> ) and member ( <<< ) and member ( – ) and member ( + ))

val nextOne : 'b (requires comparison and member op_Explicit and member ( >>> ) and member ( <<< ) and member ( – ) and member ( + ))

val lower : 'b (requires comparison and member op_Explicit and member ( >>> ) and member ( <<< ) and member ( – ) and member ( + ))

val upper : 'b (requires comparison and member op_Explicit and member ( >>> ) and member ( <<< ) and member ( – ) and member ( + ))

val range : 'b (requires comparison and member op_Explicit and member ( >>> ) and member ( <<< ) and member ( – ) and member ( + ))

val count : 'b ref (requires comparison and member op_Explicit and member ( >>> ) and member ( <<< ) and member ( – ) and member ( + ))

  type: 'b ref
  implements: Collections.IStructuralEquatable
  implements: IComparable<Ref<'b>>
  implements: IComparable
  implements: Collections.IStructuralComparable

val h : 'a ref

  type: 'a ref
  implements: Collections.IStructuralEquatable
  implements: IComparable<Ref<'a>>
  implements: IComparable
  implements: Collections.IStructuralComparable

val x : 'b (requires comparison and member op_Explicit and member ( >>> ) and member ( <<< ) and member ( – ) and member ( + ))

val x' : 'b (requires comparison and member op_Explicit and member ( >>> ) and member ( <<< ) and member ( – ) and member ( + ))

val fold : ('State -> 'T -> 'State) -> 'State -> seq<'T> -> 'State

Full name: Microsoft.FSharp.Collections.Seq.fold

val t : 'b (requires comparison and member op_Explicit and member ( >>> ) and member ( <<< ) and member ( – ) and member ( + ))

Full name: RandomBits.rndUnsignUniqueSeq

  type: 'a ref
  implements: Collections.IStructuralEquatable
  implements: IComparable<Ref<'a>>
  implements: IComparable
  implements: Collections.IStructuralComparable

Multiple items
member private RandomBits.bigint : x:int64 -> BigInteger

Full name: RandomBits.bigint

——————–
type bigint = BigInteger

Full name: Microsoft.FSharp.Core.bigint

  type: bigint
  implements: IFormattable
  implements: IComparable
  implements: IComparable<BigInteger>
  implements: IEquatable<BigInteger>
  inherits: ValueType

val x : int64

  type: int64
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int64>
  implements: IEquatable<int64>
  inherits: ValueType

type BigInteger =
  struct
    new : int -> System.Numerics.BigInteger
    new : uint32 -> System.Numerics.BigInteger
    new : int64 -> System.Numerics.BigInteger
    new : uint64 -> System.Numerics.BigInteger
    new : float32 -> System.Numerics.BigInteger
    new : float -> System.Numerics.BigInteger
    new : decimal -> System.Numerics.BigInteger
    new : System.Byte [] -> System.Numerics.BigInteger
    member CompareTo : int64 -> int
    member CompareTo : uint64 -> int
    member CompareTo : System.Numerics.BigInteger -> int
    member CompareTo : obj -> int
    member Equals : obj -> bool
    member Equals : int64 -> bool
    member Equals : uint64 -> bool
    member Equals : System.Numerics.BigInteger -> bool
    member GetHashCode : unit -> int
    member IsEven : bool
    member IsOne : bool
    member IsPowerOfTwo : bool
    member IsZero : bool
    member Sign : int
    member ToByteArray : unit -> System.Byte []
    member ToString : unit -> string
    member ToString : System.IFormatProvider -> string
    member ToString : string -> string
    member ToString : string * System.IFormatProvider -> string
    static member Abs : System.Numerics.BigInteger -> System.Numerics.BigInteger
    static member Add : System.Numerics.BigInteger * System.Numerics.BigInteger -> System.Numerics.BigInteger
    static member Compare : System.Numerics.BigInteger * System.Numerics.BigInteger -> int
    static member DivRem : System.Numerics.BigInteger * System.Numerics.BigInteger * System.Numerics.BigInteger -> System.Numerics.BigInteger
    static member Divide : System.Numerics.BigInteger * System.Numerics.BigInteger -> System.Numerics.BigInteger
    static member GreatestCommonDivisor : System.Numerics.BigInteger * System.Numerics.BigInteger -> System.Numerics.BigInteger
    static member Log : System.Numerics.BigInteger -> float
    static member Log : System.Numerics.BigInteger * float -> float
    static member Log10 : System.Numerics.BigInteger -> float
    static member Max : System.Numerics.BigInteger * System.Numerics.BigInteger -> System.Numerics.BigInteger
    static member Min : System.Numerics.BigInteger * System.Numerics.BigInteger -> System.Numerics.BigInteger
    static member MinusOne : System.Numerics.BigInteger
    static member ModPow : System.Numerics.BigInteger * System.Numerics.BigInteger * System.Numerics.BigInteger -> System.Numerics.BigInteger
    static member Multiply : System.Numerics.BigInteger * System.Numerics.BigInteger -> System.Numerics.BigInteger
    static member Negate : System.Numerics.BigInteger -> System.Numerics.BigInteger
    static member One : System.Numerics.BigInteger
    static member Parse : string -> System.Numerics.BigInteger
    static member Parse : string * System.Globalization.NumberStyles -> System.Numerics.BigInteger
    static member Parse : string * System.IFormatProvider -> System.Numerics.BigInteger
    static member Parse : string * System.Globalization.NumberStyles * System.IFormatProvider -> System.Numerics.BigInteger
    static member Pow : System.Numerics.BigInteger * int -> System.Numerics.BigInteger
    static member Remainder : System.Numerics.BigInteger * System.Numerics.BigInteger -> System.Numerics.BigInteger
    static member Subtract : System.Numerics.BigInteger * System.Numerics.BigInteger -> System.Numerics.BigInteger
    static member TryParse : string * System.Numerics.BigInteger -> bool
    static member TryParse : string * System.Globalization.NumberStyles * System.IFormatProvider * System.Numerics.BigInteger -> bool
    static member Zero : System.Numerics.BigInteger
  end

Full name: System.Numerics.BigInteger

  type: BigInteger
  implements: IFormattable
  implements: IComparable
  implements: IComparable<BigInteger>
  implements: IEquatable<BigInteger>
  inherits: ValueType

member private RandomBits.bigintU : x:uint64 -> BigInteger

Full name: RandomBits.bigintU

val x : uint64

  type: uint64
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<uint64>
  implements: IEquatable<uint64>
  inherits: ValueType

val t : bool

  type: bool
  implements: IComparable
  implements: IConvertible
  implements: IComparable<bool>
  implements: IEquatable<bool>
  inherits: ValueType

event BackgroundWorker.RunWorkerCompleted: IEvent<RunWorkerCompletedEventHandler,RunWorkerCompletedEventArgs>

member IObservable.Add : callback:('T -> unit) -> unit

member private RandomBits.ANU_BlockCount : int

Full name: RandomBits.ANU_BlockCount

member private RandomBits.ANU_Url : string

Full name: RandomBits.ANU_Url

member private RandomBits.CacheLength : int

Full name: RandomBits.CacheLength

property ConcurrentQueue.Count: int

member private RandomBits.Consume64Count : int64

Full name: RandomBits.Consume64Count

member private RandomBits.MaxCache : int

Full name: RandomBits.MaxCache

member private RandomBits.MaxPersistCache : int

Full name: RandomBits.MaxPersistCache

member private RandomBits.PersistCacheLength : int

Full name: RandomBits.PersistCacheLength

member private RandomBits.PersistPath : string

Full name: RandomBits.PersistPath

member private RandomBits.ReusePeristCache : bool

Full name: RandomBits.ReusePeristCache

member private RandomBits.RndBool : unit -> bool

Full name: RandomBits.RndBool

random bool

member private RandomBits.RndSByte : unit -> sbyte

Full name: RandomBits.RndSByte

random signed 8-bit integer

val sbyte : 'T -> sbyte (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.sbyte

member private RandomBits.bitsToNumber : bitSize:int -> zero:'a -> one:'a -> 'g

member private RandomBits.RndByte : unit -> 'c

Full name: RandomBits.RndByte

random unsigned 8-bit integer

member private RandomBits.RndInt16 : unit -> int16

Full name: RandomBits.RndInt16

random signed 16-bit integer

val int16 : 'T -> int16 (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int16

member private RandomBits.RndUint16 : unit -> 'b

Full name: RandomBits.RndUint16

random unsigned 16-bit integer

member private RandomBits.RndInt32 : unit -> int32

Full name: RandomBits.RndInt32

random signed 32-bit integer

val int32 : 'T -> int32 (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int32

member private RandomBits.RndUint32 : unit -> 'a

Full name: RandomBits.RndUint32

random unsigned 32-bit integer

member private RandomBits.RndInt64 : unit -> int64

Full name: RandomBits.RndInt64

random signed 64-bit integer

member private RandomBits.RndUint64 : unit -> uint64

Full name: RandomBits.RndUint64

random unsigned 64-bit integer

member private RandomBits.RndSByte : inclLower:sbyte * exlUpper:sbyte -> sbyte

Full name: RandomBits.RndSByte

random signed 8-bit integer in range inclusive of lower and exclusive of upper

val inclLower : sbyte

  type: sbyte
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<sbyte>
  implements: IEquatable<sbyte>
  inherits: ValueType

val exlUpper : sbyte

  type: sbyte
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<sbyte>
  implements: IEquatable<sbyte>
  inherits: ValueType

Multiple items
val byte : 'T -> byte (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.byte

——————–
type byte = Byte

Full name: Microsoft.FSharp.Core.byte

  type: byte
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<byte>
  implements: IEquatable<byte>
  inherits: ValueType

member private RandomBits.RndByte : unit -> 'c

random unsigned 8-bit integer
member private RandomBits.RndByte : inclLower:byte * exlUpper:byte -> byte

random unsigned 8-bit integer in range inclusive of lower and exclusive of upper

member private RandomBits.RndByte : inclLower:byte * exlUpper:byte -> byte

Full name: RandomBits.RndByte

random unsigned 8-bit integer in range inclusive of lower and exclusive of upper

val inclLower : byte

  type: byte
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<byte>
  implements: IEquatable<byte>
  inherits: ValueType

val exlUpper : byte

  type: byte
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<byte>
  implements: IEquatable<byte>
  inherits: ValueType

member private RandomBits.RndInt16 : inclLower:int16 * exlUpper:int16 -> int16

Full name: RandomBits.RndInt16

random signed 16-bit integer in range inclusive of lower and exclusive of upper

val inclLower : int16

  type: int16
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int16>
  implements: IEquatable<int16>
  inherits: ValueType

val exlUpper : int16

  type: int16
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int16>
  implements: IEquatable<int16>
  inherits: ValueType

Multiple items
val uint16 : 'T -> uint16 (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.uint16

——————–
type uint16 = UInt16

Full name: Microsoft.FSharp.Core.uint16

  type: uint16
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<uint16>
  implements: IEquatable<uint16>
  inherits: ValueType

member private RandomBits.RndUint16 : unit -> 'b

random unsigned 16-bit integer
member private RandomBits.RndUint16 : inclLower:uint16 * exlUpper:uint16 -> uint16

random unsigned 16-bit integer in range inclusive of lower and exclusive of upper

member private RandomBits.RndUint16 : inclLower:uint16 * exlUpper:uint16 -> uint16

Full name: RandomBits.RndUint16

random unsigned 16-bit integer in range inclusive of lower and exclusive of upper

val inclLower : uint16

  type: uint16
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<uint16>
  implements: IEquatable<uint16>
  inherits: ValueType

val exlUpper : uint16

  type: uint16
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<uint16>
  implements: IEquatable<uint16>
  inherits: ValueType

member private RandomBits.RndInt32 : inclLower:int32 * exlUpper:int32 -> int32

Full name: RandomBits.RndInt32

random signed 32-bit integer in range inclusive of lower and exclusive of upper

val inclLower : int32

  type: int32
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val exlUpper : int32

  type: int32
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

Multiple items
val uint32 : 'T -> uint32 (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.uint32

——————–
type uint32 = UInt32

Full name: Microsoft.FSharp.Core.uint32

  type: uint32
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<uint32>
  implements: IEquatable<uint32>
  inherits: ValueType

member private RandomBits.RndUint32 : unit -> 'a

random unsigned 32-bit integer
member private RandomBits.RndUint32 : inclLower:uint32 * exlUpper:uint32 -> uint32

random unsigned 32-bit integer in range inclusive of lower and exclusive of upper

member private RandomBits.RndUint32 : inclLower:uint32 * exlUpper:uint32 -> uint32

Full name: RandomBits.RndUint32

random unsigned 32-bit integer in range inclusive of lower and exclusive of upper

val inclLower : uint32

  type: uint32
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<uint32>
  implements: IEquatable<uint32>
  inherits: ValueType

val exlUpper : uint32

  type: uint32
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<uint32>
  implements: IEquatable<uint32>
  inherits: ValueType

member private RandomBits.RndInt64 : inclLower:int64 * exlUpper:int64 -> int64

Full name: RandomBits.RndInt64

random signed 64-bit integer in range inclusive of lower and exclusive of upper

val inclLower : int64

  type: int64
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int64>
  implements: IEquatable<int64>
  inherits: ValueType

val exlUpper : int64

  type: int64
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int64>
  implements: IEquatable<int64>
  inherits: ValueType

val lower : BigInteger

  type: BigInteger
  implements: IFormattable
  implements: IComparable
  implements: IComparable<BigInteger>
  implements: IEquatable<BigInteger>
  inherits: ValueType

member private RandomBits.bigint : x:int64 -> BigInteger

val range : BigInteger

  type: BigInteger
  implements: IFormattable
  implements: IComparable
  implements: IComparable<BigInteger>
  implements: IEquatable<BigInteger>
  inherits: ValueType

member private RandomBits.bigintU : x:uint64 -> BigInteger

member private RandomBits.RndUint64 : unit -> uint64

random unsigned 64-bit integer
member private RandomBits.RndUint64 : inclLower:uint64 * exlUpper:uint64 -> uint64

random unsigned 64-bit integer in range inclusive of lower and exclusive of upper

member private RandomBits.RndUint64 : inclLower:uint64 * exlUpper:uint64 -> uint64

Full name: RandomBits.RndUint64

random unsigned 64-bit integer in range inclusive of lower and exclusive of upper

val inclLower : uint64

  type: uint64
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<uint64>
  implements: IEquatable<uint64>
  inherits: ValueType

val exlUpper : uint64

  type: uint64
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<uint64>
  implements: IEquatable<uint64>
  inherits: ValueType

member private RandomBits.RndBoolSeq : length:int -> seq<bool>

Full name: RandomBits.RndBoolSeq

random bool seq of length

member private RandomBits.RndSByteSeq : length:int -> seq<sbyte>

Full name: RandomBits.RndSByteSeq

random signed 8-bit integer seq of length

member private RandomBits.rndSeq : length:int -> bitSize:int -> zero:'a -> one:'a -> signed:('a -> 'b) -> seq<'b>

member private RandomBits.RndByteSeq : length:int -> seq<byte>

Full name: RandomBits.RndByteSeq

random unsigned 8-bit integer seq of length

member private RandomBits.RndInt16Seq : length:int -> seq<int16>

Full name: RandomBits.RndInt16Seq

random signed 16-bit integer seq of length

member private RandomBits.RndUint16Seq : length:int -> seq<uint16>

Full name: RandomBits.RndUint16Seq

random unsigned 16-bit integer seq of length

member private RandomBits.RndInt32Seq : length:int -> seq<int>

Full name: RandomBits.RndInt32Seq

random signed 32-bit integer seq of length

member private RandomBits.RndUint32Seq : length:int -> seq<uint32>

Full name: RandomBits.RndUint32Seq

random unsigned 32-bit integer seq of length

member private RandomBits.RndInt64Seq : length:int -> seq<int64>

Full name: RandomBits.RndInt64Seq

random signed 64-bit integer seq of length

member private RandomBits.RndUint64Seq : length:int -> seq<uint64>

Full name: RandomBits.RndUint64Seq

random unsigned 64-bit integer seq of length

member private RandomBits.RndSByteSeq : inclLower:sbyte * exlUpper:sbyte * length:int -> seq<sbyte>

Full name: RandomBits.RndSByteSeq

random signed 8-bit integer in range inclusive of lower and exclusive of upper, seq of length

member private RandomBits.RndByteSeq : inclLower:byte * exlUpper:byte * length:int -> seq<byte>

Full name: RandomBits.RndByteSeq

random unsigned 8-bit integer in range inclusive of lower and exclusive of upper, seq of length

member private RandomBits.RndInt16Seq : inclLower:int16 * exlUpper:int16 * length:int -> seq<int16>

Full name: RandomBits.RndInt16Seq

random signed 16-bit integer in range inclusive of lower and exclusive of upper, seq of length

member private RandomBits.RndUint16Seq : inclLower:uint16 * exlUpper:uint16 * length:int -> seq<uint16>

Full name: RandomBits.RndUint16Seq

random unsigned 16-bit integer in range inclusive of lower and exclusive of upper, seq of length

member private RandomBits.RndInt32Seq : inclLower:int * exlUpper:int * length:int -> seq<int>

Full name: RandomBits.RndInt32Seq

random usigned 32-bit integer in range inclusive of lower and exclusive of upper, seq of length

val inclLower : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val exlUpper : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

member private RandomBits.RndUint32Seq : inclLower:uint32 * exlUpper:uint32 * length:int -> seq<uint32>

Full name: RandomBits.RndUint32Seq

random unsigned 32-bit integer in range inclusive of lower and exclusive of upper, seq of length

member private RandomBits.RndInt64Seq : inclLower:int64 * exlUpper:int64 * length:int -> seq<int64>

Full name: RandomBits.RndInt64Seq

random usigned 64-bit integer in range inclusive of lower and exclusive of upper, seq of length

member private RandomBits.RndUint64Seq : inclLower:uint64 * exlUpper:uint64 * length:int -> seq<uint64>

Full name: RandomBits.RndUint64Seq

random unsigned 64-bit integer in range inclusive of lower and exclusive of upper, seq of length

member private RandomBits.RndSByteUniqueSeq : inclLower:sbyte * exlUpper:sbyte * length:int -> seq<sbyte>

Full name: RandomBits.RndSByteUniqueSeq

random unique usigned 8-bit integer in range inclusive of lower and exclusive of upper, seq of length

member private RandomBits.RndByteUniqueSeq : inclLower:byte * exlUpper:byte * length:int -> seq<byte>

Full name: RandomBits.RndByteUniqueSeq

random unique unsigned 8-bit integer in range inclusive of lower and exclusive of upper, seq of length

member private RandomBits.RndInt16UniqueSeq : inclLower:int16 * exlUpper:int16 * length:int -> seq<int16>

Full name: RandomBits.RndInt16UniqueSeq

random unique signed 16-bit integer in range inclusive of lower and exclusive of upper, seq of length

member private RandomBits.RndUint16UniqueSeq : inclLower:uint16 * exlUpper:uint16 * length:int -> seq<uint16>

Full name: RandomBits.RndUint16UniqueSeq

random unique unsigned 16-bit integer in range inclusive of lower and exclusive of upper, seq of length

member private RandomBits.RndInt32UniqueSeq : inclLower:int * exlUpper:int * length:int -> seq<int>

Full name: RandomBits.RndInt32UniqueSeq

random unique signed 32-bit integer in range inclusive of lower and exclusive of upper, seq of length

member private RandomBits.RndUint32UniqueSeq : inclLower:uint32 * exlUpper:uint32 * length:int -> seq<uint32>

Full name: RandomBits.RndUint32UniqueSeq

random unique unsigned 32-bit integer in range inclusive of lower and exclusive of upper, seq of length

Multiple items
type IDisposable =
  interface
    member Dispose : unit -> unit
  end

Full name: System.IDisposable

——————–
IDisposable

override private RandomBits.Dispose : unit -> unit

Full name: RandomBits.Dispose

Component.Dispose() : unit

And that’s almost all there is to generating random sequences of different types. In a future article I’ll show you the generic bit twiddling involved.

End Note: Formatted F# Snippets

As well applying my best engineering chops to the application, I’m taking this opportunity to better engineer this blog. For the first time I’ve formatted F# code snippets using Tomas Petricek’s FSharp.Formatting code formatter. Not only is the code color-coded like in an IDE, but mouse-over tool tips work just like intellisense.

FSharp.Formatting requires FSharp.CompilerBinding, then generating formatted F# with tool tip intellisense is as easy as running the following:

 1: #r "FSharp.CodeFormat.dll"
 2: open FSharp.CodeFormat
 3: open System.IO
 4: 
 5: let fsharpCompiler = "C:\\Program Files\\Microsoft F#\\v4.0\\FSharp.Compiler.dll"
 6: let asm = System.Reflection.Assembly.LoadFile(fsharpCompiler)
 7: let formatAgent = FSharp.CodeFormat.CodeFormatAgent(asm)
 8: 
 9: let source = File.ReadAllText("C:\\Users\Jack\\Documents\\Scripts\\RandomBits.fs")
10: 
11: let snippets, errors = formatAgent.ParseSource("C:\\Users\Jack\\Documents\\Scripts\\RandomBits.fs", source.Trim())
12: let res = FSharp.CodeFormat.CodeFormat.FormatHtml(snippets, "fstipsA")
13: 
14: let wr = new StreamWriter("C:\\Users\Jack\\Documents\\Scripts\\RandomBits.output")
15: for snip in res.SnippetsHtml do
16:       wr.WriteLine(snip.Title)
17:       wr.WriteLine(snip.Html + "\n")
18: wr.WriteLine("\n\n<!-- GENERATED TOOL TIPS -->")
19: wr.Write(res.ToolTipHtml)
20: wr.Dispose();;

namespace FSharp

module CodeFormat

from FSharp

namespace System

namespace System.IO

val fsharpCompiler : string

Full name: FSharp.CodeFormat.fsharpCompiler

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>

val asm : System.Reflection.Assembly

Full name: FSharp.CodeFormat.asm

  type: System.Reflection.Assembly
  implements: System.Runtime.InteropServices._Assembly
  implements: System.Security.IEvidenceFactory
  implements: System.Reflection.ICustomAttributeProvider
  implements: System.Runtime.Serialization.ISerializable

namespace System.Reflection

type Assembly =
  class
    member CodeBase : string
    member CreateInstance : string -> obj
    member CreateInstance : string * bool -> obj
    member CreateInstance : string * bool * System.Reflection.BindingFlags * System.Reflection.Binder * obj [] * System.Globalization.CultureInfo * obj [] -> obj
    member EntryPoint : System.Reflection.MethodInfo
    member Equals : obj -> bool
    member EscapedCodeBase : string
    member Evidence : System.Security.Policy.Evidence
    member FullName : string
    member GetCustomAttributes : bool -> obj []
    member GetCustomAttributes : System.Type * bool -> obj []
    member GetCustomAttributesData : unit -> System.Collections.Generic.IList<System.Reflection.CustomAttributeData>
    member GetExportedTypes : unit -> System.Type []
    member GetFile : string -> System.IO.FileStream
    member GetFiles : unit -> System.IO.FileStream []
    member GetFiles : bool -> System.IO.FileStream []
    member GetHashCode : unit -> int
    member GetLoadedModules : unit -> System.Reflection.Module []
    member GetLoadedModules : bool -> System.Reflection.Module []
    member GetManifestResourceInfo : string -> System.Reflection.ManifestResourceInfo
    member GetManifestResourceNames : unit -> string []
    member GetManifestResourceStream : string -> System.IO.Stream
    member GetManifestResourceStream : System.Type * string -> System.IO.Stream
    member GetModule : string -> System.Reflection.Module
    member GetModules : unit -> System.Reflection.Module []
    member GetModules : bool -> System.Reflection.Module []
    member GetName : unit -> System.Reflection.AssemblyName
    member GetName : bool -> System.Reflection.AssemblyName
    member GetObjectData : System.Runtime.Serialization.SerializationInfo * System.Runtime.Serialization.StreamingContext -> unit
    member GetReferencedAssemblies : unit -> System.Reflection.AssemblyName []
    member GetSatelliteAssembly : System.Globalization.CultureInfo -> System.Reflection.Assembly
    member GetSatelliteAssembly : System.Globalization.CultureInfo * System.Version -> System.Reflection.Assembly
    member GetType : string -> System.Type
    member GetType : string * bool -> System.Type
    member GetType : string * bool * bool -> System.Type
    member GetTypes : unit -> System.Type []
    member GlobalAssemblyCache : bool
    member HostContext : int64
    member ImageRuntimeVersion : string
    member IsDefined : System.Type * bool -> bool
    member IsDynamic : bool
    member IsFullyTrusted : bool
    member LoadModule : string * System.Byte [] -> System.Reflection.Module
    member LoadModule : string * System.Byte [] * System.Byte [] -> System.Reflection.Module
    member Location : string
    member ManifestModule : System.Reflection.Module
    member PermissionSet : System.Security.PermissionSet
    member ReflectionOnly : bool
    member SecurityRuleSet : System.Security.SecurityRuleSet
    member ToString : unit -> string
    static member CreateQualifiedName : string * string -> string
    static member GetAssembly : System.Type -> System.Reflection.Assembly
    static member GetCallingAssembly : unit -> System.Reflection.Assembly
    static member GetEntryAssembly : unit -> System.Reflection.Assembly
    static member GetExecutingAssembly : unit -> System.Reflection.Assembly
    static member Load : string -> System.Reflection.Assembly
    static member Load : System.Reflection.AssemblyName -> System.Reflection.Assembly
    static member Load : System.Byte [] -> System.Reflection.Assembly
    static member Load : string * System.Security.Policy.Evidence -> System.Reflection.Assembly
    static member Load : System.Reflection.AssemblyName * System.Security.Policy.Evidence -> System.Reflection.Assembly
    static member Load : System.Byte [] * System.Byte [] -> System.Reflection.Assembly
    static member Load : System.Byte [] * System.Byte [] * System.Security.SecurityContextSource -> System.Reflection.Assembly
    static member Load : System.Byte [] * System.Byte [] * System.Security.Policy.Evidence -> System.Reflection.Assembly
    static member LoadFile : string -> System.Reflection.Assembly
    static member LoadFile : string * System.Security.Policy.Evidence -> System.Reflection.Assembly
    static member LoadFrom : string -> System.Reflection.Assembly
    static member LoadFrom : string * System.Security.Policy.Evidence -> System.Reflection.Assembly
    static member LoadFrom : string * System.Byte [] * System.Configuration.Assemblies.AssemblyHashAlgorithm -> System.Reflection.Assembly
    static member LoadFrom : string * System.Security.Policy.Evidence * System.Byte [] * System.Configuration.Assemblies.AssemblyHashAlgorithm -> System.Reflection.Assembly
    static member LoadWithPartialName : string -> System.Reflection.Assembly
    static member LoadWithPartialName : string * System.Security.Policy.Evidence -> System.Reflection.Assembly
    static member ReflectionOnlyLoad : string -> System.Reflection.Assembly
    static member ReflectionOnlyLoad : System.Byte [] -> System.Reflection.Assembly
    static member ReflectionOnlyLoadFrom : string -> System.Reflection.Assembly
    static member UnsafeLoadFrom : string -> System.Reflection.Assembly
  end

Full name: System.Reflection.Assembly

System.Reflection.Assembly.LoadFile(path: string) : System.Reflection.Assembly

val formatAgent : CodeFormatAgent

Full name: FSharp.CodeFormat.formatAgent

namespace FSharp.CodeFormat

type CodeFormatAgent =
  class
    new : fsharpCompiler:System.Reflection.Assembly -> CodeFormatAgent
    member AsyncParseSource : file:string * source:string * ?options:string * ?defines:string -> Async<Snippet [] * SourceError []>
    member ParseSource : file:string * source:string * ?options:string * ?defines:string -> Snippet [] * SourceError []
    member ParseSourceAsync : file:string * source:string * options:string * defines:string -> System.Threading.Tasks.Task<Snippet [] * SourceError []>
  end

Full name: FSharp.CodeFormat.CodeFormatAgent

val source : string

Full name: FSharp.CodeFormat.source

type File =
  class
    static member AppendAllLines : string * System.Collections.Generic.IEnumerable<string> -> unit
    static member AppendAllLines : string * System.Collections.Generic.IEnumerable<string> * System.Text.Encoding -> unit
    static member AppendAllText : string * string -> unit
    static member AppendAllText : string * string * System.Text.Encoding -> unit
    static member AppendText : string -> System.IO.StreamWriter
    static member Copy : string * string -> unit
    static member Copy : string * string * bool -> unit
    static member Create : string -> System.IO.FileStream
    static member Create : string * int -> System.IO.FileStream
    static member Create : string * int * System.IO.FileOptions -> System.IO.FileStream
    static member Create : string * int * System.IO.FileOptions * System.Security.AccessControl.FileSecurity -> System.IO.FileStream
    static member CreateText : string -> System.IO.StreamWriter
    static member Decrypt : string -> unit
    static member Delete : string -> unit
    static member Encrypt : string -> unit
    static member Exists : string -> bool
    static member GetAccessControl : string -> System.Security.AccessControl.FileSecurity
    static member GetAccessControl : string * System.Security.AccessControl.AccessControlSections -> System.Security.AccessControl.FileSecurity
    static member GetAttributes : string -> System.IO.FileAttributes
    static member GetCreationTime : string -> System.DateTime
    static member GetCreationTimeUtc : string -> System.DateTime
    static member GetLastAccessTime : string -> System.DateTime
    static member GetLastAccessTimeUtc : string -> System.DateTime
    static member GetLastWriteTime : string -> System.DateTime
    static member GetLastWriteTimeUtc : string -> System.DateTime
    static member Move : string * string -> unit
    static member Open : string * System.IO.FileMode -> System.IO.FileStream
    static member Open : string * System.IO.FileMode * System.IO.FileAccess -> System.IO.FileStream
    static member Open : string * System.IO.FileMode * System.IO.FileAccess * System.IO.FileShare -> System.IO.FileStream
    static member OpenRead : string -> System.IO.FileStream
    static member OpenText : string -> System.IO.StreamReader
    static member OpenWrite : string -> System.IO.FileStream
    static member ReadAllBytes : string -> System.Byte []
    static member ReadAllLines : string -> string []
    static member ReadAllLines : string * System.Text.Encoding -> string []
    static member ReadAllText : string -> string
    static member ReadAllText : string * System.Text.Encoding -> string
    static member ReadLines : string -> System.Collections.Generic.IEnumerable<string>
    static member ReadLines : string * System.Text.Encoding -> System.Collections.Generic.IEnumerable<string>
    static member Replace : string * string * string -> unit
    static member Replace : string * string * string * bool -> unit
    static member SetAccessControl : string * System.Security.AccessControl.FileSecurity -> unit
    static member SetAttributes : string * System.IO.FileAttributes -> unit
    static member SetCreationTime : string * System.DateTime -> unit
    static member SetCreationTimeUtc : string * System.DateTime -> unit
    static member SetLastAccessTime : string * System.DateTime -> unit
    static member SetLastAccessTimeUtc : string * System.DateTime -> unit
    static member SetLastWriteTime : string * System.DateTime -> unit
    static member SetLastWriteTimeUtc : string * System.DateTime -> unit
    static member WriteAllBytes : string * System.Byte [] -> unit
    static member WriteAllLines : string * string [] -> unit
    static member WriteAllLines : string * System.Collections.Generic.IEnumerable<string> -> unit
    static member WriteAllLines : string * string [] * System.Text.Encoding -> unit
    static member WriteAllLines : string * System.Collections.Generic.IEnumerable<string> * System.Text.Encoding -> unit
    static member WriteAllText : string * string -> unit
    static member WriteAllText : string * string * System.Text.Encoding -> unit
  end

Full name: System.IO.File

File.ReadAllText(path: string) : string
File.ReadAllText(path: string, encoding: System.Text.Encoding) : string

val snippets : Snippet []

Full name: FSharp.CodeFormat.snippets

  type: Snippet []
  implements: System.ICloneable
  implements: System.Collections.IList
  implements: System.Collections.ICollection
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.IStructuralEquatable
  implements: System.Collections.Generic.IList<Snippet>
  implements: System.Collections.Generic.ICollection<Snippet>
  implements: seq<Snippet>
  implements: System.Collections.IEnumerable
  inherits: System.Array

val errors : SourceError []

Full name: FSharp.CodeFormat.errors

  type: SourceError []
  implements: System.ICloneable
  implements: System.Collections.IList
  implements: System.Collections.ICollection
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.IStructuralEquatable
  implements: System.Collections.Generic.IList<SourceError>
  implements: System.Collections.Generic.ICollection<SourceError>
  implements: seq<SourceError>
  implements: System.Collections.IEnumerable
  inherits: System.Array

member CodeFormatAgent.ParseSource : file:string * source:string * ?options:string * ?defines:string -> Snippet [] * SourceError []

System.String.Trim() : string
System.String.Trim(trimChars: char []) : string

val res : FormattedHtml

Full name: FSharp.CodeFormat.res

type CodeFormat =
  class
    static member CreateAgent : fsharpCompiler:System.Reflection.Assembly -> CodeFormatAgent
    static member FormatHtml : snippets:Snippet [] * prefix:string -> FormattedHtml
    static member FormatHtml : snippets:Snippet [] * prefix:string * addLines:bool * addErrors:bool -> FormattedHtml
    static member FormatHtml : snippets:Snippet [] * prefix:string * openTag:string * closeTag:string * addLines:bool * addErrors:bool -> FormattedHtml
  end

Full name: FSharp.CodeFormat.CodeFormat

static member CodeFormat.FormatHtml : snippets:Snippet [] * prefix:string -> FormattedHtml
static member CodeFormat.FormatHtml : snippets:Snippet [] * prefix:string * addLines:bool * addErrors:bool -> FormattedHtml
static member CodeFormat.FormatHtml : snippets:Snippet [] * prefix:string * openTag:string * closeTag:string * addLines:bool * addErrors:bool -> FormattedHtml

val wr : StreamWriter

Full name: FSharp.CodeFormat.wr

  type: StreamWriter
  implements: System.IDisposable
  inherits: TextWriter
  inherits: System.MarshalByRefObject

type StreamWriter =
  class
    inherit System.IO.TextWriter
    new : System.IO.Stream -> System.IO.StreamWriter
    new : System.IO.Stream * System.Text.Encoding -> System.IO.StreamWriter
    new : System.IO.Stream * System.Text.Encoding * int -> System.IO.StreamWriter
    new : string -> System.IO.StreamWriter
    new : string * bool -> System.IO.StreamWriter
    new : string * bool * System.Text.Encoding -> System.IO.StreamWriter
    new : string * bool * System.Text.Encoding * int -> System.IO.StreamWriter
    member AutoFlush : bool with get, set
    member BaseStream : System.IO.Stream
    member Close : unit -> unit
    member Encoding : System.Text.Encoding
    member Flush : unit -> unit
    member Write : char -> unit
    member Write : char [] -> unit
    member Write : string -> unit
    member Write : char [] * int * int -> unit
    static val Null : System.IO.StreamWriter
  end

Full name: System.IO.StreamWriter

  type: StreamWriter
  implements: System.IDisposable
  inherits: TextWriter
  inherits: System.MarshalByRefObject

val snip : FormattedSnippet

property FormattedHtml.SnippetsHtml: FormattedSnippet []

TextWriter.WriteLine() : unit
   (+0 other overloads)
TextWriter.WriteLine(value: obj) : unit
   (+0 other overloads)
TextWriter.WriteLine(value: string) : unit
   (+0 other overloads)
TextWriter.WriteLine(value: decimal) : unit
   (+0 other overloads)
TextWriter.WriteLine(value: float) : unit
   (+0 other overloads)
TextWriter.WriteLine(value: float32) : unit
   (+0 other overloads)
TextWriter.WriteLine(value: uint64) : unit
   (+0 other overloads)
TextWriter.WriteLine(value: int64) : unit
   (+0 other overloads)
TextWriter.WriteLine(value: uint32) : unit
   (+0 other overloads)
TextWriter.WriteLine(value: int) : unit
   (+0 other overloads)

property FormattedSnippet.Title: string

property FormattedSnippet.Html: string

TextWriter.Write(value: obj) : unit
   (+0 other overloads)
TextWriter.Write(value: string) : unit
   (+0 other overloads)
TextWriter.Write(value: decimal) : unit
   (+0 other overloads)
TextWriter.Write(value: float) : unit
   (+0 other overloads)
TextWriter.Write(value: float32) : unit
   (+0 other overloads)
TextWriter.Write(value: uint64) : unit
   (+0 other overloads)
TextWriter.Write(value: int64) : unit
   (+0 other overloads)
TextWriter.Write(value: uint32) : unit
   (+0 other overloads)
TextWriter.Write(value: int) : unit
   (+0 other overloads)
TextWriter.Write(value: bool) : unit
   (+0 other overloads)

property FormattedHtml.ToolTipHtml: string

TextWriter.Dispose() : unit

The output required minimal editing for posting into WordPress. Don’t forget to add the FSharp.Formatting CSS and javascript to your site.

FSharp.Formatting is a great resource for promoting F# programming. Not only does it make your code examples look like they are in an IDE, but it makes them more informative. I encourage everyone posting F# articles to use this resource.

FSharp.Formatting Update

Tomas just released documentation updates to his project:

F# Formatting: Documentation tools

F# Formatting: Code formatting

FSharpx Data Structures Discussion

Posted on November 29, 2012 by Jack Fox

In the ten weeks since I began submitting pull requests contributing Functional Data Structures to the FSharpx open source project I’ve learned a lot, not just expanding my knowledge of the F# language, .NET Framework, and Functional Data Structures, but Git, GitHub, and perhaps most interesting of all, contributing to an open source project.

Steffen Forkmann and Mauricio Scheffer, two of the core FSharpx team, deserve special call-outs for helping me come up to speed. Steffen ported some of my work before I began doing Git pull requests, and they’ve both been very patient with my Git blunders and other mistakes. It took some time, but I’m starting to understand the somewhat anarchic governance structure to open source. With my background leading medium-sized production projects, I try to develop a big picture of the entire stack. I’m learning OS contributors tend to be much more focused on immediate issues. I think this is for good reason as commit history is crucial to the health and long-term benefit of the project. It works like a self-organizing system with big picture benefits as emergent phenomena.

I still can’t resist formulating a bigger picture framework for the FSharpx Data Structures sub-project. What follows is purely my opinion, and I hope FSharpx contributors and others will correct me where I err, and encourage me where I am right with their feedback.

FSharpx.DataStructures Namespace is Purely Functional

This namespace is for Purely Functional Data Structures. There is already one exception, TransientVector which shares the IVector interface with the purely functional PersistentVector.

Mutable structures should have their own namespace, which currently doesn’t appear to exist. There is a “Collections” folder, but its components are in the FSharpx namespace. It includes extension modules to functional and mutable structures as well as one functional structure, NonEmptyList.

Structure Type and Module

The structure’s type should exist directly in the DataStructures namespace, as well as a module with the same name as the type, but not the type under the module. There are a few structures in the latter situation with no non-breaking remedy, except perhaps duplicating the entire type at the namespace level. The type should have all the members that operate on an instantiated type. The module should have let bindings to all the the type members as well as let bindings for all other “utility” functions on the type, like ofSeq and empty.

Understand the difference between a property and a method

Property Usage Guidelines One rule of thumb, if it is not O(1), it is not a property. (The inverse does not necessarily hold.)

Pattern Discriminator

Include any relevant pattern discriminators in the module. Hint: if the type implements TryUncons or TryUnsnoc you can implement pattern discriminators.

Try to Avoid Exceptions

If a structure’s method can throw an exception, include a TryMethodName method that returns option.

Necessary Members

Every data structure should have a length member (even if length is O(n)) and an IsEmpty member in the type and ofSeq in the module.

Additional Members

Of course implement all the members central to the structure, but there can be some nice O(1) or O(log n) values just waiting to be implemented that perhaps were not directly addressed in the research paper because they were not interesting. A couple of examples: the internal structure of the type allows O(1) rev or ofList.

Necessary Interface

Implement IEnumerable in the type. It should sequence elements in the inherent order of the data structure. For instance if a structure implements the head/tail paradigm, IEnumerable should sequence elements in the order of unconsing the structure down to empty. Most every structure has some logical, if not physical, order to its elements when flattened. (I can’t think of an exception right now.)

Implementing ofSeq and IEnumerable makes practically every Data Structure composable into every other, a very useful feature!

Type Interface

In theory data structures implementing the same paradigm, e.g. queue, should implement an interface that both restricts upcasting the interface to the original type and is a usable interface. Meeting both the restrictive and usable requirements has proven difficult. I haven’t given up on this project yet, just deferred it.

Hide unsafe underlying structures

When I first went to work on data structures in the FSharpx project, I noticed some of the structures exposing unsafe (in the sense that arbitrary use could lead to a dysfunctional structure) discriminated unions. I didn’t fully appreciate at the time how an OS project like FSharpx incrementally works toward ideal practices, and considered this an intentional practice, which I emulated.

As a result of Mauricio’s initiative to test for monoid law adherence, this [mal]practice has been exposed here and here.

This is a fair amount of clean-up work. Still, the exposed union does provide one more handle for the determined hacker to be inventive with, so perhaps the correct solution is to expose the union in the type and module in some manner that is clearly identified as unsafe. Or even collecting all of the unsafe unions in a single unsafe module. “Unsafe” or “unchecked” would be ideal names, except they are already C# key words.

Still thinking this over, and hope to get feedback on this.

Intellisense

Every public member and let binding should have intellisense documentation to make it user friendly and not require a literature search or inspection of the code to determine functionality. At the type level there should be intellisense documenting the purpose and use of the structure. Include URLs to additional literature where appropriate.

Data structures should give developers useful tools, not research projects.

Time Complexity

Adopting a practice from Haskell documentation, I put the time complexity for members and let bindings at the beginning of their intellisense documentation. I even went so far as to put O(1) on empty and singleton to accustom users to seeing the time complexity in the intellisense, even though strictly speaking time complexity for these bindings has no meaning.

Take time to evaluate the naming standard

While it’s a good practice to keep the name a structure is best known as, consider renaming properties and methods if it makes sense to fit in with F# paradigms. Use the FSharp.Collections and existing FSharpx.DataStructures namepaces as models, don’t just unthinkingly adopt the names from a research paper or the implementation in another language. Use ofList and ofArray not fromList or fromArray. I intentionally renamed the Heap members findMin and deleteMin to head and tail because I think that accurately conveys the head/tail paradigm like several other data structures (and I implemented Heaps as ascending or descending, so “min” is inappropriate). Stick with cons, snoc, head, tail, init, last wherever possible.

IReadOnlyList and IReadOnlyDictionary

IReadOnlyCollection and IReadOnlyDictionary, new to .NET 4.5, would appear to be useful to implement, however backwards compatibility of FSharpx raises a problem. A discussion of this issue is here.

Should FSharpx take over the PowerPack Data Structures?

Discussion: here

There are related threads for migrating other functions from PowerPack, for instance here and here

I don’t know what the right answer is.

Conclusion

Data Structures make F# a richer multi-technology-stack language. I keep a running collection of the structures from Okasaki’s 1998 book not yet ported to FSharpx here. (There’s at least one or two covered in the book not in this collection.) Feel free to request expediting porting any or all, or work on the port yourself (I’m happy to provide any assistance I can). There’s lots of other useful structures still “in the wild”.

Simple Lookups in F#, Choices and Trade-offs

Posted on November 23, 2012 by Jack Fox

What is your go-to data structure for lookups in F#? Most any choice for key-based lookups will work just fine, but if your requirements go beyond simple lookup or you have a demanding edge case what other criteria might you consider? Here’s an overview of the available lookup data structures:

Map

Purely functional and persistent. Over 20 methods providing various custom folds, mappings, filters, etc.

IntMap

Purely functional and persistent, but restricted to integer keys. Dozens of specialized methods including folds, mappings, filters, and inequality lookups (e.g. greater than key). Part of the FSharpx open source project.

Dictionary

Mutable. Almost always the fastest lookup. The fastest object to initialize with data, provided you initialize the dictionary with the expected capacity. If the capacity is not given data loading performance will degrade significantly in the 100 to 10,000 element range. It has none of the ancillary functional methods available to native F# data structures.

Hashtable

Mutable. Very good lookup performance and data initialization performance on string keys. If the capacity is not given data loading performance will degrade significantly at all ranges of element size. None of the ancillary functional methods available to native F# data structures.

HashMultiMap

Mutable. Available in the PowerPack.Core.Community library. The distinguishing feature of this data structure is a FindAll method returning a list of all values bound to a hash key. A fold method is also available.

So what are the raw lookup performance numbers? (All timings are in milliseconds.)

Integer Key by Number of Elements in Lookup Structure, 10,000 random lookups

	Map	IntMap	Dict	HashTbl	HshMltMap
10²	0.7	0.7	0.2	0.3	1.8
10³	0.9	0.9	0.2	0.3	1.8
10⁴	1.2	1.3	0.3	0.4	1.9
10⁵	2.1	2.2	0.6	0.8	2.3
10⁶	3.3	3.1	0.9	1.0	2.6

String Key by Number of Elements in Lookup Structure, 10,000 random lookups

	Map	IntMap	Dict	HashTbl	HshMltMap
10²	1.3	n/a	0.4	0.3	1.5
10³	1.7	n/a	0.4	0.4	1.5
10⁴	3.0	n/a	0.7	0.7	1.8
10⁵	5.3	n/a	1.5	1.2	2.4
10⁶	8.4	n/a	1.6	1.5	6.3

Good old System.Collections.Generic.Dictionary consistently performs lookups about 4 times faster than Map, but all the numbers are in the very low milliseconds or even tenths. This couldn’t make a performance difference unless you are doing a bazillion lookups in some long-running machine learning system.

So what else distinguishes the lookup choices? Maybe your app repeatedly loads data into new lookup tables.

Integer Key by Number of Elements loaded into Lookup Structure

* indicates capacity was not set for Dictionary and Hashtable

	Map	IntMap	Dict	*	HashTbl	*	HshMltMap
10²	1.6	2.6	0.6	1.7	0.3	1.4	1.2
10³	1.8	2.8	0.6	1.7	0.3	2.7	1.3
10⁴	5.6	5.0	0.9	2.2	0.8	4.7	1.9
10⁵	79.0	49.2	4.3	7.4	11.6	68.7	11.3

String Key by Number of Elements loaded into Lookup Structure

	Map	IntMap	Dict	HashTbl	HshMltMap
10²	4.0	n/a	0.6	0.3	1.2
10³	4.5	n/a	0.7	0.4	1.3
10⁴	12.1	n/a	1.3	1.3	2.4
10⁵	144.0	n/a	11.2	13.5	19.6

Once again Dictionary outperforms the competition, and more so if you set the capacity properly in the constructor.

If you are doing updates performance differences start becoming very pronounced. This is especially due to mutable structures’ advantage of doing updates in place, and in the case of Map there is no update-equivalent method, so updates require remove followed by add, returning new map instances and generating work for garbage collection.

Integer Key by Number of Elements in Lookup Structure, 10,000 random updates

	Map	IntMap	Dict	HashTbl	HshMltMap
10²	4.3	2.4	0.2	0.3	0.8
10³	6.8	3.1	0.2	0.3	0.8
10⁴	10.6	4.3	0.2	0.4	0.9
10⁵	17.9	9.3	0.6	0.6	1.3

String Key by Number of Elements in Lookup Structure, 10,000 random updates

	Map	IntMap	Dict	HashTbl	HshMltMap
10²	7.5	n/a	0.3	0.4	0.8
10³	12.0	n/a	0.4	0.5	0.8
10⁴	17.9	n/a	0.6	0.7	1.1
10⁵	34.6	n/a	1.2	1.2	1.7

In conclusion, for those rare applications doing huge volumes of lookups and/or repeatedly creating new lookup tables, Dictionary is your best choice, unless you require “functional” characteristics of the lookup table. Dictionary also enjoys a clear performance advantage in iterating over its contents as IEnumerable (but I’ve already bored you with enough tables), and because of this you can overcome the lack of “functional” methods (fold, etc.) by enumerating to the Seq module and use its methods.

Note on methodology: Integer keys are in the range 1 to number of elements and string keys range in length from 1 to 26 characters, evenly distributed. Both key types are shuffled before loading the data structure (i.e. the order is somewhat random). Data is presented in array format for loading. Timed events are isolated to the greatest extent possible. Each timed event is performed 50 times and the best 40 times are averaged. This is to discard arbitrarily long timed events which inevitably occur and would skew the results if included in the average. Taking the median of 50 timed events would serve the same purpose. Original timings are in ticks and divided by 10,000 to arrive at milliseconds. Timings measured using DS_Benchmark. The machine of record is a low-end dual-core processor running 64-bit Windows 7. Not covered by this analysis is garbage collection of large monolithic structures like large dictionaries or hashtables.

Let’s Make a Bayesian Deal

Posted on November 12, 2012 by Jack Fox

Let’s have some fun with the Monty Hall problem. The set-up is three closed doors. Behind one is a nice prize, behind the other two are dud prizes. You (having no prior knowledge) choose a door, at which point the game’s host (with prior knowledge) reveals a dud prize behind one of the doors you did not choose and asks if you want to stay with the door you chose or switch and choose the other door that is still closed.

There are many published articles on why the proper strategy is to switch doors, including the article above, but when I tried to explain this to someone a few months ago I was told that I was “full of sh*t, the odds don’t change”. Well actually the odds do change, because the game’s host has revealed new information. It all has to do with Bayes’ Theorem whose basic formula

P(A|B) = P(B|A)P(A) / P(B)

reads as follows:

The probability of event “A” occurring, given event “B” has occurred
equals
The probability of event “B” occurring, given event “A” has occurred
times
the probability of event “A”
divided by
The probability of event “B”.

Since I am apparently a failure at explaining this, I wrote an F# Monte Carlo program to do my talking for me. The F# code really expresses the way the game works. There is not much to it. Here is the type for an individual game:

It constructs each game given doorWithPrize, randomly generated, fstChoice, also randomly generated, and revealedDoor the door the host opens during the game play, for which there are two rules for choosing this door.

If the player happened to choose the door hiding the real prize then the host arbitrarily chooses between the other two doors:

Otherwise the host is constrained to open one and only one of the doors:

Over a large enough sample of games the host is constrained two-thirds of the time in his choice of doors to open because the player will make the wrong first choice two-thirds of the time. So the act of exposing one of the dud prizes reveals valuable information to you the player. (At least it tells you something with better than 50/50 odds.) And that’s why this works.

For your friends who still won’t believe and think you have played some sort of trick the program comes with an audit function that will print the records of up to 100 games. The source code is available here or on GitHub. Have fun with it.