Inside F#

Brian's thoughts on F# and .NET

Archive for April, 2008

An example of the interplay between language features and library design, part two

Posted by Brian on April 17, 2008

Last time we iterated on the design of a dictionary lookup API, discussing how different language features like "generics", "exceptions", and "out parameters" could affect the design of the API.  By the end of the blog entry, we had reached this API:

    // if key not present, returns false
    // else returns true and sets value
    bool TryGetValue(string key, out int value);

which admits this client code:

    int r; 
    if (dict.TryGetValue("Brian", out r)) 
    { 
        Console.WriteLine("Brian’s favorite 32-bit integer is {0}", r); 
    }

This design choice solved a large number of problems we encountered while iterating over possibilities in the design space of this simple API.

Nevertheless, there’s something I always found mildly irksome about the TryGetValue API.  It re-introduces a minor deficiency that had been previously solved by the ‘exception version’ of the API.  Recall that the client code in the exception version looks like this:

    try 
    { 
        int r = dict.GetValue("Brian"); 
        Console.WriteLine("Brian’s favorite 32-bit integer is {0}", r); 
    } 
    catch (KeyNotFoundException) 
    { 
    }

For all its problems, the exception version of the API has one advantage over "TryGetValue", which is that you can only reference the result "r" when it has a meaningful value.  If the dictionary doesn’t contain the key, an exception is thrown, and the name "r" falls out of scope so there’s no chance that you’ll accidentally try to use it.  Whereas with TryGetValue, I could get careless and write code like:

    int r;   
    if (dict.TryGetValue("Brian", out r))   
    {   
        Console.WriteLine("Brian’s favorite 32-bit integer is {0}", r); 
    } 
    DoSomethingWith(r);  // oops

or

    int r;   
    dict.TryGetValue("Brian", out r);  // oops
    Console.WriteLine("Brian’s favorite 32-bit integer is {0}", r); 

The TryGetValue API is well-designed in that its signature steers you in the right direction for proper use, but it’s still possible to accidentally use a meaningless "result".

So let’s do one more iteration on the design of this API…

Pattern-matching to the rescue!

We can introduce another language feature to address this problem.  Pattern matching!  I wrote briefly about pattern-matching in general, and F#’s "option" type in particular, in a previous blog entry.  Let’s put it to use.  Our new API method, now using F# notation, has this signature:

    // TryGetValue : string -> option<int>

where the return type is an option<int>.  And thus the client code looks like:

    match dict.TryGetValue "Brian" with
    | Some(r) -> Console.WriteLine("Brian’s favorite 32-bit integer is {0}", r)
    | None    -> ()

Perfect!  Pattern matching is both a control structure (like an "if" – we either run the code in the Some branch or the None branch) and a binding mechanism (we associate the new name "r" with a value) at the same time.  As a result, this language mechanism directly addresses the final deficiency; now "r" is scoped only to the branch where it is meaningful. 

Whereas the "TryParse" pattern (with a boolean return value and an out parameter) is the preferred design pattern in a language like C#, in languages with pattern-matching, such as F#, the preferred design pattern is simply to return an option<‘a>.  Such an API has all the benefits we described in the previous blog entry, plus one more: you can’t accidentally misuse the API to access a meaningless result.

The end of the story

This time, that really is the end of the story.  However, having just demonstrated this lovely benefit of pattern-matching, I wanted to call out how it relates to writing idiomatic F# code.

Suppose we’re writing a very simple function to print out all the numbers in a list.  A very non-idiomatic way to write this in F# is:

// PrintNums : list<int> -> unit
let rec PrintNums (l : list<int>) =
    if not l.IsNil then
        printfn "%d" l.Head
        PrintNums l.Tail

The part that is most glaringly non-idiomatic is the use if the if-then along with calls to .IsNil, .Head, and .Tail.  You almost never write F# code that looks like this, because it’s easy to make mistakes… in fact, when writing this example up, I actually made exactly such a mistake, originally forgetting the "not" in the if condition.  Clearly, screwing up the if condition will cause the subsequent code to fail.  As a result, it is far more idiomatic to use pattern matching:

// PrintNums : list<int> -> unit
let rec PrintNums l =
    match l with
    | h :: t -> printfn "%d" h
                PrintNums t
    | [] -> ()

Now, if we write the code in terms of "h" and "t" that are bound by the pattern match, we cannot accidentally make the error I made before (accessing the head of the list in the "if nil" branch).  Pattern-matching helps prevent us from writing code containing a certain class of logic errors.  (As a side-benefit, when the code is written this way, we also get type-inference of the parameter type "l".)

The point is, when pattern matching is available, you should use it in preference to writing your own control constructs (e.g. if-then-else) or your own code to select portions of the data (e.g. accessing .Head), because the pattern-matching language syntax and type system are designed to constrain the ways you can write code so that it is much harder to make errors.

(I note finally that a more advanced, but still perfectly idiomatic way to write PrintNums is

// PrintNums : list<int> -> unit
let PrintNums = List.iter (fun x -> printfn "%d" x)

but writing it that way wouldn’t have let me talk about pattern matching.)

Posted in Uncategorized | 3 Comments »

An example of the interplay between language features and library design, part one

Posted by Brian on April 16, 2008

In today’s blog entry I want to trace an imagined lineage of a simple collection API method that demonstrates how language design, library design, and programming idioms co-evolve over time.  The API in question is a lookup function for a Dictionary, and I think careful study of this relatively mundane method can provide some fascinating insight into the interplay of programming language constructs, libraries, and idioms.

For today’s blog, I am going to use C# syntax, but merely for notational convenience, as my intention is to talk about things abstractly in a language-neutral way.

A very simple dictionary lookup

