Inside F#

Brian's thoughts on F# and .NET

F# function types: fun with tuples and currying

Posted by Brian on April 3, 2008

I wanted to write more about currying, but I realize that currying, tuples, function types, lambda, and partial application are all related topics, and I should at least give an introduction to how these work in F# before going into any particularly meaty examples.  So today’s blog entry will be a primer for these topics with regards to F#.

Tuples

Tuples are a good place to start.  A tuple is a group of two or more values (e.g. a pair, a triplet, etc.).  These are written as comma-separated entities in F#.  Here are a couple examples of tuples:

// t2 : int * string
let t2 = (3, "foo")
// t3 : int * string * bool
let t3 = (4, "bar", true)

For each example, I have written the explicit type annotation in a comment above it.  Here "t2" is a 2-tuple containing an int and a string.  The name of this type is "int * string"; tuple types in F# are written with "*".  Similarly, "t3" is a 3-tuple that also contains a bool.

The parentheses around the tuple value are optional.  That is, I could have written

let t2 = 3, "foo"

However people commonly write the parentheses for clarity, and I would encourage you to do so.  (I find that to my eyes, the comma too easily "disappears" without the parens.)

The unit type

There are no 0-tuples or 1-tuples.  Trying to write examples illustrates why:

// u : unit
let u = ()
// x : int
let x = (3)

An empty pair of parentheses denotes the only value of the "unit" type.  The type called "unit" in F# is the closest analog to "void" in a language like C#.  Functions that don’t need to return values (because they are invoked only for their effects) return unit.  And, not unexpectedly, parenthesizing a single value does not affect the value or its type.  (Like in most languages, one main purpose of parentheses is merely to override the normal operator precedence when writing expressions where you need a particular evaluation order, as in "3 * (2 + 1)".  And so "(3)" is just the "parenthesized version" of "3".)

Function types

Now that we have a basic understanding of tuple types and the unit type, let’s consider some function types.  Consider this F# code:

// f : int -> string -> unit
let f x s = 
    printfn "%d %s" x s

// g : int * string -> unit
let g(x,s)
    printfn "%d %s" x s
    
f 3 "foo"   // prints 3 "foo"
g(3, "foo") // prints 3 "foo"

The functions "f" and "g" are similar, but different.  They differ in how they accept arguments.  f’s arguments are curried, whereas g’s arguments are tupled.  This distinction is visible at the call site.  A "curried" function is called by separating its arguments by whitespace, whereas a "tupled" function is called with a comma-separated list of values enclosed in parentheses.  And we know that a comma-separated list of values enclosed in parentheses creates a tuple, so you might guess that you could also write

g t2        // prints 3 "foo"

and you’d be right!  This is clear by the type of g: "int * string -> unit".  In general, "A -> R" names the type of a function that takes an argument of type A and returns a value of type R.  So g’s type tells us that it takes an int-string 2-tuple and returns unit.  Make sense?

So what of f?  It’s type was "int -> string -> unit".  The arrow "->" is right associative, which means that this type can be interpreted as "int -> (string -> unit)".  And so if for the moment I define "A" to be "int" and "R" to be "string -> unit", we can see that f is a function that takes and A and returns an R – that is, f is a function that takes an "int" and returns a "function which takes a string and returns unit".  This becomes more apparent if I add parentheses to f’s call site:

(f 3) "foo" // prints 3 "foo"

Function application associates to the left, which means that this call to f means the same thing as the previous one.   Thus we can interpret this code as calling a one-argument function f, that takes an int and returns a new one-argument function: one that takes a string and returns unit.  To make this even more apparent:

// fp : string -> unit
let fp = f 4
fp "bar"     // prints 4 "bar"

Here I have applied f to just one argument and named this new result "fp".  It has the expected type – a function that takes a string and returns unit.  The technique of calling a function with fewer arguments than it expects (resulting in a new function that expects the rest of the arguments) is called "partial application".  We say that "fp" is a partial application of "f", it has already taken the int, but is still "waiting" to take the string.  This is the essence of the "curried" form of functions; partial application can be done simply by omitting trailing arguments.

Partial application can be done for functions that take tupled arguments as well, but doing so requires an explicit lambda.  Consider:

