Jun 26

A Sample of the Memoization Pattern in F#

Pieter Breed has been asking some useful questions on the F# list recently about using the “Map” type. I really appreciate it when people take the time to let us know when data structures are tricky to learn to use in F#.

Looking at Pieter’s blog made me think it might be instructive to show how the memoization pattern looks in F# (or at least one example of the pattern).

Jun 26


The source code for both fslib.dll and mllib.dll is included as sample code in the release. All F# programs implicitly reference both mllib.dll and fslib.dll as well as the following .NET assemblies, where available:

  • mscorlib.dll
  • System.dll
  • System.Xml.dll
  • System.Runtime.Remoting.dll
  • System.Data.dll
  • System.Drawing.dll
  • System.Web.dll
  • System.Web.Services.dll
  • System.Windows.Forms.dll

Some of the namespaces, modules and types in the F# library are:

This namespaces Microsoft.FSharp.Core, Microsoft.FSharp.Collections, Microsoft.FSharp.Control and Microsoft.FSharp.Text are automatically opened for every source code file, as is the module Microsoft.FSharp.Core.Operators. This means modules such as Microsoft.FSharp.Collections.List can typically be opened just by using open List.

Some modules are primarily of interest for those cross-compiling OCaml code, e.g. those under the Microsoft.FSharp.Compatibility.OCaml namespace.

Jun 26

Namespaces and Compilation Units

Namespaces and Compilation Units

Namespaces and module names can be specified with an initial declaration at the head of a file, e.g.,

         module MyCompany.MyLibrary.MyModule

The final identifier is treated as the module name, the preceding identifiers as the namespace. If you place your F# code into a namespace you will need to explicitly open the module using its long identifier, for example:

         open MyLibrary.MyModule

By default a module has no namespace and the ‘OCaml rule’ is used for the module name, i.e., the first letter of the filename is capitalized. A default namespace can be specified via the –namespace command-line option. If any module declaration is given it overrides the default namespace.

A namespace declaration may replace the initial module declaration. A namespace can only contain types and modules, but not values, e.g.,

         namespace MyCompany.MyLibrary

         type MyType = class
         module MyInnerModule = begin
            let myValue = 1

The namespace Microsoft.FSharp is automatically opened for all F# code. By default the namespace Microsoft.FSharp.MLLib and the module Microsoft.FSharp.MLLib.Pervasives are also automatically opened unless the –no-mllib command-line option is given.

The “.” notation

F# supports a number of variations on the “.” notation, e.g.,

  • Qualified names, e.g., Microsoft.FSharp.MLLib.Set.empty or System.Console.In.
  • Member access expressions, e.g., (System.String.Join(”a”, “b”)).Length
  • Assigning to fields and writing to properties, e.g., form.Title

In general a dot-notation expression can resolve to an F# value, a .NET method group (which will require further overload resolution), a .NET property, a .NET field, an F# record member, a .NET constructor group or a .NET delegate constructor group. The context in which the dot-notation expression occurs will dictate the rules that apply after the resolution of the notation ? for example, a .NET property on the left of an assignment will become a call to a .NET property setter. More examples are given in the section on interoperability.

Only type information prior to the expression (or within the expression itself) will be used when determining the type of this expression, so you may need to place additional type constraints at the point of declaration of the variables involved. (The only exception is when the identifiers on the right of the lookup specify a record field label, and the type of the expression is not yet determined by partial type information. In this case, the type of the expression being accessed is inferred from the type of the record to which the field label belongs)

F# record and class fields may be accessed via the . notation even when the field names have not been brought into the top-level scope via an open. For example, if a module contains

           type recd = { Name: string }

then you may use x.Name if x is determined by partial type inference to be of type recd. Likewise, the record labels involved in a record construction can be determined by type annotations, e.g.

           let x : recd = { Name="3" }

The determination of the types that govern the interpretation of record labels is subject to the same inference rules as .NET member access and many other F# language constructs, i.e., the type of the value to the left of the . must be determined by type inference using annotations and other information available on a left-to-right, outside-to-inside analysis of the program text up to the point where the construct occurs.

When accessing a field, property or method member of a type T1 where the member is declared in some T2 a constraint is asserted that T1 coerces to T2 according to the coercion relation.

Reactive Recursion and Dynamic Initialization Soundness Checks

F# permits the specification of values whose specifications are mutually-referential, but where the mutual-references are hidden inside delayed values such as inner functions, other recursive functions, anonymous fun lambdas, lazy computations, and the’methods of object-implementation expressions. A much broader class of expressions can be used in “let rec” bindings, and in particular the expressions can be applications, method calls, constructor invocations and other computations.

Some such uses of recursion are runtime checked, because there is a possibility that the computations involved in evaluating the bindings may actually take the delayed computations and execute them. The F# compiler gives a warning for “let rec” bindings that may be involve a runtime check and inserts delays and thunks so that if runtime self-reference does occur then an exception will be raised.

The recursion is “reactive” because it is used when defining objects such as forms, controls and services that respond to various inputs. For example, GUI elements that store and retrieve the state of the GUI elements as part of their specification have this behaviour. A simple example is the following menu item, which prints out part of its state when invoked:

   let rec menuItem : MenuItem =
      new MenuItem("&Say Hello",
                   new EventHandler(fun sender e ->
                        Printf.printf "Hello! Text = %sn" menuItem.Text),

A compiler warning is given when compiling this code because in theory the new MenuItem(…) constructor could evalute the callback as part of the construction process. It is a current research topic in the language design community to design type systems to catch these cases.

.NET Dynamic Type Tests

This is described in the section on interoperability.

Object Expressions

An object expression declares an implementation and/or extension of a class or interface. For example, the following uses the functionality of F#’s built-in polymorphic and > operators to construct an object that implements the .NET IComparer interface.

   {new IComparer
         with Compare(a,b) = if a 

Typically, F# generates a new class that implements/extends the given type. The required signature for Compare is inferred by looking at the unique virtual method that we must be overriding. In the longer example below note how the anonymous classes may close over free variables (e.g., capture the variable “n”) behind the scenes.

     open System
     open System.Collections
     open System.Windows.Forms
     let myComparer = {new IComparer with Compare(a,b) = compare a b}
     let myFormattable = {new IFormattable with ToString(fmt,fmtProvider) = "“}

     let myForm title n =
       let res =
        {new Form()
         with OnPaint(paintEventArgs) = Printf.printf “OnPaint: n = %dn” n
         and  OnResize(eventArgs) = Printf.printf “OnResize: n = %dn” } in

You may only override/implement methods in anonymous classes. You may not declare fields or new methods. To override/implement virtual properties you should override the “get_PropertyName” and “set_PropertyName” methods that implement the property. Likewise to override virtual events you should override the “add_EventName”, “remove_EventName” and “fire_EventName” methods that implement the event.

Objects created via object expressions can also support multiple interfaces.. The syntax is:

   { new  with 
     interface  with 
     interface  with  }


    { new Object()
        with Finalize() = cleanupFunction(false);

      interface IDisposable
        with Dispose() = cleanupFunction(true);  }

The interfaces are not part of the type of the object expression but can be revealed through type tests.

Accessing “this” in object expressions

F# members bind the name of the this parameter explicitly, see the quick tour.

There are several ways to access this in object expressions if necessary, all of quite similar. Fi