F# CheatSheet Updated

The F# CheatSheet now inlcudes Async Computations and Active Patterns.  Any further suggestions or comments are welcome.

Available at : http://www.a6systems.com/fsharpcheatsheet.pdf

F# Cheat Sheet

A6 Systems has posted an F# Cheat Sheet for those who are using or learning F# and need something easily accessible to remind them of the syntax. You can print this sheet out in landscape mode and keep it around your desk – or pull up the pdf (available at http://a6systems.com/resources.html) when you need a quick reminder.

First Class Functions:2 Multiprogramming

This is the final post of the series. Part zero was a simple illustration of the flexibility of first class functions. In part one, the iter, map and fold combinators were used to manipulate lists (and implicitly arrays and seq type objects). That was fun to go over, but not nearly as fun as this topic will be.

Over the past ten years, one may notice that the pace of processor clock speed improvements has diminished. The introduction of multi core technology is a promising innovations. I am not a computer engineer, so my thoughts don’t wander to the technical details that had to be surmounted in order to get multiple cores in a single processing unit. I am a programmer, so they wander to the complexity of concurrent computing. A complexity which, with this multicore technology, has now been placed at every programmers feet.

Simon Peyton-Jones puts it quite well in this way [I am paraphrasing]. Consider a queue, the simple structure undergraduates can create. Creating a queue with enqueue and dequeue operations is a basic undergraduate assignment. However, create a concurrent queue (in which the head and tail have separate locking mechanisms – because locking the whole thing would be inefficient) and you have a scientifically publishable result. The sequential implementation is as simple as problems come, and the concurrent version is as difficult as problems come. For the time being we will continue to use these methods, but there is no doubt that more will need to be invented. The reliability of software is sure to hit a wall (in fact I would argue it already has), if the efficiency is to be improved without simpler methods.

There are a lot of approaches being developed to solve these problems. Research today is on fire with new techniques to attack this complexity. But this is a basics post, and many of the solutions get into some advanced uses of functional languages. Also, each language tends to come with its own bag of tricks for this dilemma. Fortunately, there is a very easy way to get access to threading processes in F# using the .NET platform, and I thought a little example code would be good for people just cutting their teeth on functional programming.

Consequently, the examples below will not attack the whole world of concurrency today. In fact the scope will be quite small from the standpoint of concurrency. What I want to highlight here is the continued benefit of using higher order functions, and the simplicity they can bring to complex problems. The example below will split an array into chunks of work and then apply map and fold operators, specifically designed to be parallel, to do this work.

Today’s project starts with a couple of helper functions. One function, run, takes a function and executes it on a new thread. Another function unzip will take an array and split it up in to a given number of smaller arrays. The definitions are below.

let run f =
    let thread  = new System.Threading.Thread(new System.Threading.ThreadStart(f)) in
    thread.Start();
    thread

// Every `num` element of a list gets added to the `num` array
let unZip (arr:'a array) num =
    let vals = Array.create num [] in
    Array.iteri (fun i x -> vals.[i%num] <- vals.[i % num] @ [i]) arr;
    vals;

With these, the parallel map and parallel fold functions can be implemented. Each of these takes an array, unzips it to a given number and then executes the given function on a thread with our run function.

// Using n threads, execute the function f on every element of arr thus creating a new array
// where every element x is mapped to f x
let pMap n f (arr:'a array) =
    let vals = unZip arr n in
    let b = Array.create arr.Length arr.[0]  in
    let f' x () = List.iter (fun i -> b.[i] <- f arr.[i]) x in
    let threads = Array.map (fun x -> run (f' x)) vals in
    threads |> Array.iter (fun t -> t.Join()) ;
    b

// Using n threads, compose (f start) on to every element leading to n compositions
// thus pFold n f start arr = [ (..(((f start) arr.[0]) arr.[n-1]) ... arr[m-1]); ..;..;]
let pFold n f start arr =
    let vals = unZip arr n in
    let b = Array.zero_create n in
    let f' i x () = b.[i] <- List.fold_left (fun acc k -> f acc arr.[k]) start x in
    let threads = Array.mapi (fun i x -> run (f' i x)) vals in
    threads |> Array.iter (fun t -> t.Join());
    b

The nice thing about this is that these functions can be customized to more specific implementations. Here is something similar to what I would typically do in an API that might be used by others.

type MyComputer = class
       static member Fold f start arr = pFold System.Environment.ProcessorCount f start arr
       static member Map f arr = pMap System.Environment.ProcessorCount f arr
     end

The type MyComputer now encapsulates map and fold methods which are specific to the environment on which they are being run. The number of processors is provided as the number of threads. As a simple example I will create a program which takes an array of web addresses and counts each instance of each character on the web pages. One can intuitively grasp this as something very well suited to a combination of map and fold operations.First a dictionary is setup which can be used by multiple threads. We will use the lock function to ensure that addition of a character’s count, and the addition of a new character are processed atomically.

open System.IO
open System.Net
open System.Collections.Generic;  

let dictionary = new Dictionary<char,int>()

let addDictionaryEntry x n =
    lock dictionary
      (fun () ->
         if dictionary.ContainsKey(x) then
             dictionary.[x] <- dictionary.[x] + n
         else dictionary.Add(x,n))
    dictionary

Below are two very simple helper functions to retrieve a web page’s text and another adds a count to each character in a string using the dictionary above.

let getPage (x:string) =
                      use stream = WebRequest.Create(x).GetResponse().GetResponseStream()
                      use reader = new StreamReader(stream)
                      reader.ReadToEnd() 

let sumChars d (s:string) =
     let carr = s.ToCharArray()
     Array.iter (fun x -> addDictionaryEntry x 1 |> ignore) carr
     d

Creating the actual program is a snap now. I will first define the single threaded version.

let pageMap = Array.map getPage
let pageChars (xs:string array) = Array.fold_left sumChars dictionary xs
let runSingle pages = pageMap pages |> pageChars

This is for comparison, both in timing and in the similarity of the code. Now the parallel version.

let pPageMap = MyComputer.Map getPage
let pPageChars (xs:string array) = MyComputer.Fold sumChars dictionary xs
let runParallel pages = pPageMap pages |> pPageChar

That alone illustrates the power of these techniques quite sharply. The code is stunningly similar. I will create an array four web pages called webs

let webs = [|"http://www.cnn.com/index.html";
             "http://www.npr.org/index.html";
             "http://www.amazon.com/gp/homepage.html";
             "http://www.acm.org/index.html"|]

[Note: You can time operations in the interactive session by typing "#time" which toggles the setting to print the time an operation took :End Note] My workstation has a dual core setup, so the number of processors the environment returns is 2. Running the single threaded version with this (runSingle webs) yields a time of roughly 7.5 seconds. Running the parallel operation yields a time of roughly 5.5 seconds. Of course, the time was not cut down by as much as possible because this is not simply a CPU processing problem. First the web page request is I/O bound, and then the character counting is CPU bound (although the second is more difficult to see a benefit in concurrent processing because it is so fast). My machine attacks this with two threads, which is ideal for CPU bound operations. But more threads would be better for I/O bound operations. Setting this up with our map and fold methods running on more threads is very simple.

let customParallel (pages:string array) =
                     (pMap pages.Length getPage pages) |>
                     (pFold pages.Length sumChars dictionary)

Again we have very similar code, except this time the length of the array is used to specify the number of threads. Running this on my workstation (customParallel webs) yields the operation in 3.8 seconds.Of course, there are a number of things this simple post still does not address. This does not help us with Simon Peyton-Jones’s queue problem. It also does not free us from locking in general. What I really want to highlight here is that I was able to quite simply compose programs such that only part of the program had to deal with locking and concurrency. It was a low level detail that did not affect how I would organize larger solutions. I wrote a separate program to deal with concurrency, which I then pass programs to in order to compute them in parallel.For more on higher order functions and the functional style of programming in F# I would recommend both the Foundations and the Expert F# books by Apress. Jon Harrop’s F# Journal includes articles which are both thorough and clear, making them valuable to a wide audience. For more on concurrency in F# [the topic is rich] the Expert F# book has a very nice chapter dedicated to it. I believe that both Don Syme’s blog as well as Robert Pickering’s (foundations author) blog are great for examples [in fact Robert Pickering just finished a great series wholly related to concurrency].I also will recommend a couple of papers for the more motivated reader related to concurrency and functional programming during the holiday break. First, if you haven’t read it the MapReduce article from google is a lot of fun. Though they implemented it in C++ they designed it from functional principles.The unzip method used here is a distant reminder of a technique from a paper I read back in college. The paper was the first real groundbreaking moment for me that functional programming isn’t just a part of a new language, it is a new way to think about programming.Complete code listing:

#light

open System.IO
open System.Net
open System.Collections.Generic;  

let run f =
    let thread  = new System.Threading.Thread(new System.Threading.ThreadStart(f)) in
    thread.Start();
    thread

// Every `num` element of a list gets added to the `num` array
let unZip (arr:'a array) num =
    let vals = Array.create num [] in
    Array.iteri (fun i x -> vals.[i%num] <- vals.[i % num] @ [i]) arr;
    vals;

// Using n threads, execute the function f on every element of arr thus creating a new array
// where every element x is mapped to f x
let pMap n f (arr:'a array) =
    let vals = unZip arr n in
    let b = Array.create arr.Length arr.[0]  in
    let f' x () = List.iter (fun i -> b.[i] <- f arr.[i]) x in
    let threads = Array.map (fun x -> run (f' x)) vals in
    threads |> Array.iter (fun t -> t.Join()) ;
    b

// Using n threads, compose (f start) on to every element leading to n compositions
// thus pFold n f start arr = [ (..(((f start) arr.[0]) arr.[n-1]) ... arr[m-1]); ..;..;]
let pFold n f start arr =
    let vals = unZip arr n in
    let b = Array.zero_create n in
    let f' i x () = b.[i] <- List.fold_left (fun acc k -> f acc arr.[k]) start x in
    let threads = Array.mapi (fun i x -> run (f' i x)) vals in
    threads |> Array.iter (fun t -> t.Join());
    b

type MyComputer = class
       static member Fold f start arr = pFold System.Environment.ProcessorCount f start arr
       static member Map f arr = pMap System.Environment.ProcessorCount f arr
     end

let dictionary = new Dictionary&lt;char,int&gt;()

let addDictionaryEntry x n =
    lock dictionary
      (fun () -&gt;
         if dictionary.ContainsKey(x) then
             dictionary.[x] &lt;- dictionary.[x] + n
         else dictionary.Add(x,n))
    dictionary     

let webs = [|"http://www.cnn.com/index.html";
             "http://www.npr.org/index.html";
             "http://www.amazon.com/gp/homepage.html";
             "http://www.acm.org/index.html"|]

let getPage (x:string) =
                      use stream = WebRequest.Create(x).GetResponse().GetResponseStream()
                      use reader = new StreamReader(stream)
                      reader.ReadToEnd() 

let sumChars d (s:string) =
     let carr = s.ToCharArray()
     Array.iter (fun x -> addDictionaryEntry x 1 |> ignore) carr
     d

let pageMap = Array.map getPage
let pageChars (xs:string array) = Array.fold_left sumChars dictionary xs
let runSingle pages = pageMap pages |> pageChars

let pPageMap = MyComputer.Map getPage
let pPageChars (xs:string array) = MyComputer.Fold sumChars dictionary xs
let runParallel pages = pPageMap pages |> pPageChars

let reallyParallel (pages:string array) = (pMap pages.Length getPage pages) |&gt; pFold pages.Length sumChars dictionary

First Class Functions :1 Fold, Map, Iter

Note: I am primarily presenting these 3 articles in F#. The main reason for this is that I am being asked about F# a great deal lately. The same principles of higher order functions will apply to other languages (like OCaml and Haskell). Also, the #light directive is used on all of the following code. You can use this yourself by placing #light at the top of your code files, or type #light into the interactive shell before entering any code. This indicates to the compiler that the code should be parsed by indentation (and thus whitespace should not be ignored) :End Note

Last time we transformed an imperative program into its functional counterpart. In the process we found some patterns we were able to extract to maximize the generality of our approach. Namely, higher order functions like the combinator fold were found to be valuable. In this post, we will take a look at three combinators – iter, map and fold – in order to gain a better understanding of their broad applicability. And it is broad. An entire tutorial could have been dedicated to the surprising capabilities of the fold combinator alone. Again, all of the F# code below can be plugged into an interactive session.

Iter

First let’s look at the iter combinator. It is very simple, it takes as arguments a function which takes an element and returns unit (unit being no meaningful result), and it takes the list/array/seq as its final argument.

Now let’s create something with iter. I will create a simple windows form, and include a list on it. We will use a List type for this, but thanks to the inclusion of iter in libraries with Arrays and Seq types we could have used those as well. That opens up possibilities like applying it to recordsets, files and a number of other .Net objects easily.

#light
open System.Windows.Forms

// Create the names list
let names = ["Arthur Dent";"Ford Prefect";"Slartibartfast"]

// The list control
let listControl =
  // Create the ListBox()
  let dlist = new ListBox()
  // Iterate through the names list, adding each one to the box using "iter"
  List.iter (fun n -> ignore (dlist.Items.Add(n)) ) names
  // return the list box  (which will bind it as the value of listControl
  dlist

// Create a form, add the list box control, set the location and show the form

let form = new Form(Text = "List Manipulation",Height=400,Width=400)
let namebox = listControl
form.Controls.Add(namebox)
namebox.Location <- new System.Drawing.Point(10,10)

// For interactive session
do form.Show()

Our form above first opens the Windows.Forms namespace. It then creates a list called names. It declares the listControl which iterates over the names list. The form value creates the form with its controls and then the Show method is called. The focus here is on the List.iter call in listControl. The first argument is a function (an anonymous function created with the fun notation – also sometimes called a lambda expression). The anonymous function takes an argument and adds it to the list control. The result of the Add call is passed to ignore, which takes any type and returns unit. This is done because our lambda expression has to return unit (but ListBox.Items.Add actually returns something). The final argument is the names list.There is also a version of iter which will include the index of the element it is acting on called iteri. We will not dive into this, but we will be using this type of function when we create something with map.

Map

map is similar to iter in that it takes a function and applies it to every element of a list/array/seq. However map is expected to return something meaningful. It is expected to return a value that replaces the current element in the new list, which map returns. As a quick example, if I had an array of integers and wanted to increase each element of the array by one I could write

> Array.map ((+) 1) [|1;2;3|]

In F# interactive mode the following would be returned

 val it : int array = [|2; 3; 4|]

Let’s use our new found combinator to add something to our form. In this case I will use the mapi combinator (the modified map which accepts an integer representing the location the current element is in the list). I will use map to enumerate each of the names, and then write that to the list using iter. This represents a very powerful aspect of these combinators, using them in combination! The full listing now with map is below. The call to map is now the second let expression in the listControl function. Like iter, it uses an anonymous function and then passes the names list to it. The resulting list (enumlist) is then used in the call to iter.

#light
open System.Windows.Forms

// Create the names list
let names = ["Arthur Dent";"Ford Prefect";"Slartibartfast"]

// The list control
let listControl =
  // Create the ListBox()
  let dlist = new ListBox()
  // map the list into an enumerated list
  let enumlist = List.mapi (fun i n -> i.ToString() + ": " + n) names
  // Iterate through the names list, adding each one to the box using "iter"
  List.iter (fun n -> ignore (dlist.Items.Add(n)) ) enumlist
  // return the list box  (which will bind it as the value of listControl
  dlist

// Create a form, add the list box control, set the location and show the form

let form = new Form(Text = "List Manipulation",Height=400,Width=400)
let namebox = listControl
form.Controls.Add(namebox)
namebox.Location <- new System.Drawing.Point(10,10)

// For interactive Session
do form.Show()

Fold

Fold has a number of implementations, but before getting into that let’s just introduce its basic purpose. Fold applies a function to each element of a list while keeping an accumulating argument. At the point the entire list has been traversed fold returns the accumulated argument. The simplest example I can imagine is summation.
Note, the function in this form doesn’t exist by default in F# … I will explain the F# version shortly.
This would return
To make it painfully simple, the reduction steps that you can imagine for the above calculation are …

Let’s look at an application of fold in a language (like F#). There are two directions from which you can fold a list. For example, fold_left folds the list starting with the left most element and fold_right folds the list starting from the right most element. This would matter if the computation you were using did not commute (unlike + which we will use in most of our examples for simplicity).

Let’s see what it looks like to calculate the mean of an integer list using fold_left.

let mean () =
     let eventspace = [for i in 10 .. 10 .. 100 -> i *i]
     let sum = List.fold_left (+) 0 eventspace
     let size  = float (List.length eventspace)
     (float sum) / size

Now, let’s get back to our form example. We created a list, we enumerated everyone’s name with mapi and then we used iter to write the names to the list. Now let’s compute something for fold. As an example, we will grab the longest name and write it to a label.

#light

open System.Windows.Forms

open System.Drawing

let names = ["Arthur Dent"; "Ford Prefect"; "Slartibartfast"]

let listControl =
  let dlist = new ListBox()
  let enumlist = List.mapi (fun i n -> i.ToString() + ": " + n) names
  List.iter (fun n-> ignore (dlist.Items.Add(n))) enumlist
  dlist

let form = new Form(Text = "List Manipulation",Height=400,Width=400)
let label = new Label()
label.Text <- "The longest name is: " +
  (names |>
   List.fold1_left (fun name cand -> if(name.Length>cand.Length) then name else cand))
label.Width <- 200
label.Location <- new Point(150,20)
form.Controls.Add(label)
form.Controls.Add(listControl)
listControl.Location <- new System.Drawing.Point(10,10)

// Note: For interactive Session
form.Show()

The code added to the form function creates the label. Then the label’s Text attribute is populated with a string and the result of the fold function. Again an anonymous function is used which checks the length of two strings and returns the longest one.The final form looks like:

While this only a very basic introduction, hopefully you will be able to use higher order functions in basic processing tasks at this point. If your experience is anything like mine,
in time you will be using them to compose very powerful abstractions of your programs. At an advanced level they even allow you to create APIs that look more like little languages than a series of method calls. I frequently use combinators in this way, as well as to parameterize the context of large computations. Next time I will address some simple approaches to concurrency using higher order functions.

First Class Functions : 0

Programming by composition is a bit new to people who have never seen a functional language. Some small examples can go a long way toward developing the beginner’s understanding. As a little example in this post I will define a function

which simply returns the largest integer in a list. I will start with something imperative, and step by step turn it into a functional design. You can cut and paste any of the code below into an F# interactive session.

The imperative version might look like

int max(List<int> ls)
{
   int temp = System.Int32.MinValue;
   foreach(int l in ls)

   if(temp<l)
      temp = l;

   return temp;
}

Starting with the above definition, we will port it to a function implementation and then try to generalize the pattern in ways only a functional language will allow us to do. A first stab at the function max might look something like this

// Type signature
val max : int list -> int -> int

let rec max xs n =
    if(List.length(xs)=0) then n
    elif(n<List.hd(xs)) then max (List.tl(xs)) (List.hd(xs))
    else max (List.tl(xs)) n

This was designed to be fairly clear to those accustomed to imperative programming. We had to spend a few extra lines of code to do that but the presentation is still fairly clear. Of course, we are taking one extra argument to represent the current maximum. We will change that soon.This is a nested if statement, where the outer guard checks for the base case (empty list). We have defined max to take two arguments, the list and the current maximum. If the next element of the list is greater then the current maximum, that element becomes the current maximum in the next function call. Otherwise the current maximum remains the same. In a successive call the Tail [represented List.tl] of the list (every element except the first) is passed until the list is empty, in which case the outer guard meets its condition and returns the current maximum.For example the call (where [0;1;2] is a list constructor for the list containing 0 1 and 2), returns 2.There is lots of room for improvement here. First, I don’t like using the same function multiple times, especially with the same argument. So let’s create some shorthand here.

let rec max xs n =
  if(List.length(xs)=0) then n
  else
   let head = List.hd(xs)
   let tail = List.tl(xs) in
   if(n<head) then max tail head
   else  max tail n

Okay, but we actually added code and now I would like to fix that. This is an excellent opportunity for pattern matching. Pattern matching is an elegant way to setup several definitions of your function based on the structure of its arguments, thus dynamically dispatching logic without a lot of guarded (if/then) statements.

let rec max xs n =
   match xs with
   | []    -> n
   | l::ls  ->let v = if(l<n) then n else l in
                   max ls v

Much cleaner! And we have knocked a couple of lines off our function. Our function is essentially defined two times, depending on the condition of the list and n. The first line declares the function. The second line invokes a pattern matcher on xs. The third line is the first pattern and checks for an empty list. The fourth line (second definition) seperates the first element of the list from the rest of the list (inherent head and tail) and runs the recursion on those values.Now, let’s get fancier with higher order functions. I would like to seperate out some patterns I see that are just too complicated. I would also like to get to the original signature we designated for max. First, we must recognize that (<) is a function. Let’s try to find a super pattern here. One consideration is that we are squashing this list down to its maximum. That means we apply a boolean function to the entire list, and when it is true replace the argument for n. That could be useful somewhere else (such as say a function min …) so lets separate it by creating our generic function “fold” which folds an argument list into one element.

let rec fold f xs n =
  match xs with
   | []   -> n
   | l::ls -> fold f ls (f n l)

We will also create the little helper function select which takes a function, and two arguments. We can also define greatest_boundary in terms of select.

let select f a b = if(f a b) then a else b
let greatest_boundary = select (>)

We only applied one argument to select to get greatest_boundary. That makes greatest_boundary a new function that only takes two arguments. It binds one of the three arguments to select and stops. This is a common technique in functional programming called currying. Now max is nearly trivial to define

let max xs = fold greatest_boundary (List.tl xs) (List.hd xs)

Note that greatest_boundary is a function that is applied as an argument, and then used in fold (as f). Why is this good? Consider how easy it is to define the sister function min now.

let least_boundary = select (<)
let min xs = fold least_boundary (List.tl xs) (List.hd xs)

We have simply carved out the pattern rather than the actual logic in this last case. Functions like fold are common in functional programming languages. In F#, List, Seq and Array all have versions of folding functions. These exist as fold_left and fold_right depending on the direction you want the function to iterate (this would matter in some applications on an ordered list). The next post will be dedicated entirely to combinators like fold. Following that I am working up a way to take advantage of multicore machines with ease using higher order functions like fold.

F# – Some common mistakes

I really love introducing new people to functional programming. At some point they get a kind of light bulb moment and start to feel really empowered by it. However, up until that time, there is some work and frustration in switching from an old comfortable paradigm to a new one. Lately most of my work has been centered around helping people get started with F# because I know so many people comfortable with the .NET environment and there has been a lot of talk about this new ML variant for the .NET platform. Given that, I thought it would be prudent to explicitly write out some of the most common problems I see people having when they start writing code in F#. I don’t consider this highlighting the negatives of the language, rather I want to help people get through these pitfalls faster so they can enjoy this language for all it is worth.

Value vs. Function :

Recently a friend emailed me a question about the .NET Random object. He had the following code and it wasn’t working right.

>let r = new Random()

>let roll =  r.Next()

Then he was getting the same result for roll every time he called it … why?

He was creating a value with roll. The F# compiler immediately evaluated r.Next() and assigned the result to roll. This is very much what one would expect from instantiating a variable in a language like C#. However, my friend was trying to assign to roll the function r.Next(). The easiest way to do that is to explicitly declare roll as a function by making it take unit (indicated by the parenthesis) as an argument.

>let roll () = r.Next();;

One could do it by denying r.Next() its unit argument, however you have to be careful …

> let roll = r.Next;;

val roll : int -> int

Why int->int? We were expecting unit->int. The compiler recognized that r.Next is overloaded with three possibilities and it selected r.Next(int):int for us. When it comes to overloaded functions I find it is always best to explicitly state in the code what I want to happen. It leads to fewer inference mistakes, and much more readable code.

Type inference effects:

One of the most common error messages you will run into is the one below (FS0001).

The expression has type [1] but here is used with type [2]
This is saying that you have tried to apply a function of type [2] to an argument of type [1]. Try typing the following into the interactive session.

>1.0 + 1;;

stdin(41,6): error: FS0001: This expression has type     int but is here used with type     float stopped due to error

The fix for this is always to either change the type the function takes or change the type of the argument.

From the example above, any of the following changes would work.

> 1 + 1;; > 1.0 + 1.0;; > (int 1.0) + 1;; > 1.0 + (float 1);;

I purposefully used an operator that crashes when an int and a float are mixed because this is the most common example of this I have seen (but as you learn F# you should expect to run into it occasionally while you learn the nuances of different library functions). People from a C/C#/Java background are very confused about why an int and a float (or double) can’t be added. They can, but in C#/Java/C the compiler does the conversion for you. However, in the F# style you are expected to do the conversion for the compiler. This allows you to determine the point at which the conversion is made (for example in division where conversion at different points can lead to very different results). Just remember, you are provided the handy functions int and float to help you with this.

Value Restriction:

Try this:

>type 'a DataSet = DS of 'a list >let makeDataSet ls = DS(ls) val makeDataSet : 'a list -> 'a DataSet >let x = makeDataSet [];;

Oh no! The dreaded value restriction. This one really causes some headaches. I don’t want to get too deep in a basics post, but essentially this is caused in some cases where there is no ground type value (the type rather is still undetermined when the computation gets underway).

The easiest way to fix this is just to annotate the type

> let x = makeDataSet ([]:int list);;  val x : int DataSet

Inheritance:

And we come to one other interesting problem I have seen creep up for people in F#. Let’s make a new type and inherit IComparable. This type is meaningless, but that isn’t a problem because I am just making a point about inheritance here.

 > type Comparator =
        class
          val mutable x : int
          new () = { x = 0 }
          interface System.IComparable with
            member self.CompareTo(o) = 1
          end
        end;;
type Comparator = class
                    val mutable x: int
                  end
                  with
                     interface System.IComparable
                     new : unit -> Comparator
                  end

So far so good. Let’s instantiate it and use it.

> let c = new Comparator();; val c : Comparator > c.CompareTo(1);;

  c.CompareTo(1);;
  --^^^^^^^^^^

stdin(11,2): error: FS0039: The field, constructor or member 'CompareTo' is not defined.

stdin(0,0): error: FS0039: The value or constructor 'it' is not defined.
stopped due to error

What happened? In circumstances like this where we declare a class that inherited from an interface and then explicitly instantiate that class we need to prompt the compiler to go lookup the objects appropriate interface …

> (c :> System.IComparable).CompareTo(1);;
val it : int = 1

Alternatively, we can point out that it is an IComparable inheritance when we instantiate it …

> let c = new Comparator() :> System.IComparable;; val c : System.IComparable > c.CompareTo(1);;
val it : int = 1

We could also use an object expression, but I think the point is made. We have to do something here to prompt the lookup of the interface.

Well, I hope this post will prevent a few headaches so you can get to the fun part of functional programming more quickly! This list comprises the most common errors I am seeing when I review code and when I receive questions. If you have something else you are struggling with please feel free to post it in the comments and I will respond.

Refreshing Interactive Session Values in F# (or OCaml or Haskell)

One common misunderstanding I have seen in beginners with the interactive session is how new values become defined, and especially redefined. In the interactive session, and in F# in general, every new scope creates a new environment. One could imagine these environments like a tree of named values growing with every new declaration. And a new declaration, even if it has the same name as an old one can be bound to a new environment. Due to this fashion of scoping, the consequences of redefining a value can be a little unintuitive for those coming from a C#/Java (or especially C++) background. Incidentally, this is also true with OCaml and Haskell – but I am addressing it in F# because those are the students who have been asking about this matter recently.

An example follows.

In the interactive session, let’s bind a function like so:

> #light;;
> let f () = 2;;

Now, let’s bind a function

> let a = f;;
> a ();;
val it : int = 2

Everything there is exactly as expected. Now let’s change the value returns to get something different back.

> let f () = 3;;
> a();;
val it : int = 2

2? But we redefined and then called which then calls . How could it be 2? What happened is that we defined and bound it to the environment that exists in. When we redeclared we created a new environment, which our function lives in ignorance of at the moment. If we rebind to the new environment, then we get the expected result.

> let a = f;;
> a();;
val it : int = 3

Before you think that this is a terrible anomaly, it does not happen by accident. This approach has considerable advantages in the functional programming world. For a good introduction to the implementation of environments see the Modern Compiler Implementation series.

As an example of the advantages of this kind of scoping treatment consider

> let f a = a();; val f : (unit -> 'a) -> 'a  

> let run b =
      let g = (fun () -> b()) in
      f g  > run (fun () -> 82);;
val it : int = 82
> run (fun () -> printf "Hello!\n");;
Hello!
val it : unit = ()

Clearly in this case, executes , which in turn executes . However, was implemented in complete ignorance of . was able to carry in its environment as a value to be executed. Scoping in this fashion is not a nuisance … it is a fundamental piece of the functional style of programming.

So remember, when using that interactive session with F#, you don’t just have to redeclare values and functions when you make a change to them. You should redeclare every function that depends on the changed value or function.

Starting an F# Project

A number of people have asked me recently to write something at a very basic level on coding in F#. A lot of people really just can’t wait to get their hands in the code. That’s great, let’s do it.
First download F# and install the msi package. You will get a good deal of sample code, but for the time being we are just going to keep it simple and write some code up bit by bit.
Now, F# at the moment doesn’t add a source file by default when you add a new project. Also if you start VS, add an F# project and add a source file now, you will get all sorts of tutorial code. I recommend you do that and have a look at the tutorial code at some point because it is great for a beginner. However, here we are going to set up your environment to automatically add source to new source files (as would be done in other projects) on startup. The startup file will be comprised of some basic boilerplate items most of your projects will need.

I am assuming you installed 1.9.2.9 which is what I have. For later editions just change the version number on the directory. Navigate windows explorer to

[root]:\Program Files\FSharp-1.9.2.9\bin\FsPrjProjectItems\Source_Files

Open “SourceFile.fs” with notepad and you should see a file starting with

 //F# Visual Studio Sample File

Here you see the tutorial code. Delete the whole caboodle. Now insert in its place anything you like. Mine includes a little starter code (which languages like F# make practically pointless). There is one thing I have come to enjoy in my files and that is predefined references. In F# you do get the basic references you can expect in a C# project automatically (e.g. you can just import System.Drawing you do not have to add the reference). However, when you want to add something out of the ordinary you have to go hunt down the dll file yourself and then add the text in. Rather than doing this every time, when I hunt something down I add it into my template. Consequently my template currently has references to directX dlls and remoting apis. Then I take the approach of deleting them when I don’t want them, rather than hunting them down when I do. As you will see below F# allows new references through precompilation tags starting with ‘#’. #I includes a directory to search for imported libraries, #r references a file, and #R references a file and copies it over at compile time to the local directory. Note the paths are for my system, your system may be different. My SourceFile.fs looks like:

namespace Org.Subject
#light
#I @"C:\Windows\Microsoft.NET\Framework\v2.0.50727"
#I @"C:\Windows\Microsoft.NET\DirectX for Managed Code\1.0.2902.0"
#R "Microsoft.DirectX.dll"
#R "Microsoft.Direct3D.dll"
#R "System.Runtime.Remoting.dll"</span></code>

// A description of the organization of this file.
module Main = begin

// A description of this module 

end

Open up Visual Studio (I use 2005 here) and start a new project.Under File->New->Project the standard new project dialog window pops up. Expand the tree under Other Project Types. You will see F# is available. Select it and name your project “FPlayground”. Click OK.

With that complete add a new item to your project by right-clicking on your project FPlayground and selecting Add->New Item.

Select “F# Source File” and name it fplayground.fs. Click “Add”. You should now see the template source code in your new file. You can completely remove the references today. Above the Main module replace the comment with:

// This module prints “Hello World”

Then under the declaration of the module replace the comment with

 //The function go prints “Hello World”

Then add a function “go” which prints “Hello World” making your final code file:

namespace Org.Subject
#light

// A description of the organization of this file.

module Main=begin
// The function go prints "Hello World"
 let go() = printf "Hello World\n"
end

Note the indentation of the method “go”. Now before we run it, let’s quickly review what we have typed. The first line declares a namespace (note this does not open any previous contributions to the namespace). The second line declares the “#light” syntax which indicates we will be using an indentation based coding style (rather than using “;;” to indicate statement termination and such as we will do in interactive mode). Next is a comment. We could also have used (* *) or ///. Next we open a module, and add a function go. The type signature of go is


That means go takes a unit (something like void) type and returns a void type. The type signature of this function was inferred, we did not have to explicitly state any type information. If you mouse over go, you will see the popup indicating the inferred type. Using this information before compile time is a very powerful tool for sanity checking on your program, and I recommend you do it frequently. We will talk a lot about type inference in the future, but for today we just want to get started.

Now we want to start the interactive session. Under the Visual Studio menu go Tools-> Add-in Manager …

Check the “F# Interactive for Visual Studio” option and click okay. The interactive session will popup, but it can sometimes popup as a very small window. If you don’t see it right away do a little looking to make sure it didn’t popup in the bottom corner of the screen. I like to embed the interactive session in the same place as my output, error and task lists as a tab. You can do this by dragging it to the appropriate place.

Now you can type all of the code you want in the interactive session, but a very helpful technique in visual studio allows you to send code from the display to the interactive session. Starting from below the #light statement highlight the rest of the file going down (that is, skip the namespace declaration and the #light statement). Press Alt-Enter. You will see the code binding to the interactive session.

> >

module Main : begin

val go : unit -> unit

end

Now you can test your code by typing in the interactive window

> Main.go();;

Hello World

val it : unit = ()
>

You will find in the future the interactive mode, combined with intellisense give you a very powerful tool for the checking your code out pre-compile time. These tools facilitate a kind of pre-compilation opportunity to catch errors, which when combined with the concise nature of F# provide a powerful toolset for building more reliable software under very fast-paced conditions.

To wrap up; we have gone through the installation of F#, The basic setup of project source templates, starting a project, and running the code in interactive mode. In the future we will expand on this work by looking at how to effectively manipulate modules, create automated unit tests by saving interactive sessions, and doing some other basic F# coding. So be sure to save this project somewhere so you can revisit it.