Inside F#

Brian's thoughts on F# and .NET

Archive for March, 2008

Pipelining in F#

Posted by Brian on March 30, 2008

In my previous blog entry, I mentioned how pipelining interacts with type inference.  I wanted to find a natural example to talk about writing pipelines in F#, and Wikipedia helped out.  On this Wikipedia page describing unix command-line pipelining, there is an example of a unix pipeline that spell-checks a web page at a given URL.  So let’s write a similar tool in F#.  The logic of the individual steps in F# is a little different from the unix example, but it’s nevertheless still a great example of a long pipeline in action.

open System.IO
open System.Net
open System.Text.RegularExpressions

// fetch a web page
let HttpGet (url: string) =
    let req = System.Net.WebRequest.Create(url)
    let resp = req.GetResponse()
    let stream = resp.GetResponseStream()
    let reader = new StreamReader(stream)
    let data = reader.ReadToEnd()
    resp.Close()
    data
    
// Use Word to spellcheck (assumes you have referenced Microsoft.Office.Interop.Word.dll)
let msword = new Microsoft.Office.Interop.Word.ApplicationClass()
let mutable x = System.Reflection.Missing.Value :> System.Object
let Spellcheck text = 
    msword.CheckSpelling(text, &x, &x, &x, &x, &x, &x, &x, &x, &x, &x, &x, &x)

// find all misspelled words on a particular web page, using a pipeline 
printfn "misspelled words:"
HttpGet "http://www-static.cc.gatech.edu/classes/cs2360_98_summer/hw1"
|> fun s -> Regex.Replace(s, "[^A-Za-z']", " ")
|> fun s -> Regex.Split(s, " +")
|> Set.ofArray 
|> Set.filter (fun word -> not (Spellcheck word))
|> Set.iter (fun word -> printfn "   %s" word)

Let’s examine the pipeline (the last six lines of code) more closely.  We start by fetching a page from the web (a page I clearly picked at random, with absolutely no significance whatsoever :) ) using our HttpGet function, which returns the contents as a string:

Then we pipe this string into a function that produces a new string where all the non-word characters have been replaced by spaces:

|> fun s -> Regex.Replace(s, "[^A-Za-z']", " ") 

Then we pipe that string into a function that splits the string on whitespace into an array of words:

|> fun s -> Regex.Split(s, " +") 

Then we’d like to sort that array and get rid of duplicates, and we can do that simply by creating a Set of the words:

|> Set.ofArray 

Then we want to filter down the set to only those words which fail to spell-check:

|> Set.filter (fun word -> not (Spellcheck word)) 

And finally, we print out each remaining (misspelled) word in the Set:

|> Set.iter (fun word -> printfn "   %s" word) 

That’s a fine example of code that reads very naturally in a long pipeline. 

(Pipelining also demonstrates one of the benefits of well-authored functions that take arguments in curried form rather than tupled form.  However I’ll save those details for another blog entry.)

Of course, we could have written our web-spell-checker without using pipelining.  In one big expression, it looks like this:

(Set.iter (fun word -> printfn "   %s" word)
    (Set.filter 
        (fun word -> not (Spellcheck word))
        (Set.ofArray
            (Regex.Split(
                Regex.Replace(
                    HttpGet "http://www-static.cc.gatech.edu/classes/cs2360_98_summer/hw1"
                    "[^A-Za-z']"
                    " "
                ), " +"
            ))
        )
    )
)

Yuck.  This looks similar to how you’d write this code as one huge expression in any language (e.g. C#), and it reveals the problem with using huge expressions: they’re very hard to read.  This is true especially because expressions evaluate inside-out, which means the "first thing that happens" is nested in the middle of the expression, and then its result is passed as an argument to some function surrounding it, which is passed as argument to a function surrounding it… Code with deeply nested function calls just reads unnaturally to humans, since it’s easier to grok things in small bits in the sequence in which they occur.  As a result, the other main way to write such code without pipelining is to name each intermediate expression:

let page = HttpGet "http://www-static.cc.gatech.edu/classes/cs2360_98_summer/hw1"
let pageWords = Regex.Replace(page, "[^A-Za-z']", " ")
let wordArray = Regex.Split(pageWords, " +")
let wordSet = Set.ofArray wordArray
let filteredWordSet = Set.filter (fun word -> not (Spellcheck word)) wordSet
Set.iter (fun word -> printfn "   %s" word) filteredWordSet

That code reads pretty well.  The functions now appear in the order they will be executed, and each line "does one thing".  Each intermediate result is named, and then referenced by name.  Depending on the exact nature of what you’re coding, these names can be either a good thing or a bad thing, I think, either helping or hindering the readability of the code.  In general, I feel you should name intermediate values only if the name you introduce adds readability-value to the code by explaining what’s happening.  In this example it’s actually a pretty close call, assuming the reader has a modest familiarity with the functions in the Regex class and the Set module.  So you’ll have to tune your personal coding aesthetic to decide whether to code like the example above with all the "let"s, or using the pipelining style:

HttpGet "http://www-static.cc.gatech.edu/classes/cs2360_98_summer/hw1" 
|> fun s -> Regex.Replace(s, "[^A-Za-z']", " ") 
|> fun s -> Regex.Split(s, " +") 
|> Set.ofArray  
|> Set.filter (fun word -> not (Spellcheck word)) 
|> Set.iter (fun word -> printfn "   %s" word) 

Of course, it’s not all-or-nothing.  A mix of styles often produces the most readable code, and I am rather fond of:

let page = HttpGet "http://www-static.cc.gatech.edu/classes/cs2360_98_summer/hw1"
let words = Regex.Replace(page, "[^A-Za-z']", " ")
            |> fun s -> Regex.Split(s, " +")
            |> Set.ofArray
words |> Set.filter (fun word -> not (Spellcheck word))
      |> Set.iter (fun word -> printfn "   %s" word)

for this example.  I think I like this form of the code because it enables the eye to scan down the left side of the code and see the major conceptual tasks happening: we’re going to get a page, we’re going to compute the words, and we’re going to do something with those words.

So there you go.  Hopefully now you have a better understanding of the pipeline operator "|>" – how it works and when you might choose to use it.  Given what a simple thing it is (recall that "x |> f" just means "f x"), this little operator sure provokes a lot of discussion!

Posted in Uncategorized | 3 Comments »

On Sequences, SyndicationFeeds, and Syntax…

Posted by Brian on March 30, 2008

Back when I worked on WCF, one of the cool features we delivered in .NET 3.5 was support for consuming and publishing SyndicationFeeds (RSS or Atom).  So that provides a nice domain for a short bit of code that will let me talk about some pieces of F#.(Incidentally, it was when writing this code that I noticed my Windows Live Space blog did not yet have a title, so I corrected that today.  Like the new title?)  Anyway, here’s the code:

open System.Xml
open System.ServiceModel.Syndication

let reader = XmlReader.Create("http://lorgonblog.spaces.live.com/feed.rss")
let feed = SyndicationFeed.Load<SyndicationFeed>(reader)
printfn "Feed Title: %s" feed.Title.Text
printfn "Feed Description: %s" feed.Description.Text
feed.Items |> Seq.iter (fun item ->
    printfn "entry: %s %s" (item.PublishDate.ToString("dd MMM yyyy")) item.Title.Text
)

As you can guess, this prints out a summary of my blog, by reading the RSS feed and then printing out some select bits.  The part of F# I want to highlight here is "Seq".  The Seq module contains methods for dealing with sequences of things.  (I haven’t discussed modules yet on this blog, but for the curious reader in the meantime, it would not hurt too much to equate "module" with "static class" in your head.)  In F#, "seq" is just a short alias for "IEnumerable".  Thus in the code below, x, y, and z each describe objects with the same type and value:

let x = [1; 2; 3] :> int seq 
let y = [1; 2; 3] :> seq<int
let z = [1; 2; 3] :> System.Collections.Generic.IEnumerable<int>

The ":>" operator does an "upcast"; in the examples above I create list<int>s, but then upcast them to IEnumerable<int>s so that the variables are assigned those types.  Each variables has the same type, just spelled three different ways.  "IEnumerable<int>" is just what you already know from C# programming.  "seq<int>" is the same thing, only using "seq" as an alias for "IEnumerable".  And "int seq" is another way to write "seq<int>"; this is just one of those OCaml-isms, where "’a GenericType" means the same thing as "GenericType<’a>".  You see this most often with lists – e.g. people may write code that mentions the type "int list", which is just another way to write "list<int>".  (For sequences of ints, I expect I shall prefer the spelling "seq<int>", though this is one of many areas of F# style/preference where I think we’ve yet to decide on a coding guideline.)

Anyway, sequences are commonly used in F#, and just as in C#, one of the most common things to do with them is to perform some operation on each element of the sequence.  This is what "Seq.iter" does in the original code example.  This F# code:

feed.Items |> Seq.iter (fun item -> 
    printfn "entry: %s %s" (item.PublishDate.ToString("dd MMM yyyy")) item.Title.Text 
)

does the same as this C# code:

foreach (var item in feed.Items)
{
    Console.WriteLine("entry: {0} {1}", item.PublishDate.ToString("dd MMM yyyy"), item.Title.Text);
}

As is typical in F#, we start with the sequence itself ("feed.Items" in this example) and then use the pipelining operator "|>" to send that data through some function.  "x |> f" just evaluates to "f x", which means that we could write

Seq.iter (fun (item : SyndicationItem) ->
    printfn "entry: %s %s" (item.PublishDate.ToString("dd MMM yyyy")) item.Title.Text
) feed.Items 

instead.  However when we write it that way, we have to explicitly provide a type annotation for "item" to say that it is a "SyndicationItem".  This is because type-inference in F# works in a left-to-right manner: when written without the pipeline operator, we reach "item.PublishDate" without yet knowing the type of "item" and so we are out of luck, whereas when we do use the pipeline operator, "feed.Items" (which is a seq<SyndicationItem>) occurs first, so that by the time we reach "fun item" we can infer the proper type (SyndicationItem) based on the information we’ve already seen.  Writing code using the pipeline operator is one of those things that feels a little weird at first but then quickly becomes second nature.  (I think I’ll have to have to devote a future blog post to pipelining.)

This was going to be where I stopped writing, but as I was re-reading this blog entry, I found myself wondering, if "Foo<T>" and "T Foo" are two ways to spell the same type name, is there a way to do it if there is more than one generic type argument?  And there is:

type Pair<’a,’b>(a : ‘a, b : ‘b) =
    member this.A = a
    member this.B = b

let p1 = new Pair<int,string>(42, "life")
let p2 : (int, string) Pair = p1

In that example, p1 and p2 have the same type, spelled different ways.  That is, "Pair<int,string>" can also be written "(int,string)Pair".  This is even true in the class definition, that is, I can write

type (‘a, ‘b) Pair2(a : ‘a, b : ‘b) =
    member this.A = a
    member this.B = b

But I have never seen anyone write F# code that way unless they were originally an OCaml programmer.  I think it is pretty safe to assume that the vast majority of F# code you will encounter will use the "Angle<Brackets>" style for writing generic types.  I’ll try to be careful and consistently use the angle brackets style in my code in the future.

Posted in Uncategorized | 1 Comment »

Some common F# pitfalls to avoid

Posted by Brian on March 25, 2008

When reading other people’s blogs about F#, there are two common pitfalls I often see people make.  The first pitfall is that sometime people blindly code a recursive solution, without consideration as to whether the function is tail-recursive or not (which could lead to a StackOverflowException).  The second pitfall is that I often see people code little algorithms on lists that wind up being O(N^2) when in fact there’s a simple way to make it O(N).  So I thought I would demo this with some code.  The library function "List.rev" will reverse a list, but say we wanted to write that function ourselves… the code here shows two ways to do it, and the implications of those two strategies:

open System.Diagnostics

// naive way to reverse a list
//  – not tail recursive (can blow stack)
//  – O(N^2) algorithm (due to way append ‘@’ operator is used)
let rec rev1 list = 
    match list with
    | [] -> []
    | h::t -> (rev1 t) @ [h]

// one much better way
//  – uses loops and mutables, but is still short and readable (not inelegant)  
//  – O(N)
let rev2 list =
    let mutable result = []
    let mutable cur = list
    while cur <> [] do
        let h::t = cur
        result <- h :: result
        cur <- t
    result
    
// demo that functions do the right thing
let sample = [1; 2; 3; 4]
printfn "%A" (rev1 sample)
printfn "%A" (rev2 sample)
printfn "%A" (List.rev sample)  // the F# library function for reversing

let stopWatch = new Stopwatch()
let ResetStopWatch() = stopWatch.Reset(); stopWatch.Start()
let time op a =
    ResetStopWatch()
    let result = op a
    let ms = stopWatch.ElapsedMilliseconds
    result, ms

let timeEachReverse l =
    // do each twice, and sum times (to average a little)
    let (_,Lrevt1) = time List.rev l
    let (_,rev1t1) = time rev1 l
    let (_,rev2t1) = time rev2 l
    let (_,Lrevt2) = time List.rev l
    let (_,rev1t2) = time rev1 l
    let (_,rev2t2) = time rev2 l
    (rev1t1 + rev1t2, rev2t1 + rev2t2, Lrevt1 + Lrevt2)

let showResults n =
    let list = [for i in 1..n -> i]  // [1; 2; 3; ... n]
    let (rev1time, rev2time, Lrevtime) = timeEachReverse list
    printfn "rev1:%5d  rev2:%5d  List.rev:%5d" rev1time rev2time Lrevtime
    
showResults 20000
// One run on my box printed:
//[4; 3; 2; 1]
//[4; 3; 2; 1]
//[4; 3; 2; 1]
//rev1:25189  rev2:    4  List.rev:    0

As you can see, the naive solution took more than 25 seconds to (twice) process a 20,000-element list, whereas the better solution took just 4ms and the library call executed in a blink.  So the moral is: don’t stumble into these pitfalls.  When writing recursive functions that can process arbitrarily large data, be careful to either use tail recursion or else switch to iteration.  And when writing functions on lists, be wary of how you construct new list values; it is especially easy to abuse the append (@) operator (which must copy its left-hand argument) and wind up with something N^2 instead of N.

This little bit of code shows off one other F# feature I rarely see people use.  Pattern-matching – it’s not just for the "match blah with" statement!  You can use patterns in most binding constructs; "let" is the most common example.  As a result, rather than saying

    while cur <> [] do
        let h = cur.Head 
        let t = cur.Tail 

we just said

    while cur <> [] do
        let h::t = cur

which binds the names "h" and "t" at once.  Similarly, since timeEachReverse returns a tuple of three values, we just write

    let (rev1time, rev2time, Lrevtime) = timeEachReverse list

to bind each result to a different name.

Posted in Uncategorized | 3 Comments »

Attributes in F#

Posted by Brian on March 24, 2008

One request I’ve had is to show F# code that uses attributes.  Rather than do anything too elaborate, I’ve just written a short, meaningless progress that will let me demonstrate using attributes in F# as well as a couple other noteworthy things.  Here’s the code:

namespace Example

open System
open System.Reflection
open System.Diagnostics

[<DebuggerDisplay("{DisplayMe()}")>]
type D =
    | A of int
    | B of string * bool
    member this.DisplayMe() =
        sprintf "%A" this
    //override this.ToString() =
    //    sprintf "%A" this

module MainMod =
    let Main() =
        let x = A(3)
        let y = B("cool", true)
        printfn "Hello" 
        Console.ReadKey() |> ignore    
        
    [<assembly: AssemblyVersion("1.2.3.4")>]
    do
        Main()

Attributes work much as they do in C# – the main difference is that they are contained in paired brackets like this: [<Attr>].  In the code above, I use the DebuggerDisplay attribute on the discriminated union type "D" so that runtime values of this type display better in the debugger "locals" window.  This F# code also suggestively shows that discriminated union types get compiled into classes, which means they can have member functions (like DisplayMe) just like ordinary classes.  (An alternative way to get a "pretty" experience for values of a particular type in the debugger is to override ToString for that type, as suggested by the commented-out portion of the code.)

Assembly-scoped attributes can only appear in a limited number of places.  One such location is the main "do" block of a module.  In this example, I use the AssemblyVersion attribute to try to provide metadata about the assembly.  Right now the F# compiler fails to respect this attribute, but that is just a bug.  (If you really need to specify the assembly version, you can do so by passing a flag to the compiler, e.g. "fsc –version 1.2.3.4 foo.fs")

That’s all for now!  Hopefully next time I’ll go back to writing about solving interesting problems with F#, but sometimes it’s useful just to take a moment to show off some syntax details.

Posted in Uncategorized | 1 Comment »

What will F# deliver?

Posted by Brian on March 22, 2008

I’m happy to see a number of people blogging about F# when I search the web these days, but I haven’t seen anything posted about our concrete plans since this post five months ago which declared that

We will be partnering with Don Syme and others in Microsoft Research to fully integrate the F# language into Visual Studio and continue innovating and evolving F#.  In my mind, F# is another first-class programming language on the CLR.

So I thought I would post a minor update regarding our plans.  No dates are firm, but our intention is to have a CTP release (Community Technology Preview) some time this summer.  Nothing is set in stone, but the main features I think are most likely to be in the CTP are:

  • Runtime components:
    • fsc.exe, the compiler that knows the F# language
    • fsi.exe, the interactive command environment
    • the F# libraries (usual stuff, ranging from immutable lists to asynchronous computations library)
    • an msbuild task which lets you build an F# ".fsproj" project from the command line
  • Design-time components (Visual Studio 2008 integration):
    • F# language service, which provides syntax highlighting, intellisense, tooltips, etc.
    • F# project system, which enables you to add/remove .fs files, reference dlls, etc.
    • F# interactive window, where fsi is hosted inside Visual Studio

This is roughly on par with what you can currently download in the F# research release.  Though there will be some feature improvements, a lot of the work we have now involves driving up the product quality by fixing bugs and usability issues.  (Thanks to everyone who has already given us feedback through fsbugs@microsoft.com.)

So stay tuned in to the blogs of those on the F# product team (which I linked to in a prior post) for more info about all aspects of F# and our plans for deliverables in the coming months.  :)

Posted in Uncategorized | 2 Comments »

Pretty strings, and another scripting games problem

Posted by Brian on March 8, 2008

A mildly useful library is one that allows us to easily create "pretty" grids of text that display well on fixed-width-text consoles.  A very simple version of such a library is easy to describe: Imagine a new data type called "PrettyString" that represents a "box" of text.  There are two main operators on PrettyStrings: "++" for horizontal concatenation, and "%%" for vertical concatenation.  The function "pretty" takes in a string and returns a PrettyString object.  Here’s a short demo of such a library:

let blank = pretty " "
let str1 = (pretty "hey") %% (pretty "you") %% (pretty "there")
let str2 = pretty "check this out"
let row = str1 ++ blank ++ str2 ++ blank ++ str1
let rows = row %% row
printf "%s" (rows.ToString())

and here is the output:

hey   check this out hey
you                  you
there                there
hey   check this out hey
you                  you
there                there

Get the idea?  Using a few horizontal and vertical concatenations, it is pretty easy to lay out text into interesting grid formations.

There are many possible strategies for implementing the PrettyString type.  One of the most straightforward implementations is realized by a class hierarchy, where the concatenation operators just create an object graph that mimics the grid structure being laid out by the user.  Here is code that uses that implementation strategy:

open System
open System.Text
open Microsoft.FSharp.Collections

/// PrettyStrings are strings that support vertical and horizontal concatenation
/// for creating grids of text.
[<AbstractClass>]

type PrettyString() = 
    /// The number of lines in this PrettyString
    abstract Height : int
    /// The width of this PrettyString (width of the longest line)
    abstract Width : int
    /// Get the nth line.  If n is not in the range [0..Height), then return the empty string.
    abstract Line : int -> string
    override this.ToString()
        let sb = new StringBuilder()
        for i in 0 .. this.Height do
            sb.Append(this.Line i) |> ignore
            sb.Append("\n") |> ignore
        sb.ToString()

type StringLiteral(s:string) =
    inherit PrettyString()
    // TODO: if the input string contains newline characters, 
    // things will be ugly.  Ignoring that issue for now.
    override this.Height = 1
    override this.Width = s.Length
    override this.Line n = if n <> 0 then "" else s
    
type Vertical(top:PrettyString, bottom:PrettyString) =
    inherit PrettyString() 
    override this.Height = top.Height + bottom.Height
    override this.Width = Math.Max(top.Width, bottom.Width)
    override this.Line n =
        if n < 0 || n >= this.Height 
        then ""
        else if n < top.Height
             then top.Line n
             else bottom.Line (n – top.Height)

type Horizontal(left:PrettyString, right:PrettyString) =
    inherit PrettyString()
    override this.Height = Math.Max(left.Height, right.Height)
    override this.Width = left.Width + right.Width
    override this.Line n =
        String.Concat(left.Line(n).PadRight(left.Width)
                      right.Line(n))

let pretty s = new StringLiteral(s) :> PrettyString

let (%%) x y = new Vertical(x,y) :> PrettyString
let (++) x y = new Horizontal(x,y) :> PrettyString

PrettyString is an abstract class that knows its width and height, and can return its nth line of text, or the whole text string (containing newlines).  There are three concrete subclasses (StringLiteral, Vertical, Horizontal) which correspond to the three main functions of the library API (pretty, %%, ++). 

The implementation is straightforward.  For those readers unfamiliar with F#, here is a brief synopsis of some syntax.  The "type" keyword introduces new types; in the code above, F# infers from the members in the body of the types that these types are classes.  "inherit" defines a subclass relationship.  You can explicitly specify the type of an entity with the syntax "name:type", though thanks to type inference you rarely need to write explicit type annotations. The keywords "abstract" and "override" mean the same as in C#.  (Though there are no examples here of it, if we wanted to declare a normal non-virtual method, we would use the "member" keyword.)  The parenthesized arguments after the type name in the type declaration are used to declare a constructor for the class; these arguments can be treated liike fields in the class.  ":>" is the upcast operator, used, for example, so that "pretty s" has type PrettyString rather than type StringLiteral.  F# allows you to define new infix operators, as we did with "%%" and "++" here.  Take a moment to read over the code and understand it.

With this code in hand, we are well-poised to code up a solution to another problem from the 2008 Winter Scripting GamesThis problem asks us to pretty print a calendar for a given month and year.  So let’s say our goal is to write a "calendar" function such that

let Feb2008 = calendar 2008 2
printf "%s" (Feb2008.ToString())

yields output like

February 2008
Su Mo Tu We Th Fr Sa
                1  2
 3  4  5  6  7  8  9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29

Here’s the code:

let calendar year month =
    let maxDays = DateTime.DaysInMonth(year, month)
    // make the column that starts with day i (e.g. 1, 8, 15, 22, 29)
    let makeColumn i =
        let prettyNum (i:int) = pretty(i.ToString().PadLeft(2))
        let mutable r = prettyNum i
        let mutable j = i + 7
        while j <= maxDays do
            r <- r %% prettyNum j
            j <- j + 7
        r
        
    let firstOfMonth = new DateTime(year, month, 1)
    let firstDayOfWeek = int firstOfMonth.DayOfWeek
    // create all the columns for this month’s calendar, with Sundays in columns[0]
    let columns = Array.create 7 blank
    for i in 0 .. 6 do
        columns.[(i + firstDayOfWeek) % 7] <- makeColumn (i+1)
    // if, for example, the first of the month is a Tuesday, then we need Sunday and Monday
    // to have a blank in the first row of the calendar   
    if firstDayOfWeek <> 0 then
        for i in 0 .. firstDayOfWeek-1 do
            columns.[i] <- blank %% columns.[i]
    // put the weekday headers at the top of each column
    let dayAbbrs = [| "Su"; "Mo"; "Tu"; "We"; "Th"; "Fr"; "Sa" |]
    for i in 0 .. 6 do
        columns.[i] <- pretty(dayAbbrs.[i]) %% columns.[i]
    // Horizontally concatenate all of the columns together, with blank space between columns
    let calendarBody = Array.reduceBack (fun x y -> x ++ blank ++ y) columns
    // Surely there must be a .NET call that turns a month number into its name,
    // but I couldn’t find it when I was typing this up. 
    let monthNames = [| "January" ; "February"; "March"; "April"; "May"; "June"
        "July"; "August"; "September"; "October"; "November"; "December" |]
    let titleBar = pretty(sprintf "%s %d" monthNames.[month-1] year) 
    titleBar %% calendarBody

Again, for those unfamiliar with F#, here are a few more notes on syntax.  "let" is used to define both values and functions.  "mutable" is used for defining mutable variables, which can later be re-assigned new values using the assignment operator "<-".  Array literals appear in [| these brackets |], and arrays are indexed like.[this].  Functions can be defined to take arguments either as tuples or in curried form.  Outside of F#, .NET functions take tuples, so for example we call DaysInMonth with the arguments inside parentheses and separated by commas:

    DateTime.DaysInMonth(year, month)

whereas typically functions you write in F# use the curried form, so for example calling this F# library function (that creates a fresh array with a given default value in each cell) looks like this:

    Array.create 7 blank

where the arguments are not contained in parentheses or separated by commas. 

One common idiom in functional programming is using a "fold" (sometimes called a "reduce") to apply a function to a given data structure to accumulate a final value. The call to Array.reduceBack is an example of this.  The syntax "fun args -> body" defines a new anonymous function (lambda).  In the calendar function, this expression

  Array.reduceBack (fun x y -> x ++ blank ++ y) columns

is a way to compute

   columns.[0] ++ (… ++ (columns.[5] ++ columns.[6])…)

Have a look at the definition of "reduceBack" in the library docs if you have not encountered such "fold"s before.

Though you could write the "calendar" function without using PrettyString, our little library makes it easy to make the rows and columns line up just so.  In fact, I have been sitting on the PrettyString code for a couple weeks, and then recently I discovered this calendar problem and realized it makes for a great excuse to post a blog entry about PrettyString.  Furthermore, I am glad to have written my first F# blog post that shows code with classes and class hierarchies.  Many F# blogs just illustrate the functional core of the language, and I want to provide some balance by showing code with classes, arrays, mutable variables, and the many other features that make F# effective as a general purpose programming language.

Posted in Uncategorized | 1 Comment »

I’m on the F# team

Posted by Brian on March 8, 2008

In case you hadn’t already guessed (or read elsewhere), I recently took a job as a developer on the F# team at Microsoft.  Our team is responsible for integrating F# into Visual Studio and making F# another first-class programming language for the CLR.  Here is the announcement from a few months ago that provides an overview.

We are still a relatively small team, but a number of people on the team blog: Jomo is another developer, Chris is a tester, Luke is a program manager, and Don is the language architect.  So if you’re looking for info on F#, those blogs are one place to start.  Of course, the F# web site and its documentation and community links are another great way to find information about the language.  In addition to reading info on the web and downloading the latest distribution to try out the language, I also read Expert F# to get a jump-start on learning the details of the language.

One very cool aspect of this job is that we are developing the tools for F# using… F#.  That is, the vast majority of the development work on the compiler, libraries, and Visual Studio integration (things like syntax highlighting, Intellisense, project system, …) is being done in F#.  A number of people whom I have talked to recently have only heard about F# in passing, and they’ve had the impression that F# is a functional language, or a little scripting language, or some other narrow view of what F# is.  I can easily understand how people get this impression – a lot of people blogging about F# are just posting little scripting-snippet-solutions to small programming problems (and I’m one of them, as you can see from my previous blog post).  Though F# is a great language for this kind of programming "in the small", it is also a very effective tool for engineering large software, as exemplified by our team’s own work on the compiler and Visual Studio integration.  In my daily work, I wrote code like you see on a lot of the blogs, with tuples, discriminated unions, and pattern matching.  But I also write code with plenty of classes and interfaces – code that heavily leverages the rest of the .NET Framework.  You see less of the latter kind of code in people’s short blog posts about F#, so it’s easy to get a biased view of the language from reading what turns up from a quick web search or blog roll.

Anyway, I just wanted to write a belated introduction into what I am doing, and suggest why most of the future blog posts you’ll see from me are likely to be about F# code.  :)

Posted in Uncategorized | Leave a Comment »

Play Ball in F#

Posted by Brian on March 5, 2008

I had recently been checking out the 2008 Winter Scripting Games, and today I read a couple blogs with solutions to the Play Ball problem (go read the problem description – it’s short).  This looked like it should be straightforward in F#, so I coded up my own solution:

open System

let rng = new Random() let shuffle (array : 'a array) = // ' let n = array.Length for x in 1..n do let i = n-x let j = rng.Next(i+1) let tmp = array.[i] array.[i] <- array.[j] array.[j] <- tmp array let teams = [| 'A' .. 'F' |] let n = teams.Length let ans = seq { for i in 0..n-1 do for j in i+1..n-1 do yield (teams.[i],teams.[j]) } |> Array.ofSeq |> shuffle for x in ans do printfn "%A" x

(Sorry about the syntax highlighting – my code-snippet widget just knows C#, so "let"s are not highlighted as keywords and it thinks the generic type variable ‘a starts a character literal.)

The solution has just two main parts.  First, the solution demands the results in random order, so I wrote a quick function to shuffle an array.  This is based on the algorithm I recently read in Programming Pearls.  You walk down the array from index n-1 down to 0, and at each element, you swap it with some random element from 0..current.  This generates a random permutation.

Now we just need the list of pairings.  Each team needs to be paired with every other team exactly once, and this is easily expressed as "nested loops" in a sequence comprehension.  We yield a tuple of values for each matchup, and so the sequence comprehension results in:

('A', 'B')
('A', 'C')
('A', 'D')
('A', 'E')
('A', 'F')
('B', 'C')
('B', 'D')
('B', 'E')
('B', 'F')
('C', 'D')
('C', 'E')
('C', 'F')
('D', 'E')
('D', 'F')
('E', 'F')

We then pipeline that sequence through a couple more functions: first "Array.ofSeq", which converts the sequence to an array; then our "shuffle" function, which shuffles the array (mutating the array in place and returning a reference to the original array object).  Finally we print out the results, and get an answer like

('B', 'F')
('C', 'D')
('B', 'E')
('D', 'F')
('A', 'F')
('D', 'E')
('A', 'D')
('C', 'F')
('B', 'C')
('A', 'C')
('C', 'E')
('A', 'E')
('B', 'D')
('E', 'F')
('A', 'B')

which is what we desire.

Posted in Uncategorized | Leave a Comment »

 
Follow

Get every new post delivered to your Inbox.

Join 30 other followers