Let’s say we need a lookup table that maps string values to integer values.  (Perhaps the string represents a name, like "Brian", and the integer represents the number of blog entries posted this month.)  Suppose also we are in an introductory programming class (or perhaps using a very old language) and we don’t yet know about generics or exceptions.  We might design a "lookup" API on this "dictionary" class with an instance method that looks something like this:

    // returns -1 if key not in dictionary
    int GetValue(string key);

and then call it with client code like this:

    int r = dict.GetValue("Brian");
    if (r != –1)
    {
        Console.WriteLine("Brian posted {0} blogs", r);
    }

This API is simple and workable for this example.

Problems in the space of values

The previous GetValue() function utilized a special value (namely "-1") in the space of things that were being looked up in order to provide a way to report back whether the dictionary actually contained an entry for "Brian".  When the thing being stored is a non-negative integer (e.g. number of blog entries I posted), this is fine, but this scheme fails if we need to store values that span the entire value space of the data type.  So, for example, suppose once again that I want a structure that maps strings to integers, and the string key is a person’s name again, but this time the integer value is that person’s favorite 32-bit integer.  We can no longer use "-1" as a sentinel value to mean "not in the dictionary", because we would be unable to distinguish it from an entry of a person whose favorite number is indeed -1.  (Note: Sentinel values are also ruled out if we try to make the dictionary generic over the value type.)  So we might change the API:

    // returns true if the dictionary contains the key
    bool ContainsKey(string key);
    // (undefined behavior if key not in dictionary)
    int GetValue(string key); 

as well as the client code:

    if (dict.ContainsKey("Brian"))
    {
        int r = dict.GetValue("Brian");
        Console.WriteLine("Brian’s favorite 32-bit integer is {0}", r);
    }

We have solved the problem of not being allowed to use a particular sentinel value to mean "not there" (and thus this API makes it possible to author a "generic" dictionary class).  However in the process, we introduced a number of new problems.  First, the API has gotten more complicated – there are two methods the user needs to know about rather than just one.  Furthermore, the behavior of the APIs requires the client to use a particular idiom – the client code must call ContainsKey() before calling GetValue() to ensure the behavior is well-defined.  Things have probably become less performant, since we are now looking up the value in the data structure twice (once in the ContainsKey() call, and then again in the GetValue() call).  And finally, if this data structure can be simultaneously accessed by multiple execution threads, we would require the client to lock the data structure across the two calls, or else ContainsKey() might succeed, but then some other thread might remove that key-value pair before GetValue() runs.  What a mess!

Exceptions to the rescue?

One possible way out of the mess is to introduce a new language feature – exceptions.  If our programming language supports exceptions, we can redefine the API like so:

    // throws KeyNotFoundException if key is not in dictionary
    int GetValue(string key);

and the client code becomes:

    try
    {
        int r = dict.GetValue("Brian");
        Console.WriteLine("Brian’s favorite 32-bit integer is {0}", r);
    }
    catch (KeyNotFoundException)
    {
    }

The "exceptions" language feature just helped solve all four problems we introduced in our previous attempt at the API.  We are back down to a single method, which requires no special client calling-order idioms, which needs only perform the lookup once, and which can do thread synchronization inside the method.  Quite an improvement!

Nevertheless, this API design is still poor, as exceptions are a very heavyweight mechanism.  In many languages, throwing an exception means your code’s performance will be poor (worse than an if-then-else, anyway).  Throwing an exception means you will disrupt the debugging experience (e.g. for those using ‘catch all first-chance exceptions’ to find real problems in the code).  And exceptions syntactically burden the caller (by requiring a try-catch).  So our API is still not great.

Out parameters to the rescue…

We can introduce another language feature to address these problems.  If our programming language supports "out" parameters, we can rewrite the API like this:

    // if key not present, returns false
    // else returns true and sets value
    bool TryGetValue(string key, out int value);

and our client code becomes:

    int r;
    if (dict.TryGetValue("Brian", out r))
    {
        Console.WriteLine("Brian’s favorite 32-bit integer is {0}", r);
    }

Once again, we have solved the problems introduced by our previous attempt.  This API is simple and performant.  Indeed, this is the API used by System.Collections.Generic.Dictionary, and is an instance of a more general design idiom known as the TryParse pattern, described here and here.  (If you haven’t read about "TryParse" before, follow the links and learn!)

The end of the story?

I could end the story here.  We’ve gone through four iterations of API design, constantly improving things by repairing deficiencies with the prior designs.  Along the way we saw how certain language features (like "generics", "exceptions" and "out parameters") interacted with the library API design and influenced the idioms used in the calling code.

But there is still more to say.  I’ll save it for the next blog entry, though.  (I’m such a tease!)

Posted in Uncategorized | Leave a Comment »

Catamorphisms, part three

Posted by Brian on April 9, 2008

As promised in a previous blog entry, today let’s apply catamorphisms to a more real-world-ish example.  Say we’re creating a new programming language, and we’re authoring tools for this language.  A parser for the language will probably output an intermediate representation called an abstract syntax tree (AST), which other language tools then process.  For example, an interpreter would walk the AST and "execute" the code that it represents, whereas a pretty-printer would walk the AST and convert it into a nicely displayed text string.  If you were coding in an OO language, you’d probably apply the visitor pattern, where the interpreter and pretty-printer were two different kinds of visitors accepted by the AST.  (Once upon a time I gave just such an assignment in a programming languages class.)  On the other hand, if you’re using a functional language, then each ‘visitor’ is just a catamorphism on the tree type.  Today we’ll see that.

The problem facing the blog author (that is, me) is trying to make the example rich enough to demonstrate the overall generality of the point I’m trying to make, as well as deep enough to give you the sense that yes, this does apply/scale to real-world problems… while at the same time keeping things small enough that you can digest it all in a sitting while reading the blog, and the code snippets stay short enough to be readable on the screen along with the complementary prose.  I’ve tried to invent a tiny "language" that is the smallest possible thing that will allow me to demonstrate the power of catamorphisms without being overwhelming.  So I decided a minimal set would be an expression language with: literal values, operators, control structures, and effects.  Hence…

