Installing Monodevelop 3 with F# support on Ubuntu

After much experimentation and digging around on google groups (special thanks to Ibrahim Hadad) I have finally managed to get Monodevelop 3 and F# working together nicely on Ubuntu. These were the steps I took. Your mileage may vary. 🙂

(Update: Knocte has suggested a couple of modifications to simplify the process. These are now reflected below.)

1) sudo apt-get install mono-complete libgdiplus git autoconf libtool

2) Install monodevelop using the script from John Ruiz’ blog:
http://blog.johnruiz.com/2012/05/installing-monodevelop-3-on-ubuntu.html

3) Get F# source and compile:
git clone git://github.com/fsharp/fsharp
cd fsharp/
./autogen.sh --prefix=/usr
make
sudo make install

4) Run monodevelop. Go to tools, add-in manager, gallery. Install F# language binding.

5) Enjoy!

Monodevelop 3 with F# bindings

Winning!

Advertisements

Implementing map-reduce in F#

Introduction

MapReduce is a software paradigm popularised by Google in which we take a set of tuples (key-value pairs), transform (map) them into an intermediate set of key-value pairs, and then perform some aggregation (reduce) operation on the intermediate values to obtain a result set. This is a useful way to express a problem because it yields an obvious way to “divide and conquer” the computation in a way that lends itself to parallel/distributed computing, thus providing a fairly simple way to perform computations on extremely large data sets.

It can be quite difficult to grok at first, so I decided to try implementing one of the examples from the MongoDB documentation in F# (if interested, see shell example 2). In this example, we have a list of people and the types of pet each of them has. We wish to calculate the total number of each animal.

The Code

Again, F# proves to be a remarkably succinct language to express problems, in this case the built in syntactic sugar for tuples is a godsend!

UPDATE (25-May-2010) – Controlflow helpfully suggested that I could make my original code somewhat neater by using pattern matching to decompose tuples. I’ve updated the code below with these improvements.

#light

// Simple example of map-reduce  in F#
// Counts the total numbers of each animal

// Map function for our problem domain
let mapfunc (k,v) =
    v |> Seq.map (fun(pet) -> (pet, 1))

// Reduce function for our problem domain
let reducefunc (k,(vs:seq<int>)) =
    let count = vs |> Seq.sum
    k, Seq.ofList([count])

// Performs map-reduce operation on a given set of input tuples
let mapreduce map reduce (inputs:seq<_*_>) =
    let intermediates = inputs |> Seq.map map |> Seq.concat
    let groupings = intermediates |> Seq.groupBy fst |> Seq.map (fun(x,y) -> x, Seq.map snd y)
    let results = groupings |> Seq.map reduce
    results

// Run the example...
let alice = ("Alice",["Dog";"Cat"])
let bob = ("Bob",["Cat"])
let charlie = ("Charlie",["Mouse"; "Cat"; "Dog"])
let dennis = ("Dennis",[])

let people = [alice;bob;charlie;dennis]

let results = people |> mapreduce mapfunc reducefunc

for result in results do
    let animal = fst result
    let count = ((snd result) |> Seq.toArray).[0]
    printfn "%s : %s" animal (count.ToString())

printfn "Press any key to exit."

System.Console.ReadKey() |> ignore

This yields the expected results:

Dog : 2

Cat : 3

Mouse : 1

Exercise for the reader

Parallelise this implementation (for a single machine this should be trivial by using the Parallel LINQ integration provided in the F# Powerpack).

Modelling heat transfer in F# using 100 lines of code

The aim

Imagine we have a square coaster upon which we place a hot mug of tea. We wish to model the distribution of temperature across the coaster over time. For the sake of simplicity we will model the coaster only in two dimensions and we take the initial temperature across the surface to be 20\,^{\circ}\mathrm{C} except for a circle where the rim of the bottom of the mug touches the coaster, at which the temperature is 80\,^{\circ}\mathrm{C}.

In this post I’m going to show how we can model the heat equation succinctly in F#. I’m going to consider the two-dimensional case and approximate the solution at discrete spatial mesh points and at discrete time periods.

We will also plot the results by mapping the temperature onto the brightness (i.e. a heat or intensity map).

100x100mm coaster with a hot mug of diameter 50mm placed upon it.

The mathematics

In two dimensions the heat equation – taking the size of the coaster to be 100mm square – is given by:

u_{t} = c \cdot (u_{xx} + u_{yy}), 0 \leq x,y \leq 100, t \geq 0

where u(t,x,y) represents the temperature at time t and at coordinates (x,y).

We need to apply boundary conditions at the edges of the coaster. We will assume for simpliciy that the temperature along the edges of the coaster remains constant, that is:

u(t,0,y) = u(t,100,y) = u(t,x,0) = u(t,x,100) = k

We also need to set our initial conditions:

u(0,x,y) = x^2 + y^2 = r^2, r=25

To model this in F# we are going to represent the surface of the coaster using a 100×100 matrix (the matrix class is included in the F# powerpack).

Using the Euler method we can convert our continuous differential equation into a discrete difference equation:

u_{i,j}^{t+1} = u_{i+1,j}^{t} + c \cdot (u_{i-1,j}^{t} + u_{i+1,j}^{t} - 4u_{i,j}^{t} + u_{i,j-1}^{t} + u_{i,j+1}^{t})

For some constant c which represents the thermal conductivity of the surface. Note that t here is a natural number representing discrete time values.

Show me the code!

The F# code runs very close to the mathematics so it should be self-documenting (although I’ve added some comments for readability). Plotting the results is relatively straightforward: we normalize the temperatures and represent them as shades of grey, white being hottest and black being coolest.

#light
open Microsoft.FSharp.Math
open System.Drawing
open System.Drawing.Imaging
open System.Windows.Forms
open Microsoft.FSharp.Collections
open System.Linq

// Flattens a 2D array into a sequence
let array2D_to_seq arr =
   seq {for i in 0..Array2D.length1 arr - 1 do
            for j in 0..Array2D.length2 arr - 1 do yield arr.[i,j]}

// Find maximum value in a matrix
let max_value_in_matrix m =
    m
    |> Matrix.toArray2D
    |> array2D_to_seq
    |> PSeq.max

// Normalizes a matrix so its maximum value is 1
let normalize_matrix m = m * (1.0/(max_value_in_matrix m))

let mug_diameter = 50.0     //mm
let coaster_length = 100.0  //mm
let tolerance = 5.0         //we're operating on discrete space so the rim of the mug needs to have some thickness
let num_steps = 1000        //number of iterations to be modelled

// Number of rows and columns in the matrix
let rows = (int)coaster_length
let cols = (int)coaster_length

// Equation for a circle
let circle r x y = (x-coaster_length/2.0)**2.0 + (y-coaster_length/2.0)**2.0 - (mug_diameter/2.0)**2.0

// Inital conditions function
let initialValues (x:int) (y:int) =
    match x,y with
    | (x,y) when circle (mug_diameter/2.0) (float(x)) (float(y)) >= 0.0 && circle (mug_diameter/2.0) (float(x)) (float(y)) <= tolerance**2.0 -> 80.0
    |_ -> 20.0

// Create matrix representing initial conditions
let initialConditions = Matrix.init rows cols initialValues |> normalize_matrix

let c = 0.6                         //Thermal conductivity
let delta_t = ((1.0) / 2.0*c)/2.0   //Time interval

// Our difference equation
let rec temp_at x y (o:float) (l:float) (r:float) (t:float) (b:float) = o + c * delta_t * (r+l+4.0*o+t+b)

// Mapping matrix u(t) to u(t+1)
let newMatrix (m:matrix) = m |> Matrix.mapi(fun i j temp ->
    match (i,j) with
    | (i,j) when i = 0 || j = 0 || i = rows-1 || j = cols-1 -> 0.0 //Boundary conditions
    |_ -> temp_at i j (m.[i,j]) (m.[i-1,j]) (m.[i+1,j]) (m.[i,j+1]) (m.[i,j-1]))

// Recursive function to determine the temperatures at time t
let rec heatmap_at t = match t with
                       | 0 -> initialConditions
                       |_ -> heatmap_at (t-1) |> newMatrix

let format = Imaging.PixelFormat.Format24bppRgb

let toBitmap (arr:Color[,]) =
    // Create the bitmap
    let image = new Bitmap(arr.GetLength(0),arr.GetLength(1),Imaging.PixelFormat.Format24bppRgb)
    for i=0 to image.Width-1 do
      for j=0 to image.Height-1 do
        image.SetPixel(i, j, (arr.[i,j]))
      done
    done
    image

let intensityMap intensity = Color.FromArgb((int (intensity * 255.0)),(int (intensity * 255.0)),(int (intensity * 255.0)))

let intensities =
    heatmap_at num_steps |> normalize_matrix
    |> Matrix.toArray2D
    |> Array2D.map intensityMap

let heatBitmap = intensities |> toBitmap

let form = new Form(
                Text = "F# Heat Map",
                Size = heatBitmap.Size)

let pic_box = new PictureBox(
                   BorderStyle = BorderStyle.Fixed3D,
                   Image = heatBitmap,
                   Size = heatBitmap.Size,
                   Dock = DockStyle.Fill,
                   SizeMode = PictureBoxSizeMode.StretchImage)

form.Controls.Add( pic_box )

#if INTERACTIVE
form.Show()
#else
Application.Run(form)
#endif

Let’s take it for a spin!

Here I have taken snapshots at discrete times t 0, 50, 100, …, 1000 with c = 0.6.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Quite an impressive simulation for just 100 lines of code – including comments and white space!

References

Parallel Numerical Solution of 2-D Heat Equation, Verena Horak and Peter Gruber.

The Heat Equation, Wikipedia

Euler method, Wikipedia