New Austin Functional Programmers Group in 2008

In his talk at CUFP Noel Welsh made a great point about conferences in functional programming being too high of a bar for people with a basic curiosity (or even skepticism) about functional programming (especially in a commercial domain). I think that small groups of people, whose agenda is simple to get together and spend some time with this subject, are an important piece of our future.

Groups like the Bay Area Functional Programmers and London Haskell Users have made great examples. Here in Austin, we will be forming the Austin Functional Programmers group. I would like this group to be an opportunity for those in this city who are interested in commercial applications of functional languages to meet others. This group will be a forum where beginners, skeptics and experts will have an opportunity to come together. I expect it will start out as a low commitment for people, and can be flexible as the level of interest becomes clear.

If you would like to sign up to the email list over the holiday break, please go to

http://groups.google.com/group/austin-fp/subscribe

I will be sending out a message just after the new year about a first meeting.

I encourage you to contact me, or go to the email list to sign up if you are interested. If there is anything specific you would like to see in a group like this, don’t hesitate to mention it.

Happy Holidays!
Chance

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.

Josh Smith on WPF and F#

Josh Smith, who has a blog I recently found on WPF wrote a few nice articles about F# back in late October and specifically his “aha” moments while interacting with WPF.  Fun reading for functional programming enthusiasts who might be new to WPF (as I am).

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.

More F# Posts

Don Syme recently mentioned on his blog Harry Pierson’s [Microsoft Enterprise Application Services] short series about F#.  Some good reading on the strengths and not-so strengths of F#.