Today’s tiny language

Our "language" for today will be a language of integer expressions.  It can represent literal numbers (e.g. 42) as well as plus or minus expressions (e.g. 3+4-2).  It has one control structure, an if-then-else (where the condition is an integer, and 0 means false).  And it has one "effect" expression: print(5) would print out 5 and also return 5 as a value.  We aren’t writing a parser for the language (not today, at least), but the corresponding AST might look like this:

// types capable of representing a small integer expression language
type Op =
    | Plus
    | Minus
    override this.ToString() =
        match this with
        | Plus -> "+"
        | Minus -> "-"
type Expr =
    | Literal of int
    | BinaryOp of Expr * Op * Expr     // left, op, right
    | IfThenElse of Expr * Expr * Expr // cond, then, else; 0=false in cond
    | Print of Expr                    // prints, then returns that value

Discriminated unions fit the bill nicely.  One thing I haven’t discussed before is that discriminated unions can have member functions, just like classes (indeed they are converted into IL classes under the hood).  In this code I’m overriding the ToString() for the "Op" type to give us a pretty-printable representation (which we’ll use later when we write a function to pretty-print entire expressions).  Apart from that, there’s no new F# here.  I hope it’s clear how these data types represent the language I described in the previous paragraph.

Since we’re not writing a parser for this language today, we have to create representations of these expressions "by hand".  Here is a list of three small expressions:

let exprs = [Literal(42)
             BinaryOp(Literal(1), Plus, Literal(1))
             IfThenElse(Literal(1), Print(Literal(42)), Print(Literal(0)))
            ]

Lovely.

Folding expressions

If you’ve been following along, then you know that a catamorphism on the "Expr" type will be a function that takes five arguments – one for each of the four alternatives of the discriminated union (Literal, BinaryOp, IfThenElse, Print), and a final argument that is the Expr to be "folded".  This function can be derived entirely from the shape of the data type itself, so even if you don’t quite follow how catamorphisms work yet, you still might be able to write:

let FoldExpr litF binF ifF printF e =
    let rec Loop e cont =
        match e with
        | Literal(x) -> cont (litF x)
        | BinaryOp(l,op,r) -> Loop l (fun lacc ->
                              Loop r (fun racc ->
                              cont (binF lacc op racc)))
        | IfThenElse(c,t,e) -> Loop c (fun cacc ->
                               Loop t (fun tacc ->
                               Loop e (fun eacc ->
                               cont (ifF cacc tacc eacc))))
        | Print(e) -> Loop e (fun eacc ->
                      cont (printF eacc))
    Loop e (fun x -> x)

just based on the previous examples we’ve done.  We do our usual "loop with continuation" pattern to ensure the function is tail-recursive.  For each alternative, we pattern-match out the corresponding data, recurse when necessary, call the corresponding function on the results, and pass the final value to the continuation.   So, for example, the second alternative of the Expr data type was

    BinaryOp of Expr * Op * Expr

First we pattern match it to

    BinaryOp(l,op,r)

Since "l" and "r" have type "Expr", we need to recurse with each, following the usual pattern:

    Loop l (fun lacc -> 
    Loop r (fun racc ->

Finally we apply the corresponding function (which I named "binF") on the pieces, and pass the final result to the continuation:

    cont (binF lacc op racc)

The same logic applies to each alternative.  So creating the "fold" function which defines a catamorphism over a recursive data type is mechanically straightforward.

Visitor 1: a pretty-printer

Now let’s define a simple pretty-printing function for Exprs.  Since we have the "fold" in hand, it is very easy:

// PrettyPrint : Expr -> String
let PrettyPrint = 
    FoldExpr (fun x ->      sprintf "%d" x)
             (fun l op r -> sprintf "%s %s %s" l (op.ToString()) r)
             (fun c t e ->  sprintf "if %s then %s else %s endif" c t e)
             (fun e ->      sprintf "print(%s)" e)

// call it on our sample expressions

exprs |> List.iter (fun expr -> printfn "%s" (PrettyPrint expr))
// 42
// 1 + 1
// if 1 then print(42) else print(0) endif

All we do is create four functions – one for each Expr alternative – where each function defines how to pretty-print that particular alternative.  Pass those 4 functions to FoldExpr and we have our pretty-printer.  FoldExpr takes care of the recursion.  This is, in a sense, the visitor pattern boiled down to its essence: we want to walk the tree to accomplish some task, and so we just need to define the logic about how to handle each kind of node in the tree.

Visitor 2: an interpreter

Now let’s define an interpreter – an expression evaluator that will "run" the code represented by an expression tree.  Once again, it seems we can just pass simple functions for each alternative to FoldExpr and have it all work out:

// NaiveEval : Expr -> int
let NaiveEval = 
    FoldExpr (fun x -> x)
             (fun l op r -> match op with
                            | Plus -> l + r
                            | Minus -> l – r)
             (fun c t e -> if c <> 0 then t else e)
             (fun e -> let x = e
                       printf "<%d>" x
                       x) 
                    
// call it on our sample expressions
exprs |> List.iter (fun expr -> printfn "%d" (NaiveEval expr))
// 42
// 2
// <42><0>42

It almost works, but notice that the third expression – the one with the if-then-else – ended up "executing" both the "then" branch and the "else" branch, printing both "<42>" and "<0>" while evaluating the expression.  Presumably this is not the desired semantic for our little language!  Since FoldExpr handles the recursion and always recurses to traverse the whole tree, it isn’t obvious how to fix this.  But in fact, we just use a trick we already saw in the last installment.  Currently FoldExpr returns an "int", and thus each recursive call fully evaluates things to yield a final result.  We can easily change it so that instead of returning an int, the FoldExpr call will return a function "unit -> int" – a function that is waiting to be invoked to produce a result.  This changes the type of all the recursive parts, and gives us control over when code is actually executed.  Here’s the new code:

// Eval : Expr -> int
let Eval expr = 
    // f : Expr -> unit -> int
    let f = FoldExpr (fun x () -> x)
                     (fun l op r () -> match op with
                                       | Plus -> l() + r()
                                       | Minus -> l() – r())
                     (fun c t e () -> if c() <> 0 then t() else e())
                     (fun e () -> let x = e()
                                  printf "<%d>" x
                                  x)
    f expr ()
                    
exprs |> List.iter (fun expr -> printfn "%d" (Eval expr))
// 42
// 2
// <42>42

We’ve added one extra "unit" argument to each function passed to FoldExpr.  As a result, the types change so that entities like "c", "t", and "e" in the third function no longer have type "int"; instead they have type "unit -> int".  Thus the code we write in the body of the third function can choose when&whether to call each of these functions.  We call c(), and based on its value, either call t() or call e().  As a result, in our third example expression, only the print in the "then" branch gets executed ("<42>" is printed but "<0>" is not).  Just what we want!  Note that in the last line of the Eval function, we had to call the result of the FoldExpr (which I named "f" above) with not just the expression, but also a unit in order to ‘kick off’ the execution of the evaluation.

This example demonstrates not only the power of currying and partial application, but also the value of type inference.  In the change from "NaiveEval" to "Eval", we changed the type of 7 different named entities.  But we didn’t have to write a single type annotation.  Type inference works out all those details, so we can focus on making a simple change to the code, without having to worry about changing various occurances of "int" to "Func<unit,int>" or some other such drudgery.

Summary

A catamorphism is a generalization of the "fold" function to a particular data type.  In three blog entries, we’ve seen examples of folds on lists, binary trees, and abstract syntax trees for a tiny expression language.  Data that can be described using a discriminated union type is data that’s naturally amenable to catamorphisms.  Rather than define a data type, and then write lots of recursive functions that walk over that data to do various computations, you can write a single "fold" function that encapsulates all the logic in walking/recursing the data structure once-and-for-all, and then all the various computations can be expressed as applications of that "fold".  Just pass in the logic that’s essential to the particular computation to "fold" and you’re done.  As a result, writing functions like Sum for a list or a binary tree, or PrettyPrint and Eval for an AST, doesn’t need to involve writing any code that actually recurses/traverses/pattern-matches the structure.  Instead, "fold" will handle that, and the individual functions like Sum/PrettyPrint/Eval can just call "fold" with the logic appropriate to each alternative.

This was a very quick/steep walk through a deep topic.  If you’re new to functional programming in general, or F# in particular, I can imagine it may have been hard to follow.  If so, feel free to leave comments with questions.  I’m toying with the idea of trying to rewrite these examples in C#, if there are readers having a tough time coping with both the new concepts and the new syntax all at once.

Posted in Uncategorized | 1 Comment »

Discriminated unions in F#

Posted by Brian on April 7, 2008

Discriminated unions are used a lot in F# code.  A discriminated union is a data type with a finite number of distinct alternative representations.  If you have used "union" in C/C++, you can think of discriminated unions as a somewhat similar construct; the main differences are that F# discriminated unions are type-safe (every instance knows which alternative is ‘active’) and that F# discriminated unions work with pattern-matching.  Here is a short example that suggests how to define and use a discriminated union type:

type ADiscriminatedUnionType =
    | Alternative1 of int * string
    | Alternative2 of bool
    | Alternative3

// constructing instances
let du1 = Alternative1(42,"life")
let du3 = Alternative3

let f du = 
    // pattern matching
    match du with
    | Alternative1(x,s) -> printfn "x is %d, s is %s" x s
    | Alternative2(b) -> printfn "b is %A" b
    | Alternative3 -> printfn "three"

 
f du1  // x is 42, s is life
f du3  // three
 

The list<‘a> type

One of the most common F# types, list<‘a>, is a discriminated union.  It has two alternatives: nil (spelled "[]"), and cons (spelled "::").  The former alternative carries no data, whereas the latter carries an ‘a*list<‘a>.  Thus you frequently write code like

match l with
| [] -> printfn "do something in nil case"
| h :: t -> printfn "do something else in cons case"

in F#.  If "l" was a list<int>, then "h" would be an int (the head of the list – that is, the first element), and "t" would be a list<int> (the tail of the list – that is, all the rest of the elements except the first one).  The existence of pattern-matching for lists means you very rarely call functions like List.head, List.tail, and List.isEmpty (see the List module).  Note that the code above has roughly the same meaning as this C# code:

if (l.IsEmpty)
{
    Console.WriteLine("do something in nil case");
}
else
{
    var h = l.Head;
    var t = l.Tail;
    Console.WriteLine("do something else in cons case");
}

In essence, pattern matching is simultaneously both a control construct (like an if-then-else or switch statement) and a binding construct (a "let" that binds values to names).  It’s hard to appreciate just how useful and elegant pattern-matching is until you’ve used it a bit in practice.  (I had read about pattern matching in ML before, years ago, but I just shrugged it off as a cute little bit of syntax sugar.  But now that I’m using it in F#, it really is very handy, and I finally "get" why the ML folks always tout this language feature.)

The option<‘a> type

Apart from list<‘a>, the other most-commonly-encountered discriminated union type in F# is option<‘a>.  Its definition is very simple:

type option<‘a> =
    | Some of ‘a
    | None

This type is mostly often used for functions that may or may not return a result.  For example, if we’re trying to find an element in a list that matches some predicate, the list might or might not contain such an element.  Thus, List.tryfind returns an option.  Here is a contrived example:

let PrintFirstStartsWithM l =
    let answer = List.tryFind (fun (s : String) -> s.StartsWith("M")) l
    match answer with
    | Some(s) -> printfn "%s" s
    | None -> printfn "list had no strings starting with M"

PrintFirstStartsWithM ["Sunday"; "Monday"; "Tuesday"] // Monday
PrintFirstStartsWithM ["one"; "two"; "three"] // list had no strings starting with M

If you’re familiar with the method TryGetValue in System.Collections.Generic.Dictionary, then it should be clear how the option<‘a> type solves the same problem as the signature of TryGetValue (or more generally, the "TryParse" design pattern as described briefly here).

When to use discriminated unions

Use discriminated unions where a type has a finite number of alternative representations, and you want to leverage pattern-matching.  This means that you can often express what would otherwise be a small class hierarchy as a discriminated union.  For example, consider the "PrettyString" code from a previous blog entry.  Originally I wrote it using a small class hierarchy; here it is again using a discriminated union instead.  (I preserved the class code in the "#if CLASSES" portion.)

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

#if CLASSES
/// 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
     
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

#else
type PrettyString =
    | StringLiteral of String
    | Vertical of PrettyString * PrettyString
    | Horizontal of PrettyString * PrettyString

let rec Height ps =
    match ps with
    | StringLiteral(_) -> 1
    | Vertical(top, bottom) -> (Height top) + (Height bottom)
    | Horizontal(left, right) -> max (Height left) (Height right)

let rec Width ps =
    match ps with
    | StringLiteral(s) -> s.Length
    | Vertical(top, bottom) -> max (Width top) (Width bottom)
    | Horizontal(left, right) -> (Width left) + (Width right)

let rec Line ps n =
    match ps with
    | StringLiteral(s) -> if n <> 0 then "" else s
    | Vertical(top, bottom) -> 
        if n < 0 || n >= Height ps
        then "" 
        else if n < Height top
             then Line top n 
             else Line bottom (n – Height top) 
    | Horizontal(left, right) -> 
        String.Concat((Line left n).PadRight(Width left)
                      Line right n) 

let ToString ps =
    let sb = new StringBuilder()
    for i in 0 .. Height ps do 
        sb.Append(Line ps i) |> ignore
        sb.Append("\n") |> ignore
    sb.ToString() 
    
let pretty s = StringLiteral(s)
let (%%) x y = Vertical(x,y)
let (++) x y = Horizontal(x,y)
#endif

let blank = pretty " "

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

let c = calendar 2008 4
#if CLASSES
printfn "%s" (c.ToString())
#else
printfn "%s" (ToString c)
#endif

The PrettyString abstract class became a discriminated union type, and each of its subclasses became one alternative of the discriminated union.  The methods on the abstract class became top-level functions that took a PrettyString as an argument.  Apart from that, little else changes.  Hopefully this example will help you draw the analogy between discriminated unions and class hierarchies.

Whereas a class hierarchy is "open", in that someone else can come along later and add a new subclass, discriminated unions are "closed", in that the author of the type specifies all the alternatives once-and-for-all (analogy: imagine a "sealed" class hierarchy).  This is often the main factor to consider when trying to decide between a class hierarchy and a discriminated union.

That’s it for today; I’ve already had a number of blog posts that took discriminated unions and pattern matching for granted, so it’s about time I stopped to explain them a little, eh?  :)

Posted in Uncategorized | 3 Comments »

Catamorphisms, part two

Posted by Brian on April 6, 2008

Last time we talked about folds on lists.  Today we’ll generalize to folds on trees, and suggest how to generalize folds to arbitrary data types.

Binary trees

Binary trees are a common data structure.  Sometimes (such as in the wikipedia page for "catamorphism") you’ll see tree data types defined where they store data in the leaves (on the fringe), but more commonly I think people author tree structures that store data in the interior nodes of the tree.  So that’s the kind of data structure I’ll define for the next example:

type Tree<‘a> =
    | Node of (*data*)‘a * (*left*)Tree<‘a> * (*right*)Tree<‘a>
    | Leaf

//     4
//  2     6
// 1 3   5 7
let tree7 = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf)),
                    Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf)))

A tree "Node" has a bit of data, a left child, and a right child.  "Leaf" represents null – the edge of the tree.  I’ve also defined a small sample tree called "tree7", which is the full and balanced binary search tree containing the numbers 1-7 (the canonical ‘example tree’ we always used in my CS classes).  (Aside: Currently F# doesn’t let you name the bits of data in each alternative of a discriminated union, so I put the names I would give those fields ("data", "left", and "right") in comments.)

There are a number of common functions you might write for trees.  Here are a few, along with naive implementations:

// SumTree : Tree<int> -> int
let rec SumTree t =
    match t with
    | Node(x,left,right) -> x + (SumTree left) + (SumTree right)
    | Leaf -> 0

// InOrder : Tree<‘a> -> list<‘a>   
let rec InOrder t =
    match t with
    | Node(x,left,right) -> (InOrder left) @ [x] @ (InOrder right)
    | Leaf -> []

// Height : Tree<‘a> -> int
let rec Height t =
    match t with
    | Node(x,left,right) -> 1 + (max (Height left) (Height right))
    | Leaf -> 0

 
printfn "%d" (SumTree tree7) // 28
printfn "%A" (InOrder tree7) // [1; 2; 3; 4; 5; 6; 7]
printfn "%d" (Height tree7)  // 3

SumTree adds up the data values in all the Nodes in the tree.  InOrder yields a list of data values in the order of an inorder traversal of the tree.  Height computes the height (sometimes called the "depth") of the tree, the longest chain of Nodes starting from the root.

Note that I called the implementations "naive" because they are not tail-recursive.  Additionally, InOrder uses the append operator (@) to concatenate lists, which is needlessly inefficient.  These are both pitfalls that I discussed in a prior blog entry.

Folds over trees

You may notice lot of commonality in those three tree functions, and again we can factor out that commonality into a general fold function for trees.  Here it is, along with a redefinition of our three tree functions:

// FoldTree : (‘a -> ‘r -> ‘r -> ‘r) -> ‘r -> Tree<‘a> -> ‘r
let FoldTree nodeF leafV t =
    let rec Loop t cont =
        match t with
        | Node(x,left,right) -> Loop left  (fun lacc -> 
                                Loop right (fun racc ->
                                cont (nodeF x lacc racc)))
        | Leaf -> cont leafV
    Loop t (fun x -> x)
 
let SumTree = FoldTree (fun x l r -> x + l + r)   0
let InOrder = FoldTree (fun x l r -> l @ [x] @ r) []
let Height  = FoldTree (fun _ l r -> 1 + max l r) 0

FoldTree takes three parameters.  The first parameter ("nodeF") is a function that processes Nodes, combining the data value in the node with the result of recursive calls on the left and right subtrees.  The second parameter ("leafV") is the result value of a fold on just a Leaf (an empty tree).  The third parameter ("t") is the tree that we want to process.  Our three tree functions are now defined simply as partial applications of this very general FoldTree function.

The code for FoldTree leverages the "continuation" strategy we used last time in order to make the implementation tail-recursive.  For a Node, we recurse on the left subtree, along with a continuation function that takes that result (which I’ve called "lacc" for "left accumulator") and recurses on the right subtree with a new continuation function that takes that result ("racc" – right accumulator) and then uses the "nodeF" function to combine the data in the current node, the left-recursion result, and the right-recursion result into a final result which it passes to the continuation for the current call.  For a Leaf, we just continue with the "leafV" value.  (That sounds complicated, but if you followed the description of using a continuation to implement FoldRight in the previous blog entry, this is the same thing, only we applied it twice since we have two recursive calls to make.)

Since the implementation of FoldTree is tail-recursive, we’ve addressed one of the two pitfalls.  SumTree and Height now have terrific definitions. 

InOrder, however, still suffers from the second pitfall, in that it inefficiently builds a list through a number of appends (order N^2) rather than consing up the list in reverse order (order N).  It’s not immediately obvious how to fix this.  We ideally want to build the list in a "reverse inorder" traversal, consing each new data value on to the front of an accumulator list.  How can we achieve this?  Where would the accumulator go, and how can we thread it through the fold computation in the right order?

The answer is surprising:

let InOrder t = (FoldTree (fun x l r acc -> l (x :: (r acc))) (fun acc -> acc) t) []

What’s going on here?  Something seems fishy – for example, the function passed as the first parameter to FoldTree is taking four parameters instead of three.  However, as I alluded to in a prior blog entry, an implication of currying and partial application is that "fun x y -> body" means the same thing as "fun x -> fun y -> body" (you can tease apart multiple arguments).  And so in our example, "fun x l r acc ->" can be interpreted as "fun x l r -> fun acc ->", which now makes it more apparent how this fits the signature of FoldTree:

// FoldTree : (‘a -> ‘r -> ‘r -> ‘r) -> ‘r -> Tree<‘a> -> ‘r

Here the final result type ‘r is not just any ordinary value type – it’s a function type!  Since we need to thread an accumulator through the computation, we’ll have FoldTree compute a new function that takes the accumulator.  And so this explains the extra "acc" parameters.  As a result, now "l" and "r" (the results of the recursive calls on left and right subtrees) are also also one-argument functions that expect an accumulator parameter.  And thus our "nodeF" node function can create our in-order list in reverse order, by first calling the right-subtree function with the accumulator "(r acc)", and then consing the data of the current node onto the front of that "(x :: …)", and then passing that result as the final accumulator to the left-subtree function "(l …)".  Traversing a Leaf does not have an impact on the traversal, and so the "leafV" leaf value is just the identity function (it returns the same accumulator without any changes).  The result of the call to FoldTree is thus a function that will compute the inorder traversal list once it’s passed the "seed" accumulator, which explains the empty list "[]" at the end of InOrder’s definition.

Whew!  I find it hard to write prose that does justice to the explanation of what’s going on here, so I encourage you to study this until you understand what’s going on.  Here are three different tree traversal definitions, along with sample calls:

let InOrder t   = (FoldTree (fun x l r acc -> l (x :: (r acc))) (fun acc -> acc) t) []
let PreOrder t  = (FoldTree (fun x l r acc -> x :: l (r acc))   (fun acc -> acc) t) []
let PostOrder t = (FoldTree (fun x l r acc -> l (r (x :: acc))) (fun acc -> acc) t) []
//     4
//  2     6    <– tree7
// 1 3   5 7
printfn "%A" (InOrder tree7)   // [1; 2; 3; 4; 5; 6; 7]
printfn "%A" (PreOrder tree7)  // [4; 2; 1; 3; 6; 5; 7]
printfn "%A" (PostOrder tree7) // [1; 3; 2; 5; 7; 6; 4]

Awesome.

Aside: currying and partial application

We just saw the "particularly interesting" application of currying that I mentioned at the end of the blog entry from a few days ago.  When we needed to thread an extra accumulator parameter through the FoldTree function to efficiently perform our traversal, we were free to just tack on that extra parameter, and the types and the computation all just worked out.  A "function that takes four arguments and returns a value" is the same thing as a "function that takes three arguments and returns another function that takes one argument and returns a value".  These niceties of the F# type system and syntax made it easy to express tree traversals as one-liner applications of a general fold function on trees.  The resulting traversal functions are tail-recursive (no fear of blowing the stack) and have the optimal complexity (order N for a tree of N nodes).  How cool is that?  F# rocks.

Catamorphisms

Now that we’ve authored folds over both lists and trees, we can start thinking about what they have in common and start understanding what a catamorphism is.  To sum up what we’ve seen so far, here are the two data types and the signatures of the corresponding fold functions.  (I’ve used my own type definition for List; the F# list<‘a> type is very similar, but would sidetrack us with a couple needless syntax details.)

type List<‘a> =
    | Cons of ‘a * List<‘a>
    | Nil
// FoldList : (‘r -> ‘a -> ‘r)        -> ‘r  -> List<‘a>  -> ‘r

type Tree<‘a> =
    | Node of ‘a * Tree<‘a> * Tree<‘a>
    | Leaf
// FoldTree : (‘a -> ‘r -> ‘r -> ‘r)  -> ‘r  -> Tree<‘a>  -> ‘r

See some similarity?  As we’ll see in a future entry, we can generalize folds to arbitrary discriminated-union types, where the first N parameters to the fold correspond to the N alternatives in the discriminated union, and the final (N+1) parameter is the data structure itself.  Both List and Tree are discriminated unions with two alternatives, and so each has a corresponding fold function of 3 (2+1) parameters.  FoldList’s first parameter is a function that says what to do with a Cons (given the result of a recursive call on the rest of the list, and the current node value, compute a result), and its second parameter says what to do return for a Nil.  Similarly, FoldTree’s first parameter says what to do with a Node (given the current node value, the result of recursing the left subtree, and the result of recursing the right subtree, compute a result), and its second parameter says what to return for a Leaf.

This is the essence of a catamorphism – we let the structure of the data guide the computation.  The shape of the data structure implies a particular signature for a fold function that can be used as a general mechanism for doing arbitrary computations over data of that shape.  In a future installment I hope to demonstrate this in more detail with a cool, more-real-world example.

Posted in Uncategorized | 4 Comments »

Catamorphisms, part one

Posted by Brian on April 5, 2008

(Read this blog entry at a pace which is appropriate for you.  Some readers will find this mostly old-hat, whereas others will find it rough going at parts.  I encourage you to take a break and try out the code examples, if that helps you out.)
I would like to discuss catamorphisms.  A catamorphism is a generalization of a fold on lists to an arbitrary data type.  So for today’s blog entry, let’s review lists and folds.  We’ll also end up discussing continuations as a cool technique for preserving tail-recursion in certain kinds of folds.

Lists and folds

If you’ve taken a CS class that was some sort of “introduction to functional programming”, you almost surely started out writing recursive functions that operated on lists.  For example:
// SumList : list<int> -> int let rec SumList l = match l with | h :: t -> h + SumList t | [] -> 0
printfn "%d" (SumList [1; 2; 3; 4]) // prints 10
But then the instructor has you sum the list of numbers from 1 to 100000 and *kaboom* you blow the stack.  The instructor doesn’t allow you to use iterative constructs like “for” or “while” in this class, and thus you learn about tail recursion, and rewrite the function like this:
// SumList : list<int> -> int let SumList l = let rec Loop l acc = match l with | h :: t -> Loop t (h + acc) | [] -> acc Loop l 0
The essence of rewriting this tail recursively is to take the computation that would normally happen after the recursive call finishes (the “h+” in the original example), and doing the computation before the recursive call, passing the result as an extra “accumulator” argument (often conventionally named “acc”).  Then when you reach the end of the list, the accumulated value is the final result.  Since you don’t want the implementation detail of the accumulator to leak into the public API, the tail-recursive accumulating function is just a nested helper function (often conventionally called “Loop”, since tail recursion and loops are equivalent) and the real function calls this helper with an appropriate “seed value” for the accumulator. In the case of summing a list, the sum of an empty list is 0, so we use the value 0 to seed the accumulator.
So you get accustomed to writing your list functions tail-recursively, writing more functions like
// LengthList : list<'a> -> int let LengthList l = let rec Loop l acc = match l with | h :: t -> Loop t (1 + acc) | [] -> acc Loop l 0
printfn "%d" (LengthList [1; 2; 3; 4]) // 4
// ReverseList : list<'a> -> list<'a> let ReverseList l = let rec Loop l acc = match l with | h :: t -> Loop t (h :: acc) | [] -> acc Loop l []
printfn "%A" (ReverseList [1; 2; 3; 4]) // [4; 3; 2; 1]
and one day you notice a pattern emerging – the code for each function looks eerily similar.  But you’re just learning functional programming and so it isn’t immediately obvious how to factor out the common pattern until one day someone shows you
// Fold : ('a -> 'b -> 'a) -> 'a -> list<'b> -> 'a let rec Fold combine acc l = match l with | h :: t -> Fold combine (combine acc h) t | [] -> acc
printfn "%d" (Fold (fun acc e -> e+acc) 0 [1; 2; 3; 4]) // sum: 10 printfn "%d" (Fold (fun acc _ -> 1+acc) 0 [1; 2; 3; 4]) // length: 4 printfn "%A" (Fold (fun acc e -> e::acc) [] [1; 2; 3; 4]) // reverse: [4; 3; 2; 1]
You puzzle over this a bit, but upon inspecting the call sites you see that Fold has indeed factored out the essential differences from the three functions we wrote.  The only differences were (1) the “computations on the accumulators” (either adding the current value to the accumulator to sum, adding one to the accumulator to get the length, or consing onto the front of the accumulator to reverse the list) and (2) the “seed values” (zero, zero, and nil, respectively).  Fold neatly factors these differences out, and thus provides a general function for doing all sorts of computations on lists.
For some people the real understanding and appreciation of Fold comes in one of those “aha!” moments where it finally clicks and a ray of sunshine shines down on you from the heavens and a choir of angels sings the praises of higher-order functions.  For others, it’s a gradual process, where repeated exposure over time allow you to accumulate the necessary experience to understand exactly where, when, and how “Fold” is applicable.  Regardless of which of these types of person describes you, once you “get it” you keep “Fold” handy as a very useful tool in your toolbox, and you almost never write recursive functions to process lists again, because the moment you start writing them you realize you could just do it in one line of code with a fold.  So now you’d write the functions just by giving names to partial applications of folds:
let SumList = Fold (fun acc e -> e+acc) 0 let LengthList = Fold (fun acc _ -> 1+acc) 0 let ReverseList = Fold (fun acc e -> e::acc) [] printfn "%d" (SumList [1; 2; 3; 4]) // 10 printfn "%d" (LengthList [1; 2; 3; 4]) // 4 printfn "%A" (ReverseList [1; 2; 3; 4]) // [4; 3; 2; 1]
Of course, in practice you wouldn’t be writing any of these functions yourself since they’re all already in the F# library (most notably, the “Fold” function we wrote is fold in the List module).  But this is what you do in the first few weeks of any introductory CS class – you reimplement a bunch of functionality that’s already in the standard library because those functions are simple little functions that help you learn all the main concepts.

fold, foldBack, and continuations

Why are there two functions in the List module called “fold” and “foldBack”?  The difference is the order in which the elements of the list are processed and combined.  The “fold” version goes left-to-right, whereas the “foldBack” version goes right-to-left.  (These functions also take arguments in a slightly different order; inspect their signatures for the details.)  Here are a couple examples that demonstrate the difference in behavior:
// print "1 2 3 4 " List.fold  (fun _ e -> printf "%d " e) () [1; 2; 3; 4] printfn "" // print "4 3 2 1 " List.foldBack (fun e _ -> printf "%d " e) [1; 2; 3; 4] () printfn ""
// reverse: [4; 3; 2; 1] printfn "%A" (List.fold  (fun acc e -> e::acc) [] [1; 2; 3; 4]) // clone:   [1; 2; 3; 4] printfn "%A" (List.foldBack (fun e acc -> e::acc) [1; 2; 3; 4] [])
In the first example, I’ve passed a function that prints each element as it is encountered as the “combining function” argument to the fold.  The output demonstrates the evaluation order.  In the second example, I’ve passed a function that conses the current element onto the front of the accumulated list.  If we walk the list left-to-right, creating a new list by consing elements onto the front of an accumulator, we end up with a reversed copy of the list.  Whereas if we do the same thing traversing from right-to-left, we get a copy of the list with the elements in the original order (we just cloned the list).
The “Fold” we already wrote today corresponds to the “fold” version. The question is, how would you write the “foldBack” version?  The initial naive approach is
let rec FoldBack combine l acc = match l with | h :: t -> combine h (FoldBack combine t acc) | [] -> acc
but this isn’t tail-recursive, and so calling it on a large list yields a StackOverflowException.  How do we get around this?  We’re already using an accumulator.  We need to traverse to the end before we start calling the “combine” function, since the last value of the list is the first value it processes.  But we also need to remember all the elements in the list so that we can process them in reverse order… only not on the call stack on the way back, because our whole goal is to be tail-recursive and not use the call stack.  We’re going to need to allocate an auxiliary data structure.  There are a number of choices here.  One straightforward way is to reverse the list and call fold_left (reordering the arguments as necessary):
let FoldBack combine l acc =
List.fold (fun x y -> combine y x) acc (List.rev l)
The auxiliary data structure here was another list – the reversed copy of the original list.  However there’s another possible implementation strategy.  A particularly elegant and generally useful strategy is to employ a continuation.  A continuation is just a function that describes “the remaining portion of the computation”.  Here is what it looks like to rewrite FoldBack to use a continuation:
// FoldBack : ('a -> 'b -> 'b) -> list<'a> -> 'b -> 'b let FoldBack combine l acc = // Loop : list<'a> -> ('b -> 'c) -> 'c let rec Loop l cont = match l with | h :: t -> Loop t (fun racc -> cont (combine h racc)) | [] -> cont acc Loop l (fun x -> x)
Just as accumulator parameters are often conventionally named “acc”, continuation parameters are often conventionally named “cont”.  Here the continuation describes the remaining work at a given point in the list as a function of the result of the work that is yet to be done.  In the expression
(fun racc -> cont (combine h racc))
“racc” is the right-accumulated result of the tail-recursive call that will happen in the future.  This functions basically says: “Once I eventually have that result, the next thing to do is combine that result with the current element of the list.  Then I’ll know my answer, and so I can pass that answer to the continuation that the previous recursive call handed to me.”  So we walk forward down the list, building up a delayed computation that represents all the work we have to do.  And when we reach the end of the list, we finally invoke this computation.
Just as we needed to “seed” accumulator parameters, we need to “seed” the continuation parameter, and in this case, the correct seed value is the identity function “(fun x -> x)”.
Where is the auxiliary data structure in this solution?  It’s the continuation.  Specifically, the lambda creates a closure, a data structure representing values captured by the lambda.  Each recursive call differs only in the values of “h” and “cont”, so we can imagine the closure being represented in memory as a pair of those two values.  This is (not coincidentally) quite similar to how we might ‘draw’ the process of reversing a list:
// [] // // /---+--\ // | 1 | -+--> [] // \---+--/ // // /---+--\   /---+--\ // | 2 | -+-->| 1 | -+--> [] // \---+--/   \---+--/ // // /---+--\   /---+--\   /---+--\ // | 3 | -+-->| 2 | -+-->| 1 | -+--> [] // \---+--/   \---+--/   \---+--/
To reverse a list, we start with the seed value “nil”, and then walk the list from left to right, consing each value onto the font of the list.  You’ve probably seen pictures like the above before, where [] represents nil, and each ‘box’ represents a cons call, with two fields: “data” and “next”.  “data” is an int, and “next” is a reference to another list<int>.
The exact same picture applies to how FoldBack builds continuations as it recurses.  We are building the same kind of structure, only now each diagram represents a one-argument function of type “int -> int” rather than a “list<int>”.  This time, [] represents the identity function (fun x -> x).  Each box represents a closure over the lambda “fun racc -> cont (combine h racc)”, where the two fields are “h” and “cont”.  “h” is an int, and “cont” is a reference to another int->int function.

To be continued…

Today we’ve built a foundation.  With an understanding of folds on lists, we are prepared to consider folds over other data structures.  So we’ll continue along those lines in a future blog entry.

Posted in Uncategorized | 3 Comments »

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.)

Posted in Uncategorized | 2 Comments »