// gp : string -> unit
let gp = fun s -> g(4, s)
gp "bar"     // prints 4 "bar"

Here we have done the same thing with "g", we’ve handed it an int (the value 4) and named the result "gp".  gp is still "waiting" for the string, which means we can call it with just the string as seen in the example.  Note that we had to use a lambda (in F#, lambdas are written as "fun args -> body") in order to partially apply g.  This is how it is in most programming languages (which do not have currying built in to the syntax); see, for example, Dustin Campbell’s blog entry about partial application in C#.

While there is more to the story of exactly how the F# type system works with regards to function types (especially with regards to calling .NET methods that take multiple arguments), we have covered enough new ground for today.  The essential points I want to communicate today are that you can get a good mental model of F# function types by thinking like this:

  • F# function types are written "A -> R"
  • All F# functions take one argument.  But
    • the argument type can be a tuple, which means you have calls like "g (x,s)", and
    • the result type can be another function, which means you also can have calls like "f x s".

In general, when programming in F#, the curried form for authoring functions is preferred.  This is because curried functions avoid needless parentheses at the call site, and because curried functions allow for easy partial application by omitting trailing arguments.  You’ve probably already seen examples of the latter in some of my previous blog entries, as partial application is common in pipelines.

Example

Let’s consider a very simple example to make this a little more concrete.  Suppose I have a list and I want to get a new list that contains only the odd numbers in the original list.  I could imagine writing a function called "JustTheOdds":

let origList = [1; 2; 3; 4; 5]
let newList = JustTheOdds origList
printfn "%A" newList  // prints [1; 3; 5]

If you are aware of the "filter" function from the List module, then writing "JustTheOdds" is easy:

let IsOdd x = 
    (x % 2) = 1
    
// justTheOdds : list<int> -> list<int>
let JustTheOdds l =
    List.filter IsOdd l

However I would be unlikely to write such a function in practice.  The name "JustTheOdds" does not add much value, especially when compared to "List.filter IsOdd".  Both are functions that take a list<int> and return a list<int>.  Let’s look a little closer at the type of the value described by the expression "List.filter IsOdd".

// List.filter : (‘a -> bool) -> list<’a> -> list<’a>
// IsOdd : int -> bool
// (List.filter IsOdd) : list<int> -> list<int>

List.filter is a curried function.  Its first argument is a function that takes an ‘a and returns a bool.  (Aside: In F#, generic parameters are named by identifiers preceded by an apostrophe.  In C# we’d probably call it "T" instead.  In any case, list<’a> is just like list<T> in C# – filter is a generic function of one type argument.)  And its result is a new function that takes a list and returns a list.  IsOdd has the right shape to be the first parameter to List.filter (with the generic parameter ‘a being bound to type "int").  As a result, when we apply List.filter to IsOdd, we get a function that takes a list<int> as an argument and returns a list<int> as a result.  Which is just what we need.  As a result, I’d be more likely to write

let origList = [1; 2; 3; 4; 5]
let newList = origList |> List.filter IsOdd
printfn "%A" newList  // prints [1; 3; 5]

Here we pipe the original list into a list-transforming function – the function that is the result of partially applying List.filter to IsOdd.  Since this example is very simple, I could have just written

let newList = List.filter IsOdd origList

That is, this example didn’t need partial application and the pipeline.  But if we were doing a more complicated series of transformations on the list, then the pipeline style and partial applications would be the way to go.  Indeed, we saw this in the previous blog entry about pipelines, where there were a number of partial applications of functions in the Set module.

In general, partial application of curried functions is a handy technique, and in practice I find that pipelines are the place where this technique is most commonly used.

(Teaser: I have an idea for a more detailed example that utilizes partial application in a particularly interesting way, and I hope to write about it in the near future.)

About these ads

2 Responses to “F# function types: fun with tuples and currying”

  1. Brian said

    See also
    http://www.atrevido.net/blog/2008/11/03/Common+Conceptual+Issues+With+F.aspx
    for another discussion along the same lines.

  2. Amit said

    Very nice, helpful post, but I have come to expect that of you.Now, if only you would do a tutorial on F# and databases (SQL Server), I would be able to clear that last hurdle.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

Join 30 other followers

%d bloggers like this: